频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
划分方法聚类(一) K-MEANS算法
2017-02-28 12:12:00         来源:尽管我很鱼  
收藏   我要投稿

划分方法聚类(一) K-MEANS算法:1,原型聚类(划分方法):给定一个n个对象的集合,划分方法构建数据的K个分区。大部分划分方法是基于距离的,所以只能发现球类簇。

为了达到全局最优,K值需要全局遍历。计算量太大。普遍采用了流行的启发式算法。如K均值和k-中心点算法,渐进的提高聚类质量,逼近局部最优解,这些启发聚类算法适合发现中小规模的数据的球状簇。

划分方法的基本特点:

(1)发现球状互斥的簇

(2)基于距离

(3)可以用均值或者中心点代表簇的中心

(4)对中小规模数据有效

K均值算法

K-均值算法原理:

(1)对于给定的数据集,首先随机选取K个样本作为初始均值向量。

(2)遍历数据集,找到距离最近的中心点,加入该簇。

(3)重新计算K个簇的中心点。

If u(i)!=U(i)

更新中心点

(4)重复(2)(3)直到所有的中心点向量均不在发生改变。

为了避免运行时间过长,通常设置一个最大运行轮数或者最小调整幅度阈值。若达到最大轮数或调整幅度小于阈值,则停止运行。

划分算法这一模块,首先讲K-MEANS算法,从K-MEANS的原理,优缺点,改进方向方面,将其他划分方法的聚类算法引出来。

K均值算法分析:

(1)不能保证K均值算法收敛于全局最优解,常常终止于局部最优解。结果可能依赖于初始簇中心的随机选择。实践中,为了得到好的结果,通常以不同的初始簇中心,多次运行K-均值算法。(初始簇中心的选择对结果的影响)

(2)K-Means算法的时间复杂度为O(nkt),其中n是对象总数,k是簇数,t是迭代次数。对于处理大数据集,该算法是相对可伸缩和有效的。

(3) 需要事先知道要K值是该算法的一个缺点改进之一:提供K值的近似范围,使用分析技术,比较不同K值得到的聚类效果。K均值算法不能够发现非凸状的簇,或者大小差别很大的簇。此外对噪声和离群点敏感,因此少量的这类数据就能够对均值产生极大的影响。

K均值缺点总结:??

(1)算法需要人工输入参数K的值,而K值取值的不同,将导致聚类结果的质量和时间的不同。(K值的选取)

2)算法初始聚类中也的选择直接影响了聚类结果的质量,与算法运行的效率也是息息相关的,随机选取聚类中也,就有陷入局部最优解(即代价函数取极小值)的情况,这样就无法达到最优解,严重影响聚类质量。(初始化的K歌中心的选择)

(3)由于算法的距离计算量为欧几里德距离,用此距离计算,将形成球状或者类球状的簇。对于不同形状的数据分布还有不完善的地方。(球状簇)

(4)对未经过预处理的异常数据非常敏感,因为异常数据的存在严重影响了聚类结果的质量。(对异常值敏感)

(5)算法每次迭代需要计算数据集中各个数据点到聚类中也的距离,根据距离矩阵来重新分配数据到各个簇中,运算量庞大,耗时而低效。(效率低下)

(6)对标称属性无法计算均值,标称属性无法使用K-均值。(标称属性)

(7)算法是无监督的学习式聚类方法,当处理有初始类或者标签类属性的数据时,需要一种半监督半学习式的处理模式,如果任算法自由运算,聚类结果很可能得不到用户的肯定。

接下来根绝K-MEANS的主要缺点,逐一进行改进。

K-MEANS的JAVA代码: 大家可以参考一下,实现比较简单。

