zhengruifeng commented on a change in pull request #27758:
URL: https://github.com/apache/spark/pull/27758#discussion_r411884957
##########
File path:
mllib/src/main/scala/org/apache/spark/mllib/clustering/DistanceMeasure.scala
##########
@@ -154,22 +255,81 @@ object DistanceMeasure {
}
private[spark] class EuclideanDistanceMeasure extends DistanceMeasure {
+
+ /**
+ * Statistics used in triangle inequality to obtain useful bounds to find
closest centers.
+ * @see <a
href="https://www.aaai.org/Papers/ICML/2003/ICML03-022.pdf";>Charles Elkan,
+ * Using the Triangle Inequality to Accelerate k-Means</a>
+ *
+ * @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 Euclidean distance, radius of center i is half of the
distance between center i
+ * and its closest center;
+ * 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 = {
+ 0.25 * distance * distance
+ }
+
+ /**
+ * @return the index of the closest center to the given point, as well as
the cost.
+ */
+ override def findClosest(
+ centers: Array[VectorWithNorm],
+ statistics: Array[Double],
+ point: VectorWithNorm): (Int, Double) = {
+ var bestDistance =
EuclideanDistanceMeasure.fastSquaredDistance(centers(0), point)
Review comment:
do you mean:
```scala
if (bestDistance < statistics(0)) {
return (0, bestDistance)
}
```
yes, `statistics(0)` here is just equal to
`statistics(indexUpperTriangular(k, 0, 0))`
----------------------------------------------------------------
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:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org
