srowen commented on a change in pull request #27758:
URL: https://github.com/apache/spark/pull/27758#discussion_r411795159
##########
File path: mllib-local/src/main/scala/org/apache/spark/ml/impl/Utils.scala
##########
@@ -18,7 +18,7 @@
package org.apache.spark.ml.impl
-private[ml] object Utils {
+private[spark] object Utils {
Review comment:
If this is the natural home for this, fine, though I'd usually put code
used by both in .mllib. Maybe. I'm not sure anymore
##########
File path: mllib-local/src/main/scala/org/apache/spark/ml/impl/Utils.scala
##########
@@ -27,4 +27,55 @@ private[ml] object Utils {
}
eps
}
+
+ /**
+ * Convert an n * (n + 1) / 2 dimension array representing the upper
triangular part of a matrix
+ * into an n * n array representing the full symmetric matrix (column major).
+ *
+ * @param n The order of the n by n matrix.
+ * @param triangularValues The upper triangular part of the matrix packed in
an array
+ * (column major).
+ * @return A dense matrix which represents the symmetric matrix in column
major.
+ */
+ def unpackUpperTriangular(
Review comment:
I thought breeze or commons math had a utility method for this already
but I can't find it immediately
##########
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:
So centers are ordered by statistic?
And this is just a short-circuit?
##########
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)
+ if (bestDistance < statistics(0)) {
+ return (0, bestDistance)
+ }
+
+ val k = centers.length
+ var bestIndex = 0
+ var i = 1
+ while (i < k) {
+ val center = centers(i)
+ // Since `\|a - b\| \geq |\|a\| - \|b\||`, we can use this lower bound
to avoid unnecessary
+ // distance computation.
+ val normDiff = center.norm - point.norm
+ val lowerBound = normDiff * normDiff
+ if (lowerBound < bestDistance) {
+ val index1 = indexUpperTriangular(k, i, bestIndex)
+ if (statistics(index1) < bestDistance) {
+ val d = EuclideanDistanceMeasure.fastSquaredDistance(center, point)
+ val index2 = indexUpperTriangular(k, i, i)
+ if (d < statistics(index2)) {
+ return (i, d)
+ } else if (d < bestDistance) {
Review comment:
Nit: you don't need the else here
----------------------------------------------------------------
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
