>From Hongyu Shi <[email protected]>: Hongyu Shi has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21674?usp=email )
Change subject: [ASTERIXDB-3785][COMP][RT] CLUSTER BY: cosine similarity ...................................................................... [ASTERIXDB-3785][COMP][RT] CLUSTER BY: cosine similarity Admit cosine as a CLUSTER BY similarity. The assignment reuses the shared distance kernels; the centroid update projects the arithmetic mean back onto the unit sphere, since the cosine optimum is a direction and the mean already lies on that ray, so the projection changes no assignment. The cosine-metric test pins a data set whose two directions are held at very different magnitudes, so cosine and Euclidean must disagree; dot replaces cosine as the unsupported-similarity probe. Co-Authored-By: Claude <[email protected]> Change-Id: Ibf5e6679d2f51ca56d053603ff67292bc85448cf --- M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/ClusterByQueries.xml A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.1.ddl.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.2.update.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.3.query.sqlpp M asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/negative/unsupported-distance/test.1.query.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/cosine-metric/cosine-metric.3.adm M asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppClusterByVisitor.java M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansLoopIO.java 8 files changed, 117 insertions(+), 11 deletions(-) git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/74/21674/1 diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/ClusterByQueries.xml b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/ClusterByQueries.xml index f24d66c..bdaefbb 100644 --- a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/ClusterByQueries.xml +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/ClusterByQueries.xml @@ -148,13 +148,13 @@ <test-case FilePath="cluster-by/negative"> <compilation-unit name="unknown-distance"> <output-dir compare="Text">unknown-distance</output-dir> - <expected-error>CLUSTER BY 'similarity' 'euclidian' is not supported. Supported: EUCLIDEAN, EUCLIDEAN_SQUARED.</expected-error> + <expected-error>CLUSTER BY 'similarity' 'euclidian' is not supported. Supported: COSINE, EUCLIDEAN, EUCLIDEAN_SQUARED.</expected-error> </compilation-unit> </test-case> <test-case FilePath="cluster-by/negative"> <compilation-unit name="unsupported-distance"> <output-dir compare="Text">unsupported-distance</output-dir> - <expected-error>CLUSTER BY 'similarity' 'cosine' is not supported</expected-error> + <expected-error>CLUSTER BY 'similarity' 'dot' is not supported</expected-error> </compilation-unit> </test-case> <test-case FilePath="cluster-by/negative"> @@ -182,6 +182,11 @@ <!-- Cosine: two directions held at very different magnitudes, so Euclidean would group by magnitude and return {1,3},{2,4} instead. Passing means the metric reached both the loops and the labeling, and that the centroid update kept the centroids on the unit sphere. --> + <test-case FilePath="cluster-by"> + <compilation-unit name="cosine-metric"> + <output-dir compare="Text">cosine-metric</output-dir> + </compilation-unit> + </test-case> <!-- v1 scope restrictions: no set operations. --> <test-case FilePath="cluster-by/negative"> <compilation-unit name="setop-with-clusterby"> diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.1.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.1.ddl.sqlpp new file mode 100644 index 0000000..588e9dd --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.1.ddl.sqlpp @@ -0,0 +1,28 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +-- Two directions, each at two very different magnitudes. Cosine groups by direction, Euclidean by magnitude, +-- so the two metrics must disagree and the assertion below can only pass under cosine. + +drop dataverse test if exists; +create dataverse test; +use test; + +create type PointType as closed { id : integer, vec : [double] }; +create dataset Points(PointType) primary key id; diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.2.update.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.2.update.sqlpp new file mode 100644 index 0000000..c341036 --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.2.update.sqlpp @@ -0,0 +1,30 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +-- 1 and 2 share a direction, as do 3 and 4. By Euclidean distance 1 and 3 are the near pair and 2 and 4 the +-- far pair, so a Euclidean clustering would return {1,3} and {2,4} instead. + +use test; + +insert into Points ([ + {"id": 1, "vec": [1.0, 0.0]}, + {"id": 2, "vec": [100.0, 0.0]}, + {"id": 3, "vec": [0.0, 1.0]}, + {"id": 4, "vec": [0.0, 100.0]} +]); diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.3.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.3.query.sqlpp new file mode 100644 index 0000000..1c8bbaf --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/cosine-metric/cosine-metric.3.query.sqlpp @@ -0,0 +1,31 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +-- Members grouped by direction: {1,2} and {3,4}. + +use test; + +select ids from ( + from Points as p + cluster by p.vec as sc + cluster as members + with {"clustering_algorithm": "K-Means", "dimension": [2], "num_clusters": 2, "similarity": "cosine" } + select array_sort((select value m.p.id from members as m)) as ids +) as c +order by ids; diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/negative/unsupported-distance/test.1.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/negative/unsupported-distance/test.1.query.sqlpp index 4f0fa17..8d6c2e8 100644 --- a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/negative/unsupported-distance/test.1.query.sqlpp +++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/cluster-by/negative/unsupported-distance/test.1.query.sqlpp @@ -22,5 +22,5 @@ // update (the mean renormalized to unit length), is supported. from [{"x": [1.0, 2.0]}] as r cluster by r.x as sc -with { "clustering_algorithm": "K-Means", "dimension": [2], "num_clusters": 5, "similarity": "cosine" } +with { "clustering_algorithm": "K-Means", "dimension": [2], "num_clusters": 5, "similarity": "dot" } select sc.cluster_id; diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/cosine-metric/cosine-metric.3.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/cosine-metric/cosine-metric.3.adm new file mode 100644 index 0000000..3919aea --- /dev/null +++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/cluster-by/cosine-metric/cosine-metric.3.adm @@ -0,0 +1,2 @@ +{ "ids": [ 1, 2 ] } +{ "ids": [ 3, 4 ] } diff --git a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppClusterByVisitor.java b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppClusterByVisitor.java index 069e331..94b2f90 100644 --- a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppClusterByVisitor.java +++ b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppClusterByVisitor.java @@ -99,7 +99,7 @@ * does. * <p> * Supports K-Means only, with the {@code kmeans_parallel} (default) and {@code random} init modes, the - * Euclidean(-squared) metrics, and a fixed number of Lloyd iterations. + * Euclidean(-squared) and cosine metrics, and a fixed number of Lloyd iterations. */ @AiProvenance(agent = AiProvenance.Agent.CLAUDE_OPUS_5, tool = AiProvenance.Tool.CLAUDE_CODE_CLI, contributionKind = AiProvenance.ContributionKind.ASSISTED) public class SqlppClusterByVisitor extends AbstractSqlppSimpleExpressionVisitor { @@ -142,11 +142,12 @@ // Only K-Means is supported. private static final String ALGORITHM_KMEANS = ClusterByOptions.ALGORITHM_KMEANS; private static final Set<String> KNOWN_ALGORITHMS = Set.of("k-means", ALGORITHM_KMEANS); - // Only the Euclidean family has a matching centroid update: the arithmetic-mean update minimizes - // squared-Euclidean distance. Cosine and dot would need a normalized-mean (spherical) update to converge, - // so they are rejected until that is implemented. - private static final Set<VectorSimilarityMetric> SUPPORTED_METRICS = - Set.of(VectorSimilarityMetric.EUCLIDEAN, VectorSimilarityMetric.EUCLIDEAN_SQUARED); + // A metric is usable only if some point minimizes total distance to a cluster, since that point is what + // the update step moves each centroid to: the arithmetic mean for the Euclidean family, that mean + // projected onto the unit sphere for cosine. Dot is refused -- a negated inner product is unbounded + // below, so no centroid minimizes it and the update step has nothing to reach. + private static final Set<VectorSimilarityMetric> SUPPORTED_METRICS = Set.of(VectorSimilarityMetric.EUCLIDEAN, + VectorSimilarityMetric.EUCLIDEAN_SQUARED, VectorSimilarityMetric.COSINE); // Listed back to the user on an unsupported value. Built from the enum so it cannot drift from the check, // and sorted so the message does not depend on Set iteration order. private static final String SUPPORTED_METRICS_DISPLAY = SUPPORTED_METRICS.stream() diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansLoopIO.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansLoopIO.java index 5e9292e..fcfa8e1 100644 --- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansLoopIO.java +++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/kmeans/KMeansLoopIO.java @@ -28,6 +28,7 @@ import org.apache.asterix.common.exceptions.ErrorCode; import org.apache.asterix.common.exceptions.RuntimeDataException; import org.apache.asterix.common.vector.VectorSimilarityMetric; +import org.apache.asterix.runtime.operators.KMeansUtils; import org.apache.asterix.runtime.utils.VectorDistanceFunctionFactory; import org.apache.hyracks.api.comm.VSizeFrame; import org.apache.hyracks.api.context.IHyracksTaskContext; @@ -618,8 +619,13 @@ } /** - * The centroid of a cluster whose members sum to {@code sum}: for squared Euclidean, the arithmetic mean, - * the point minimizing total distance to the members. + * The centroid of a cluster whose members sum to {@code sum}: the point minimizing total distance to them, + * which is a different point per metric. + * <p> + * For squared Euclidean it is the arithmetic mean. For cosine it is that mean projected back onto the unit + * sphere -- the cosine optimum is a direction, and the mean already lies on that ray, so the projection + * changes no assignment. It keeps centroids on the same sphere as the data and avoids later dividing by a + * near-zero norm. * * @param sum component-wise sum of the cluster's members; not modified * @param weight how many members it holds, at least one @@ -629,6 +635,9 @@ for (int d = 0; d < centroid.length; d++) { centroid[d] = sum[d] / weight; } + if (metric == VectorSimilarityMetric.COSINE) { + KMeansUtils.normalizeL2(centroid); + } return centroid; } -- To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21674?usp=email To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email Gerrit-MessageType: newchange Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Change-Id: Ibf5e6679d2f51ca56d053603ff67292bc85448cf Gerrit-Change-Number: 21674 Gerrit-PatchSet: 1 Gerrit-Owner: Hongyu Shi <[email protected]>
