nbhkdz.com冰点文库

2019年第6章聚类分析ppt课件.ppt_图文

时间:2019-04-28

第5章 聚类分析

本章概述 本章的学习目标 主要内容

第1页

什么是聚类
? ?

聚类(Clustering)就是将数据分组成为多个类 (Cluster或译为簇)。 在同一个类内对象之间具有较高的相似度,不同类 之间的对象差别较大。
在一个簇内的距 离最小化 簇之间的距离最 大化

第2页

? ?

从机器学习的角度讲,簇相当于隐藏模式。聚类是 搜索簇的无监督学习过程。 与分类不同,无监督学习不依赖预先定义的类或带 类标记的训练实例,需要由聚类学习算法自动确定 标记,而分类学习的实例或数据对象有类别标记。

第3页

什么是聚类
? ?

早在孩提时代,人就通过不断改进下意识中的聚类 模式来学会如何区分猫和狗,动物和植物 将周围的人分为家人和非家人

第4页

聚类分析无处不在
?

谁经常光顾商店,谁买什么东西,买多少? ?按忠诚卡记录的光临次数、光临时间、性别、 年龄、职业、购物种类、金额等变量分类 ?这样商店可以…. ?识别顾客购买模式(如喜欢一大早来买酸奶和 鲜肉,习惯周末时一次性大采购) ?刻画不同的客户群的特征(用变量来刻画,就 象刻画猫和狗的特征一样)

第5页

什么情况下需要聚类
?

?

为什么这样分类? 因为每一个类别里面的人消费方式都不一样,需要 针对不同的人群,制定不同的关系管理方式,以提 高客户对公司商业活动的响应率。

第6页

聚类分析无处不在
?

?

挖掘有价值的客户,并制定相应的促销策略: ?如,对经常购买酸奶的客户 ?对累计消费达到12个月的老客户 针对潜在客户派发广告,比在大街上乱发传单命中 率更高,成本更低!

第7页

聚类分析无处不在
?

谁是银行信用卡的黄金客户? ?利用储蓄额、刷卡消费金额、诚信度等变量对客 户分类,找出“黄金客户”! ?这样银行可以…… ?制定更吸引的服务,留住客户!比如:
? 一定额度和期限的免息透资服务! ? 百盛的贵宾打折卡! ? 在他或她生日的时候送上一个小蛋糕!

?

手机套餐的制定

第8页

聚类的应用领域
?

经济领域: ?帮助分析人员从客户数据库中发现不同的客户群, 并且用购买模式来刻画不同的客户群的特征。 ?谁喜欢打国际长途,在什么时间,打到那里? ?对住宅区进行聚类,确定自动提款机ATM的安放 位置 ?股票市场板块分析,找出最具活力的板块龙头股 ?企业信用等级分类 ?……

第9页

?

?

生物学领域 ?推导植物和动物的分类(门、纲、目、科、属、 种 ); ?对基因分类,获得对种群的认识 数据挖掘领域 ?作为其他数学算法的预处理步骤,获得数据分布 状况,集中对特定的类做进一步的研究

第10页

聚类分析原理介绍
?

聚类分析中“类”的特征: ?聚类所说的类不是事先给定的,而是根据数据的 相似性和距离来划分 ?聚类的数目和结构都没有事先假定

第11页

簇(类)的概念可能是模糊的

有多少个簇?

6个簇

2个簇

四个簇

如何对汉语方言进行分类?
第12页

聚类分析原理介绍
我们看以下的例子: ? 有16张牌 ? 如何将他们分为 一组一组的牌呢?
?

A K Q J

第13页

聚类分析原理介绍
?

?
?

分成四组 每组里花色相同 组与组之间花色相异
A K

Q
J

花色相同的牌为一副 Individual suits
第14页

聚类分析原理介绍
?

?

分成四组 符号相同的牌为一组
A K

Q
J

符号相同的的牌 Like face cards
第15页

聚类分析原理介绍
?

?

分成两组 颜色相同的牌为一组
A K

Q
J

颜色相同的配对

Black and red suits
第16页

聚类分析原理介绍
?

?

分成两组 大小程度相近的牌分到 一组
A K

Q
J

大配对和小配对

Major and minor suits
第17页

聚类分析原理介绍
?

这个例子告诉我们,分 组的意义在于我们怎么 定义并度量“相似性” (Similar)

?

因此衍生出一系列度量 相似性的方法

A K

Q
J

大配对和小配对 Major and minor suits
第18页

聚类分析原理介绍
变量按测量尺度(Measurement Level)分类 ? 区间(Interval)值变量 ?连续变量,如长度、重量、速度、温度等 ? 有序(Ordinal)值变量 ?等级变量,不可加,但可比,如一等、二等、三 等奖学金 ? 名词性(Nominal)变量 ?类别变量,不可加也不可比,如性别、职业等 ? 下面介绍对各种不同类型的变量如何进行度量

第19页

度量对象间的相似与差异
? ?

对象间的相似度或相异度通常基于每对对象间的距 离的计算 欧几里得距离

d (i, j) ? (| x ? x | ? | x ? x | ?...? | x ? x | ) i1 j1 i2 j 2 ip jp
q 2 2 2

?

Minkowski距离
d (i, j) ? q (| x ? x |q ? | x ? x |q ?...? | x ? x |q ) i1 j1 i2 j2 ip jp

第20页

度量对象间的相似与差异
?

曼哈顿距离(Block距离)

d (i, j) ?| x ? x | ? | x ? x | ?...? | x ? x | i1 j1 i2 j2 ip jp

?

?
?

欧几里得距离是当q=2时的Minkowski距离的特例 曼哈顿距离是当q=1时的Minkowski距离的特例 当q=?时得到无穷距离(无穷范数),由向量间各分量 的最大差决定

第21页

度量对象间的相似与差异
?

距离所应满足的数学性质

?d(i,j) ? 0
?d(i,i) = 0

?d(i,j) = d(j,i)
?d(i,j) ? d(i,k) + d(k,j)
?

除此之外,还可以使用加权的距离

第22页

二元属性变量
?

?

二元变量只有两种状态:0或1 ?例如给定描述患者的变量smoker,1表示患者抽 烟,0表示不抽烟 像处理一般数值量一样来处理二元变量会产生误导 的聚类结果

第23页

二元属性变量的相依表
Object j

1
Object i

0 r t

sum q?r s ?t p

1 0

q s

sum q ? s r ? t
?

如果所有的二元变量具有相同的权重,则可以得到 上表所示的两行两列的相依表 ?q是对象i和j值都为1的变量的数目 ?r是在对象i值为1,但对象j值为0的变量数目 ?…… ?变量的总数是p=q+r+s+t
第24页

对称二元变量和非对称二元变量
?

?

?

对二元变量的相异度计算还要考虑变量的对称性 对称二元变量 ?如果他的两个状态具有同等价值和相等的权重 ?输出用0或1编码没有优先权,如性别 对称二元相异度

d (i, j) ?

r?s q ? r ? s ?t

第25页

对称二元变量和非对称二元变量
?

?

非对称二元变量 ?如果状态的输出不是同等重要的 ?例如基本检查的阳性和阴性结果。根据惯例,将 比较重要的输出结果(通常也是出现机率较小的结 果)编码为1,而将另一种结果编码为0(如HIV阴性) ?给定两个非对称二元变量,两个都取值1的情况认 为比两个都取值0的情况更有意义 非对称二元相异度

r?s d (i, j) ? q ? r?s

第26页

对称二元变量和非对称二元变量
? ?

有时采用两个二元变量的相似度而不是相异度来测 量他们之间的距离。 非对称二元相似度sim(i,j)如下定义

q simJaccard(i, j) ? q ? r ? s ?1? d (i, j)

?

系数sim(i,j)常称作Jaccard系数

