189 8069 5689
第一次迭代下,除了a4点,其他点都归为一类c1:(a1 a2 a3 a5);c2:(a4) 聚类中心：c1:(2,2);c2(5,4)（聚类中心的计算方式是平均类中所有点）
创新互联建站长期为1000+客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为三台企业提供专业的网站设计制作、网站设计，三台网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。
第二次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚类中心c1:(4/3,5/3);c2(9/2 7/2)
第三次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚类中心c1:(4/3,5/3);c2(9/2 7/2)结果已经稳定跳出循环
大数据分析之聚类算法
1. 什么是聚类算法
所谓聚类，就是比如给定一些元素或者对象，分散存储在数据库中，然后根据我们感兴趣的对象属性，对其进行聚集，同类的对象之间相似度高，不同类之间差异较大。最大特点就是事先不确定类别。
这其中最经典的算法就是KMeans算法，这是最常用的聚类算法，主要思想是:在给定K值和K个初始类簇中心点的情况下，把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。
KMeans算法本身思想比较简单，但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。
聚类算法实现
假设对象集合为D，准备划分为k个簇。
基本算法步骤如下：
1、从D中随机取k个元素，作为k个簇的各自的中心。
2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。
3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。
4、将D中全部元素按照新的中心重新聚类。
5、重复第4步，直到聚类结果不再变化。
6、将结果输出。
核心Java代码如下：
/**
* 迭代计算每个点到各个中心点的距离，选择最小距离将该点划入到合适的分组聚类中，反复进行，直到
* 分组不再变化或者各个中心点不再变化为止。
* @return
*/
public List[] comput() {
List[] results = new ArrayList[k];//为k个分组，分别定义一个聚簇集合，未来放入元素。
boolean centerchange = true;//该变量存储中心点是否发生变化
while (centerchange) {
iterCount++;//存储迭代次数
centerchange = false;
for (int i = 0; i k; i++) {
results[i] = new ArrayListT();
}
for (int i = 0; i players.size(); i++) {
T p = players.get(i);
double[] dists = new double[k];
for (int j = 0; j initPlayers.size(); j++) {
T initP = initPlayers.get(j);
/* 计算距离 这里采用的公式是两个对象相关属性的平方和，最后求开方*/
double dist = distance(initP, p);
dists[j] = dist;
}
int dist_index = computOrder(dists);//计算该点到各个质心的距离的最小值，获得下标
results[dist_index].add(p);//划分到对应的分组。
}
/*
* 将点聚类之后，重新寻找每个簇的新的中心点，根据每个点的关注属性的平均值确立新的质心。
*/
for (int i = 0; i k; i++) {
T player_new = findNewCenter(results[i]);
System.out.println("第"+iterCount+"次迭代，中心点是："+player_new.toString());
T player_old = initPlayers.get(i);
if (!IsPlayerEqual(player_new, player_old)) {
centerchange = true;
initPlayers.set(i, player_new);
}
}
}
return results;
}
上面代码是其中核心代码，我们根据对象集合List和提前设定的k个聚集,最终完成聚类。我们测试一下，假设要测试根据NBA球员的场均得分情况，进行得分高中低的聚集，很简单，高得分在一组，中等一组，低得分一组。
我们定义一个Player类，里面有属性goal，并录入数据。并设定分组数目为k=3。
测试代码如下:
List listPlayers = new ArrayList();
Player p1 = new Player();
p1.setName(“mrchi1”);
p1.setGoal(1);
p1.setAssists(8);
listPlayers.add(p1);
Player p2 = new Player();
p2.setName("mrchi2");
p2.setGoal(2);
listPlayers.add(p2);
Player p3 = new Player();
p3.setName("mrchi3");
p3.setGoal(3);
listPlayers.add(p3);
//其他对象定义此处略。制造几个球员的对象即可。
KmeansPlayer kmeans = new KmeansPlayer(listPlayers, 3);
ListPlayer[] results = kmeans.comput();
for (int i = 0; i results.length; i++) {
System.out.println("类别" + (i + 1) + "聚集了以下球员：");
ListPlayer list = results[i];
for (Player p : list) {
System.out.println(p.getName() + "---" + p.getGoal()
}
}
算法运行结果：
可以看出中心点经历了四次迭代变化，最终分类结果也确实是相近得分的分到了一组。当然这种算法有缺点，首先就是初始的k个中心点的确定非常重要，结果也有差异。可以选择彼此距离尽可能远的K个点，也可以先对数据用层次聚类算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
以前做项目时候写的代码，数据是一维的，多维的也一样，把距离计算的改一改就行int term = Math.abs(dotlist.get(centerIndex[j]).x- dotlist.get(i).x);
[java] view plaincopy
package uestc.dmlab.call;
import java.io.BufferedReader;
import java.io.FileReader;
import java.security.KeyStore.Entry;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
public class Clustering {
/**
*
* @param fileName
* 文件中每个字段对应一个概率
* @param k
* 聚成k个类
* @param minDistance
* 聚类中心位移小于minDistance时停止迭代
* @return
*/
public static HashMapString, Integer cluster(String fileName, int k,
int minDistance) {
try {
BufferedReader br = new BufferedReader(new FileReader(fileName));
ListDot dotlist = new LinkedListDot();
String line;
int count = 0;// 行数
while ((line = br.readLine()) != null) {
String s[] = line.split(",");
Dot dot = new Dot();
dot.isCenter = false;
dot.isVirtual = false;
dot.name = s[0];
// if(s.length4){
// System.out.println(line);
// }
dot.x = Integer.parseInt(s[3]);
dotlist.add(dot);
count++;
}
if (count k) {
k = count;
}
// 随机初始化k个聚类中心
int centerIndex[] = new int[k]; // 存储k个中心点在dotlist中的索引
int centerNum = k;
while (centerNum 0) {
int index = new Random().nextInt(count);
if (!dotlist.get(index).isCenter) {
centerNum--;
dotlist.get(index).isCenter = true;
centerIndex[centerNum] = index;
}
}
// K个聚类
Cluster[] clusers = new Cluster[k];
boolean flag = true;
while (flag) {
flag = false;
clusers = new Cluster[k];
for (int i = 0; i clusers.length; i++) {
clusers[i] = new Cluster();
}
//System.out.println(clusers.length);
// 找到离第i个点最近的聚类中心
for (int i = 0; i dotlist.size(); i++) {
// 该点不是中心点也不是虚拟点就计算它与所有中心点的距离并取最小值
// if(!dotlist.get(i).isCenter!dotlist.get(i).isVirtual){
if (!dotlist.get(i).isVirtual) {
int distance = Integer.MAX_VALUE;
int c = 0;// 记录离该节点最近的中心点的索引
for (int j = 0; j k; j++) {
int term = Math.abs(dotlist.get(centerIndex[j]).x
- dotlist.get(i).x);
if (distance term) {
distance = term;
c = j;
}
}
clusers[c].dots.add(i);
}
}
// 重新计算聚类中心
for (int i = 0; i k; i++) {
Cluster cluster = clusers[i];
if (cluster.dots.size() 0) { //若该类中有点
int sum = 0;
for (int j = 0; j cluster.dots.size(); j++) {
sum += dotlist.get(cluster.dots.get(j)).x;
}
Dot dot = new Dot();
dot.x = sum / cluster.dots.size();
dot.isCenter = true;
dot.isVirtual = true;
// 新旧聚类中心的距离
int term = Math.abs(dotlist.get(centerIndex[i]).x
- dot.x);
if (term minDistance)
flag = true;
dotlist.add(dot);
centerIndex[i] = dotlist.indexOf(dot); // 第i个聚类的中心改变
}
}
}
// 生成分类映射
HashMapString, Integer map = new HashMapString, Integer();
for (Dot dot : dotlist) {
if (dot.isVirtual == false) {
int className = -1;
for (int i = 0; i k; i++) {
if (clusers[i].dots.contains(dotlist.indexOf(dot)))
className = i;
}
map.put(dot.name, className);
}
}
return map;
} catch (Exception e) {
e.printStackTrace();
}
return new HashMapString, Integer();
}
public static void main(String[] args) {
MapString, Integer map = Clustering.cluster(
"C:/Documents and Settings/Administrator/桌面/123.txt", 2, 0);
IteratorMap.EntryString, Integer it = map.entrySet().iterator();
while(it.hasNext()){
Map.EntryString, Integer entry = it.next();
System.out.println(entry.getKey()+","+entry.getValue());
}
}
}
class Dot {
String name;
int x;
boolean isCenter;
boolean isVirtual;
}
class Cluster {
// 记录了该类中点的索引值
LinkedListInteger dots = new LinkedListInteger();