元素映射坏了 [英] Mapping of elements gone bad
问题描述
我实现的 k均值的，我想创造新的重心。但叶映射一个元素了！然而，当 K 是一个较小的值，如15，它会正常工作。
I am implementing k-means and I want to create the new centroids. But the mapping leaves one element out! However, when K is of a smaller value, like 15, it will work fine.
href=\"http://www.cs.berkeley.edu/~rxin/ampcamp-ecnu/machine-learning-with-spark.html\" rel=\"nofollow\"> code 我有：
Based on that code I have:
val K = 25 // number of clusters
val data = sc.textFile("dense.txt").map(
t => (t.split("#")(0), parseVector(t.split("#")(1)))).cache()
val count = data.count()
println("Number of records " + count)
var centroids = data.takeSample(false, K, 42).map(x => x._2)
do {
var closest = data.map(p => (closestPoint(p._2, centroids), p._2))
var pointsGroup = closest.groupByKey()
println(pointsGroup)
pointsGroup.foreach { println }
var newCentroids = pointsGroup.mapValues(ps => average(ps.toSeq)).collectAsMap()
//var newCentroids = pointsGroup.mapValues(ps => average(ps)).collectAsMap() this will produce an error
println(centroids.size)
println(newCentroids.size)
for (i <- 0 until K) {
tempDist += centroids(i).squaredDist(newCentroids(i))
}
..
和在for循环，我会得到错误，它会找不到元素（这并不总是相同的，这取决于 K ：
and in the for loop, I will get the error that it won't find the element (which is not always the same and it depends on K:
java.util.NoSuchElementException 2
java.util.NoSuchElementException: key not found: 2
错误之前的输出出现：
Number of records 27776
ShuffledRDD[5] at groupByKey at kmeans.scala:72
25
24 <- IT SHOULD BE 25
这是什么问题？
>>> println(newCentroids)
Map(23 -> (-0.0050852959701492536, 0.005512245104477607, -0.004460964477611937), 17 -> (-0.005459583045685268, 0.0029015278781725795, -8.451635532994901E-4), 8 -> (-4.691649213483123E-4, 0.0025375451685393366, 0.0063490755505617585), 11 -> (0.30361112034069937, -0.0017342255382385204, -0.005751167731061906), 20 -> (-5.839587918939964E-4, -0.0038189763756820145, -0.007067070459859708), 5 -> (-0.3787612396704685, -0.005814121628643806, -0.0014961713117870657), 14 -> (0.0024755681263616547, 0.0015191503267973836, 0.003411769193899781), 13 -> (-0.002657690932944597, 0.0077671050923225635, -0.0034652379980563263), 4 -> (-0.006963114731610361, 1.1751361829025871E-4, -0.7481135105367823), 22 -> (0.015318187079953534, -1.2929035958285013, -0.0044176372190034684), 7 -> (-0.002321059060773483, -0.006316359116022083, 0.006164669723756913), 16 -> (0.005341800955165691, -0.0017540737037037035, 0.004066574093567247), 1 -> (0.0024547379611650484, 0.0056298656504855955, 0.002504618082524296), 10 -> (3.421068671121009E-4, 0.0045169004751299275, 5.696239049740164E-4), 19 -> (-0.005453716071428539, -0.001450277556818192, 0.003860007248376626), 9 -> (-0.0032921685273631807, 1.8477108457711313E-4, -0.003070412228855717), 18 -> (-0.0026803160958904053, 0.00913904078767124, -0.0023528013698630146), 3 -> (0.005750011594202901, -0.003607098309178754, -0.003615918896940412), 21 -> (0.0024925166025641056, -0.0037607353461538507, -2.1588444871794858E-4), 12 -> (-7.920202960526356E-4, 0.5390774232894769, -4.928884539473694E-4), 15 -> (-0.0018608492323232324, -0.006973787272727284, -0.0027266663434343404), 24 -> (6.151173211963486E-4, 7.081812613784045E-4, 5.612962808842611E-4), 6 -> (0.005323933953732931, 0.0024014750473186123, -2.969338590956889E-4), 0 -> (-0.0015991676750160377, -0.003001317289659613, 0.5384176139563245))
有关错误问题：<一href=\"http://stackoverflow.com/questions/29271879/spark-scala-throws-java-util-nosuchelementexception-key-not-found-0-exception\">spark斯卡拉抛出java.util.NoSuchElementException：关键未找到：0例外
编辑：
zero323两个质心的观察后是一样的，我改变了code，这样的所有的质心是唯一的。然而，该行为是相同的。出于这个原因，我怀疑 closestPoint（）可以返还相同指数两个重心。下面是函数：
After the observation of zero323 that two centroids were the same, I changed the code so that all the centroids are unique. However, the behaviour remains the same. For that reason, I suspect that closestPoint() may return the same index for two centroids. Here is the function:
def closestPoint(p: Vector, centers: Array[Vector]): Int = {
var index = 0
var bestIndex = 0
var closest = Double.PositiveInfinity
for (i <- 0 until centers.length) {
val tempDist = p.squaredDist(centers(i))
if (tempDist < closest) {
closest = tempDist
bestIndex = i
}
}
return bestIndex
}
如何蒙混过关呢？我运行的是code就像我在星火集群<描述/ A>
How to get away with this? I am running the code like I describe in Spark cluster.
推荐答案
它可以在E-步发生（点簇指数的分配类似于EM算法的E步骤），一个你的指数将不会分配任何点。如果发生这种情况，那么你需要有一个指数的一些点相关联的方式，否则你会在M步后，用较少的集群清盘（质心的指标分配是类似的M- 。EM算法的步骤）像这样的东西或许应该工作：
It can happen in the "E-step" (the assignment of points to cluster-indices is analogous to the E-step of the EM algorithm) that one of your indices will not be assigned any points. If this happens then you need to have a way of associating that index with some point, otherwise you're going to wind up with fewer clusters after the "M-step" (the assignment of centroids to the indices is analogous to the M-step of the EM algorithm.) Something like this should probably work:
val newCentroids = {
val temp = pointsGroup.mapValues(ps => average(ps.toSeq)).collectAsMap()
val nMissing = K - temp.size
val sample = data.takeSample(false, nMissing, seed)
var c = -1
(for (i <- 0 until K) yield {
val point = temp.getOrElse(i, {c += 1; sample(c) })
(i, point)
}).toMap
}
刚刚替补是code表示您当前使用计算 newCentroids 行。
有处理这个问题和上面的方法的其他方式的可能不是最好的（它是一个好主意，可以调用 takeSample 多次，一次为每个在第k-means算法？如果数据中含有大量的重复值？等）什么的迭代，但它是一个简单的起点。
There are other ways of dealing with this issue and the approach above is probably not the best (is it a good idea to be calling takeSample multiple times, once for each iteration of the the k-means algorithm? what if data contains a lot of repeated values?, etc.), but it is a simple starting point.
顺便说一句，你可能要想想你如何更换 groupByKey 与 reduceByKey 。
By the way, you might want to think about how you can replace the groupByKey with a reduceByKey.
请注意：对于好奇，这里的描述EM-算法和之间的相似性的参考k-means算法：的http://papers.nips.cc/paper/989-convergence-properties-of-the-k-means-algorithms.pdf.
Note: For the curious, here's a reference describing the similarities between the EM-algorithm and the k-means algorithm: http://papers.nips.cc/paper/989-convergence-properties-of-the-k-means-algorithms.pdf.
这篇关于元素映射坏了的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
