首页 首页 大数据 查看内容

聚类分析经典算法讲解及实现

木马童年 2019-7-1 20:06 93 0

聚类和分类的区别一开始笔者就想谈谈这个话题,毕竟在数据挖掘算法领域,这两者有着很大的差别,对于初学者很容易混淆。抛开晦涩的定义陈述,在此我们先通过两个生活比喻看看什么是监督学习,什么是非监督学习。回首 ...

聚类和分类的区别

一开始笔者就想谈谈这个话题,毕竟在数据挖掘算法领域,这两者有着很大的差别,对于初学者很容易混淆。抛开晦涩的定义陈述,在此我们先通过两个生活比喻看看什么是监督学习,什么是非监督学习。

回首我们人生最美好的豆蔻年华,那时的我们,少年初长成,结束了小学生涯,步入初中,这个年龄是我们人生中第一个分水岭。初中一年级刚入学时,同学们之间彼此不认识,老师对同学们也都不熟悉。但随着时间的推移,同学们基本上都分成了三五群,回想一下那时的我们,是不是整天玩在一起的同学总是那几个?我们发现,这个过程老师是不参与的,老师不会让同学们分成几组,让哪几个同学经常在一起学习和玩耍。想想这个过程,其实是我们自己辨别和哪些同学合得来一个过程,这期间我们可能会判断同学的性格,学习成绩,共同爱好与话题,是否和同学家离的很近还能一起上学和回家等等很多的维度因素。时间久了,班级里就会出现不同的几个圈子,这个圈子的数量及细节一开始并没有人知晓,并且这个过程无老师进行监督,因此我们视之为无监督学习。在此我们指出,聚类算法是无监督学习的算法。

初中三年级,因为我们背负着中考的重担,大家都为了自己的理想高中做最后的冲刺努力。设想这样一种情况:为了更好的帮助大家不断提高学习成绩,班主任老师将班级分成了五个互帮互助小组(语文、数学、物理、生物、英语),每个小组十位同学,分别是班级里这几个科目考试成绩最好的前十名同学,为了达到更好的互帮互助效果,每位达到条件要求的同学只能加入一门科目小组,也就是说,如果某位同学有两门或两门以上的科目都排在班级前十名,则班主任老师随机指定其加入某一小组。这样所有同学都可以在互帮互助小组的帮助下更大程度的提升自己的薄弱科目,实现共赢。在此我们可以看到小组的种类,数量,都是定义好的,只需要老师指定好各个小组的成员。因此,这样的学习过程是一种监督学习过程,老师给出小组的种类和数量用排名的方式来监督并激励学生学习。在此我们指出,分类算法是监督学习的算法。

总结一下,数据分类是分析已有的数据,寻找其共同的属性,并根据分类模型将这些数据划分成不同的类别,这些数据赋予类标号。这些类别是事先定义好的,并且类别数是已知的。相反,数据聚类则是将本没有类别参考的数据进行分析并划分为不同的组,即从这些数据导出类标号。聚类分析本身则是根据数据来发掘数据对象及其关系信息,并将这些数据分组。每个组内的对象之间是相似的,而各个组间的对象是不相关的。不难理解,组内相似性越高,组间相异性越高,则聚类越好。

层次聚类算法详解及实现

层次聚类简介

层次聚类分为凝聚式层次聚类和分裂式层次聚类。

凝聚式层次聚类,就是在初始阶段将每一个点都视为一个簇,之后每一次合并两个最接近的簇,当然对于接近程度的定义则需要指定簇的邻近准则。

分裂式层次聚类,就是在初始阶段将所有的点视为一个簇,之后每次分裂出一个簇,直到最后剩下单个点的簇为止。

本文中我们将详细介绍凝聚式层次聚类算法。

对于凝聚式层次聚类,指定簇的邻近准则是非常重要的一个环节,在此我们介绍三种最常用的准则,分别是 MAX, MIN, 组平均。如下图所示:

图 2. 层次聚类计算准则

聚类分析经典算法讲解及实现

算法流程