1. package cluster.com;
2.
3. import java.util.Arrays;
4. import java.util.HashMap;
5. import java.util.Map;
6. import java.util.Random;
7.
8. public class KMeans {
9.
10. private static double[][] DATA = { { 5.1, 3.5, 1.4, 0.2},
11. { 4.9, 3.0, 1.4, 0.2 },{ 4.7, 3.2, 1.3, 0.2 },
12. { 4.6, 3.1, 1.5, 0.2 },{ 5.0, 3.6, 1.4, 0.2 },
13. { 7.0, 3.2, 4.7, 1.4 },{ 6.4, 3.2, 4.5, 1.5 },
14. { 6.9, 3.1, 4.9, 1.5 },{ 5.5, 2.3, 4.0, 1.3 },
15. { 6.5, 2.8, 4.6, 1.5 },{ 5.7, 2.8, 4.5, 1.3 },
16. { 6.5, 3.0, 5.8, 2.2 },{ 7.6, 3.0, 6.6, 2.1 },
17. { 4.9, 2.5, 4.5, 1.7 },{ 7.3, 2.9, 6.3, 1.8 },
18. { 6.7, 2.5, 5.8, 1.8 },{ 6.9, 3.1, 5.1, 2.3 } };
19. public int k;//k个中心点
20. public int[] memberShip;
21. public int[] centersIndex;
22. public double[][] centers;
23. public int[] elementsInCenters;
24.
25.
26. public static void main(String[] args) {
27. KMeans kmeans = new KMeans(5);
28. String lastMembership = "";
29. String nowMembership = "";
30. int i=0;
31. while(true){
32. i++;
33. kmeans.randomCenters();
34.
35. kmeans.calMemberShip();
36. nowMembership = Arrays.toString(kmeans.memberShip);
37. System.out.println("DATA聚类之后Membership为:"+nowMembership);
38. System.out.println("Elements in centers cnt:"+Arrays.toString(kmeans.elementsInCenters));
39. if(nowMembership.equals(lastMembership)){
40. System.out.println("本次聚类与上次相同,退出执行!");
41. System.out.println("一共聚类了 "+i+" 次!");
42. kmeans.calNewCenters();
43. System.out.println("新中心点为:"+Arrays.deepToString(kmeans.centers));
44. double totalDistance = kmeans.computeTotalDistance();
45. System.out.println("totalDistance : "+totalDistance);
46. break;
47. }else{
48. lastMembership = nowMembership;
49. }
50. System.out.println("----------------华丽的分割线----------------");
51. }
52. }
53.
54. public KMeans(int k){
55. this.k = k;
56. }
57.
58. public double manhattanDistince(double []paraFirstData,double []paraSecondData){
59. double tempDistince = 0;
60. if((paraFirstData!=null && paraSecondData!=null) && paraFirstData.length==paraSecondData.length){
61. for(int i=0;i 62. tempDistince += Math.abs(paraFirstData[i] - paraSecondData[i]);
63. }
64. }else{
65.
66. }
67. return tempDistince;
68. }
69.
70. public void randomCenters(){
71. centersIndex = new int[k];
72. Random random = new Random();
73. Map map = new HashMap();
74. for(int i=0;i 75. int index = Math.abs(random.nextInt())%DATA.length;
76. if(map.containsKey(index)){
77. i--;
78. }else{
79.
80. map.put(index, DATA[index]);
81.
82. centersIndex[i] = index;
83. }
84. }
85. }
86.
87. public void calMemberShip(){
88. memberShip = new int[DATA.length];
89. elementsInCenters = new int[k];
90. for(int j=0;j 91. double currentDistance = Double.MAX_VALUE;
92. int currentIndex = -1;
93. double[] item = DATA[j];
94. for(int i=0;i 95. //中心点
96. double[] tempCentersValue = DATA[centersIndex[i]];
97. double distance = this.manhattanDistince(item, tempCentersValue);
98. if(distance 99. currentDistance = distance;
100. currentIndex = i;
101. }
102. }
103. memberShip[j] = currentIndex;
104. }
105.
106. for(int i=0;i 107. elementsInCenters[memberShip[i]]++;
108. }
109. }
110.
111. public void calNewCenters(){
112. centers = new double[k][DATA[0].length];
113. for(int i=0;i 114. for(int j=0;j 115. centers[memberShip[i]][j] += DATA[i][j];
116. }
117. }
118.
119. for(int i=0;i 120. for(int j=0;j 121. centers[i][j] /= elementsInCenters[i];
122. }
123. }
124. }
125.
126. public double computeTotalDistance() {
127. double tempTotal = 0;
128. for (int i = 0; i < DATA.length; i ++) {
129. tempTotal += manhattanDistince(DATA[i], centers[memberShip[i]]);
130. }
131. return tempTotal;
132. }
133. }


