srowen commented on a change in pull request #27758: [SPARK-31007][ML][WIP]
KMeans optimization based on triangle-inequality
URL: https://github.com/apache/spark/pull/27758#discussion_r408158947
##########
File path:
mllib/src/main/scala/org/apache/spark/mllib/clustering/DistanceMeasure.scala
##########
@@ -234,6 +389,57 @@ private[spark] object EuclideanDistanceMeasure {
}
private[spark] class CosineDistanceMeasure extends DistanceMeasure {
+
+ /**
+ * Statistics used in triangle inequality to obtain useful bounds to find
closest centers.
+ *
+ * @return One element used in statistics matrix to make matrix(i)(j)
represents:
+ * 1, squared radii of the center i, if i==j. If distance between
point x and center i
+ * is less than the radius of center i, then center i is the closest
center to point x.
+ * For Cosine distance, it is similar to Euclidean distance.
However, here radian/angle
+ * is used instead of Cosine distance: for center c, finding its
closest center,
+ * computing the radian/angle between them, halving it, and
converting it back to Cosine
+ * distance at the end.
+ * 2, a lower bound r=matrix(i)(j) to help avoiding unnecessary
distance computation.
+ * Given point x, let i be current closest center, and d be current
best squared
+ * distance, if d < r, then we no longer need to compute the
distance to center j.
+ */
+ override def computeStatistics(distance: Double): Double = {
+ // d = 1 - cos(x)
+ // r = 1 - cos(x/2) = 1 - sqrt((cos(x) + 1) / 2) = 1 - sqrt(1 - d/2)
+ 1 - math.sqrt(1 - distance / 2)
+ }
+
+ /**
+ * @return the index of the closest center to the given point, as well as
the cost.
+ */
+ def findClosest(
Review comment:
Is there any clean way to avoid duplicating most of this code? maybe not. It
looks almost identical to the above though
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
