执行K均值聚类时的问题

2 投票

2 回答

1760 浏览

提问于 2025-04-18 14:49

我正在尝试使用K均值聚类来处理一个CSV文件中的数据。

Sample1,Sample2,45
Sample1,Sample3,69
Sample1,Sample4,12
Sample2,Sample2,46
Sample2,Sample1,78

这基本上是一个图，样本是节点，数字是边（权重）。

我用以下方式读取文件：

fileopening = fopen('data.csv', 'rU')
reading = csv.reader(fileopening, delimiter=',')

L = list(reading)

我使用了这段代码：https://gist.github.com/betzerra/8744068

在这里，聚类是基于以下内容构建的：

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

我把点替换成了列表L。但是我遇到了很多错误，比如：AttributeError, 'int' object has no attribute 'n'等等。

我需要根据CSV文件中第三列的数字（边）来进行K均值聚类。这个教程是随机创建点的。但是我不确定如何将这个CSV数据作为输入传递给这个K均值函数。我该如何对我的数据进行K均值聚类（k=2）？我该如何将CSV文件中的数据作为输入传递给这个K均值函数？

error handling data preprocessing k-means clustering clustering algorithms edge weights csv data processing data input handling graph representation

2 个回答

简单来说，“你不能这样做”。

详细说说： K-means（聚类算法）只适用于欧几里得空间，而且它需要有效的点的位置，但你现在只有这些点之间的距离，可能并不是严格的数学意义上的距离，而是一种“相似性”。K-means并不是为了处理相似性矩阵而设计的。

那你可以做什么呢？

你可以使用其他方法把你的点嵌入到欧几里得空间中，使得它们的布局尽量接近你已有的距离，其中一种工具是多维尺度分析（MDS）：http://en.wikipedia.org/wiki/Multidimensional_scaling
完成第一步后，你就可以运行K-means了。

另外，你也可以通过一些核学习技术来构建一个核（在Mercer的意义上有效），然后在得到的Gram矩阵上运行核K-means。

回答于 2025-04-18 由 Python大师

分享举报

正如lejlot所说，仅仅知道点与点之间的距离是不够的，无法按照传统的方式运行k-means算法。要理解这一点，首先要明白k-means的基本原理。简单来说，k-means的工作原理如下：

1) Randomly assign points to cluster.
  (Technically, there are more sophisticated ways of initial  partitioning, 
  but that's not essential right now).

2) Compute centroids of the cluster. 
  (This is where you need the actual coordinates of the points.)

3) Reassign each point to a cluster with the closest centroid.

4) Repeat steps 2)-3) until stop condition is met.

所以，正如你所看到的，在传统的理解中，k-means无法正常工作，因为我们不知道如何计算中心点。不过，我有几个建议可以考虑。

建议1.

把你的点放到一个N维空间中，其中N是点的数量，这样每个点的坐标就是它到其他所有点的距离。

举个例子，你展示的数据：

Sample1,Sample2,45
Sample1,Sample3,69
Sample1,Sample4,12
Sample2,Sample2,46
Sample2,Sample1,78

变成：

Sample1: (0,45,69,12,...)
Sample2: (78,46,0,0,...)

这样你就可以合法地使用欧几里得距离了。需要注意的是，点与点之间的实际距离可能不会被保留，但这可以是一个简单且合理的近似方法，用来保持点之间的相对距离。另一个缺点是，如果你的点很多，那么内存和运行时间的需求将是N的平方级别。

建议2.

可以尝试使用k-medoids，而不是k-means。这个方法不需要点的实际坐标，因为你需要计算的是“中位点”而不是中心点。一个聚类的中位点是这个聚类中，与其他所有点的平均距离最小的点。你可以在网上查找相关的实现，或者其实自己实现也很简单。运行时间同样会是N的平方级别。

最后的提醒。

你为什么想使用k-means呢？看起来你有一个加权有向图。其实有专门针对图的聚类算法。这超出了你问题的范围，但也许这是值得考虑的方向？

回答于 2025-04-18 由 Python大师

分享举报

执行K均值聚类时的问题

2 个回答

撰写回答