第27页

例 二元变量之间的相异度
姓名 Jack Mary Jim 性别 M F M 发烧 Y Y Y 咳嗽 N N P Test-1 P P N Test-2 N N N Test-3 N P N Test-4 N N N

?

?

假设一个患者记录表包含上述属性,其中name是标 识符,性别是对称二元属性,其余的属性都是非对 称二元属性 对于非对称属性,值Y和P(positive)置为1,值N(no 或negative)置为0

第28页

例 二元变量之间的相异度
?

假设对象之间的距离只基于非对称变量来计算。根 据公式,三个患者Jack、Mary和Jim两两之间的相 0?1 异度如下: d ( jack, mary) ? ? 0.33
2? 0?1 1?1 d ( jack, jim ) ? ? 0.67 1?1?1 1? 2 d ( jim , mary) ? ? 0.75 1?1? 2

?

度量显示Jim和Mary不大可能患相似的疾病,而 Jack和Mary最可能患相似的疾病
姓名 Jack Mary Jim 性别 M F M 发烧 Y Y Y 咳嗽 N N P Test-1 P P N Test-2 N N N Test-3 N P N Test-4 N N N

第29页

名词性属性变量
?

?

?

可取多个相异值,之间没有序关系 如产品颜色可以取:红、黄、绿、蓝等 ?也可以用0,1,2,3等代码来表示,但注意这里 的数字仅是标识,不能做运算 两个对象i和j之间的相异度简单的处理方法是计算不 匹配率: p?m

d (i, j) ?

p

?

?其中p是全部变量的数目,m是匹配的数目 也可以构造一个大的二元变量数组,再按二元变量 处理
第30页

余弦相似度
?

文档数据
timeout season

coach

game

score

team

ball

lost

pla y

wi n

Document 1 Document 2 Document 3

3 0 0

0 7 1

5 0 0

0 2 0

2 1 1

6 0 2

0 0 2

2 3 0

0 0 3

2 0 0

第31页

余弦相似度
在信息检索、文本文档聚类和生物学分类中,需要 对包含了大量符号实体的复杂对象进行比较和聚类 ?为了测量复杂对象间的距离,通常期望放弃传统的度 量距离计算,而引入非度量的相似度函数 ? 如果d1 和 d2 是两个文档向量,则 cos( d1, d2 ) = (d1 ? d2) / ||d1|| ||d2|| , ? 其中 ? 表示向量的点积(内积),|| d ||表示向量的范 数. ?问题:余弦相似度的范围?取最大值时是否两个向量 相等?
?
第32页

余弦相似度计算的例子
? ? ?

?

?

?

d1 = 3 2 0 5 0 0 0 2 0 0 d2 = 1 0 0 0 0 0 0 1 0 2 d1 ? d2 = 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 =5 ||d1|| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481 ||d2|| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245 cos( d1, d2 ) = 5/(6.481*2.245).3150
第33页

如何选择恰当的度量
? ?

有很多方法用来选择一个具体的相似度或距离函数, 但是还没有一个通用的标准用来指导这样的选择 这种度量的选择高度依赖于具体的应用。

第34页

主要聚类方法的分类
?

?

划分方法:给定n个对象,划分方法构建数据的k个 划分,每个划分表示一簇,k<=n,满足如下要求 ?每组至少包含一个对象 ?每个对象必须只属于一个组(在软聚类技术中可放 宽) 对于给定的划分数目k,通常创建一个初始划分,然 后采用迭代方法尝试通过对象在组间移动来改进划 分

第35页

主要聚类方法的分类
? ?

好的划分的标准:同一个簇中的对象之间尽可能相 似,不同簇的对象尽可能有大的差异 常用方法: ?k均值方法:每个簇都用该簇中对象的均值来表示 ?k中心点法:每个簇用接近簇中心的一个对象来表 示

第36页

层次方法
?

?

层次方法创建给定数据对象的层次分解 根据使用的方法,层次的方法可以分类为凝聚的或 分裂的方法 ?凝聚法:也称自底向上的方法,开始将每个对象 形成单独的组,然后逐次合并相近的对象或组, 直到所有的组合并为一个或满足某个终止条件 ?分裂法:自顶向下的方法,一开始将所有对象置 于一个簇中,每次迭代,簇分裂为更小的簇,直 到每个对象在一个簇中或满足终止条件

第37页

基于模型的方法
? ?

为每簇假定一个模型,并寻找数据对给定模型的最 佳拟合 常见算法 ?EM算法:基于统计模型并进行期望最大化分析 ?COBWEB:概念学习算法,进行概率分析并把概 念作为簇模型 ?SOM(自组织映射):一种基于神经网络的算法, 通过把高维数据映射到2维或3维特征空间进行聚 类

第38页

划分聚类

原始点

划分聚类

第39页

层次聚类
p1 p3 p2 p4

p1 p2
Traditional Hierarchical Clustering

p3 p4

Traditional Dendrogram

p1 p3 p2 p4

p1 p2
Non-traditional Hierarchical Clustering

p3 p4

Non-traditional Dendrogram

第40页

其他的聚类类型的差别
?

?

互斥的与非互斥的 ?在非互斥聚类中,点可以属于多个簇. ?可以表示多重类或边界类 模糊聚类与非模糊聚类 ?模糊聚类中,一个点到隶属于每个簇的情况可 以用一个在0到1之间的隶属度描述

第41页

不同的簇类型
?

?
? ?

?

明显分离的簇 基于中心的簇 基于近邻的簇 基于密度的簇 概念簇

第42页

不同的簇类型
?

明显分离的簇: ?每个点到同簇中任意点的距离比到不同簇中所 有点的距离更近

3 个明显分离的簇
第43页

不同的簇类型
?

基于中心的簇 ? 每个点到其簇中心的距离比到任何其他簇中心 的距离更近 ?簇的中心通常是重心,簇中所有点的平均值, 或者是簇的原型,即一个簇中最具代表性的点

4 center-based clusters
第44页

不同的簇类型
?

基于近邻的簇(基于图的——连通分支) ?每个点到该簇中至少一个点的距离比到不同簇 中任意点的距离更近

8 contiguous clusters
第45页

不同的簇类型
?

基于密度的簇 ?簇是被低密度区域分开的高密度区域. ?当簇不规则或互相盘绕,并且有噪声和离群点 时,通常使用基于密度的簇定义

6 density-based clusters
第46页

划分方法
?

?

?

对于一个给定的n个对象或元组的数据库,采用目标 函数最小化的策略,通过迭代把数据分成k个划分块, 每个划分块为一个簇,这就是划分方法。 划分方法满足两个条件: ?(1)每个分组至少包含一个对象; ?(2)每个对象必属于且仅属于某一个分组。 常见的划分方法有k-均值方法和k-中心点方法。其他 方法大都是这两种方法的变形。

第47页

k-均值算法
?

k-均值聚类算法的核心思想是通过迭代把数据对象划 分到不同的簇中,以求目标函数最小化,从而使生 成的簇尽可能地紧凑和独立。 ?随机选取k个对象作为初始的k个簇的质心; ?将其余对象根据其与各个簇质心的距离分配到最 近的簇;再求新形成的簇的质心。 ?这个迭代重定位过程不断重复,直到目标函数最 小化为止。

第48页

k-均值算法
算法 K均值 输入 K:簇的数目 D:包含n个对象的点集 输出 K个簇的集合 方法

1 2
3

从D中任意选择K个点作为初始簇中心 Repeat
根据簇中对象的均值,将每个对象再指派到最相似的簇

4
5

更新簇均值,即计算每个簇中对象的均值
Until 不再发生变化
第49页

初始质心的选择非常重要
Iteration 6 1 2 3 4 5
3 2.5

2

1.5

y
1 0.5 0 -2

-1.5

-1

-0.5

