简介 1.1 简介 1 1.2 距离与相异性度量 6 1.3 聚类方法 11 1.3.1系统聚类法 12 1.3.2 K-means.. 19 1.3.3谱聚类. 24 1.4确定类的数目 30 1.5聚类质量的评价... 38 Previous Next First Last Back Forward 1
简介 1.1 简介 . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 距离与相异性度量 . . . . . . . . . . . . . . . 6 1.3 聚类方法 . . . . . . . . . . . . . . . . . . . . 11 1.3.1 系统聚类法 . . . . . . . . . . . . . . . 12 1.3.2 K-means . . . . . . . . . . . . . . . . . 19 1.3.3 谱聚类 . . . . . . . . . . . . . . . . . . 24 1.4 确定类的数目 . . . . . . . . . . . . . . . . . . 30 1.5 聚类质量的评价 . . . . . . . . . . . . . . . . . 38 Previous Next First Last Back Forward 1
1.1 简介 ·将一组数据依照内在相似性划分为多个类别，使类别内的数据 相似度较大而类别间的数据相似度较小。 ·聚类分析假设数据的特征允许我们可以识别不同的类别，但事 先并不知道数据由几个组构成，因而是一种无监督的学习。 ·同义词：data segmentation(数据挖掘领域)、class discovery (机器学习领域)。 ·应用领域包括经济领域，生物领域，数据挖掘等等 ·例如商店希望刻画顾客群的特征，区分不同的客户类，挖掘有 价值的客户，以制定不同的关系管理方式，提高客户对商业活 动的响应率 Previous Next First Last Back Forward 1
1.1 简介 • 将一组数据依照内在相似性划分为多个类别，使类别内的数据 相似度较大而类别间的数据相似度较小。 • 聚类分析假设数据的特征允许我们可以识别不同的类别，但事 先并不知道数据由几个组构成，因而是一种无监督的学习。 • 同义词：data segmentation（数据挖掘领域）、class discovery （机器学习领域）。 • 应用领域包括经济领域，生物领域，数据挖掘等等 • 例如商店希望刻画顾客群的特征，区分不同的客户类，挖掘有 价值的客户，以制定不同的关系管理方式，提高客户对商业活 动的响应率 Previous Next First Last Back Forward 1
相关的研究领域 一数据挖掘：各种各种复杂形状类的识别，高维聚类等 一统计学：主要集中在基于距离的聚类分析，发现球状类 一机器学习：无指导学习（聚类不依赖预先定义的类） 一其他领域：空间数据技术，生物学，市场营销学 什么是类？ -至今还没有普遍接受的定义：哪些特征决定了一个类。因此， 不同的聚类方法多得到不同的聚类结果。 一直观上：一个类是一组个体（对象、点等），这些个体离这个类 的中心个体比较“近”（在合适的度量下）；不同类的成员之间 的距离“比较远”。 Previous Next First Last Back Forward 2
相关的研究领域 – 数据挖掘: 各种各种复杂形状类的识别，高维聚类等 – 统计学: 主要集中在基于距离的聚类分析，发现球状类 – 机器学习: 无指导学习（聚类不依赖预先定义的类） – 其他领域: 空间数据技术, 生物学, 市场营销学 什么是类? – 至今还没有普遍接受的定义：哪些特征决定了一个类。因此， 不同的聚类方法多得到不同的聚类结果。 – 直观上：一个类是一组个体（对象、点等），这些个体离这个类 的中心个体比较“近”（在合适的度量下）；不同类的成员之间 的距离“比较远”。 Previous Next First Last Back Forward 2
·在2D或3D散点图中，我 00 们很容易的发现数据中的 00d000 o 类。 80 89 ,对发现的类我们经常赋予 我们认为“应该”会存在 的结构或者意义。 。必须注意：“类”可能仅 仅是一个聚类方法的结果 ·一个“类”依赖于如何定 义它以及应用背景 Previous Next First Last Back Forward 3
• 在 2D 或 3D 散点图中，我 们很容易的发现数据中的 类。 • 对发现的类我们经常赋予 我们认为“应该”会存在 的结构或者意义。 • 必须注意：“类”可能仅 仅是一个聚类方法的结果 • 一个“类”依赖于如何定 义它以及应用背景 Previous Next First Last Back Forward 3
聚类与分类(clustering and classification) ·分类： 一有类别标记信息.因此是一种监督学习 一根据训练样本获得分类器，然后把每个数据归结到某个 已知的类，进而也可以预测未来数据的归类。 一分类具有广泛的应用，例如医疗诊断、信用卡的信用分 级、图像模式识别。 ·聚类： 一无类别标记，因此是一种无监督学习 一无训练样本，根据信息相似度原则进行聚类，通过聚类， 人们能够识别密集的和稀疏的区域，因而发现全局的分 布模式，以及数据属性之间的关系 Previous Next First Last Back Forward 4
聚类与分类(clustering and classification) • 分类： – 有类别标记信息, 因此是一种监督学习 – 根据训练样本获得分类器，然后把每个数据归结到某个 已知的类，进而也可以预测未来数据的归类。 – 分类具有广泛的应用，例如医疗诊断、信用卡的信用分 级、图像模式识别。 • 聚类： – 无类别标记, 因此是一种无监督学习 – 无训练样本，根据信息相似度原则进行聚类，通过聚类， 人们能够识别密集的和稀疏的区域，因而发现全局的分 布模式，以及数据属性之间的关系 Previous Next First Last Back Forward 4
·使用可视化工具探测类 一多峰性是不同类存在的标志 -多种可视化技术可以使用：PCA,FA,MDS,Manifest learning,SOM等等. Previous Next First Last Back Forward
• 使用可视化工具探测类 – 多峰性是不同类存在的标志 – 多种可视化技术可以使用: PCA, FA, MDS, Manifest learning, SOM 等等. Previous Next First Last Back Forward 5
1.2 距离与相异性度量 ·聚类就是发现数据中具有“相似性”(similarity)的个体 ·选择合适的“相似性”度量是进行聚类的关键，相似性度量函 数s(,)一般满足 1.0≤s(x,y）≤1 2.s(x,x)=1 3.s(x,y)=s(y,x) ·也可以使用相异性(dissimilarity)来度量数据之间的接近程度. 下面我们以相异性为例.相异性度量和相似性度量之间一般可 以相互转换 ·相异性度量多为某种”距离”度量 ·样本点之间的相异性（距离）函数d(,)一般满足 Previous Next First Last Back Forward 6
1.2 距离与相异性度量 • 聚类就是发现数据中具有“相似性”(similarity) 的个体 • 选择合适的“相似性”度量是进行聚类的关键, 相似性度量函 数 s(·, ·) 一般满足 1. 0 ≤ s(x, y) ≤ 1 2. s(x, x) = 1 3. s(x, y) = s(y, x) • 也可以使用相异性 (dissimilarity) 来度量数据之间的接近程度. 下面我们以相异性为例. 相异性度量和相似性度量之间一般可 以相互转换. • 相异性度量多为某种” 距离” 度量 • 样本点之间的相异性 (距离) 函数 d(·, ·) 一般满足 Previous Next First Last Back Forward 6
1.d(x,y)≥0，等号成立当且仅当x=y 2.d(x,x)=0 metric dissimilarity 3.d(x,y)=d(y,x) 4.d(x,y）≤d(x,z)+d(z,y) 5.d(x,y）≤max{d(x,z),d(z,y)} 如果还满足第5条，则称d为ultrametric dissimilarity 。 样本点之间的相异性记x,y∈P为两个样本点，则距离的选 择非常重要，最好的距离谁则往往要基于经验，知识和运气等得 到 ·一般要根据数据的类型选择合适的相异性（距离）度量准则 一比例尺度（区间尺度）下的样本数据点常用距离准则 Previous Next First Last Back Forward
1. .d(x, y) ≥ 0, 等号成立当且仅当 x = y 2. d(x, x) = 0 3. d(x, y) = d(y, x) 4. d(x, y) ≤ d(x, z) + d(z, y) .. metric dissimilarity 5. d(x, y) ≤ max{d(x, z), d(z, y)} . 如果还满足第 5 条, 则称 d 为ultrametric dissimilarity • 样本点之间的相异性 记 x, y ∈ R p 为两个样本点, 则距离的选 择非常重要, 最好的距离准则往往要基于经验, 知识和运气等得 到. • 一般要根据数据的类型选择合适的相异性 (距离) 度量准则. – 比例尺度 (区间尺度) 下的样本数据点常用距离准则 Previous Next First Last Back Forward 7
Minkowski: dn(x,y） [wm--ylm Manhattan:city-block distance,box-car distance) P dk-空-则=k- Euclidean: d(x,y)=llx-yll2 maximum:(Chebyshev distance) d(x,y)=maxi-yl=llx-ylloo Canberra:(非负量) d(x,y)=】 工k十 k=1 Previous Next First Last Back Forward f
Minkowski: dm(x, y) = [∑p k=1 |xk − yk| m ]1/m = ∥x − y∥m Manhattan: ( city-block distance, box-car distance) d(x, y) = ∑p k=1 |xk − yk| = ∥x − y∥1 Euclidean: d(x, y) = ∥x − y∥2 maximum:(Chebyshev distance) d(x, y) = max |xi − yi| = ∥x − y∥∞ Canberra:(非负量) d(x, y) = ∑p k=1 |xk − yk| xk + yk Previous Next First Last Back Forward 8
-0-1型变量：若x,y的元素均非零即1，则 0 行和 y 的 b a+b 0 d c+d 列和 a+c b+d n=a+b+c+d binary(Jaccard): d(x,y)= b+c←-no0-0 match a+b+c Czekanowski:d(x,y）= b+c 2a+b+c ←-no0-0 natch double 1-1 match 其他见课本表12.1. -属性变量：若x,y为属性变量，各有p和q个不同的类 别，则度量两者之间的相似性常常基于列联表度量性检验 Previous Next First Last Back Forward
– 0-1 型变量: 若 x, y 的元素均非零即 1, 则 ❅ ❅y ❅ x 1 0 行和 1 a b a+b 0 c d c+d 列和 a+c b+d n=a+b+c+d binary(Jaccard) : d(x, y) = b + c a + b + c Czekanowski : d(x, y) = b + c 2a + b + c . ←no 0-0 match ←no 0-0 match double 1-1 match 其他见课本表 12.1. – 属性变量: 若 x, y 为属性变量, 各有 p 和 q 个不同的类 别, 则度量两者之间的相似性常常基于列联表度量性检验 Previous Next First Last Back Forward 9
