文档介绍：主要步骤
1. 数据预处理，
2. 为衡量数据点间的相似度定义一个距离函数，
3. 聚类或分组，
4. 评估输出。
第一页，共三十三页。
1
(C) Vipin Kumar, Parallel Issues in Data
A
K
Q
J
第八页，共三十三页。
8
(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002
聚类分析原理介绍
分成四组
每组里花色相同
组与组之间花色相异
A
K
Q
J
花色相同的牌为一副
Individual suits
第九页，共三十三页。
9
(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002
聚类分析原理介绍
分成四组
符号相同的牌为一组
A
K
Q
J
符号相同的的牌
Like face cards
第十页，共三十三页。
10
(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002
聚类分析原理介绍
分成两组
颜色相同的牌为一组
A
K
Q
J
颜色相同的配对
Black and red suits
第十一页，共三十三页。
11
(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002
聚类分析原理介绍
这个例子告诉我们，分组的意义在于我们怎么定义并度量“相似性”Similar
因此衍生出一系列度量相似性的算法
第十二页，共三十三页。
12
(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002
聚类分析中的数据类型
1．数据结构
(1) 数据矩阵(Data Matrix)：数据矩阵用p个变量(也称为度量或属性)来表示n个对象，这种数据结构是关系表的形式，或者看成n×p(n个对象×p个变量)的矩阵。
第十三页，共三十三页。
13
(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002
(2)相异度矩阵(Dissimilarity Matrix)：相异度矩阵存储n个对象两两之间的近似性，表现形式是一个n×n维的矩阵。在此，d(i,j)是对象i和对象j之间相异性的量化表示，通常是一个非负的数值，当对象i和j越相似或“接近”时，其值越接近0；两个对象越不同，其值越大，而且d(i,j)=d(j,i)，d(i,i)=0。
第十四页，共三十三页。
14
(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002
相异度计算
区间标度变量是一个粗略线性标度的连续度量。典型的例子包括重量和高度、经度和纬度坐标以及大气温度等。区间标度变量对象间的相异度d(i,j)是基于对象间的距离来计算的，最常用的距离度量方法是欧几里得距离、曼哈坦距离、明考斯基距离。欧几里得距离的定义如下。
这里的和是数据对象i、j的m个属性值。
曼哈坦距离的定义如下。
以上的d(i,j)都满足如下的数学要求。
(1) 非负性：d(i,j)≥0，是一个非负的数值。
(2) 一个对象与自身的距离是0，即d(i,i)=0。
(3) 对称性：d(i,j)=d(j,i)。
(4) 三角不等式：d(i,j)≤d(i,k)+d(k,j)，表示从对象i到对象j的直接距离不会大于途经任何其他对象k的距离。
明考斯基距离是欧