聚类分析综述

– 类间具有较低的相似度
• 聚类结果的质量依赖于相似度评价方法以及 它们的应用； • 聚类结果的质量也取决于它发现隐藏模式的 能力。
聚类分析在数据挖掘中的应用
• 作为一个独立的分析工具，用于了解数据的分布情况,观察每个簇 的特点, 对特定的某些簇做进一步的分析. • 作为其它算法的一个数据预处理步骤,这些算法再在生成的簇上进 行处理. • 应用领域(举例): 市场销售:帮助市场人员发现客户中的不同群体，然后用这些 知识来开展 一个目标明确的市场计划； 土地使用: 在一个陆地观察数据库中标识那些土地使用相似的 地区； 保险: 对购买了汽车保险的客户，标识那些有较高平均赔偿成 本的客户； 城市规划: 根据类型、价格、地理位置等来划分不同类型的住 宅； 地震研究: 根据地质断层的特点把已观察到的地震中心分成不 同的类。
• 方法1:简单匹配方法
m d (i, j) p p – 其中m表示对象i和对象j中取同样状态的标称变量个
数（匹配数）；p为所有的标称变量个数。
– 为增强的作用，可以给它赋予一定的权值；对于拥 有许多状态的标称变量，可以相应赋予更大的权值。
标称变量（2）
• 方法2:通过为标称变量的每个状态创建一个新 二元变量，能够将标称变量表示为非对称的二 元变量。对于具有给定状态的一个对象，代表 一个状态的二元变量置为1；而其它的二元变量 置为0。
01 0.33 2 01 11 d ( jack, jim ) 0.67 111 1 2 d ( jim , mary) 0.75 11 2 d ( jack, mary)
标称变量（1）
• 标称变量是二元变量的一个推广。标称变量可以对两个 以上的状态进行描述。例如：地图颜色map_color 变 量就是一个标称变量；它可以表示五种状态，即红、绿、 篮、粉红和黄色。
i = (xi1, xi2, …, xip) 和 j = (xj1, xj2, …, xjp) 是两 个n维的数据,其中q为一个正整数； • 如果 q = 1, d 是Manhattan 距离
d (i, j) | x x | | x x | ... | x x | i1 j1 i2 j2 ip jp
聚类分析：机器学习观点
• 从机器学习的角度讲，簇相当于隐藏模 式。聚类是搜索簇的无监督学习过程。 与分类不同，无监督学习不依赖预先定 义的类或带类标记的训练实例，需要由 聚类学习算法自动确定标记，而分类学 习的实例或数据对象有类别标记。聚类 是观察式学习，而不是示例式的学习。
聚类分析：其它观点
• 从实际应用的角度看，聚类分析是数据挖掘的 主要任务之一。 • 就数据挖掘功能而言，聚类能够作为一个独立 的工具获得数据的分布状况，观察每一簇数据 的特征，集中对特定的聚簇集合作进一步地分 析。 • 聚类分析还可以作为其他数据挖掘任务（如分 类、关联规则）的预处理步骤。 • 数据挖掘领域主要研究面向大型数据库、数据 仓库的高效实用的聚类分析算法。
聚类分析
提纲
• • • • • • • • 聚类分析简介 聚类分析中的数据类型 划分方法 层次方法 基于密度的方法 基于网格的方法 基于模型的聚类方法 孤立点分析
聚类（Clustering）
• 聚类:是一个数据集 –聚类（Clustering）是对物理的或抽象的对 象集合分组的过程； –将数据集划分为若干组（class）或簇 （cluster）的过程，并使得同一个组内的数 据对象具有较高的相似度； –而不同组中的数据对象是不相似的。 • 聚类生成的组称为簇（Cluster） –簇是数据对象的集合。簇内部的任意两个对 象之间具有较高的相似度，而属于不同簇的 两个对象间具有较高的相异度。相异度可以 根据描述对象的属性值计算，对象间的距离 是最常采用的度量指标。
• 属性的组合。
区间标度变量
• 数据标准化（数据预处理） – 计算平均的绝对偏差:
sf 1 n (| x1 f m f | | x2 f m f | ... | xnf m f |) 1 (x1 f x2 f ... xnf ). mf n
– 计算标准化的度量值 (z-score)
cij cos ij
k 1 n 2 n ki k 1 k 1