0

0.5

1

1.5

2

x

第50页

使用K均值算法的迭代过程
Iteration 1
3 3 2.5 2.5

Iteration 2
3 2.5

Iteration 3

2

2

2

1.5

1.5

1.5

y

y

1

1

y
1 0.5 0.5 0 0 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2

0.5

0

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-1.5

-1

-0.5

0

0.5

1

1.5

2

x

x

x

Iteration 4
3 3 2.5 2.5

Iteration 5
3 2.5

Iteration 6

2

2

2

1.5

1.5

1.5

y

y

1

1

y
1 0.5 0.5 0 0 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2

0.5

0

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-1.5

-1

-0.5

0

0.5

1

1.5

2

x

x

x

第51页

K-均值算法
10

10 9 8 7 6 5

10
9

9
8

8
7

7
6

6
5

5
4

4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10

Assign each objects to most similar center

3 2 1 0 0 1 2 3 4 5 6 7 8 9 10

Update the cluster means

4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10

reassign
10 9 8
10 9 8 7 6

reassign

K=2 Arbitrarily choose K object as initial cluster center

7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10

Update the cluster means

5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10

第52页

欧几里得空间中的数据
? ?

?

通常使用误差的平方和(sum of the squared error, SSE)作为度量聚类质量的目标函数 SSE也称散布(scatter):计算每个数据点的误差—— 即它到最近质心的欧几里得距离,然后计算误差的 平方和 给定由两次运行K均值产生的两个不同的簇集,我们 更喜欢误差的平方和最小的那个,这意味着聚类的 原型(质心)是簇中点的更好代表

SSE ? ? ? dist2 (mi , x)
i ?1 x?Ci
第53页

K

欧几里得空间中的数据
? ?

?

可以证明在欧几里得空间中是簇的SSE最小的质心 就是均值 K均值算法的第3步和第4步试图直接最小化SSE ?步骤3通过将点指派到最近的质心形成簇,最小化 关于给定质心集的SSE ?步骤4重新计算质心,进一步最小化SSE 问题:K均值的步骤3和4只能找到关于SSE的局部最 小值,因为它们是对选定的质心和簇,而不是对 所 有可能的选择来优化SSE

第54页

初始质心的选择非常重要
Iteration 5 1 2 3 4
3 2.5

2

1.5

y
1 0.5 0 -2

-1.5

-1

-0.5

0

0.5

1

1.5

2

x

第55页

初始质心的选择非常重要
Iteration 1
3 3 2.5 2.5

Iteration 2

2

2

1.5

1.5

y

1

y
1 0.5 0.5 0 0 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2

-1.5

-1

-0.5

0

0.5

1

1.5

2

x

x

Iteration 3
3 3 2.5 2.5

Iteration 4
3 2.5

Iteration 5

2

2

2

1.5

1.5

1.5

y

y

1

1

y
1 0.5 0.5 0 0 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2

0.5

0

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-1.5

-1

-0.5

0

0.5

1

1.5

2

x

x

x

第56页

随机初始化
?

? ?

由于K均值算法会陷入局部最小值而得到次优聚类, 一种常用的选取初始质心的方法是多次运行,每次 使用一组不同的随机初始质心,然后选取具有最小 SSE的簇集 下面我们看一看这种方法的问题 下页的图中有5个簇对,每个簇对有上下两个簇。 ?如果每个簇对有两个初始质心,则效果较好 ?如果有一个簇对中只有一个初始中心,而另一个 簇对中有三个初始中心,则会出现错误。

第57页

5个簇对,10个簇的例子
Iteration 4 1 2 3
8 6 4 2

y

0 -2 -4 -6

0

5

10

15

20

x Starting with two initial centroids in one cluster of each pair of clusters
第58页

5个簇对,10个簇的例子
Iteration 1
8 6 4 2 8 6 4 2

Iteration 2

y

0 -2 -4 -6

y
0 5 10 15 20

0 -2 -4 -6

0

5

10

15

20

Iteration 3
8 6 4 2 8 6 4 2

x

Iteration 4

x

y

0 -2 -4 -6

y
0 5 10 15 20

0 -2 -4 -6

0

5

10

15

20

x

x

Starting with two initial centroids in one cluster of each pair of clusters
第59页

5个簇对,10个簇的例子
Iteration 4 1 2 3
8 6 4 2

y

0 -2 -4 -6

0

5

10

15

20

x

Starting with some pairs of clusters having three initial centroids, while other have only one.

第60页

5个簇对,10个簇的例子
Iteration 1
8 6 4 2 8 6 4 2

Iteration 2

y

0 -2 -4 -6

y
0 5 10 15 20

0 -2 -4 -6

0 8 6 4 2

5

10

15

20

x Iteration 3
8 6 4 2

x Iteration 4

y

0 -2 -4 -6

y
0 5 10 15 20

0 -2 -4 -6

0

5

10

15

20

x

x

Starting with some pairs of clusters having three initial centroids, while other have only one.

第61页

解决初始质心设置问题的方法
?

?

?

? ?

多次运行 ?不一定总有效 对数据作采样并使用层次聚类,从中提取K个簇并使 用这些簇的质心作为初始质心 选取多于k个的初始质心,然后从其中选择k个 ?最分离的k个点 后处理 二分K-均值

第62页

二分K均值
?

?

?

?

基本思想: 为了得到K个簇,将所有点的集合分裂成两个簇,从 这些簇中选取一个继续分裂,如此下去直到产生K个 簇 可以使用多种方法选择待分裂的簇 ?最大的簇 ?具有最大SSE的簇 ?基于大小和SSE 二分K均值得到的最终的簇集并不代表使SSE局部最 小的聚类
第63页

二分K均值算法
算法 二分K均值 1 2 3 4 5 6 7 8 9 10 初始化簇表,使之包含有所有的点组成的簇 Repeat 从簇表中取出一个簇 对选定的簇进行多次二分试验 for i=1 to 试验次数 do 使用基本K均值,二分选定的簇 end for 从二分试验中选择具有最小总SSE的两个簇 将这两个簇添加到簇表中 until 簇表中包含K个簇
第64页

二分K-均值的例子

第65页

K-均值方法的缺陷
?

K-均值方法当簇在下述方面有较大不同时会出现问 题 ?不同大小 ?不同密度 ?非球形的形状

第66页

K-均值的缺陷:不同的簇大小

Original Points

K-means (3 Clusters)

WHY?
第67页

K-均值的缺陷—不同的密度分布

Original Points

K-means (3 Clusters)

WHY?
第68页

K—均值的缺陷:非球形形状

Original Points

K-means (2 Clusters)

K均值目标函数是最小化等尺度和等密度的球形簇,或明显分 离的簇
第69页

克服K—均值方法的缺陷

Original Points

K-means Clusters

一种方法是使用更多的簇,再反过来使其部分合并
第70页

克服K—均值方法的缺陷

Original Points

K-means Clusters

第71页

克服K—均值方法的缺陷

Original Points

K-means Clusters

第72页

层次聚类方法
?

?

?

定义:对给定的数据进行层次的分解: 凝聚的(agglomerative)方法(自底向上) ?思想:一开始将每个对象作为单独的一组,然后 根据同类相近,异类相异的原则,合并对象,直 到所有的组合并成一个,或达到一个终止条件为 止。 分裂的方法(divisive)(自顶向下) ?思想:一开始将所有的对象置于一类,在迭代的 每一步中,一个类不断地分为更小的类,直到每 个对象在单独的一个类中,或达到一个终止条件。
第73页

凝聚的和分裂的层次聚类
分裂的(DIANA) 第4步 第3步 a, b, c, d, e 第0步 c, d, e 第1步 第2步 第1步 a, b d, e 第2步 第3步 b c d e

第0步

a

第4步

凝聚的(AGENS)

