Embed Size (px)
Citation preview
2
上次课的内容:
分类概述
分类与预测
分类算法
决策树分类－ID3算法贝叶斯分类
3
本讲的主要内容:
聚类概念
聚类方法
4
什么是聚类分析？
聚类（簇）：数据对象的集合
在同一个聚类（簇）中的对象彼此相似
不同簇中的对象则相异
聚类分析
将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程
聚类是一种无指导的学习：没有预定义的类编号
聚类分析的数据挖掘功能
作为一个独立的工具来获得数据分布的情况
作为其他算法（如：特征和分类）的预处理步骤
5
聚类分析的典型应用
模式识别
空间数据分析在GIS系统中，对相似区域进行聚类，产生主题地图检测空间聚类，并给出它们在空间数据挖掘中的解释
图像处理
经济学（尤其是市场研究）
万维网对WEB上的文档进行分类对WEB日志的数据进行聚类，以发现相同的用户访问模式
6
聚类分析应用实例
市场营销：帮市场分析人员从客户基本库中发现不同的客户群，从而可以对不同的客户群采用不同的营销策略
土地使用：在地球监测数据库中，发现相同的土地使用区域
保险业：发现汽车保险中索赔率较高的客户群
城市规划：根据房子的类型、价值和地理位置对其进行分组
地震研究：将观测到的震中点沿板块断裂带进行聚类，得出地震高危区
7
什么是好的聚类分析？
一个好的聚类分析方法会产生高质量的聚类
高类内相似度
低类间相似度
作为统计学的一个分支，聚类分析的研究主要是基于距离的聚类；一个高质量的聚类分析结果，将取决于所使用的聚类方法
方法发现隐藏模式的能力
8
数据挖掘对聚类分析的要求 (1)可扩展性(Scalability)大多数来自于机器学习和统计学领域的聚类算法在处理数百万条数据时能表现出高效率
处理不同数据类型的能力数字型；二元类型，分类型/标称型，序数型,比例标度型等等
发现任意形状的能力基于距离的聚类算法往往发现的是球形的聚类，其现实的聚类是任意形状的
用于决定输入参数的领域知识最小化对于高维数据，参数很难决定，聚类的质量也很难控制
处理噪声数据的能力对空缺值、孤立点、数据噪声不敏感
9
数据挖掘对聚类分析的要求 (2)对于输入数据的顺序不敏感
同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果
高维度
高维度的数据往往比较稀松，而且高度倾斜。而一般的聚类算法擅长处理低维的数据，如只涉及2，3维。
基于约束的聚类
找到既满足约束条件，又具有良好聚类特性的数据分组
可解释性和可用性
聚类要和特定的语义解释和应用相联系
10
聚类分析中的数据类型
⎥⎥⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢⎢
⎣
⎡
npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x许多基于内存的聚类
算法采用以下两种数据结构数据矩阵：用p个变量来表示n个对象也叫二模矩阵，行与列代表不同实体
相异度矩阵：存储n个对象两两之间的近似性也叫单模矩阵，行和列代表相同的实体 ⎥
⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢
⎣
⎡
0...)2,()1,(:::
)2,3()
...ndnd
0dd(3,10d(2,1)
0
11
相异度计算
许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。
相异度d(i,j)的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括：
区间标度变量
二元变量
标称型、序数型和比例标度型变量
混合类型的变量
12
区间标度变量区间标度度量是一个粗略线性标度的连续度量，比如重量、高度等选用的度量单位将直接影响聚类分析的结果，因此需要实现度量值的标准化，将原来的值转化为无单位值，给定一个变量f的度量值，可使用以下转化：计算平均的绝对偏差：
其中
计算标准化的度量值(z-score)：
使用平均的绝对偏差往往比使用标准差更具有健壮性
.)...211
nffff xx(xn m +++=
|)|...|||(|121 fnffffff mxmxmxns −++−+−=
f
fifif s
mx z
−=
13
对象间的相似度和相异度(1)对象间的相似度和相异度是基于两个对象间的距离来计算的
Euclidean距离：
i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维数据对象
Manhattan距离：
)||...|||(|),( 22
22
2
11 pp jxixjxixjxixjid −++−+−=
||...||||),(2211 pp jxixjxixjxixjid −++−+−=
14
对象间的相似度和相异度(2)Manhattan距离和Euclidean距离的性质
d(i,j) ≥ 0d(i,i) = 0d(i,j) = d(j,i)d(i,j) ≤ d(i,k) + d(k,j)
Minkowski距离
上式中，q为正整数，如果q=1则表示Manhattan距离，如果q=2则表示Euclidean距离
q q
pp
jxixjxixjxixjid )||...|||(|),(2211
−++−+−=
15
二元变量 (1)一个二元变量只有两种状态：0或1；
e.g. smoker来表示是否吸烟一个对象可以包含多个二元变量。
二元变量的可能性表：
如何计算两个二元变量之间的相似度？
pdbcasumdcdcbaba
sum
++++
01
01Object j
Object i
16
二元变量 (2)对称的 VS. 不对称的二元变量对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g. 性别基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度：
不对称的二元变量中，变量的两个状态的重要性是不同的；e.g. HIV阳性 VS HIV阴性基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相异度
dcbacb jid+++
+=),(
cbacb jid++
+=),(
17
二元变量的相异度——示例例 二元变量之间的相异度 （病人记录表）
Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4Jack M Y N P N N NMary F Y N P N P NJim M Y P N N N N
Name是对象标识gender是对称的二元变量其余属性都是非对称的二元变量如果Y和P（positive阳性）为1，N为0，则：
75.0211
21),(
67.0111
11),(
33.0102
10),(
=++
+=
=++
+=
=++
+=
maryjimd
jimjackd
maryjackd
18
标称变量标称变量是二元变量的推广，它可以具有多于两个的状态值。比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序是不重要的。
计算标称变量所描述的对象（一个对象可以包含多个标称变量）i和j之间的相异度方法一：简单匹配方法
m: 匹配的数目，即对象i和j取值相同的变量的数目 (也可加上权重)
方法二：对M个标称状态中的每个状态创建一个新的二元变量，并用非对称的二元变量来编码标称变量
pmpjid −=),(
红 绿 蓝 黄 取值
0 1 0 0 绿
0 0 1 0 蓝
。。。。。。
19
序数型变量
一个序数型变量可以是离散的或者是连续的
序数型变量的值之间是有顺序关系的，比如：讲师、副教授、正教授。
假设f是描述n个对象的一组序数型变量之一，f的相异度计算如下：
1. 设第i个对象的f值为xif，则用它在值中的序rif代替
2. 将每个变量的值域映射到[0,1]的空间
3. 采用一种距离度量的相异度计算方法计算f的相异度
11−−
=f
ifif M
rz
},...,1{ fif Mr ∈
20
比例标度变量一个比例标度型变量xif是在非线性的标度中取正值的度量，例如指数标度，近似的遵循以下公式：
AeBt or Ae-Bt
计算比例标度型变量描述的对象之间的相异度采用与区间标度变量同样的方法——标度可能被扭曲，效果往往不好
对比例标度型变量进行对数变化之后进行与区间标度变量的相似处理
yif = log(xif)将xif看作连续的序数型数据，将其秩作为区间标度的值来对待
21
混合类型的变量在真实的数据库中，数据对象不是被一种类型的度量所描述，而是被多种类型（即混合类型）的度量所描述，包括：
区间标度度量、对称二元变量，不对称二元变量，标称变量，序数型变量合比例标度变量
计算混合型变量描述的对象之间的相异度
将变量按类型分组，对每种类型的变量进行单独的聚类分析
如果每种聚类分析导出兼容结果，则可行
所有变量一起处理，进行一次聚类分析，可以将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间[0,1]之内
22
主要的聚类方法
聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的，常用的聚类算法包括：
划分方法
层次的方法
基于密度的方法
基于网格的方法
基于模型的方法
实际应用中的聚类算法，往往是上述聚类方法中多种方法的整合
23
划分方法给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k<=n。每个组至少包含一个对象每个对象属于且仅属于一个组
划分准则：同一个聚类中的对象尽可能的接近或相关，不同聚类中的对象尽可能的不同簇的表示
k-means算法由簇的平均值来代表整个簇
k中心点算法由处于簇的中心区域的某个值代表整个簇
24
基于质心的k-means算法
1.选择一个含有随机选择样本的k个簇的初始划
分，计算这些簇的质心。
2.根据欧氏距离把剩余的每个样本分配到距离
它最近的簇质心的一个划分。
3.计算被分配到每个簇的样本的均值向量，作
为新的簇的质心。
4.重复2,3直到k个簇的质心点不再发生变化或
准则函数收敛。
25
基于质心的k-means算法坐标表示5个点｛X1,X2,X3,X4,X5｝作为一个聚类分析的
二维样本：X1＝（0,2），X2＝（0,0），X3＝（1.5,0），
X4＝（5,0），X5＝（5,2）。假设要求的簇的数量k=2。
第1步：由样本的随机分布形成两个簇：
C1＝｛X1,X2,X4｝和C2＝｛X3,X5｝。
这两个簇的质心M1和M2是：
M1＝｛(0+0+5)/3,(2+0+0)/3｝＝｛1.66，0.66｝；
M2＝｛（1.5+5）/2，（0+2）/2｝＝｛3.25，1.00｝；
26
基于质心的k-means算法样本初始随机分布之后，方差是：
e12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-
0.66)2]+[(5-1.66)2+(0-0.66)2]=19.36；
e22=8.12；
总体平方误差是：E2＝e12+e2
2＝19.36+8.12＝
27.48（公式）
2
1|| i
iCX
k
ie mXJ −= ∑∑
∈=
27
基于质心的k-means算法第2步：取距离其中一个质心（M1或M2）最小最小的
离分配所有样本，簇内样本的重新分布如下：
d(M1,X1)=(1.662+1.342)1/2=2.14
d(M2,X1)=3.40 ==>X1∈C1；
d(M1,X2)=1.79 和 d(M2,X2)=3.40 ==>X2∈C1
d(M1,X3)=0.83 和 d(M2,X3)=2.01 ==>X3∈C1
d(M1,X4)=3.41 和 d(M2,X4)=2.01 ==>X4∈C2
d(M1,X5)=3.60 和 d(M2,X5)=2.01 ==>X5∈C2
新簇C1＝｛X1,X2,X3｝和C2＝｛X4,X5｝
28
基于质心的k-means算法第3步：计算新的质心新的质心：
M1＝｛0.5，0.67｝； M2＝｛5.0，1.0｝。
相应的方差及总体平方误差分别是：
e12＝4.17； e2
2＝2.00； E2＝6.17；
可以看出第一次迭代后，总体误差显著减小
（从值27.48到6.17）。在这个简单的例子中，
第一次迭代同时也是最后一次迭代，因为如果
继续分析新中心和样本间的距离，样本将会全
部分给同样的簇，不将重新分配，算法停止。
29
层次的方法
对给定数据对象集合进行层次分解
自底向上方法（凝聚）：开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件。
自顶向下方法（分裂）：开始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，直到最终每个对象在一个单独的簇中，或达到一个终止条件
30
凝聚层次聚类
1.初始化：计算包含每对样本间距离（如欧氏距离）的相似矩阵，把每个样本作为一个簇；
2.选择：使用相似矩阵查找最相似的两个簇；
3.更新：将两个簇合并为一个簇，簇的个数通过合并被更新；同时更新相似矩阵，将两个簇的两行（两列）距离用1行（1列）距离替换反映合并操作。
4.重复：执行n-1次步骤2和步骤3；
5.结束：当所有样本都合并成一个簇或满足指定的簇的数目时，整个过程结束。
31
凝聚层次聚类
一．单连接算法单连接算法(single-linkage)（最近邻(Nearest Neighbor)）：
基本思想：两个簇之间的距离用从两个簇中抽取的每对样本的最小距离：
作为距离度量，一旦最近的两个类的距离超过某个任意给定的阈值，算法就自动结束。
二．全连接算法全连接算法
三．平均连接算法平均连接算法
),(min ji CCD
32
单连接算法先将五个样本都分别看成是一个簇，最靠近的两个簇是3和4，因为他们具有最小的簇间距离D（3，4）=5.0。
第一步：合并簇3和4，得到新簇集合1,2,（34）,5
33
单连接算法更新距离矩阵：
D(1,(34)) = min(D(1,3),D(1,4)) = min(20.6, 22.4) = 20.6;
D(2,(34)) = min(D(2,3),D(2,4)) = min(14.1, 11.2) = 11.2;
D(5,(34)) = min(D(3,5),D(4,5)) = min(25.0, 25.5) = 25.0.
原有簇1,2,5间的距离不变，修改后的距离矩阵如图所示，在四个簇1,2,(34),5中，最靠近的两个簇是1和5，它们具有最小簇间距离D（1,5）＝7.07。
34
单连接算法
35
单连接算法
单单连接树连接树
36
改进的层次聚类BIRCH是一个综合的层次聚类方法，它引入了两
个概念：聚类特征和聚类特征树（CF树）
CURE方法采用了一种新颖的层次聚类算法，该
算法选择基于质心和基于代表对象方法之间的
中间策略。
ROCK方法是一个可选的凝聚的层次聚类算法，
适用于分类属性。
Chameleon（变色龙）方法是一个在层次聚类中
采用动态模型的层次聚类算法
37
基于密度的方法
基于距离的聚类方法的缺点：只能发现球状的簇，难以发现任意形状的簇。
基于密度的聚类：只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类。优点：可以过滤掉“噪声”和“孤立点”，发现任意形状的簇。
38
基于密度的方法
基于密度聚类的相关定义：
a.给定对象半径ε内的区域称为该对象的ε－邻域。
b.如果一个对象的ε－邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。
c.给定一个对象集合D，如果p是在q的ε－邻域内，而q是一个核心对象，则称对象p从对象q出发是直接密度可达的。
39
基于密度的方法
d.如果存在一个对象链p1,p2,…,pn，p1＝q，pn＝p，对pi∈D（1<=i<=n），pi+1是从pi关于ε和MinPts直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的。
e.如果对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于ε和MinPts密度相连的。
40
基于密度的方法一．基于高密度连接区域的聚类方法：DBSCAN
二．通过对象排序识别聚类结构的聚类方法：OPTICS
a.核心距离：一个对象p的核心距离是使得p成为核心对象的最小的ε。如果p不是核心对象，p的核心距离没有定义；
b.可达距离：一个对象q关于另一个对象p的可达距离是p的核心距离和p与q的欧几里德距离之间的较大值。如果p不是一个核心对象，p和q之间的可达距离没有定义。
三.基于密度分布函数的聚类方法：DENCLUE
41
基于网格的方法
把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类都在这个网格结构上进行。
优点：处理数度快（因为处理时间独立于数据对象数目，只与量化空间中每一维的单元数目有关）
42
基于模型的方法
为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。
一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类
这种方法同时也用于自动的决定数据集中聚类的数目
通过统计学的方法，考虑噪声和孤立点，从而产生健壮的聚类方法
43
补充内容：孤立点挖掘
什么是孤立点？一个数据集与其他数据有着显著区别的数据对象的集合例如：运动员：Michael Jordon, 舒马赫，布勃卡
孤立点产生原因度量或执行错误（年龄：-999）数据变异的结果
孤立点挖掘给定一个n个数据对象的集合，以及预期的孤立点数目k，发现与剩余的数据有着显著差异的头k个数据对象
应用信用卡欺诈检测移动电话欺诈检测客户划分医疗分析（异常）
44
基于统计的孤立点检测
统计的方法对于给定的数据集合假定了一个分布或概率模型（例如正态分布）
使用依赖于以下参数的不一致性检验（discordancytests）数据分布
分布参数（e.g. 均值或方差）预期的孤立点数
缺点
绝大多数检验是针对单个属性的，而数据挖掘要求在多维空间中发现孤立点
大部分情况下，数据分布可能是未知的
45
基于距离的孤立点检测
为了解决统计学方法带来的一些限制，引入了基于距离的孤立点检测在不知道数据分布的情况下对数据进行多维分析
基于距离的孤立点：即DB(p,d)，如果数据集合S中的对象至少有p部分与对象o的距离大于d，则对象o就是DB(p,d)。挖掘基于距离的孤立点的高效算法：基于索引的算法
嵌套－循环算法
基于单元的算法
46
基于偏离的孤立点检测
通过检查一组对象的主要特征来确立孤立点
跟主要特征的描述相“偏离”的对象被认为是孤立点
两种基于偏离的孤立点探测技术序列异常技术
模仿人类从一系列推测类似的对象中识别异常对象的方式
OLAP数据立方体技术在大规模的多维数据中采用数据立方体来确定异常区域。如果一个立方体的单元值显著的不同于根据统计模型得到的期望值，则改单元值被认为是一个异常，并用可视化技术表示。
