聚类分析
什么是聚类分析？
? 聚类（簇）：数据对象的集合
? 在同一个聚类（簇）中的对象彼此相似
? 不同簇中的对象则相异
? 聚类分析
? 将物理或抽象对象的集合分组成为由类似的对象组成的多个
类的过程
? 聚类是一种无指导的学习：没有预定义的类编号
? 聚类分析的数据挖掘功能
? 作为一个独立的工具来获得数据分布的情况
? 作为其他算法（如：特征和分类）的预处理步骤
聚类分析的典型应用
? 模式识别
? 空间数据分析
? 在 GIS系统中，对相似区域进行聚类，产生主题地图
? 检测空间聚类，并给出它们在空间数据挖掘中的解释
? 图像处理
? 经济学（尤其是市场研究）
? 万维网
? 对 WEB上的文档进行分类
? 对 WEB日志的数据进行聚类，以发现相同的用户访问模式
聚类分析应用实例
? 市场营销：帮市场分析人员从客户基本库中发现不同
的客户群，从而可以对不同的客户群采用不同的营销
策略
? 土地使用：在地球监测数据库中，发现相同的土地使
用区域
? 保险业：发现汽车保险中索赔率较高的客户群
? 城市规划：根据房子的类型、价值和地理位置对其进
行分组
? 地震研究：将观测到的震中点沿板块断裂带进行聚类，
得出地震高危区
什么是好的聚类分析？
? 一个好的聚类分析方法会产生高质量的聚类
? 高类内相似度
? 低类间相似度
? 作为统计学的一个分支，聚类分析的研究主要
是基于距离的聚类；一个高质量的聚类分析结
果，将取决于所使用的聚类方法
? 聚类方法的所使用的相似性度量和方法的实施
? 方法发现隐藏模式的能力
数据挖掘对聚类分析的要求 (1)
? 可扩展性 (Scalability)
? 大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率
? 处理不同数据类型的能力
? 数字型；二元类型，分类型 /标称型，序数型,比例标度型等
等
? 发现任意形状的能力
? 基于距离的聚类算法往往发现的是球形的聚类，其实现实的
聚类是任意形状的
? 用于决定输入参数的领域知识最小化
? 对于高维数据，参数很难决定，聚类的质量也很难控制
? 处理噪声数据的能力
? 对空缺值、孤立点、数据噪声不敏感
数据挖掘对聚类分析的要求 (2)
? 对于输入数据的顺序不敏感
? 同一个数据集合，以不同的次序提交给同一个算法，
应该产生相似的结果
? 高维度
? 高维度的数据往往比较稀松，而且高度倾斜
? 基于约束的聚类
? 找到既满足约束条件，又具有良好聚类特性的数据
分组
? 可解释性和可用性
? 聚类要和特定的语义解释和应用相联系
聚类分析中的数据类型
? 许多基于内存的聚类
算法采用以下两种数
据结构
? 数据矩阵：用 p个变量
来表示 n个对象
? 也叫二模矩阵，行与列
代表不同实体
? 相异度矩阵：存储 n个
对象两两之间的近似性
? 也叫单模矩阵，行和列
代表相同的实体
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
np
x.,,
nf
x.,,
n1
x
.,,.,,.,,.,,.,,
ip
x.,,
if
x.,,
i1
x
.,,.,,.,,.,,.,,
1p
x.,,
1f
x.,,
11
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0...)2,()1,(
:::
)2,3()
...ndnd
0dd ( 3,1
0d ( 2,1 )
0
相异度计算
? 许多聚类算法都是以相异度矩阵为基础，如果
数据是用数据矩阵形式表示，则往往要将其先
转化为相异度矩阵。
? 相异度 d(i,j)的具体计算会因所使用的数据类型
不同而不同，常用的数据类型包括,
? 区间标度变量
? 二元变量
? 标称型、序数型和比例标度型变量
? 混合类型的变量
区间标度变量
? 区间标度度量是一个粗略线性标度的连续度量，比如重量、高度
等
? 选用的度量单位将直接影响聚类分析的结果，因此需要实现 度量值的标准化,将原来的值转化为无单位的值，给定一个变量 f的度
量值，可使用以下转化,
? 计算平均的绝对偏差
? 其中
? 计算标准化的度量值 (z-score)
? 使用平均的绝对偏差往往比使用标准差更具有健壮性
.)...211 nffff xx(xn m ????
|)|...|||(|1 21 fnffffff mxmxmxns ???????
f
fif
if s
mx z ??
对象间的相似度和相异度 (1)
? 对象间的相似度和相异
度是基于两个对象间的
距离来计算的
? Euclidean距离
? i=(xi1,xi2,…,x ip)和
j=(xj1,xj2,…,x jp)是两个 p维
数据对象
? Manhattan距离
)||.,,|||(|),( 2222211 pp jxixjxixjxixjid ???????
||.,,||||),( 2211 pp jxixjxixjxixjid ???????
对象间的相似度和相异度 (2)
? Manhattan距离和 Euclidean距离的性质
? d(i,j) ? 0
? d(i,i) = 0
? d(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
qq jxixjxixjxixjid )||...|||(|),(
2211 ???????
二元变量 (1)
? 一个二元变量只有两种状态,0或 1；
? e.g,smoker来表示是否吸烟
? 一个对象可以包含多个二元变量。
? 二元变量的可能性表,
? 如何计算两个二元变量之间的相似度？
pdbcasu m
dcdc
baba
su m
??
?
?
0
1
01
Object i
Object j
二元变量 (2)
? 对称的 VS,不对称的 二元变量
? 对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g,性别
? 基于对称的二元变量的相似度称为恒定的相似度，可以使用
简单匹配系数评估它们的相异度,
? 不对称的二元变量中，变量的两个状态的重要性是不同的；e.g,HIV阳性 VS HIV阴性
? 基于不对称的二元变量的相似度称为非恒定的相似度，可以
使用 Jaccard系数评估它们的相异度
dcba cb jid ??? ??),(
cba cb jid ?? ??),(
二元变量的相异度 —— 示例
N am e G end er Fev er Coug h Tes t-1 Tes t-2 Tes t-3 Tes t-4
Jac k M Y N P N N N
Mar y F Y N P N P N
Ji m M Y P N N N N
P228 例 8.1 二元变量之间的相异度 （病人记录表）
Name是对象标识
gender是对称的二元变量
其余属性都是非对称的二元变量
如过 Y和 P（ positive阳性）为 1,N为 0，则,
75.0
211
21
),(
67.0
111
11
),(
33.0
102
10
),(
?
??
?
?
?
??
?
?
?
??
?
?
m a r yjimd
jimja c kd
m a r yja c kd
标称变量
? 标称变量是二元变量的推广，它可以具有多于两个的状态值。
比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序
是不重要的。
? 计算标称变量所描述的对象（一个对象可以包含多个标称变量）
i和 j之间的相异度
? 方法一：简单匹配方法
? m,匹配的数目，即对象 i和 j取值相同的变量的数目 (也可加上权重 )
? 方法二：对 M个标称状态中的每个状态创建一个新的二元变量，并
用非对称的二元变量来编码标称变量
p mpjid ??),(
红 绿 蓝 黄 取值
0 1 0 0 绿
0 0 1 0 蓝
。。。。。。
序数型变量
? 一个序数型变量可以是离散的或者是连续的
? 序数型变量的值之间是有顺序关系的，比如：
讲师、副教授、正教授。
? 假设 f是描述 n个对象的一组序数型变量之一,f
的相异度计算如下,
? 1,设的 i个对象的 f值为 xif，则用它在值中的序 rif代
替
? 2,将每个变量的值域映射到 [0,1]的空间
? 3,采用区间标度变量的相异度计算方法计算 f的
相异度
1
1
?
??
f
if
if M
rz
},...,1{ fif Mr ?
比例标度变量
? 一个比例标度型变量 xif是在非线性的标度中所取的正
的度量值，例如指数标度，近似的遵循以下公式,
AeBt or Ae-Bt
? 计算比例标度型变量描述的对象之间的相异度
? 采用与区间标度变量同样的方法 —— 标度可能被扭曲，效果
往往不好
? 对比例标度型变量进行对数变化之后进行与区间标度变量的
相似处理
yif = log(xif)
? 将 xif看作连续的序数型数据，将其秩作为区间标度的值来对
待
混合类型的变量
? 在真实的数据库中，数据对象不是被一种类型的度量
所描述，而是被多种类型（即混合类型）的度量所描
述，包括,
? 区间标度度量、对称二元变量，不对称二元变量，标称变量，
序数型变量合比例标度变量
? 计算混合型变量描述的对象之间的相异度
? 将变量按类型分组，对每种类型的变量进行单独的聚类分析
? 在每种聚类分析导出相似结果的情况下可行
? 所有变量一起处理，进行一次聚类分析，可以将不同类型的
变量组合在单个相异度矩阵中，把所有有意义的变量转换到
共同的值域区间 [0,1]之内
主要的聚类方法
? 聚类分析算法种类繁多，具体的算法选择取决于数据
类型，聚类的应用和目的，常用的聚类算法包括,
? 划分方法
? 层次的方法
? 基于密度的方法
? 基于网格的方法
? 基于模型的方法
? 实际应用中的聚类算法，往往是上述聚类方法中多种
方法的整合
划分方法
? 给定一个 n个对象或元组的数据库，一个划分方法构
建数据的 k个划分，每个划分表示一个簇，并且 k<=n。
? 每个组至少包含一个对象
? 每个对象属于且仅属于一个组
? 划分准则：同一个聚类中的对象尽可能的接近或相关,不同聚类中的对象尽可能的原理或不同
? 簇的表示
? k-平均算法
? 由簇的平均值来代表整个簇
? k中心点算法
? 由处于簇的中心区域的某个值代表整个簇
层次的方法
? 对给定数据对象集合进行层次分解
? 自底向上方法（凝聚）：开始将每个对象作为单独
的一个组，然后相继的合并相近的对象或组，直到
所有的组合并为一个，或者达到一个终止条件。
? 自顶向下方法（分裂）：开始将所有的对象置于一
个簇中，在迭代的每一步，一个簇被分裂为多个更
小的簇，直到最终每个对象在一个单独的簇中，或
达到一个终止条件
? 缺点：合并或分裂的步骤不能被撤销
基于密度的方法
? 基于距离的聚类方法的缺点：只能发现球状的
簇，难以发现任意形状的簇。
? 基于密度的据类：只要临近区域的密度（对象
或数据点的数目）超过某个临界值，就继续聚
类。
? 优点：可以过滤掉“噪声”和“孤立点”，发现任
意形状的簇。
基于网格的方法
? 把对象空间量化为有限数目的单元，形成一个
网格结构。所有的聚类都在这个网格结构上进
行。
? 优点：处理数度快（因为处理时间独立于数据对象
数目，只与量化空间中每一维的单元数目有关）
基于模型的方法
? 为每个簇假定一个模型，寻找数据对给定模型
的最佳拟合。
? 一个基于模型的算法可能通过构建反映数据点空间
分布的密度函数来定位聚类
? 这种方法同时也用于自动的决定数据集中聚类的数
目
? 通过统计学的方法，考虑噪声和孤立点，从而产生健壮的
聚类方法
孤立点挖掘
? 什么是孤立点？
? 一个数据集与其他数据有着显著区别的数据对象的集合
? 例如：运动员,Michael Jordon,舒马赫，布勃卡
? 孤立点产生原因
? 度量或执行错误（年龄,-999）
? 数据变异的结果
? 孤立点挖掘
? 给定一个 n个数据对象的集合，以及预期的孤立点数目 k，发现与
剩余的数据有着显著差异的头 k个数据对象
? 应用
? 信用卡欺诈检测
? 移动电话欺诈检测
? 客户划分
? 医疗分析（异常）
基于统计的孤立点检测
? 统计的方法对于给定的数据集合假定了一个分布或概
率模型（例如正态分布）
? 使用依赖于以下参数的不一致性检验（ discordancy
tests）
? 数据分布
? 分布参数（ e.g,均值或方差）
? 预期的孤立点数
? 缺点
? 绝大多数检验是针对单个属性的，而数据挖掘要求在多维空
间中发现孤立点
? 大部分情况下，数据分布可能是未知的
基于距离的孤立点检测
? 为了解决统计学方法带来的一些限制，引入了
基于距离的孤立点检测
? 在不知道数据分布的情况下对数据进行多维分析
? 基于距离的孤立点：即 DB(p,d)，如果数据集
合 S中的对象至少有 p部分与对象 o的距离大于
d，则对象 o就是 DB(p,d)。
? 挖掘基于距离的孤立点的高效算法,
? 基于索引的算法
? 嵌套－循环算法
? 基于单元的算法
基于偏离的孤立点检测
? 通过检查一组对象的主要特征来确立孤立点
? 跟主要特征的描述相“偏离”的对象被认为是
孤立点
? 两种基于偏离的孤立点探测技术
? 序列异常技术
? 模仿人类从一系列推测类似的对象中识别异常对象的方式
? OLAP数据立方体技术
? 在大规模的多维数据中采用数据立方体来确定异常区域。
如果一个立方体的单元值显著的不同于根据统计模型得到
的期望值，则改单元值被认为是一个异常，并用可视化技
术表示。
什么是聚类分析？
? 聚类（簇）：数据对象的集合
? 在同一个聚类（簇）中的对象彼此相似
? 不同簇中的对象则相异
? 聚类分析
? 将物理或抽象对象的集合分组成为由类似的对象组成的多个
类的过程
? 聚类是一种无指导的学习：没有预定义的类编号
? 聚类分析的数据挖掘功能
? 作为一个独立的工具来获得数据分布的情况
? 作为其他算法（如：特征和分类）的预处理步骤
聚类分析的典型应用
? 模式识别
? 空间数据分析
? 在 GIS系统中，对相似区域进行聚类，产生主题地图
? 检测空间聚类，并给出它们在空间数据挖掘中的解释
? 图像处理
? 经济学（尤其是市场研究）
? 万维网
? 对 WEB上的文档进行分类
? 对 WEB日志的数据进行聚类，以发现相同的用户访问模式
聚类分析应用实例
? 市场营销：帮市场分析人员从客户基本库中发现不同
的客户群，从而可以对不同的客户群采用不同的营销
策略
? 土地使用：在地球监测数据库中，发现相同的土地使
用区域
? 保险业：发现汽车保险中索赔率较高的客户群
? 城市规划：根据房子的类型、价值和地理位置对其进
行分组
? 地震研究：将观测到的震中点沿板块断裂带进行聚类，
得出地震高危区
什么是好的聚类分析？
? 一个好的聚类分析方法会产生高质量的聚类
? 高类内相似度
? 低类间相似度
? 作为统计学的一个分支，聚类分析的研究主要
是基于距离的聚类；一个高质量的聚类分析结
果，将取决于所使用的聚类方法
? 聚类方法的所使用的相似性度量和方法的实施
? 方法发现隐藏模式的能力
数据挖掘对聚类分析的要求 (1)
? 可扩展性 (Scalability)
? 大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率
? 处理不同数据类型的能力
? 数字型；二元类型，分类型 /标称型，序数型,比例标度型等
等
? 发现任意形状的能力
? 基于距离的聚类算法往往发现的是球形的聚类，其实现实的
聚类是任意形状的
? 用于决定输入参数的领域知识最小化
? 对于高维数据，参数很难决定，聚类的质量也很难控制
? 处理噪声数据的能力
? 对空缺值、孤立点、数据噪声不敏感
数据挖掘对聚类分析的要求 (2)
? 对于输入数据的顺序不敏感
? 同一个数据集合，以不同的次序提交给同一个算法，
应该产生相似的结果
? 高维度
? 高维度的数据往往比较稀松，而且高度倾斜
? 基于约束的聚类
? 找到既满足约束条件，又具有良好聚类特性的数据
分组
? 可解释性和可用性
? 聚类要和特定的语义解释和应用相联系
聚类分析中的数据类型
? 许多基于内存的聚类
算法采用以下两种数
据结构
? 数据矩阵：用 p个变量
来表示 n个对象
? 也叫二模矩阵，行与列
代表不同实体
? 相异度矩阵：存储 n个
对象两两之间的近似性
? 也叫单模矩阵，行和列
代表相同的实体
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
np
x.,,
nf
x.,,
n1
x
.,,.,,.,,.,,.,,
ip
x.,,
if
x.,,
i1
x
.,,.,,.,,.,,.,,
1p
x.,,
1f
x.,,
11
x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0...)2,()1,(
:::
)2,3()
...ndnd
0dd ( 3,1
0d ( 2,1 )
0
相异度计算
? 许多聚类算法都是以相异度矩阵为基础，如果
数据是用数据矩阵形式表示，则往往要将其先
转化为相异度矩阵。
? 相异度 d(i,j)的具体计算会因所使用的数据类型
不同而不同，常用的数据类型包括,
? 区间标度变量
? 二元变量
? 标称型、序数型和比例标度型变量
? 混合类型的变量
区间标度变量
? 区间标度度量是一个粗略线性标度的连续度量，比如重量、高度
等
? 选用的度量单位将直接影响聚类分析的结果，因此需要实现 度量值的标准化,将原来的值转化为无单位的值，给定一个变量 f的度
量值，可使用以下转化,
? 计算平均的绝对偏差
? 其中
? 计算标准化的度量值 (z-score)
? 使用平均的绝对偏差往往比使用标准差更具有健壮性
.)...211 nffff xx(xn m ????
|)|...|||(|1 21 fnffffff mxmxmxns ???????
f
fif
if s
mx z ??
对象间的相似度和相异度 (1)
? 对象间的相似度和相异
度是基于两个对象间的
距离来计算的
? Euclidean距离
? i=(xi1,xi2,…,x ip)和
j=(xj1,xj2,…,x jp)是两个 p维
数据对象
? Manhattan距离
)||.,,|||(|),( 2222211 pp jxixjxixjxixjid ???????
||.,,||||),( 2211 pp jxixjxixjxixjid ???????
对象间的相似度和相异度 (2)
? Manhattan距离和 Euclidean距离的性质
? d(i,j) ? 0
? d(i,i) = 0
? d(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
qq jxixjxixjxixjid )||...|||(|),(
2211 ???????
二元变量 (1)
? 一个二元变量只有两种状态,0或 1；
? e.g,smoker来表示是否吸烟
? 一个对象可以包含多个二元变量。
? 二元变量的可能性表,
? 如何计算两个二元变量之间的相似度？
pdbcasu m
dcdc
baba
su m
??
?
?
0
1
01
Object i
Object j
二元变量 (2)
? 对称的 VS,不对称的 二元变量
? 对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g,性别
? 基于对称的二元变量的相似度称为恒定的相似度，可以使用
简单匹配系数评估它们的相异度,
? 不对称的二元变量中，变量的两个状态的重要性是不同的；e.g,HIV阳性 VS HIV阴性
? 基于不对称的二元变量的相似度称为非恒定的相似度，可以
使用 Jaccard系数评估它们的相异度
dcba cb jid ??? ??),(
cba cb jid ?? ??),(
二元变量的相异度 —— 示例
N am e G end er Fev er Coug h Tes t-1 Tes t-2 Tes t-3 Tes t-4
Jac k M Y N P N N N
Mar y F Y N P N P N
Ji m M Y P N N N N
P228 例 8.1 二元变量之间的相异度 （病人记录表）
Name是对象标识
gender是对称的二元变量
其余属性都是非对称的二元变量
如过 Y和 P（ positive阳性）为 1,N为 0，则,
75.0
211
21
),(
67.0
111
11
),(
33.0
102
10
),(
?
??
?
?
?
??
?
?
?
??
?
?
m a r yjimd
jimja c kd
m a r yja c kd
标称变量
? 标称变量是二元变量的推广，它可以具有多于两个的状态值。
比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序
是不重要的。
? 计算标称变量所描述的对象（一个对象可以包含多个标称变量）
i和 j之间的相异度
? 方法一：简单匹配方法
? m,匹配的数目，即对象 i和 j取值相同的变量的数目 (也可加上权重 )
? 方法二：对 M个标称状态中的每个状态创建一个新的二元变量，并
用非对称的二元变量来编码标称变量
p mpjid ??),(
红 绿 蓝 黄 取值
0 1 0 0 绿
0 0 1 0 蓝
。。。。。。
序数型变量
? 一个序数型变量可以是离散的或者是连续的
? 序数型变量的值之间是有顺序关系的，比如：
讲师、副教授、正教授。
? 假设 f是描述 n个对象的一组序数型变量之一,f
的相异度计算如下,
? 1,设的 i个对象的 f值为 xif，则用它在值中的序 rif代
替
? 2,将每个变量的值域映射到 [0,1]的空间
? 3,采用区间标度变量的相异度计算方法计算 f的
相异度
1
1
?
??
f
if
if M
rz
},...,1{ fif Mr ?
比例标度变量
? 一个比例标度型变量 xif是在非线性的标度中所取的正
的度量值，例如指数标度，近似的遵循以下公式,
AeBt or Ae-Bt
? 计算比例标度型变量描述的对象之间的相异度
? 采用与区间标度变量同样的方法 —— 标度可能被扭曲，效果
往往不好
? 对比例标度型变量进行对数变化之后进行与区间标度变量的
相似处理
yif = log(xif)
? 将 xif看作连续的序数型数据，将其秩作为区间标度的值来对
待
混合类型的变量
? 在真实的数据库中，数据对象不是被一种类型的度量
所描述，而是被多种类型（即混合类型）的度量所描
述，包括,
? 区间标度度量、对称二元变量，不对称二元变量，标称变量，
序数型变量合比例标度变量
? 计算混合型变量描述的对象之间的相异度
? 将变量按类型分组，对每种类型的变量进行单独的聚类分析
? 在每种聚类分析导出相似结果的情况下可行
? 所有变量一起处理，进行一次聚类分析，可以将不同类型的
变量组合在单个相异度矩阵中，把所有有意义的变量转换到
共同的值域区间 [0,1]之内
主要的聚类方法
? 聚类分析算法种类繁多，具体的算法选择取决于数据
类型，聚类的应用和目的，常用的聚类算法包括,
? 划分方法
? 层次的方法
? 基于密度的方法
? 基于网格的方法
? 基于模型的方法
? 实际应用中的聚类算法，往往是上述聚类方法中多种
方法的整合
划分方法
? 给定一个 n个对象或元组的数据库，一个划分方法构
建数据的 k个划分，每个划分表示一个簇，并且 k<=n。
? 每个组至少包含一个对象
? 每个对象属于且仅属于一个组
? 划分准则：同一个聚类中的对象尽可能的接近或相关,不同聚类中的对象尽可能的原理或不同
? 簇的表示
? k-平均算法
? 由簇的平均值来代表整个簇
? k中心点算法
? 由处于簇的中心区域的某个值代表整个簇
层次的方法
? 对给定数据对象集合进行层次分解
? 自底向上方法（凝聚）：开始将每个对象作为单独
的一个组，然后相继的合并相近的对象或组，直到
所有的组合并为一个，或者达到一个终止条件。
? 自顶向下方法（分裂）：开始将所有的对象置于一
个簇中，在迭代的每一步，一个簇被分裂为多个更
小的簇，直到最终每个对象在一个单独的簇中，或
达到一个终止条件
? 缺点：合并或分裂的步骤不能被撤销
基于密度的方法
? 基于距离的聚类方法的缺点：只能发现球状的
簇，难以发现任意形状的簇。
? 基于密度的据类：只要临近区域的密度（对象
或数据点的数目）超过某个临界值，就继续聚
类。
? 优点：可以过滤掉“噪声”和“孤立点”，发现任
意形状的簇。
基于网格的方法
? 把对象空间量化为有限数目的单元，形成一个
网格结构。所有的聚类都在这个网格结构上进
行。
? 优点：处理数度快（因为处理时间独立于数据对象
数目，只与量化空间中每一维的单元数目有关）
基于模型的方法
? 为每个簇假定一个模型，寻找数据对给定模型
的最佳拟合。
? 一个基于模型的算法可能通过构建反映数据点空间
分布的密度函数来定位聚类
? 这种方法同时也用于自动的决定数据集中聚类的数
目
? 通过统计学的方法，考虑噪声和孤立点，从而产生健壮的
聚类方法
孤立点挖掘
? 什么是孤立点？
? 一个数据集与其他数据有着显著区别的数据对象的集合
? 例如：运动员,Michael Jordon,舒马赫，布勃卡
? 孤立点产生原因
? 度量或执行错误（年龄,-999）
? 数据变异的结果
? 孤立点挖掘
? 给定一个 n个数据对象的集合，以及预期的孤立点数目 k，发现与
剩余的数据有着显著差异的头 k个数据对象
? 应用
? 信用卡欺诈检测
? 移动电话欺诈检测
? 客户划分
? 医疗分析（异常）
基于统计的孤立点检测
? 统计的方法对于给定的数据集合假定了一个分布或概
率模型（例如正态分布）
? 使用依赖于以下参数的不一致性检验（ discordancy
tests）
? 数据分布
? 分布参数（ e.g,均值或方差）
? 预期的孤立点数
? 缺点
? 绝大多数检验是针对单个属性的，而数据挖掘要求在多维空
间中发现孤立点
? 大部分情况下，数据分布可能是未知的
基于距离的孤立点检测
? 为了解决统计学方法带来的一些限制，引入了
基于距离的孤立点检测
? 在不知道数据分布的情况下对数据进行多维分析
? 基于距离的孤立点：即 DB(p,d)，如果数据集
合 S中的对象至少有 p部分与对象 o的距离大于
d，则对象 o就是 DB(p,d)。
? 挖掘基于距离的孤立点的高效算法,
? 基于索引的算法
? 嵌套－循环算法
? 基于单元的算法
基于偏离的孤立点检测
? 通过检查一组对象的主要特征来确立孤立点
? 跟主要特征的描述相“偏离”的对象被认为是
孤立点
? 两种基于偏离的孤立点探测技术
? 序列异常技术
? 模仿人类从一系列推测类似的对象中识别异常对象的方式
? OLAP数据立方体技术
? 在大规模的多维数据中采用数据立方体来确定异常区域。
如果一个立方体的单元值显著的不同于根据统计模型得到
的期望值，则改单元值被认为是一个异常，并用可视化技
术表示。