第74页

层次聚类方法
?

?

产生一个相邻簇的集合,通常用一棵树来表示 Can be visualized as a dendrogram ?树状图记录了分裂或合并的序列
0.2

6 4

5

0.15

3

2

4 5 2

0.1

0.05

1 3 1

0

1

3

2

5

4

6

以树状图和嵌套簇图显示的4个点的层次聚类
第75页

层次聚类法的特点
?

?

?

不用预知(预设)簇的数目 ?任何需要簇数的聚类可以通过在树状图的适当层 次切割而得到 得到更有意义的结构 ?如生物学中的分类 传统的层次聚类算法使用相似度矩阵或距离矩阵 ?每次合并或分裂一个簇

第76页

基本凝聚层次聚类算法
1 计算距离矩阵 2 令每个点为一个簇 3 Repeat 4 合并最接近的两个簇 5 更新距离矩阵 6 until 仅剩下一个簇

第77页

基本凝聚层次聚类算法
?

关键步骤在于计算两个簇之间的邻近度 ? 不同的定义簇之间的距离的方法区分了不同的 算法

第78页

开始...
?

每个点为一个簇,计算各个簇两两之间的距离矩阵
p1 p1 p2 p3 p4 p5
. . .

p2

p3

p4 p5

...

距离矩阵

...
p1 p2 p3 p4 p9 p10 p11 p12

第79页

接下来...
?

经过若干凝聚步骤,得到如下的簇
C1 C1 C2 C3 C3 C4 C4 C5 C2 C3 C4 C5

距离矩阵
C1

C2

C5

...
p1 p2 p3 p4 p9 p10 p11 p12

第80页

接下来...
?

合并两个最靠近的簇 (C2 和 C5) 并更新距离矩阵
C1 C1 C2 C3 C4 C5

C2
C3 C3 C4 C4 C5

距离矩阵
C1

C2

C5

...
p1 p2 p3 p4 p9 p10 p11 p12

第81页

合并后
?

问题变为如何更新距离矩阵
C1 C1 C3 C4 C2 U C5 ?

C2 U C5
? ?

C3

C4

?

?

C3
C4

?
?

C1

距离矩阵

C2 U C5

...
p1 p2 p3 p4 p9 p10 p11 p12

第82页

如何定义簇之间的邻近度
p1 p2 p3 p4 p5

...

距离

p1

p2
p3 p4

? ? ? ?

?

MIN(单链) MAX(全链) Group Average(组平均) 质心的距离 其他的源自目标函数的方法 ?Ward方法使用平方差

p5

. . .

距离矩阵

第83页

如何定义簇之间的邻近度
p1 p1 p2 p3 p4 p5

...

p2
p3 p4

? ? ? ?

?

MIN(单链) MAX(全链) Group Average(组平均) 质心的距离 其他的源自目标函数的方法 ?Ward方法使用平方差

p5

. . .

距离矩阵

第84页

如何定义簇之间的邻近度
p1 p1 p2 p3 p4 p5

...

p2
p3 p4

? ? ? ?

?

MIN(单链) MAX(全链) Group Average(组平均) 质心的距离 其他的源自目标函数的方法 ?Ward方法使用平方差

p5

. . .

距离矩阵

第85页

如何定义簇之间的邻近度
p1 p1 p2 p3 p4 p5

...

p2
p3 p4

? ? ? ?

?

MIN(单链) MAX(全链) Group Average(组平均) 质心的距离 其他的源自目标函数的方法 ?Ward方法使用平方差

p5

. . .

距离矩阵

第86页

如何定义簇之间的邻近度
p1 p1 p2 p3 p4 p5

...

?

?

p2
p3 p4

? ? ? ?

?

MIN(单链) MAX(全链) Group Average(组平均) 质心的距离 其他的源自目标函数的方法 ?Ward方法使用平方差

p5

. . .

距离矩阵

第87页

MIN或单链
?

两个簇之间的邻近度基于两个簇中最近的两个点的 距离 ?由一个点对决定,或者说由图中的一条链决定

I1 I2 I3 I4 I5

I1 1.00 0.90 0.10 0.65 0.20

I2 0.90 1.00 0.70 0.60 0.50

I3 0.10 0.70 1.00 0.40 0.30

I4 0.65 0.60 0.40 1.00 0.80

I5 0.20 0.50 0.30 0.80 1.00

1

2

3

4

5
第88页

层次聚类: MIN
1 5

3
5 2 4 4
0.2

2 3

1 6

0.15

0.1

0.05

0

3

6

2

5

4

1

Nested Clusters

Dendrogram
第89页

MIN的优点

Original Points

Two Clusters

?可以处理非椭圆的形状

第90页

MIN的不足

Original Points

Two Clusters

? 对噪声点和离群点很敏感
第91页

MAX或全链
?

两个簇之间的邻近度由两个簇间最不相似的(最大距 离的)点对决定 ?由两个簇中所有的点对决定

I1 I2 I3 I4 I5 I1 1.00 0.90 0.10 0.65 0.20 I2 0.90 1.00 0.70 0.60 0.50 I3 0.10 0.70 1.00 0.40 0.30 I4 0.65 0.60 0.40 1.00 0.80 I5 0.20 0.50 0.30 0.80 1.00

1

2

3

4

5
第92页

MAX或全链
4 2 5 2 3 3 4 1 1 5
0.4 0.35 0.3 0.25

6

0.2 0.15 0.1 0.05 0 3 6 4 1 2 5

Nested Clusters

Dendrogram

第93页

MAX的优点

Original Points

Two Clusters

?对噪声点和离群点不太敏感

第94页

MAX的不足

Original Points

Two Clusters

?倾向于分裂大的簇
?倾向于球状的簇
第95页

组平均
? ?

两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度 Need to use average connectivity for scalability since total proximity favors large clusters
proximity( Cluster i , Cluster j) ?
pi?Cluster i p j?Clusterj

