dongjoon-hyun commented on code in PR #58595:
URL: https://github.com/apache/spark/pull/58595#discussion_r3957193932
##########
mllib/src/main/scala/org/apache/spark/mllib/clustering/BisectingKMeansModel.scala:
##########
@@ -156,13 +158,31 @@ object BisectingKMeansModel extends
Loader[BisectingKMeansModel] {
}
}
- private def buildTree(rootId: Int, nodes: Map[Int, Data]):
ClusteringTreeNode = {
+ private def buildTree(rootId: Int, nodes: Map[Int, Data]):
ClusteringTreeNode =
+ buildTree(rootId, nodes, mutable.Set.empty)
+
+ /**
+ * `visiting` accumulates every node id reached while building the tree. A
valid tree reaches each
+ * id exactly once, so encountering an id that is already present means the
saved data is not a
+ * tree: either its child ids form a cycle (which would otherwise recurse
until the driver hits a
+ * StackOverflowError) or a child id is shared by more than one parent.
Either way we fail with a
+ * clear message. Valid trees build unchanged.
+ */
+ private def buildTree(
+ rootId: Int,
+ nodes: Map[Int, Data],
+ visiting: mutable.Set[Int]): ClusteringTreeNode = {
+ if (!visiting.add(rootId)) {
+ throw new IllegalArgumentException(
+ s"Cycle detected among node ids while loading the bisecting k-means
model " +
+ s"(node id = $rootId).")
+ }
Review Comment:
Now that `visiting` is never cleared, this rejects a cross edge (a child id
shared by more than one parent) as well as a back edge, which is what we want
-- but the message still only says "Cycle detected". The scaladoc right above
already spells out both cases, so the message is now the odd one out, and
someone hitting the shared-child case would go looking for a cycle that does
not exist.
Something like:
```scala
throw new IllegalArgumentException(
s"Node id $rootId is reached more than once while loading the bisecting
k-means " +
s"model; the saved node data is not a tree (its child ids form a cycle,
or a child " +
s"id is shared by more than one parent).")
```
`DecisionTreeModel.constructNode` keeps "Cycle detected" correctly, since
the pre-existing `nodes` memo means only a back edge can reach that branch
there.
##########
mllib/src/test/scala/org/apache/spark/mllib/clustering/BisectingKMeansSuite.scala:
##########
@@ -199,4 +202,38 @@ class BisectingKMeansSuite extends SparkFunSuite with
MLlibTestSparkContext {
Utils.deleteRecursively(tempDir)
}
}
+
+ test("load rejects a model whose node ids form a cycle") {
+ val srcDir = Utils.createTempDir()
+ val dstDir = Utils.createTempDir()
+ try {
+ val src = srcDir.toURI.toString
+ val dst = dstDir.toURI.toString
+ val data = sc.parallelize((1 until 8).map(i =>
Vectors.dense(i.toDouble)), 2)
+ val model = new BisectingKMeans().run(data)
+ model.save(sc, src)
+ val rootId = model.root.index
+
+ // Copy the metadata verbatim, and write a modified data set where the
root node lists
+ // itself as its own child (a cycle). Reading src and writing dst avoids
a self-overwrite.
+ val hadoopConf = sc.hadoopConfiguration
+ val srcMeta = new HadoopPath(Loader.metadataPath(src))
+ val dstMeta = new HadoopPath(Loader.metadataPath(dst))
+ FileUtil.copy(
+ srcMeta.getFileSystem(hadoopConf), srcMeta,
+ dstMeta.getFileSystem(hadoopConf), dstMeta, false, hadoopConf)
+ spark.read.parquet(Loader.dataPath(src))
+ .withColumn("children",
+ when(col("index") === rootId,
array(lit(rootId))).otherwise(col("children")))
+ .write.parquet(Loader.dataPath(dst))
+
+ val e = intercept[IllegalArgumentException] {
+ BisectingKMeansModel.load(sc, dst)
+ }
+ assert(e.getMessage.contains("Cycle detected"))
Review Comment:
Needs to follow whatever wording you settle on above.
--
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.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
