簇的距离是属于不同簇的两个样本间的最近距 离
d(c1,c2)=min{d(o,O)}
完全连接（最远邻）
两个簇的距离隶属于不同簇的距离最远的两 个对象的距离所决定（最远邻的距离）
组平均
两个簇的距离就是隶属不同簇的所有对象的距离 的平均
1
d(c1,c2)
{d(o,O}
n1n2oc1,oc2
对象的数量 和任何启发式搜素算法一样，局部最优是一个问题 对结果的解释具有主观性
算法的步骤
决定k的取值 初始化k个簇中心 通过把对象分配给最近的簇中心来确定N个
对象的簇隶属关系 假设上面所得的隶属关系是正确的，重新计
算k个簇中心 若在最后一次迭代中N个对象无一再改变隶
属关系，则退出，否则再转第3步
在经济研究中，为了研究不同地区城镇居民生活中的收入 和消费情况，往往需要划分不同的类型去研究。
在地质学中，为了研究矿物勘探，需要根据各种矿石的化 学和物理性质和所含化学成分把它们归于不同的矿石类。
在人口学研究中，需要构造人口生育分类模式、人口死亡 分类状况，以此来研究人口的生育和死亡规律。
但历史上这些分类方法多半是人们主要依靠经验作定性分 类，致使许多分类带有主观性和任意性，不能很好地揭示 客观事物内在的本质差别与联系；特别是对于多因素、多 指标的分类问题，定性分类的准确性不好把握。
n
1 p
dita scn(e o1,o2)( oikojk )r
k 1
（5）差异百分率
dtia scn (o e1 ,o2)10 [N 0 um (oib ko ejk )r] n
二元属性对象的相似性
当项不能用有意义的p维测量表示时，项对之间的 比较通常根据某些特征的存在和缺失完成，相似的 项具有更多的共同项
依靠共同的距离度量，聚类过程从寻找距 离最近的簇开始，并把这两个簇合并为一个 簇。
在开始时，让每个对象自成一簇，每个簇都 以选定的距离度量定义
合并后，如何确定新簇之间的距离？？？
单连接（single linkage） 完全连接（complete linkage）
单连接（最近邻）
两个簇的距离由不同簇的两个最近的对象间 的距离决定
引入二元变量来描述是否具有某种特征，若具有该 特征变量值为1，否则变量值为0
个体对的变量得分计算得分矩阵
1 1的个数为a 1 0的个数为b 0 1的个数为c 0 0的个数为d
相似性系数
简单匹配系数SMC Ssm(cxi,xj)(a(b a cb)d)
Jaccard系数
Sjc(xi,xj)aabc
K-means算法
基本思想是初始随机给定K个簇中心，按照最邻近 原则把待分类样本点分到各个簇。然后按平均法重 新计算各个簇的质心，从而确定新的簇心。一直迭 代，直到簇心的移动距离小于某个给定的值
k 1
（1）绝对距离（ q 1）
p
dij (1) X ik X jk k 1
（2）欧氏距离（ q 2）
p
dij (2) (
X ik X jk )2 1/ 2
k 1
（3）切比雪夫距离（ q ）
dij
()
max
1k p
X ik
X jk
(5.2) (5.3) (5.4)
（4）幂距离
当所有项被聚类后，通常用距离表明邻近度 变量通常基于相关系数或关联度量而聚合
距离度量的常见计算方法
令O1和O2表示客观世界中的两个对象，O1和 O2之间的距离（相异性）是一个实数，用 distance(O1,O2)或d(O1，O2)
明考夫斯基距离
p
dij (q) (
X ik X jk )q 1/ q
加权平均 组质心 加权组质心 沃德法
单连接
完全连接
层次聚类的优缺点
优点
可以通过观察树状图来确定正确的簇数目 层次的本质很好地反映了人类对某些领域的直觉 树状图的一个潜在应用时可以用来检测离群点
缺点
有时会表现出无意义的或者不合逻辑的模式
无需事先指定簇的数目 层次本质很好地反映了人类对某些领域认识的直觉 可伸缩性不好：时间复杂性至少为O(n2),n是所有
Rao系数
Src(xi,xj)(ab acd)
实例分析
聚类的基，然后寻找最佳配 对并合并成一个新的簇
自顶向下（分裂）
开始将所有数据看作一个簇，考虑所有可能的 方法，将簇一分为二选择最佳划分，并递归第 在这两个上继续划分
凝聚层次聚类
为了克服定性分类存在的不足，人们把数学方法引入分类 中，形成了数值分类学。
后来随着多元统计分析的发展，从数值分类学中逐渐分离 出了聚类分析方法。
随着计算机技术的不断发展，利用数学方法研究分类不仅 非常必要而且完全可能，因此近年来，聚类分析的理论和 应用得到了迅速的发展。
聚类分析就是分析如何对样品（或变量-在多元统计中，它 就是一个向量）进行量化分类的问题。通常聚类分析分为Q 型聚类和R型聚类。Q型聚类是对样品进行分类处理，R型 聚类是对变量进行分类处理。
什么情况下应该聚类
聚类分析原理
聚类与分类
相似性及其度量
从复杂数据中提取相对简单分组结构的主要 工作是找到一个“紧密度”或相似性度量
“当我们看到它的时候，我们即可领会” 基于特征来测量相似性
产生特征 提炼特征 规范化特征 减少特征
测量相似性
在选择相似性度量时掺杂着大量的主观因素： 变量的本质（离散的、连续的、二值的）或 测量刻度（标称的、顺序的、间隔的、比值 的）及主题知识
数据挖掘聚类分析
引言
“物以类聚，人以群分”。对事物进行分类，是人们认识 事物的出发点，也是人们认识世界的一种重要方法。因此， 分类学已成为人们认识世界的一门基础科学。
在生物、经济、社会、人口等领域的研究中，存在着大量 量化分类研究。例如：在生物学中，为了研究生物的演变， 生物学家需要根据各种生物不同的特征对生物进行分类。
什么是聚类
聚类（clustering）就是将数据分组成多 个簇（cluster），使得同一个簇的对象之 间具有较高的相似度，不同簇的对象相异
早在孩提时代，人就通过不断改进下意识中 的聚类模式来学会如何区分猫和狗、动物和 植物
聚类无所不在
聚类无所不在
聚类无所不在
聚类的应用领域
有贡献的领域