kmeans 聚类

应该是最简单的一种聚类方法，最大的缺点是需要事先有监督地给出要聚出的簇的数目。

kmeans的实现相对简单，如果你还不知道它的原理，那么，百度一下吧。

系统输入要求以数字的方式进行，如要对多篇文档进行聚类，首先找出文档的特征向量并数字化，如：

1:10000 2:2 3:300 4:40 5:0.05 6:0.6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:1 2:2 3:3 4:4 5:5 6:6
1:10 2:20 3:30 4:40 5:50 6:600
1:10 2:20 3:30 4:40 5:50 6:600
1:10 2:20 3:30 4:40 5:50 6:600
1:10 2:20 3:30 4:40 5:50 6:600
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:0.001 2:0.002 3:0.003 4:0.004 5:0.005 6:0.006
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:100 2:200 3:300 4:400 5:500
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:10000 2:20000 3:30000 4:40000 5:50000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000
1:1000 2:2000 3:3000 4:4000 5:5000 6:6000

 

同时需要提供给系统要求最终聚出的簇数N，通过迭代取中心点（取中心点的方法：首次均匀取所有数据点每个dimensioin的N平均；之后每个簇迭代取簇内均值中心点。），按照上述进行输入有下列聚类结果：

N=4时，

0##10000 2 300 40 0.05 0.6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##0.001 0.002 0.003 0.004 0.005 0.006
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
3##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000

N=7时，

0##10000 2 300 40 0.05 0.6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
6##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
5##0.001 0.002 0.003 0.004 0.005 0.006
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000

N=10时，

0##10000 2 300 40 0.05 0.6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
4##0.001 0.002 0.003 0.004 0.005 0.006
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
6##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000

由以上聚类结果可以看出，最终聚类的结果跟选择的初始点的数量N有很大的关联：若给出的N小于语料中实际存在的簇数，那聚出的结果会比较粗糙，存在没有聚出的簇，这些簇被分配到了与其特征向量最接近的簇中，如N=5的结果；反之，若给出的N>=实际存在的簇数，则可以较准确地给出聚类结果，如N=7和N=10的结果是最理想的，但是N=10时的cost却比N=7时要高得多。因此N的选择对整个聚类系统的好坏起着决定性作用。

对于未知的语料该信息可通过不断尝试来决定；也可通过分析每次聚类结果中每个簇的最大间隔和平均间隔的差值来决定是否需要调整N的值。

 

数据打乱顺序后，聚类结果不变。

0##10000 2 300 40 0.05 0.6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
6##0.001 0.002 0.003 0.004 0.005 0.006
6##0.001 0.002 0.003 0.004 0.005 0.006
6##0.001 0.002 0.003 0.004 0.005 0.006
5##1 2 3 4 5 6
5##1 2 3 4 5 6
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
3##10 20 30 40 50 600
6##0.001 0.002 0.003 0.004 0.005 0.006
6##0.001 0.002 0.003 0.004 0.005 0.006
5##1 2 3 4 5 6
5##1 2 3 4 5 6
5##1 2 3 4 5 6
4##100 200 300 400 500 0
4##100 200 300 400 500 0
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
4##100 200 300 400 500 0
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
2##10000 20000 30000 40000 50000 6000
1##1000 2000 3000 4000 5000 6000
1##1000 2000 3000 4000 5000 6000