189 8069 5689
大数据分析之聚类算法
在成都网站设计、成都网站制作过程中，需要针对客户的行业特点、产品特性、目标受众和市场情况进行定位分析，以确定网站的风格、色彩、版式、交互等方面的设计方向。创新互联建站还需要根据客户的需求进行功能模块的开发和设计，包括内容管理、前台展示、用户权限管理、数据统计和安全保护等功能。
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个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
我们生活在数据大爆炸时代，每时每刻都在产生海量的数据如视频，文本，图像和博客等。由于数据的类型和大小已经超出了人们传统手工处理的能力范围，聚类，作为一种最常见的无监督学习技术，可以帮助人们给数据自动打标签，已经获得了广泛应用。聚类的目的就是把不同的数据点按照它们的相似与相异度分割成不同的簇（注意：簇就是把数据划分后的子集），确保每个簇中的数据都是尽可能相似，而不同的簇里的数据尽可能的相异。从模式识别的角度来讲，聚类就是在发现数据中潜在的模式，帮助人们进行分组归类以达到更好理解数据的分布规律。
聚类的应用非常广泛，比如在商业应用方面，聚类可以帮助市场营销人员将客户按照他们的属性分层，发现不同的客户群和他们的购买倾向（如下图将客户按照他们对颜色喜好归类）。这样公司就可以寻找潜在的市场，更高效地开发制定化的产品与服务。在文本分析处理上，聚类可以帮助新闻工作者把最新的微博按照的话题相似度进行分类，而快速得出热点新闻和关注对象。在生物医学上，可以根据对相似表达谱的基因进行聚类，从而知道未知基因的功能。
由于聚类是无监督学习方法，不同的聚类方法基于不同的假设和数据类型。由于数据通常可以以不同的角度进行归类，因此没有万能的通用聚类算法，并且每一种聚类算法都有其局限性和偏见性。也就是说某种聚类算法可能在市场数据上效果很棒，但是在基因数据上就无能为力了。
聚类算法很多，包括基于划分的聚类算法（如：k-means），基于层次的聚类算法（如：BIRCH），基于密度的聚类算法（如：DBSCAN），基于网格的聚类算法( 如：STING )等等。本文将介绍聚类中一种最常用的方法——基于密度的聚类方法 （density-based clustering）。
相比其他的聚类方法，基于密度的聚类方法可以在有噪音的数据中发现各种形状和各种大小的簇。DBSCAN（Ester, 1996）是该类方法中最典型的代表算法之一（DBSCAN获得 2014 SIGKDD Test of Time Award ）。其核心思想就是先发现密度较高的点，然后把相近的高密度点逐步都连成一片，进而生成各种簇。算法实现上就是，对每个数据点为圆心，以eps为半径画个圈（称为邻域eps-neigbourhood），然后数有多少个点在这个圈内，这个数就是该点密度值。然后我们可以选取一个密度阈值MinPts，如圈内点数小于MinPts的圆心点为低密度的点，而大于或等于MinPts的圆心点高密度的点（称为核心点Core point）。如果有一个高密度的点在另一个高密度的点的圈内，我们就把这两个点连接起来，这样我们可以把好多点不断地串联出来。之后，如果有低密度的点也在高密度的点的圈内，把它也连到最近的高密度点上，称之为边界点。这样所有能连到一起的点就成一了个簇，而不在任何高密度点的圈内的低密度点就是异常点。下图展示了DBSCAN的工作原理。
由于DBSCAN是靠不断连接邻域内高密度点来发现簇的，只需要定义邻域大小和密度阈值，因此可以发现不同形状，不同大小的簇。下图展示了一个二维空间的DBSCAN聚类结果。
DBSCAN算法伪码表达如下：
由于DBSCAN使用的是全局的密度阈值MinPts, 因此只能发现密度不少于MinPts的点组成的簇，即很难发现不同密度的簇。其成功与失败的情况举例如下：
为了解决其发现不同密度的簇，目前已经有很多新的方法被发明出来，比如OPTICS （ordering points to identify the clustering structure）将邻域点按照密度大小进行排序，再用可视化的方法来发现不同密度的簇，如下图所示。OPTICS必须由其他的算法在可视化的图上查找“山谷”来发现簇，因此其性能直接受这些算法的约束。
另外SNN （shared nearest neighbor）采用一种基于KNN（最近邻）来算相似度的方法来改进DBSCAN。对于每个点，我们在空间内找出离其最近的k个点（称为k近邻点）。两个点之间相似度就是数这两个点共享了多少个k近邻点。如果这两个点没有共享k近邻点或者这两个点都不是对方的k近邻点，那么这两个点相似度就是0。然后我们把DBSCAN里面的距离公式替换成SNN相似度，重新算每个点的邻域和密度，就可以发现不同密度的簇了。SNN的核心就是，把原始的密度计算替换成基于每对点之间共享的邻域的范围，而忽略其真实的密度分布。SNN的缺点就是必须定义最近邻个数k, 而且其性能对k的大小很敏感。下图展示了SNN计算相似度的方法。
2014年Science 杂志刊登了一种基于密度峰值的算法DP (Clustering by fast search and find of density peaks)，也是采用可视化的方法来帮助查找不同密度的簇。其思想为每个簇都有个最大密度点为簇中心，每个簇中心都吸引并连接其周围密度较低的点，且不同的簇中心点都相对较远。为实现这个思想，它首先计算每个点的密度大小（也是数多少点在邻域eps-neigbourhood内），然后再计算每个点到其最近的且比它密度高的点的距离。这样对每个点我们都有两个属性值，一个是其本身密度值，一个是其到比它密度高的最近点的距离值。对这两个属性我们可以生成一个2维图表（决策图），那么在右上角的几个点就可以代表不同的簇的中心了，即密度高且离其他簇中心较远。然后我们可以把其他的点逐步连接到离其最近的且比它密度高的点，直到最后连到某个簇中心点为止。这样所有共享一个簇中心的点都属于一个簇，而离其他点较远且密度很低的点就是异常点了。由于这个方法是基于相对距离和相对密度来连接点的，所以其可以发现不同密度的簇。DP的缺陷就在于每个簇必须有个最大密度点作为簇中心点，如果一个簇的密度分布均与或者一个簇有多个密度高的点，其就会把某些簇分开成几个子簇。另外DP需要用户指定有多少个簇，在实际操作的时候需要不断尝试调整。下图展示了一个DP生成的决策图。
除此之外，还可以用密度比估计（Density-ratio estimation）来克服DBSCAN无法发现不同密度簇的缺陷。密度比的核心思想就是对每个点，计算其密度与其邻域密度的比率，然后用密度比计算替换DBSCAN的密度计算来发现核心点Core point，而其他过程和DBSCAN不变。这样一来，每个局部高密度点就会被选出来作为核心点，从而发现不同密度的簇。基于这个思想，我们还可以把原始数据按其密度分布进行标准化（ReScale），即把密度高的区域进行扩张，密度低的区域继续收缩。这样以来，不同密度的簇就可以变成密度相近的簇了，我们再在标准化后的数据上直接跑DBSCAN就搞定了。这种方法需要用户设置邻域范围来计算密度比，下图展示了标准化前后的数据分布对比。
基于密度的聚类是一种非常直观的聚类方法，即把临近的密度高的区域练成一片形成簇。该方法可以找到各种大小各种形状的簇，并且具有一定的抗噪音特性。在日常应用中，可以用不同的索引方法或用基于网格的方法来加速密度估计，提高聚类的速度。基于密度的聚类也可以用在流数据和分布式数据中，关于其他方向的应用，详见 （ Aggarwal 2013 ）.
DP:
DBSCAN, SNN, OPTICS 和 Density-ratio:
Aggarwal, C. C., Reddy, C. K. (Eds.). (2013). Data clustering: algorithms and applications. CRC press.
Ankerst, M., Breunig, M. M., Kriegel, H. P., Sander, J. (1999, June). OPTICS: ordering points to identify the clustering structure. In ACM Sigmod record (Vol. 28, No. 2, pp. 49-60). ACM.
Ertöz, L., Steinbach, M., Kumar, V. (2003, May). Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data. In Proceedings of the 2003 SIAM International Conference on Data Mining(pp. 47-58). Society for Industrial and Applied Mathematics.
Ester, M., Kriegel, H. P., Sander, J., Xu, X. (1996, August). A density-based algorithm for discovering clusters in large spatial databases with noise. In SIGKDD (Vol. 96, No. 34, pp. 226-231).
Han, J., Pei, J., Kamber, M. (2011).Data mining: concepts and techniques. Elsevier.
Rodriguez, A., Laio, A. (2014). Clustering by fast search and find of density peaks.Science,344(6191), 1492-1496.
Zhu, Y., Ting, K. M., Carman, M. J. (2016). Density-ratio based clustering for discovering clusters with varying densities. Pattern Recognition, Volume 60, 2016, Pages 983-997, ISSN 0031-3203.
五十多行
K均值（K-Means）是聚类算法中最为简单、高效的，属于无监督学习算法。聚类算法有K均值聚类、基于密度的聚类、最大期望聚类三种类型。
核心思想是由用户指定K个初始质心（initial centroids），以作为聚类的类别（cluster），重复迭代直至算法收敛。对每个样本点，计算得到距其最近的质心，将其类别标为该质心所对应的cluster；重新计算K个cluster对应的质心。
DBSCAN是一种基于密度的聚类算法 它的基本原理就是给定两个参数 ξ和minp 其中 ξ可以理解为半径 算法将在这个半径内查找样本 minp是一个以ξ为半径查找到的样本个数n的限制条件 只要n=minp 查找到的样本点就是核心样本点 算法的具体描述见参考文件 下边是这个算法的java实现
首先定义一个Point类 代表样本点
! [endif]
package sunzhenxing;
public class Point {
private int x;
private int y;
private boolean isKey;
private boolean isClassed;
public boolean isKey() {
return isKey;
}
public void setKey(boolean isKey) {
this isKey = isKey;
this isClassed=true;
}
public boolean isClassed() {
return isClassed;
}
public void setClassed(boolean isClassed) {
this isClassed = isClassed;
}
public int getX() {
return x;
}
public void setX(int x) {
this x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this y = y;
}
public Point(){
x= ;
y= ;
}
public Point(int x int y){
this x=x;
this y=y;
}
public Point(String str){
String[] p=str split( );
this x=Integer parseInt(p[ ]);
this y=Integer parseInt(p[ ]);
}
public String print(){
return +this x+ +this y+ ;
}
}
然后定义一个工具类 为算法的实现服务
package sunzhenxing;
import java io BufferedReader;
import java io FileReader;
import java io IOException;
import java util *;
public class Utility {
/**
* 测试两个点之间的距离
* @param p 点
* @param q 点
* @return 返回两个点之间的距离
*/
public static double getDistance(Point p Point q){
int dx=p getX() q getX();
int dy=p getY() q getY();
double distance=Math sqrt(dx*dx+dy*dy);
return distance;
}
/**
* 检查给定点是不是核心点
* @param lst 存放点的链表
* @param p 待测试的点
* @param e e半径
* @param minp 密度阈值
* @return 暂时存放访问过的点
*/
public static ListPoint isKeyPoint(ListPoint lst Point p int e int minp){
int count= ;
ListPoint tmpLst=new ArrayListPoint();
for(IteratorPoint it=erator();it hasNext();){
Point q=it next();
if(getDistance(p q)=e){
++count;
if(!ntains(q)){
tmpLst add(q);
}
}
}
if(count=minp){
p setKey(true);
return tmpLst;
}
return null;
}
public static void setListClassed(ListPoint lst){
for(IteratorPoint it=erator();it hasNext();){
Point p=it next();
if(!p isClassed()){
p setClassed(true);
}
}
}
/**
* 如果b中含有a中包含的元素 则把两个集合合并
* @param a
* @param b
* @return a
*/
public static boolean mergeList(ListPoint a ListPoint b){
boolean merge=false;
for(int index= ;indexb size();++index){
if(ntains(b get(index))){
merge=true;
break;
}
}
if(merge){
for(int index= ;indexb size();++index){
if(!ntains(b get(index))){
a add(b get(index));
}
}
}
return merge;
}
/**
* 返回文本中的点集合
* @return 返回文本中点的集合
* @throws IOException
*/
public static ListPoint getPointsList() throws IOException{
ListPoint lst=new ArrayListPoint();
String txtPath= src\\\\sunzhenxing\\points txt ;
BufferedReader br=new BufferedReader(new FileReader(txtPath));
String str= ;
while((str=br readLine())!=null str!= ){
lst add(new Point(str));
}
br close();
return lst;
}
}
最后在主程序中实现算法 如下所示
package sunzhenxing;
import java io *;
import java util *;
public class Dbscan {
private static ListPoint pointsList=new ArrayListPoint();//存储所有点的集合
private static ListListPoint resultList=new ArrayListListPoint();//存储DBSCAN算法返回的结果集
private static int e= ;//e半径
private static int minp= ;//密度阈值
/**
* 提取文本中的的所有点并存储在pointsList中
* @throws IOException
*/
private static void display(){
int index= ;
for(IteratorListPoint it=erator();it hasNext();){
ListPoint lst=it next();
if(lst isEmpty()){
continue;
}
System out println( 第 +index+ 个聚类 );
for(IteratorPoint it =erator();it hasNext();){
Point p=it next();
System out println(p print());
}
index++;
}
}
//找出所有可以直达的聚类
private static void applyDbscan(){
try {
pointsList=Utility getPointsList();
for(IteratorPoint it=erator();it hasNext();){
Point p=it next();
if(!p isClassed()){
ListPoint tmpLst=new ArrayListPoint();
if((tmpLst=Utility isKeyPoint(pointsList p e minp)) != null){
//为所有聚类完毕的点做标示
Utility setListClassed(tmpLst);
resultList add(tmpLst);
}
}
}
} catch (IOException e) {
// TODO Auto generated catch block
e printStackTrace();
}
}
//对所有可以直达的聚类进行合并 即找出间接可达的点并进行合并
private static ListListPoint getResult(){
applyDbscan();//找到所有直达的聚类
int length=resultList size();
for(int i= ;ilength;++i){
for(int j=i+ ;jlength;++j){
if(rgeList(resultList get(i) resultList get(j))){
resultList get(j) clear();
}
}
}
return resultList;
}
/**
* 程序主函数
* @param args
*/
public static void main(String[] args) {
getResult();
display();
//System out println(Utility getDistance(new Point( ) new Point( )));
}
}
下边是一个小测试 即使用src\\\\sunzhenxing\\points txt文件的内容进行测试 points txt的文件内容是
最后算法的结果是
第 个聚类
第 个聚类
lishixinzhi/Article/program/Java/hx/201311/26957