凝聚式层次聚类算法也是一个迭代的过程,算法流程如下:

  1. 每次选最近的两个簇合并,我们将这两个合并后的簇称之为合并簇。

  2. 若采用 MAX 准则,选择其他簇与合并簇中离得最远的两个点之间的距离作为簇之间的邻近度。若采用 MIN 准则,取其他簇与合并簇中离得最近的两个点之间的距离作为簇之间的邻近度。若组平均准则,取其他簇与合并簇所有点之间距离的平均值作为簇之间的邻近度。

  3. 重复步骤 1 和步骤 2,合并至只剩下一个簇。

算法过程举例

下面我们看一个例子:

下图是一个有五个点的而为坐标系:

图 3. 层次聚类举例

聚类分析经典算法讲解及实现

下表为这五个点的欧式距离矩阵:

表 1. 欧式距离原始矩阵





P1P2P3P4P5
P100.811.321.941.82
P20.8101.562.161.77
P31.321.5600.630.71
P41.942.160.6300.71
P51.821.770.710.710

根据算法流程,我们先找出距离最近的两个簇,P3, P4。

合并 P3, P4 为 {P3, P4},根据 MIN 原则更新矩阵如下:

MIN.distance({P3, P4}, P1) = 1.32;

MIN.distance({P3, P4}, P2) = 1.56;

MIN.distance({P3, P4}, P5) = 0.70;

表 2. 欧式距离更新矩阵 1




P1P2{P3, P4}P5
P100.811.321.82
P20.8101.561.77
{P3, P4}1.321.5600.71
P51.821.770.710

接着继续找出距离最近的两个簇,{P3, P4}, P5。

合并 {P3, P4}, P5 为 {P3, P4, P5},根据 MIN 原则继续更新矩阵:

MIN.distance(P1, {P3, P4, P5}) = 1.32;

MIN.distance(P2, {P3, P4, P5}) = 1.56;

表 3. 欧式距离更新矩阵 2



P1P2{P3, P4, P5}
P100.811.32
P20.8101.56
{P3, P4, P5}1.321.560

接着继续找出距离最近的两个簇,P1, P2。

合并 P1, P2 为 {P1, P2},根据 MIN 原则继续更新矩阵:

MIN.distance({P1,P2}, {P3, P4, P5}) = 1.32

表 4. 欧式距离更新矩阵 3


{P1, P2}{P3, P4, P5}
{P1, P2}01.32
{P3, P4, P5}1.320

最终合并剩下的这两个簇即可获得最终结果,如下图:

图 4. 层次聚类举例结果

聚类分析经典算法讲解及实现

MAX,组平均算法流程同理,只是在更新矩阵时将上述计算簇间距离变为簇间两点最大欧式距离,和簇间所有点平均欧式距离即可。

算法实现

清单 4. 层次聚类算法代码实现