p ,p ) ? proximity(
i j

|Cluster i |?|Cluster j|

I1 I2 I3 I4 I5

I1 1.00 0.90 0.10 0.65 0.20

I2 0.90 1.00 0.70 0.60 0.50

I3 0.10 0.70 1.00 0.40 0.30

I4 0.65 0.60 0.40 1.00 0.80

I5 0.20 0.50 0.30 0.80 1.00

1

2

3

4

5
第96页

组平均
5 2 5 2 4

1
0.25 0.2 0.15

3
1 4 3

6

0.1 0.05 0

3

6

4

1

2

5

Nested Clusters

Dendrogram

第97页

组平均
? ?

?

是单链和全链之间的一个折中,该法利用了所有样 本的信息,被认为是较好的层次聚类法 优点 ? 对噪声和离群点不太敏感 不足 ? 倾向于球状的簇

第98页

Ward方法和质心方法
?

?
? ?

两个簇的邻近度定义为两个簇合并时导致的平方误 差的增量,该方法使用的目标函数与K均值相同 ?可以证明,当取距离的平方作为两个点间的邻近 度时,Ward方法与组平均方法相似 对噪声和离群点不太敏感 倾向于球状的簇 可以用来初始化K均值方法

第99页

层次聚类法:比较
1 3 5 2 4 4 2 3 1 6 3 5 MIN MAX 5 4 1

2
2 3 1 6

5

4

1 2

5

5

4 2 2 3

1

5

2 3 3 6 1 4

Ward’s Method
Group Average

5

6 1

4

4

3

第100页

层次聚类:时间和空间复杂度
? ?

O(N2) 空间复杂度,因为要存储邻近度矩阵,N为点 的数目 最坏情况下O(N3) 的时间复杂度 ?共有N步,在每一步中要更新和搜索N2规模的邻 近度矩阵 ?在某些算法中可以接近O(N2 log(N) ) 的时间复杂 度

第101页

层次聚类方法的优缺点
? ?

?

层次聚类方法的优点在于可以在不同粒度水平上对 数据进行探测,而且容易实现相似度量或距离度量。 单纯的层次聚类算法终止条件含糊,而且执行合并 或分裂簇的操作后不可修正,这很可能导致聚类结 果质量很低。 通常考虑把层次聚类方法与其他方法(如迭代重定 位方法)相结合来解决实际聚类问题。

第102页

基于密度的聚类:DBSCAN
?

DBSCAN是一种基于密度的聚类算法 ? 密度 = 给定半径(Eps)内点的数目 ? 核心点(core point ) 在半径Eps的邻域内拥有 多于特定数目(MinPts)的邻点的点,在基于密 度的簇内部的点 ? 边界点(border point )在半径Eps的邻域内拥 有多于特定数目(MinPts)的邻点的点,但是落 在某个核心点的邻域内 ? 噪声点(noise point )既非核心点也非边界点 的任何点
第103页

DBSCAN: 核心点,边界点和噪声点

第104页

DBSCAN 算法
?

算法 ?1:将所有点标记为核心点、边界点或噪声点 ?2:删除噪声点 ?3:为距离在Eps之内的所有核心点之间赋予一条 边 ?4:每组连通的核心点形成一个簇 ?将每个边界点指派到一个与之关联的核心点的簇 中

第105页

DBSCAN 算法

原始点

点的类型: 核心, 边界 和噪声 Eps = 10, MinPts = 4
第106页

当DBSCAN工作良好时

原始点 ? 对噪声不敏感 ? 可以处理不同形状和大小的簇

得到的簇

第107页

当DBSCAN工作不佳时

(MinPts=4, Eps=9.75).

原始点集 ? 变密度的簇

? 对高维数据计算量巨大
(MinPts=4, Eps=9.92)
第108页

DBSCAN算法: 确定EPS和 MinPts
?

? ?

基本方法:观察点到它的k个最近邻的距离(称作 k-距离)。对于属于某个簇的点,如果k不大于簇 的大小的话,则k-距离将很接近 噪声点由于不在簇中,其k-距离将相对较大 对于某个k,计算所有点的k-距离,以递增次序将 它们排序,然后绘制排序后的值,则预期会看到 k-距离的急剧变化处对应于合适的Eps值

第109页

DBSCAN算法: 确定EPS和 MinPts

第110页

簇评估
?

? ?

对于有监督的分类,我们可以有多种方式评价模型 的优劣 ?准确度, 精度, 召回率 对于聚类分析, 相应的问题是如何评价聚类结果是否 是 “好”的 评估簇的目的 ?避免寻找噪声中的模式 ?比较不同的聚类算法 ?比较两个聚类的结果 ?比较两个簇
第111页

在随机数据中发现的簇
1 0.9 0.8 0.7

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1
0 0.2 0.4 0.6 0.8 1

100个 随机分 布的点

0.6 0.5 0.4 0.3 0.2 0.1 0

DBSCAN

y

y

0

0

0.2

0.4

0.6

0.8

1

x
1 0.9 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.2 0.4 0.6 0.8 1 0 0 0.2 0.4

x

K-均值
y

0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

全链聚类

y

0.6

0.8

1

x

x

第112页

簇评估
1. 确定数据的聚类趋势( clustering tendency ), 即 识别数据中是否实际存在非随机结构. 2. 比较聚类分析的结果与通过外部知识得到的类标 (确定正确的簇个数). 3. 评估聚类分析的结果在不引用附加信息的情况下 是否能较好拟合数据. 4. 比较两个不同的聚类结果的优劣. 5. 确定“正确”的类的个数 ? 对于 2, 3, 4, 还可以进一步分为是要比较整个分类 结果还是其中的某个簇
第113页

度量簇的正确性
?

用于评估簇各方面的评估度量或指标分成如下三类 ?监督的(外部指标): 度量聚类算法发现的聚类结构 与某种外部结构的匹配程度。例如熵,度量簇标 号与外部提供的标号的匹配程度 ?非监督的(内部指标): 聚类结构的优良性度量, 不考虑外部因素。如SSE(平方误差和)。簇的有 效性的非监督度量常常可以进一步分成两类:
? 簇的凝聚性(紧凑性):度量簇中对象如何密切相关 ? 簇的分离性(孤立性):度量确定一个簇如何不同于 其它簇

第114页

度量簇的正确性
?

用于评估簇各方面的评估度量或指标分成如下三类 ?相对指标: 比较不同的聚类或簇。是用于比较的 监督或非监督评估度量,例如SSE或熵

第115页

通过相关性度量簇的有效性
?

? ?

给定数据集的相似度矩阵和数据集聚类分析得到的 类标号,则可以通过考察相似度矩阵和基于类标号 的相似度矩阵的理想版本之间的相关性,来评估聚 类的优良性 一个理想的簇:它的点与簇内所有点的相似度为1, 而与其它簇中的所有点的相似度为0 如果我们将相似度矩阵的行和列排列,使得属于相 同簇的对象在一起,则理想的相似度矩阵具有块对 角结构:在相似度矩阵中代表簇内相似度的相的块 内部相似度非0,而其它地方为0
第116页

通过相关性度量簇的有效性
?

? ?

理想的相似度矩阵如下构造:创建一个矩阵,每个 数据点一行一列,矩阵的一个项为1,如果它所关联 的一对点属于同一个簇,否则为0 理想和实际相似度矩阵之间高度相关表明属于同一 个簇的点相互之间很接近。 由于实际和理想相似度矩阵都是对称的,所以只需 要对矩阵对角线下方或上方的n(n-1)/2个项计算相关 度

第117页

实际的和理想的相似度矩阵
?

对如下的两个数据集使用K-均值算法得到的簇计算 相似度矩阵
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1

y

x

y

x

Corr = 0.9235

Corr = 0.5810
第118页

通过相似度矩阵可视化的评价聚类
?

按照簇标号调整相似度矩阵的行列次序,然后画出 它们。如果有明显分离的簇,则相似度矩阵应当粗 略的是块对角的
1 0.9 0.8 0.7 0.6 10 20 30 40 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 20 40 60 80 0 100 Similarity

Points
0 0.2 0.4 0.6 0.8 1

0.5 0.4 0.3 0.2 0.1 0

50 60 70 80 90 100

y

x

Points

第119页

随机数据的簇的相似度矩阵
?

随机数据的簇的相似度矩阵
1 10 20 30 40 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 20 40 60 80 0 100 Similarity 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1

Points

50 60 70 80 90 100

Points

y

x

DBSCAN

第120页

随机数据的簇的相似度矩阵
?

随机数据的簇的相似度矩阵
1 10 20 30 40 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 20 40 60 80 0 100 Similarity 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1

Points

50 60 70 80 90 100

y

Points

x

K-means

第121页

随机数据的簇的相似度矩阵
1 10 20 30 40 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 20 40 60 80 0 100 Similarity 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1

Points

50 60 70 80 90 100

Points

y

x

Complete Link

第122页

?

在随机数据上,DBSCAN、K均值和全链发现的簇 的重新排序的相似度矩阵中也存在弱对角模式

第123页

通过相似度矩阵可视化的评价聚类
1 0.9

1 2 6

500

0.8 0.7 0.6

1000

3 4
1500

0.5 0.4

2000

0.3 0.2 0.1

5
2500

7
3000 500 1000 1500 2000 2500 3000 0

DBSCAN

第124页

内部测度: SSE
? ?

?

有更复杂图像的簇很难被分离 内部指标: 不使用外部信息而独立簇结构的优良性 ?SSE SSE可以较好地比较两个聚类结果或具体的两个簇

第125页

内部测度: SSE
?

可以用来估计簇的个数。左图的数据集有10个自然 簇。当簇个数等于10时,SSE有一个明显的拐点
10
6 4 2

9 8 7 6

SSE

5 4

0 -2 -4 -6 5 10 15

3 2 1 0 2 5 10 15 20 25 30

K

第126页

内部测度: SSE
?

更复杂数据集的SSE曲线

1 2 6

3 4

5

7

SSE of clusters found using K-means
第127页

聚类趋势
? ? ? ?

确定数据集中是否包含簇的一种显而易见的方法是 使着对它聚类。 给定数据,几乎所有的聚类算法都会发现簇。 为了处理这一问题,我们可以评估结果簇,至少有 些簇具有好的质量,才能说数据集包含簇 问题在于数据集中可能存在不同于我们是有的聚类 算法所能发现的簇类型 ?尝试使用多种方法,并评估结果簇的质量。如果 簇都很差,则可能表示数据中确实没有簇。

第128页

Hopkins统计量
?

?
?

?

使用统计检验来检验空间随机性 产生p个随机地分别在数据空间上的点,并且也抽取 p个实际数据点。 对于这两个点集,找出每个点到原数据集的最近邻 距离。设ui是人工产生的点的最近邻距离,而wi是 样本点到原数据集的最近邻距离。 Hopkins统计量H由下式定义

H?

?

?
p

p

i ?1

wi ? ?i ?1 ui
p
第129页

i ?1

wi

Hopkins统计量
?

?

如果随机产生的点与样本点具有大致相同的最近距 离,则H将在0.5左右。H接近0或1表明数据是高度 聚类的和数据在数据空间是有规律分布的。 对于p=20和100的不同实验,左图的H平均值为0.95, 标准差为0.0006,右图的H平均值为0.59,标准差为 0.03
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1

y

y

x

x

第130页

聚类:选择聚类的个数
?

如何选择k-均值算法中的k?可能的策略 ?对不同的可能个数进行试验,选择能使所有点离 开它们聚类中心的距离平方的总和达到最小的k值 ?从一个给定的最小个数开始,一直试验到一个较 小的固定的最大值,用交叉验证法找出最好的个 数 ?根据距离平方和标准来决定最佳聚类训练数据的 方法,将总是选择和数据点一样多的聚类。为了 抑制选择很多聚类的方案,必须采用诸如最短描 述长度准则,或采用交叉验证
第131页

如何理解聚类
?

?

?

&nbsp;坦哥,你好啊,关于数据挖掘作业,我试着 先聚类再决策树分析,很多时候都会导致聚类得到 的结果跟决策树有冲突,例如:聚类后得到影响某 个属性的几个属性,但是在决策树分析中决定我感 兴趣的 那个属性的决策树却不存在这几个属性子结点,这 样反而是聚类影响了决策树的准确性了。我想问几 个问题: 1.我发现项目里的两个问题用决策树是可以完全解决, 为什么还要先聚类再用决策树分析呢?
第132页

如何理解聚类
? ?

?

2.聚类分析跟决策树之间有何联系?对于具体问题, 应该如何将它们联系起来分析。困惑中。。。。。。 3.聚类分析在于分类,但是我感觉聚类分析要应用到 实际问题中很困难,请指教。。。。。 我跟很多同学请教过这些问题,发现他们也有类似 疑惑,请坦哥不吝赐教啊。

第133页

如何理解聚类
?

?
?

数据挖掘的任务是寻找有意义的数据模式,但这种 模式不是立刻就能得到 ?有时候根本找不到(明显的)模式 ?有时候的问题不是缺乏模式,而是模式太多 这些数据可能包含很多复杂的结构以至于最佳数据 挖掘技术也不能找出有意义的模式 当挖掘这些数据集以寻找特定问题的答案时,相互 对立的解释往往使彼此相互抵消。

第134页

如何理解聚类
? ?

?

?

象接受无线电信号一样,太多相互竞争的信号叠加 到一起就变为噪音。 聚类提供了一种获悉复杂数据结构的方法,即将竞 争的信号的杂音分解成各自的成分。 当人们试图弄清复杂问题的意义时,往往趋向于将 问题分解为更小的片断,每一个片断可以更简单地 解释。 在许多情况下,非常杂乱的数据集实际上可能由许 多表现较好的簇组成,聚类分析的目的就是如何发 现它们。
第135页

如何理解聚类
?

聚类分析是一种描述性的任务,用来发现数据集的 分布特征。也可以作为对他发现的簇运行的数据挖 掘算法的预处理步骤。

第136页

案例研究:聚类城镇
?

? ?

《波士顿环球报》是服务于波士顿以及东马萨诸塞 州和新罕布什尔南部周围区域的两家大日报之一, 是波士顿的主流报纸。 2003年的日发行量超过457 000份,在周日发行量超 过705 000份。 《波士顿环球报》面临如下问题:波士度核心市场 读者群在缩减,郊区报业市场面临来自地方报纸的 有力竞争,一些读者已流失。

第137页

案例研究:聚类城镇
?

?

为了与郊区报纸更好地竞争,环球报加入了为不同 地区定制的报纸版面,为按照地域划分的12个地区 加入了特别编辑内容。每周有两天,读者都可以读 到为本区精心整理的一些地方报道页。 环球报使用的编辑区域利用的是环球报已有的数据、 常识性内容以及地图,但没有正式的统计分析。

第138页

案例研究:聚类城镇
?

?

编辑区域组成方面有一些限制条件 ?地域必须是地理上连续的,以便运输 ?地域必须适度紧凑,且包含足够人口已证明特殊 化编辑的内容是恰当的 ?编辑区域必须接近于过去做广告的地理区域。 下面采用数据挖掘技术来把相似的城镇聚集在一起 形成编辑区。

第139页

1 创造城镇特征
?

?

在做聚类分析之前,首要的问题是找到描述城镇的 特征,需要包括可以用于表征城镇特点,以及可用 于比较该城镇及其邻近城镇的每个特征的一个列 城镇特征标识可以有几个来源,大部分数据可以从 1990年和2001年城镇级的美国人口普查数据 (census data)得到,包括年龄、种族、宗教信仰、 职业、收入、住宅价值、平均通勤时间以及其他令 人感兴趣的变量。

第140页

1 创造城镇特征
?

?

此外还有外围数据提供商提供的关于订户家庭层次 的数据,还有每个城镇的发行量数据,以订阅者层 次的信息,如优惠计划、投诉电话和订户类型 (日常、 周日或者两者都是)等 数据的处理:本例中通过四个基本步骤来创建城镇 特征 ?聚集 ?归一化 ?计算趋势 ?创建衍生变量
第141页

1 创造城镇特征
?

?

聚集:将较细层次的数据汇总到城镇层次,例如聚 集订户的数据以得出每个城镇中订户的总数和中值 订户家庭收入 归一化:将计数值(例如收入、住宅价值和孩子数目) 转变成百分比。这实际上是把人口差别很大的不同 城镇的数据归一化,为了可以有效地进行对比。例 如2001年有4年大学学历的27573个人住在 Borrkline,这只占到教育水平高的城镇的47.5%。 在波士顿,具有类似学位的人非常多,但只占到当 地总人口的19.4%.

第142页

1 创造城镇特征
?

?

计算趋势:人口普查数据中每个变量都有相隔11年 的两个值可以使用。历史数据的一个令人感兴趣的 地方是可以观察到其中的趋势。如人口的变化:包 括学龄人口的变化、不同族裔人口的变化,或拥有 自有住房人口比例的变化。 创建衍生变量:从已存在的变量中衍生另外一些变 量。例如从邮政编码数据数据中产生各个城镇到中 心城市(波士顿)的距离

第143页

创建簇
? ?

?

?

利用人口统计学和地理学数据描述该城镇的特征标 识 使用这些特征得到的聚类结果不能直接用于创建报 纸的编辑区,因为还有地理方面的约束条件,即编 辑区域必须由相邻的城镇构成。 有相似人口统计学数据的城镇未必在地理上相邻, 这个问题可以通过使用加权的方式来增加形成簇过 程中地理变量的重要性。 但在本案例中最终放弃了地域簇的设计,因为目标 是寻找至少部分基于人口统计学的相似性,更侧重 于人口统计学方面。
第144页

?

Massachusetts东部及 New Hampshire南部各 城镇人口统计学聚类情况

第145页

确定簇的正确数量
?

?

?

处于商业方面的原因,可能需要12个编辑区域,但 不能保证找到这么多好的簇。这直接提出如何为数 据集确定合适数目的簇的问题。 这里使用类似二分K均值的算法。首先以较低的K值 确定簇数目,使用普通的K均值算法构建K聚类,利 用适应度度量(如SSE)确定最差的簇,然后把这个簇 分裂为2个簇,反复重复这个过程,一直到簇数达到 上界。 每次迭代后,记录该簇的总体适应度。

第146页

?

对于实际商业问题,簇的最重要的适应度度量是难 以量化的度量——簇对某个应用的有效性。

按照算法的建议,聚类算法的下一 次迭代将把簇2进行分裂。形成的簇 有明确的差异,但对于环球报感兴 趣的变量而言,所形成的新簇都没 有不同的表现,如家庭递送穿透度 或订户资历等。
Cluster 1B

Cluster 2

Cluster 1AB

第147页

城镇的最终的四个分组
?

簇2包含了50个城镇中的31300个家庭,其中 137000个家庭订阅日报或周末版环球报。 “Best” based on delivery 它是“最佳簇” penetration
Cluster 2

“2nd Best” based on delivery penetration

Cluster 1B

Cluster 1AB

第148页

?

簇2与其他簇和人口总体区分开的变量是住宅价值和 教育程度。这个簇有最高的住宅价值比例、最高的 有4年大学学历的人数比例、最高受教育的品均年数 和最低的蓝领工作人员比例

第149页

? ?

从家庭递送穿透度来看,次好的簇是簇1AA。住宅 价值和家庭收入与总人口的均值非常接近。 簇1B的特征:主要以有最低家庭收入 “Best” based on delivery 历时最久且临近波士顿的订户 penetration
Cluster 2

“2nd Best” based on delivery penetration

Cluster 1B

Cluster 1AB

第150页

簇1AB是唯一主要以地域为特征形成的簇,都是远 离波士顿的城镇,其家庭递送穿透度很低。 ?其住宅价值最低,但家庭收入为平均数。 ? 簇1AB中的人选择在离城市较远的 地方居住,因为他们希望有自己的 住宅(郊区边缘房间较便宜)
?

第151页

利用簇调整区域边界
?

?

聚类项目的目标是确定已存 城镇 在的编辑区域是否最优。每 Brookline Boston 个编辑区域都是处于上述四 Cambridge 个簇之一的城镇集合构成 Somerville 下一个步骤是通过手工方法 Needham 将某些城镇交换到邻近的区 Newton 域,以增加每个区域的纯度。 Wellesley
Waltham
Weston Watertown

编辑区域 所属簇

City
City City City West 1 West 1 West 1

2
1B 1B 1B 2 2 2

West 1
West 1 West 1

1B
2 1B

第152页

?

?
?

除Brookline外,所以处于 city区域的城镇都属于簇1B 中 ?将Brookline交换到邻近 的West1区域 ?将Waltham和Watertown 交换到邻近的City区域 新的West1区域是整个簇2 新的City区域是整个簇1B

城镇

编辑区域 所属簇

Brookline
Boston Cambridge Somerville Needham Newton Wellesley

City
City City City West 1 West 1 West 1

2
1B 1B 1B 2 2 2

Waltham
Weston Watertown

West 1
West 1 West 1

1B
2 1B

有了相似城镇组成的编辑区域,就可以容易的集中对本地内容 提供有针对性的评论,增加发行量和广告销售。
第153页

Microsoft 聚类分析算法
?

?

Microsoft 聚类分析算法提供两种创建分类并为分类 分配数据点的方法。 ?第一种方法是 K-means 算法,属于硬聚类方法。 这意味着一个数据点只能属于一个分类 ?第二种方法是“期望值最大化”(EM) 方法,这是 “软聚类分析”方法。这意味着一个数据点总是 属于多个分类,并会为每个数据点和分类的组合 计算一个概率。 可以通过设置 CLUSTERING_METHOD 参数来选择 要使用的算法。聚类分析的默认方法是可缩放的 EM。
第154页

EM 聚类分析
?

?

在 EM 聚类分析中,此算法反复优化初始分类模型 以适合数据,并确定数据点存在于某个分类中的概 率。当概率模型适合于数据时,此算法终止这一过 程。用于确定是否适合的函数是数据适合模型的对 数可能性。 EM 聚类分析方法的结果是概率性的。这意味着每个 数据点都属于所有分类,但数据点向分类的每次分 配都有一个不同的概率。

第155页

? ?

?

Microsoft 实现提供两个选项:可缩放 EM 和不可缩 放 EM。 默认情况下,在可缩放 EM 中,前 50,000 个记录用 于为初始扫描设种子。如果成功,则模型将仅仅使 用这些数据。如果使用 50,000 个记录时模型不适合, 则会继续读取 50,000 个记录。 在不可缩放 EM 中,总是读取整个数据集,而不考 虑数据集的大小。 ?此方法可能会创建更准确的分类,但内存需求非 常高。
第156页

?

? ?

因为可缩放 EM 作用于本地缓冲区,所以循环访问 数据要快得多,并且此算法对 CPU 内存缓存的利用 率比不可缩放 EM 要高得多。 此外,可缩放 EM 比不可缩放 EM 快三倍,即使所 有数据都可容纳于主内存中也是如此。 在大多数情况下,性能改进不会导致完成的模型的 质量下降。

第157页

k-means 聚类分析
?

?

?

k-means 通过尽量缩小一个分类中的项之间的差异, 同时尽量拉大分类之间的距离,来分配分类成员身 份。 k-means 中的 "means" 指的是分类的“中点”, 它是任意选定的一个数据点,之后反复优化,直到 真正代表该分类中的所有数据点的平均值。 "k" 指的是用于为聚类分析过程设种子的任意数目的 点。k-means 算法计算一个分类中的数据记录之间 的欧几里得距离的平方,以及表示分类平均值的矢 量,并在和达到最小值时在最后一组 k 分类上收敛。
第158页

k-means 聚类分析
?

?

?

k-means 算法仅仅将每个数据点分配给一个分类, 并且不允许成员身份存在不确定性。分类中的成员 身份表示为与中点的距离。 通常,k-means 算法用于创建连续属性的分类,在 这种情况下,计算与平均值的距离非常简单。但是, Microsoft 实现通过使用概率针对分类离散属性对 k-means 方法进行改编。 注意:Microsoft 聚类分析算法不公开用于计算 kmeans 的距离函数,并且在完成的模型中不能测量 距离。但是,可以使用预测函数返回与距离对应的 值,在这种情况下,距离计算为某个数据点属于此 分类的概率。请参阅 ClusterProbability。
第159页

自定义 Microsoft 聚类分析算法
? ?

?

Microsoft 聚类分析算法支持几个参数,这些参数会 影响所生成的挖掘模型的行为、性能和准确性。 设置算法参数 ?这些参数影响生成的挖掘模型的性能和准确性。 CLUSTERING_METHOD:指定算法要使用的聚类 分析方法,默认值为 1(可缩放 EM)。
ID 方法

1 2 3 4

可缩放 EM 不可缩放 EM 可缩放 k-means 不可缩放 k-means。
第160页

?

CLUSTER_COUNT

?指定将由算法生成的大致分类数。如果无法基于 相应的数据生成该大致数目的分类,则算法将生 成尽可能多的分类。如果将 CLUSTER_COUNT 设置为 0,则算法将使用试探性方法最准确地确 定要生成的分类数。 ?默认值为 10。

第161页

?

CLUSTER_SEED

?指定在为建模初始阶段随机生成分类时所要使用 的种子数字。 ?通过更改此数字,可以更改生成初始分 的方法, 然后使用不同的种子比较已生成的模型。如果种 子已更改,但所发现的分类并没有太大的更改, 则模型可被视为相对稳定。 ?默认值为 0。

第162页

?

MINIMUM_SUPPORT

?

?指定生成某个分类至少需要的事例数。如果分类 中的事例数小于此数目,则此分类将被视为空, 并将被丢弃。 ?如果将这个数目设置得过高,则可能遗漏有效分 类。 注意:如果使用 EM,即默认聚类分析方法,则一些 分类可能具有低于指定值的支持值。这是因为会计 算每个事例在所有可能分类中的成员身份,对于某 些分类,可能仅存在最小支持。
第163页

?

MODELLING_CARDINALITY ?指定在聚类分析过程中构建的示例模型数。 ?减少候选模型数会提高性能,但存在遗漏一些好 的候选模型的风险。 ?默认值为 10。

第164页

?

STOPPING_TOLERANCE

?指定一个值,它可确定何时达到收敛而且算法完 成建模。当分类概率中的整体变化小于 STOPPING_TOLERANCE 参数与模型大小之比 时,即达到收敛。 ?默认值为 10。

第165页

?

SAMPLE_SIZE ?如果 CLUSTERING_METHOD 参数设置为其中 一个可缩放聚类分析方法,请指定算法在每个传 递中使用的事例数。如果将 SAMPLE_SIZE 参数 设置为 0,则会导致在单个传递中对整个数据集 进行聚类分析操作。在单个传递中加载整个数据 集会导致内存和性能问题。 ?默认值为 50000。

第166页

?

MAXIMUM_INPUT_ATTRIBUTES

?指定算法在调用功能选择之前可以处理的最大输 入属性数。将该值设置为 0 表示不限制属性的最 大数目。 ?增大属性的数目会大大降低性能。 ?默认值为 255。

第167页

?

MAXIMUM_STATES

?指定算法支持的最大属性状态数。如果属性的状 态数超过此最大值,则算法将使用最常见状态, 而忽略其余状态。 ?增大状态的数目会大大降低性能。 ?默认值为 100。

第168页


第6章聚类分析ppt课件_图文.ppt

第6章聚类分析ppt课件_幼儿读物_幼儿教育_教育专区。第5章 聚类分析本章概述

2019最新第六章聚类分析化学_图文.ppt

2019最新第六章聚类分析化学 - 第六章 聚类分析 ? §6.1 引言 ? §

[课件]第6章 相关分析回归分析和聚类分析PPT_图文.ppt

[课件]第6章 相关分析回归分析和聚类分析PPT_基础医学_医药卫生_专业资料。[课件]第6章 相关分析回归分析和聚类分析PPT 第6章 相关分析回归分析 和聚类分析 本...

最新2019-4SPSS判别分析与聚类分析-PPT课件_图文.ppt

最新2019-4SPSS判别分析与聚类分析-PPT课件_数学_高中教育_教育专区。最新2019-...Tot al 11 11 6 2 100.0 100.0 100.0 100.0 11 11 6 100.0 100....

2019年第五章空间分析的原理和方法.ppt_图文.ppt

2019年第五章空间分析的原理和方法.ppt - 第五章 空间分析的原理和方法 第一节 数字地面模型分析 第二节 空间叠合分析 第三节 空间缓冲区分析 第四节 空间...

2019年-7 第七章 空间分析-PPT精选文档_图文.ppt

2019年-7 第七章 空间分析-PPT精选文档_互联网_IT/计算机_专业资料。2019 第七章 GIS空间分析空间分析是GIS系统的核心功能之一,也是最重 要的功能,是GIS系统...

2019精品第五章聚类分析聚类化学_图文.ppt

2019精品第五章聚类分析聚类化学_数学_自然科学_专业资料。模式识别第三章--

第五章聚类分析Kmeans聚类23页PPT_图文.ppt

2019/9/22 河北大学工商学院 Industrial & Comerricial College , Hebei ...第6章聚类分析ppt课件16... 暂无评价 169页 5下载券 第5章聚类分析ppt...

最新2019-应用多元统计分析北大版第一章-PPT课件_图文.ppt

最新2019-应用多元统计分析北大版第一章-PPT课件_数学_小学教育_教育专区。应用...第五章 判别分析 第六章 聚类分析 分类方法 第七章 主成分分析 第八章 因子...

2019年-信息分析方法课件-PPT精选文档_图文.ppt

2019年-信息分析方法课件-PPT精选文档_数学_小学教育_教育专区。2019 ...方法回归分析法多元统计分析方法因子分析法 聚类分析法 定量与定性相...

2019年-11第十一课生物信息学的基因聚类分析-PPT精选文....ppt

2019年-11第十一课生物信息学的基因聚类分析-PPT精选文档_理学_高等教育_教育专区。2019 基因表达数据的聚类分析基因表达数据主要来自于两个方面:一是基因芯片,这是...

做聚类分析-PPT精选文档_图文.ppt

毛本清 2019.08.27 SPSS中的聚类分析 Spss中的聚类功能常用的有两种: 快速聚类(迭代过程): K-Means Cluster 系统聚类:Hierarchical Cluster 毛本清 2019.08.27 ...

2019年最新-数字电子电路课件第6章6.4-PPT文档资料-精....ppt

2019年最新-数字电子电路课件第6章6.4-PPT文档资料-精选文档 - 6.3.4 常用集成计数器功能分析及应用 (一)采用中规模集成器件实现任意模值计数(分频)器 应用 N ...

Cluster Analysis of聚类分析125页PPT_图文.ppt

Cluster Analysis of聚类分析125页PPT_数学_自然科学...(2019). Journal of the Royal Statistics Society,...【大学课件】方差分析 (... 58页 5下载券 Analys...

2018-2019学年人教版高中生物必修一课件:第6章 实验(共....ppt

2018-2019学年人教版高中生物必修一课件:第6章 实验(共27张PPT)_理化生_高中教育_教育专区 人阅读|次下载 2018-2019学年人教版高中生物必修一课件:第6章 ...

通信原理-第6章 课件PPT_图文.ppt

第8章 差错控制编码 第9章 同步原理 2019/10/4 1 2019/10/4 《通课信程原名理称》课件 第1章 通信系统概述 第2章 信号分析 第3章 信道与噪声 第4章 ...

2019年实践技能 第一站病例分析 PPT课件.ppt_图文.ppt

2019年实践技能 第一站病例分析 PPT课件.ppt_数学_小学教育_教育专区。www....(肺心病、肺炎、COPD等所致I、II型呼衰)## ()结核病肺结核、结核性胸膜...

北京大学统计学经典课件第八章聚类分析28_图文.ppt

北京大学统计学经典课件第八章聚类分析28_中职中专_职业教育_教育专区。 文档贡献者 倪云山 贡献于2019-10-08 1 /2 相关文档推荐 ...

第六章 聚类分析(1).ppt

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 自然科学 ...第六章 聚类分析(1)_数学_自然科学_专业资料。第6章 聚类分析本章目标 ? 辩...

2019年应用统计分析实验R软件.ppt_图文.ppt

2019年应用统计分析实验R软件.ppt_计算机软件及应用_IT/计算机_专业资料。应用...回归分析 四. 判别分析五. 聚类分析 . 主成分分析 ? 基本语法 1. 变量...