大数据分析之聚类算法
公司主营业务：成都做网站、网站设计、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出察哈尔右翼中旗免费做网站回馈大家。
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();
K-MEANS算法:
k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
具体如下：
输入：k, data[n];
（1） 选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1];
（2） 对于data[0]….data[n], 分别与c[0]…c[n-1]比较，假定与c[i]差值最少，就标记为i;
（3） 对于所有标记为i点，重新计算c[i]=/标记为i的个数；
（4） 重复(2)(3),直到所有c[i]值的变化小于给定阈值。
算法实现起来应该很容易，就不帮你编写代码了。