1. package cluster.com;
2.
3. import java.util.Arrays;
4. import java.util.HashMap;
5. import java.util.Map;
6. import java.util.Random;
7.
8. public class KMeans {
9.
10. private static double[][] DATA = { { 5.1, 3.5, 1.4, 0.2},
11. { 4.9, 3.0, 1.4, 0.2 },{ 4.7, 3.2, 1.3, 0.2 },
12. { 4.6, 3.1, 1.5, 0.2 },{ 5.0, 3.6, 1.4, 0.2 },
13. { 7.0, 3.2, 4.7, 1.4 },{ 6.4, 3.2, 4.5, 1.5 },
14. { 6.9, 3.1, 4.9, 1.5 },{ 5.5, 2.3, 4.0, 1.3 },
15. { 6.5, 2.8, 4.6, 1.5 },{ 5.7, 2.8, 4.5, 1.3 },
16. { 6.5, 3.0, 5.8, 2.2 },{ 7.6, 3.0, 6.6, 2.1 },
17. { 4.9, 2.5, 4.5, 1.7 },{ 7.3, 2.9, 6.3, 1.8 },
18. { 6.7, 2.5, 5.8, 1.8 },{ 6.9, 3.1, 5.1, 2.3 } };
19. public int k;//k个中心点
20. public int[] memberShip;
21. public int[] centersIndex;
22. public double[][] centers;
23. public int[] elementsInCenters;
24.
25.
26. public static void main(String[] args) {
27. KMeans kmeans = new KMeans(5);
28. String lastMembership = "";
29. String nowMembership = "";
30. int i=0;
31. while(true){
32. i++;
33. kmeans.randomCenters();
34.
35. kmeans.calMemberShip();
36. nowMembership = Arrays.toString(kmeans.memberShip);
37. System.out.println("DATA聚类之后Membership为:"+nowMembership);
38. System.out.println("Elements in centers cnt:"+Arrays.toString(kmeans.elementsInCenters));
39. if(nowMembership.equals(lastMembership)){
40. System.out.println("本次聚类与上次相同,退出执行!");
41. System.out.println("一共聚类了 "+i+" 次!");
42. kmeans.calNewCenters();
43. System.out.println("新中心点为:"+Arrays.deepToString(kmeans.centers));
44. double totalDistance = kmeans.computeTotalDistance();
45. System.out.println("totalDistance : "+totalDistance);
46. break;
47. }else{
48. lastMembership = nowMembership;
49. }
50. System.out.println("----------------华丽的分割线----------------");
51. }
52. }
53.
54. public KMeans(int k){
55. this.k = k;
56. }
57.
58. public double manhattanDistince(double []paraFirstData,double []paraSecondData){
59. double tempDistince = 0;
60. if((paraFirstData!=null && paraSecondData!=null) && paraFirstData.length==paraSecondData.length){
61. for(int i=0;i 62. tempDistince += Math.abs(paraFirstData[i] - paraSecondData[i]);
63. }
64. }else{
65.
66. }
67. return tempDistince;
68. }
69.
70. public void randomCenters(){
71. centersIndex = new int[k];
72. Random random = new Random();
73. Map map = new HashMap();
74. for(int i=0;i 75. int index = Math.abs(random.nextInt())%DATA.length;
76. if(map.containsKey(index)){
77. i--;
78. }else{
79.
80. map.put(index, DATA[index]);
81.
82. centersIndex[i] = index;
83. }
84. }
85. }
86.
87. public void calMemberShip(){
88. memberShip = new int[DATA.length];
89. elementsInCenters = new int[k];
90. for(int j=0;j 91. double currentDistance = Double.MAX_VALUE;
92. int currentIndex = -1;
93. double[] item = DATA[j];
94. for(int i=0;i 95. //中心点
96. double[] tempCentersValue = DATA[centersIndex[i]];
97. double distance = this.manhattanDistince(item, tempCentersValue);
98. if(distance 99. currentDistance = distance;
100. currentIndex = i;
101. }
102. }
103. memberShip[j] = currentIndex;
104. }
105.
106. for(int i=0;i 107. elementsInCenters[memberShip[i]]++;
108. }
109. }
110.
111. public void calNewCenters(){
112. centers = new double[k][DATA[0].length];
113. for(int i=0;i 114. for(int j=0;j 115. centers[memberShip[i]][j] += DATA[i][j];
116. }
117. }
118.
119. for(int i=0;i 120. for(int j=0;j 121. centers[i][j] /= elementsInCenters[i];
122. }
123. }
124. }
125.
126. public double computeTotalDistance() {
127. double tempTotal = 0;
128. for (int i = 0; i < DATA.length; i ++) {
129. tempTotal += manhattanDistince(DATA[i], centers[memberShip[i]]);
130. }
131. return tempTotal;
132. }
133. }
点击复制链接 与好友分享!回本站首页
上一篇:solr6.4.1+tomcat8.5.0+jdk1.8.0_112安装Solr环境
下一篇:关于服务器
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站