import java.io.BufferedReader;  import java.io.FileReader;  import java.io.IOException;  import java.io.PrintStream;  import java.text.DecimalFormat;  import java.util.ArrayList;    public class Hierarchical {   private double[][] matrix;   private int dimension;// 数据维度     private class Node {   double[] attributes;     public Node() {   attributes = new double[100];   }   }     private ArrayListarraylist;     private class Model {   int x = 0;   int y = 0;   double value = 0;   }     private Model minModel = new Model();     private double getDistance(Node one, Node two) {// 计算两点间的欧氏距离   double val = 0;   for (int i = 0; i < dimension; ++i) {   val += (one.attributes[i] - two.attributes[i]) * (one.attributes[i] - two.attributes[i]);   }   return Math.sqrt(val);   }     private void loadMatrix() {// 将输入数据转化为矩阵   for (int i = 0; i < matrix.length; ++i) {   for (int j = i + 1; j < matrix.length; ++j) {   double distance = getDistance(arraylist.get(i), arraylist.get(j));   matrix[i][j] = distance;   }   }   }     private Model findMinValueOfMatrix(double[][] matrix) {// 找出矩阵中距离最近的两个簇   Model model = new Model();   double min = 0x7fffffff;   for (int i = 0; i < matrix.length; ++i) {   for (int j = i + 1; j < matrix.length; ++j) {   if (min > matrix[i][j] && matrix[i][j] != 0) {   min = matrix[i][j];   model.x = i;   model.y = j;   model.value = matrix[i][j];   }   }   }   return model;   }     private void processHierarchical(String path) {   try {   PrintStream out = new PrintStream(path);   while (true) {// 凝聚层次聚类迭代   out.println("Matrix update as below: ");   for (int i = 0; i < matrix.length; ++i) {// 输出每次迭代更新的矩阵   for (int j = 0; j < matrix.length - 1; ++j) {   out.print(new DecimalFormat("#.00").format(matrix[i][j]) + " ");   }   out.println(new DecimalFormat("#.00").format(matrix[i][matrix.length - 1]));   }   out.println();   minModel = findMinValueOfMatrix(matrix);   if (minModel.value == 0) {// 当找不出距离最近的两个簇时,迭代结束   break;   }   out.println("Combine " + (minModel.x + 1) + " " + (minModel.y + 1));   out.println("The distance is: " + minModel.value);     matrix[minModel.x][minModel.y] = 0;// 更新矩阵   for (int i = 0; i < matrix.length; ++i) {// 如果合并了点 p1 与 p2,则只保留 p1,p2 其中之一与其他点的距离,取较小值   if (matrix[i][minModel.x] <= matrix[i][minModel.y]) {   matrix[i][minModel.y] = 0;   } else {   matrix[i][minModel.x] = 0;   }   if (matrix[minModel.x][i] <= matrix[minModel.y][i]) {   matrix[minModel.y][i] = 0;   } else {   matrix[minModel.x][i] = 0;   }   }   }     out.close();   System.out.println("Please check results in: " + path);   } catch (Exception e) {   e.printStackTrace();   }   }     public void setInput(String path) {   try {   BufferedReader br = new BufferedReader(new FileReader(path));   String str;   String[] strArray;   arraylist = new ArrayList();   while ((str = br.readLine()) != null) {   strArray = str.split(",");   dimension = strArray.length;   Node node = new Node();   for (int i = 0; i < dimension; ++i) {   node.attributes[i] = Double.parseDouble(strArray[i]);   }   arraylist.add(node);   }   matrix = new double[arraylist.size()][arraylist.size()];   loadMatrix();   br.close();   } catch (IOException e) {   e.printStackTrace();   }   }     public void printOutput(String path) {   processHierarchical(path);   }     public static void main(String[] args) {   Hierarchical hi = new Hierarchical();   hi.setInput("c:/hierarchical.txt");   hi.printOutput("c:/hierarchical_results.txt");   }  }

测试数据

给出一组简单的二维测试数据

清单 5. 层次聚类算法测试数据

0.7,1.2  0.8,2  2,1  2.6,0.8  2.5,1.5

运行结果

清单 6. 层次聚类算法运行结果

Matrix update as below:   .00 .81 1.32 1.94 1.82  .00 .00 1.56 2.16 1.77  .00 .00 .00 .63 .71  .00 .00 .00 .00 .71  .00 .00 .00 .00 .00    Combine 3 4  The distance is: 0.6324555320336759  Matrix update as below:   .00 .81 1.32 .00 1.82  .00 .00 1.56 .00 1.77  .00 .00 .00 .00 .00  .00 .00 .00 .00 .71  .00 .00 .00 .00 .00    Combine 4 5  The distance is: 0.7071067811865475  Matrix update as below:   .00 .81 1.32 .00 .00  .00 .00 1.56 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00    Combine 1 2  The distance is: 0.806225774829855  Matrix update as below:   .00 .00 1.32 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00    Combine 1 3  The distance is: 1.3152946437965907  Matrix update as below:   .00 .00 .00 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00  .00 .00 .00 .00 .00

其他聚类算法简介

BIRCH 算法

Birch 是一种能够高效处理大数据聚类的基于树的层次聚类算法。设想这样一种情况,一个拥有大规模数据的数据库,当这些数据被放入主存进行聚类处理时,一般的聚类算法则没有对应的高效处理能力,这时 Birch 算法是最佳的选择。

Birth 不仅能够高效地处理大数据聚类,并且能最小化 IO 花销。它不需要扫描全局数据已经现有的簇。

算法流程

聚类特征 CF=(N,LS,SS),其中 N 代表簇中点的个数,LS 代表簇中代表簇中各点线性和,SS 代表簇中各点的平方和距离。聚类特征被应用于 CF 树中,CF 树是一种高度平衡树,它具有两个参数:平衡因子 B 和簇半径阈值 T。其中平衡因子 B 代表每一个非叶子节点最多能够引入 B 个实体条目。

叶子节点最多只能包含 L 个实体条目,并且它们具有前向后向指针,这样可以彼此链接起来。

树的大小取决于簇半径阈值 T 的大小。

  1. 从根节点开始,递归查找与要插入的数据点距离最近的叶子节点中的实体条目,递归过程选择最短路径。

  2. 比较上述计算出的数据点与叶子节点中实体条目间的最近距离是否小叶簇半径阈值 T,小于则吸收该数据点。否则执行下一步。

  3. 判断当前条目所在的叶节点个数是否小于 L,若小于则直接将该数据点插入当前点。否则分裂叶子节点,分裂过程是将叶子节点中距离最远的两个实体条目变为新的两个叶子节点,其他条目则根据距离最近原则重新分配到这两个新的叶子节点中。删除原来的叶子节点并更新 CF 树。

若不能将所有数据点加入 CF 树中,则考虑增加簇半径阈值 T,并重新更新 CF 树直至所有的数据点被加入 CF 树为止。

CURE 算法

算法流程

  1. 在数据集中选择样本数据。

  2. 将上述样本数据划分为 P 个同样大小的划分。

  3. 将每个划分中的点聚成 m/pq 个簇,共得到 m/q 个簇。过程中需删除噪声点。

  4. 对上述 m/q 个簇进行聚类直至剩下 k 个簇。

  5. 继续删除离群点。

  6. 将剩下的点指派到最近的簇完成聚类过程。


聚类算法是数据挖掘算法中最为重要的部分之一,算法种类繁多,应用场景也各有不同,本文章提到的聚类算法为常见常用的一些较为基本的算法,对于其他的聚类算法,如最小生成树聚类,CLIQUE,DENCLUE,SOM 等等如有兴趣,读者可以自行查找相关资料进行学习。本文旨在提高读者对算法本身的理解,代码实现过程及结果打印能够更好的帮助读者剖析算法,使读者能够更快的入门并掌握基本的聚类算法。

在不久的将来,多智时代一定会彻底走入我们的生活,有兴趣入行未来前沿产业的朋友,可以收藏多智时代,及时获取人工智能、大数据、云计算和物联网的前沿资讯和基础知识,让我们一起携手,引领人工智能的未来!

数据挖掘 数据分类 数据聚类 数据库
0
为您推荐
大数据技术改变城市的运作方式,智慧城市呼之欲出

大数据技术改变城市的运作方式,智慧城市呼

纽奥良虽像大多数城市一样有火灾侦测器安装计划,但直到最近还是要由市民主动申装。纽…...

大数据分析面临生死边缘,未来之路怎么走?

大数据分析面临生死边缘,未来之路怎么走?

大数据分析开始朝着营销落地,尤其像数果智能这类服务于企业的大数据分析供应商,不仅…...

什么是工业大数据,要通过3B和3C来理解?

什么是工业大数据,要通过3B和3C来理解?

核心提示:工业视角的转变如果说前三次工业革命分别从机械化、规模化、标准化、和自动…...

大数据普及为什么说肥了芯片厂商?

大数据普及为什么说肥了芯片厂商?

科技界默默无闻的存在,芯片行业年规模增长到了3520亿美元。半导体给无人驾驶汽车带来…...

大数据技术有哪些,为什么说云计算能力是大数据的根本!

大数据技术有哪些,为什么说云计算能力是大

历史规律告诉我们,任何一次大型技术革命,早期人们总是高估它的影响,会有一轮一轮的…...

个人征信牌照推迟落地,大数据 重新定义个人信用!!

个人征信牌照推迟落地,大数据 重新定义个

为金融学的基础正日益坚实。通过互联网大数据精准记录海量个人行为,进而形成分析结论…...