n
xki xkj
2 xkj
x
2 2 dij 1 Cij
25
(1) 所选择的亲疏测度指标在实际应用中应有明确的意
选择原则
义。如在经济变量分析中，
(2) 亲疏测度指标的选择要综合考虑已对样本观测数据 实施了的变换方法和将要采用的聚类分析方法。 (3) 如在标准化变换之下，夹角余弦实际上就是相关系 数；又如若在进行聚类分析之前已经对变量的相关性
划分方法
• 给定一个包含n个对象或数据行，划分方法将数据集 划分为k个子集（划分）。其中每个子集均代表一个 聚类（k）。也就是说将数据分为k组，这些组满 足以下要求：
– 每组至少应包含一个对象； – 每个对象必须只能属于某一组。需要注意的是后一个要求 在一些模糊划分方法中可以放宽。
作了处理，则通常就可采用欧氏距离，而不必选用斜
交空间距离。 (4) 所选择的亲疏测度指标，还须和所选用的聚类分析 方法一致。如聚类方法若选用离差平方和法，则距离 只能选用欧氏距离。
2
提纲
• • • • • • • 聚类分析简介 聚类分析中的数据类型 划分方法 层次方法 基于密度的方法 基于网格的方法 基于模型的聚类方法
• 其中d (i, j)表示对象i与j的相异度，它是一个非负的数 值。当对象i和j越相似或“接近”时，d (i, j)值越接近 0；而对象i和j越不相同或相距“越远”时，d (i, j)值 越大。显然，d (i, j)=d (j, i)，d (i, i)=0。相异度矩阵 是对象-对象结构的一种数据表达方式。
• 称为数据矩阵。数据矩阵是对象-变量结构的数 据表达方式。
相异度矩阵（Dissimilarity Matrix）
• 按n个对象两两间的相异度构建n阶矩阵（因为相异度 矩阵是对称的，只需写出上三角或下三角即可）：
0 d (2, 1) d (3, 1) d (n, 1) 0 d (3, 2) 0 d (n, 2) 0
2 p
2 [ k ( x x ) ][ ( x x ) ] ik i jk j 1 k 1
2
（2）夹角余弦
夹角余弦时从向量集合的角度所定义的一种 测度变量之间亲疏程度的相似系数。设在n维 空间的向量 x x , x , , x xi x1i , x2i ,, xni j 1j 2j nj
序数型变量
比例标度型变量
• 比例标度型变量:一个比例数值变量就在非线性尺度上 所获得的正测量值，如：指数比例，可以用以下公式 近似描述： AeBt or Ae-Bt
• 方法:
– 将比例数值变量当作间隔数值变量来进行计算处理； 但这不是一个好方法，因为比例尺度时非线性的。 –利用对数转换方法 yif = log(xif) –最后就是将xif当作连续顺序数据，即将其顺序值作 为间隔数值来进行相应的计算处理。
• 一个序数型变量可以是离散的也可以是连续的; • 序号是重要的, 例如., rank • 处理方法与间隔数值变量的处理方法类似 • -scaled – 用xif的序数值替换 xif，rif { 1 ,...,M f } –由于每个顺序变量的状态个数可能不同。因此 有必要将每个顺序变量的取值范围映射到[0,1] 区间，以便使每个变量的权值相同。 r 1 if zif M f 1 –用有关间隔数值变量的任一个距离计算公式， 来计算用顺序变量描述的对象间距离；
xif m f zif sf
• 使用平均的绝对偏差比使用标准差更加健壮：异常数
据的Z－ 分值不会变得太小，从而使得异常数据仍是 可识别的。
Βιβλιοθήκη Baidu
区间标度的相似度(1)
• 由间隔数值所描述对象之间的差异（或相似）程度 可以通过计算相应两个对象之间距离来确定； • Minkowski 举例:
d (i, j) q (| x x |q | x x |q ... | x x |q ) i1 j1 i2 j2 ip jp
• 可以使用权重函数
二元变量
• 二元属性的可能性表
Object j
1
Object i
0 b d
sum a b cd p
1 0
a c
sum a c b d
• 简单匹配相关系数(不变相似性，如果二元变量是对称的): bc d (i, j) a bc d • Jaccard相关系数 (非变相似性，如果二元变量是非对称 的):
if f
相似系数的算法 （1）相似系数
x (x 和 , x j 2 ,, x jp ) 设 j j1 x i xi1 , xi 2 , , xip 是第 i 和 j 个样品的观测值，则二者之间的相似 测度为:
( xik
p
其中
ij
k 1 p
xi )( x jk x j )
聚类分析处理的数据类型
• 区间标度（ Interval-scaled variables ）属性； • 二元(Binary variables)属性； • 标称(Nominal variables)属性; • 序数型(Ordinal, and ratio variables)属性; • 比例(Ratio variables)属性;
聚类分析的一些典型要求
• 可扩展性 • 处理不同类型属性的能力 • 发现任意形状的聚类 • 需要（由用户）决定的输入参数最少 • 处理噪声数据的能力 • 对输入记录顺序不敏感
• 高维问题
• 基于约束的聚类 • 可解释性和可用
什么是好的聚类方法?
• 一个好的聚类方法可以产生高质量的聚类： – 类的内部具有较高的相似度
d (i, j) bc a bc
二元变量的相似度
• 示例
Name Jack Mary Jim Gender M F M Fever Y Y Y Cough N N P Test-1 P P N Test-2 N N N Test-3 N P N Test-4 N N N
– gender 是对称属性 – 其余属性是非对称属性 – 可将其Y和P设为1；N设为0。
提纲
• • • • • • • 聚类分析简介 聚类分析中的数据类型 划分方法 层次方法 基于密度的方法 基于网格的方法 基于模型的聚类方法
数据矩阵（Data Matrix）
• 设有n个对象，可用p个变量（属性）描述每个 对象，则np矩阵
x11 x12 x1 p x21 x22 x2 p x x x np n1 n 2
区间标度的相似度(2)
• 如果 q = 2, d是 Euclidean 距离:
d (i, j) (| x x |2 | x x |2 ... | x x |2 ) i1 j1 i2 j2 ip jp
– 属性
• d(i,j) 0 • d(i,i) = 0 • d(i,j) = d(j,i) • d(i,j) d(i,k) + d(k,j)
混合类型变量
• 一个数据库经常包含上述六种数据类型 • 一种将每种类型的变量分别组织在一起，并根据每种 类型的变量完成相应的聚类分析。
(f ) (f ) p d d (i, j ) f p1 ij ( f ij f 1ij )
– f 是二元变量或标称标量: dij(f) = 0 如果xif = xjf ,否则 dij(f) = 1 – f 是间隔数值变量使用:间隔数值变量距离计算 – f 是序数型变量和比例标度型变量 • 则计算顺序rif 并且 • 并将zif当作间隔数值变量来进行计算处理。 zif r 1 M 1