1. 数据聚类分析
聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。
从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。
聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用方法的不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。
2. 层次聚类分析
层次聚类分为凝聚式层次聚类和分裂式层次聚类。
凝聚式层次聚类，就是在初始阶段将每一个点都视为一个簇，之后每一次合并两个最接近的簇，当然对于接近程度的定义则需要指定簇的邻近准则。
分裂式层次聚类，就是在初始阶段将所有的点视为一个簇，之后每次分裂出一个簇，直到最后剩下单个点的簇为止。
本文中我们将详细介绍凝聚式层次聚类算法。
对于凝聚式层次聚类，指定簇的邻近准则是非常重要的一个环节，在此我们介绍三种最常用的准则，分别是 MAX, MIN, 组平均。如下图所示：
3.层次聚类算法流程
凝聚式层次聚类算法也是一个迭代的过程，算法流程如下：
每次选最近的两个簇合并，我们将这两个合并后的簇称之为合并簇。
若采用 MAX 准则，选择其他簇与合并簇中离得最远的两个点之间的距离作为簇之间的邻近度。若采用 MIN 准则，取其他簇与合并簇中离得最近的两个点之间的距离作为簇之间的邻近度。若组平均准则，取其他簇与合并簇所有点之间距离的平均值作为簇之间的邻近度。
重复步骤 1 和步骤 2，合并至只剩下一个簇。
算法过程举例，下面我们看一个例子：
下图是一个有五个点的而为坐标系：
下表为这五个点的欧式距离矩阵：
表 1. 欧式距离原始矩阵
P1 | P2 | P3 | P4 | P5 | |
|---|---|---|---|---|---|
P1 | 0 | 0.81 | 1.32 | 1.94 | 1.82 |
P2 | 0.81 | 0 | 1.56 | 2.16 | 1.77 |
P3 | 1.32 | 1.56 | 0 | 0.63 | 0.71 |
P4 | 1.94 | 2.16 | 0.63 | 0 | 0.71 |
P5 | 1.82 | 1.77 | 0.71 | 0.71 | 0 |
根据算法流程，我们先找出距离最近的两个簇，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
P1 | P2 | {P3, P4} | P5 | |
|---|---|---|---|---|
P1 | 0 | 0.81 | 1.32 | 1.82 |
P2 | 0.81 | 0 | 1.56 | 1.77 |
{P3, P4} | 1.32 | 1.56 | 0 | 0.71 |
P5 | 1.82 | 1.77 | 0.71 | 0 |
接着继续找出距离最近的两个簇，{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
P1 | P2 | {P3, P4, P5} | |
|---|---|---|---|
P1 | 0 | 0.81 | 1.32 |
P2 | 0.81 | 0 | 1.56 |
{P3, P4, P5} | 1.32 | 1.56 | 0 |
接着继续找出距离最近的两个簇，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} | 0 | 1.32 |
{P3, P4, P5} | 1.32 | 0 |
最终合并剩下的这两个簇即可获得最终结果，如下图：
MAX，组平均算法流程同理，只是在更新矩阵时将上述计算簇间距离变为簇间两点最大欧式距离，和簇间所有点平均欧式距离即可。
4.层次聚类算法实现
代码语言：javascript复制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 ArrayList<Node> arraylist;
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<Node>();
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.测试数据
给出一组简单的二维测试数据
清单 5. 层次聚类算法测试数据
代码语言：javascript复制0.7,1.2
0.8,2
2,1
2.6,0.8
2.5,1.5
运行结果
清单 6. 层次聚类算法运行结果
代码语言：javascript复制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
