0

我正在为一个使用集群来识别对象的项目编写一个 K-Means 集群，因此机器人几乎是自主的。相机基本上以半秒的
速度拍摄一张图片，该图片存储在一个“斑点”像素中。这个 blob 被发送到数据挖掘算法 k-means，它将对象的“阴影”识别为一个集群，因此可以对机器人进行编程以避开这些区域。我发布了我的 k-means 代码。它是用python编写的。

import sys, math, random

class Point:

    def __init__(self, coords, reference=None):
        self.coords     = coords
        self.n          = len(coords)
        self.reference  = reference

    def __repr__(self):
        return str(self.coords)

class Cluster:

    def __init__(self, points):

        if len(points) == 0: 
            raise Exception("ILLEGAL: empty cluster")

        self.points = points
        self.n      = points[0].n       # make the first element to be the number of clusters

        for p in points:
            if p.n != self.n:
                raise Exception("ILLEGAL: wrong dimension")

        self.centroid = self.calculateCentroid()

    def __repr__(self):
        return str(self.points)

    def update(self, points):
        old_centroid    = self.centroid
        self.points     = points
        self.centroid   = self.calculateCentroid()
        return getDistance(old_centroid, self.centroid)

    def calculateCentroid(self):
        reduce_coord = lambda i:reduce(lambda x,p : x + p.coords[i], self.points, 0.0)
        if len(self.points) == 0:
            print "Dividing by 0"
            self.points = [1]
        centroid_coords = [reduce_coord(i) / len(self.points) for i in range(self.n)]

        return Point(centroid_coords)

def kmeans(points, k, cutoff):

    initial = random.sample(points, k)
    clusters = [Cluster([p]) for p in initial]
    print clusters
    while True:
        lists = [ [] for c in clusters]
        for p in points:
            smallest_distance   = getDistance(p, clusters[0].centroid)
            index = 0

            for i in range(len(clusters[1:])):
                distance = getDistance(p, clusters[i+1].centroid)
                if distance < smallest_distance:

                    smallest_distance = distance
                    index = i+1

                lists[index].append(p)
            biggest_shift = 0.0

            for i in range(len(clusters)):
                shift = clusters[i].update(lists[i])
                biggest_shift = max(biggest_shift, shift)

            if biggest_shift < cutoff:
                break

    return clusters

def getDistance(a, b):

    if a.n != b.n:
        raise Exception("ILLEGAL: non comparable points")

    ret = reduce(lambda x, y: x + pow((a.coords[y] - b.coords[y]), 2), range(a.n), 0.0)
    return math.sqrt(ret)

def makeRandomPoint(n, lower, upper):
    return Point([random.uniform(lower, upper) for i in range(n)])

def main():
    num_points, dim, k, cutoff, lower, upper = 10, 2, 3, 0.5, 0, 200
    points = map(lambda i: makeRandomPoint(dim, lower, upper), range(num_points))

    clusters = kmeans(points, k, cutoff)

    for i, c in enumerate(clusters):
        for p in c.points:
            print "Cluster: ", i, "\t Point: ", p


if __name__ == "__main__":
    main()

果然，它不工作！

  Traceback (most recent call last):
  File "C:\Users\philippe\Documents\workspace-sts-2.7.2.RELEASE\scribber\kmeans\kmeans.py", line 100, in ?
    main()    
  File "C:\Users\philippe\Documents\workspace-sts-2.7.2.RELEASE\scribber\kmeans\kmeans.py", line 92, in main
[    clusters = kmeans(points, k, cutoff)
[[89.152748179548524, 81.217634455465131]], [[83.439023369838509, 169.75355953688432]], [[1.8622622156419633, 41.364078271733739]]]
Dividing by 0
  File "C:\Users\philippe\Documents\workspace-sts-2.7.2.RELEASE\scribber\kmeans\kmeans.py", line 69, in kmeans
    shift = clusters[i].update(lists[i])
  File "C:\Users\philippe\Documents\workspace-sts-2.7.2.RELEASE\scribber\kmeans\kmeans.py", line 35, in update
    self.centroid   = self.calculateCentroid()
  File "C:\Users\philippe\Documents\workspace-sts-2.7.2.RELEASE\scribber\kmeans\kmeans.py", line 43, in calculateCentroid
    centroid_coords = [reduce_coord(i) / len(self.points) for i in range(self.n)]
  File "C:\Users\philippe\Documents\workspace-sts-2.7.2.RELEASE\scribber\kmeans\kmeans.py", line 39, in <lambda>
    reduce_coord = lambda i:reduce(lambda x,p : x + p.coords[i], self.points, 0.0)
  File "C:\Users\philippe\Documents\workspace-sts-2.7.2.RELEASE\scribber\kmeans\kmeans.py", line 39, in <lambda>
    reduce_coord = lambda i:reduce(lambda x,p : x + p.coords[i], self.points, 0.0)
AttributeError: 'int' object has no attribute 'coords'

当我lists在函数中进行打印时，kmeans(points, k, cutoff)我得到 [[], [], []]. 我试图弄清楚，为什么给我一个空列表。我发布了整个代码，因此可以运行代码并复制错误。在错误日志中，可以看到“集群”是什么：点列表。谢谢

4

1 回答 1

1

问题是，如果最接近给定集群的点列表是空的（所有点都更接近不同的集群），那么您将得到除以 0 错误，此时您将垃圾数据分配给 self.points这会导致您看到的最终错误。

如果两个集群具有相同的质心，这是可能的，在这种情况下，第二个集群将永远不会分配给它的点。

顺便说一句，还有另一个错误。您在 lists[index].append(p) 前面有一个额外的缩进，您应该考虑使用 enumerate 和 min 重写整个循环以使其更清晰。

这是我建议重写的方法。

while True:
    newPoints = dict([(c,[]) for c in clusters])
    for p in points:
        cluster = min(clusters, key = lambda c:getDistance(p, c.centroid))
        newPoints[cluster].append(p)

    biggest_shift = 0.0

    for c in clusters:
        if newPoints[c]:
            shift = c.update(newPoints[c])
            biggest_shift = max(biggest_shift, shift)

    if biggest_shift < cutoff:
        break
于 2012-07-01T15:51:47.653 回答