shahidki31 commented on a change in pull request #21627:
[SPARK-24484][MLLIB]Power Iteration Clustering is giving incorrect clustering
results when there are mutiple leading eigen values.
URL: https://github.com/apache/spark/pull/21627#discussion_r249514919
##########
File path:
mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala
##########
@@ -378,6 +378,27 @@ object PowerIterationClustering extends Logging {
logInfo(s"$msgPrefix: delta = $delta.")
diffDelta = math.abs(delta - prevDelta)
logInfo(s"$msgPrefix: diff(delta) = $diffDelta.")
+
+ if (math.abs(diffDelta) < tol) {
+ /**
+ * Power Iteration fails to converge if absolute value of top 2 eigen
values are equal,
+ * but with opposite sign. The resultant vector flip-flops between two
vectors.
+ * We should give an exception, if we detect the failure of the
convergence of the
+ * power iteration
+ */
+
+ // Rayleigh quotient = x^tAx / x^tx
+ val xTAx = curG.joinVertices(v) {
+ case (_, x, y) => x * y
+ }.vertices.values.sum()
+ val xTx = curG.vertices.mapValues(x => x * x).values.sum()
+ val Rayleigh = xTAx / xTx
+
+ if (math.abs(norm - math.abs(Rayleigh)) > tol) {
+ throw new SparkException(s"Power Iteration fail to converge, delta =
${delta}," +
Review comment:
The result may be partially correct. Refer UT: even though both the clusters
are well separable, any standard clustering algorithm would correctly assign
the clusters, but due to the drawback of PIC, it gives incorrect result.
So, if we log an error, it is up to user to decide, whether to take the
results from the PIC or use some other algorithm.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on 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]
