第四期数据挖掘-聚类算法

基本概念1算法介绍2案例分析3数据预处理2数据挖掘从数据中非平凡地提取隐含的，先前未知的，潜在有用的信息用自动或半自动

段，探索与分析大量数据以便及时发现更有意义的模式数据挖掘的任务未知的或者是其他使用一些变量去变量未来的值找到人可以接受的模式来描述数据描述数据挖掘的任务分类（

）聚类（描述）3.发现关联规则（描述）4.

回归（

）5.偏差检测（描述）基本概念1算法介绍2案例分析3数据预处理2数据预处理降维离散化和二元化特征创建聚合1采样256属性转换3数据预处理4基本概念1算法介绍3案例分析3数据预处理2群组的概念是模糊的应该分为几组？四组两组六组群组类别划分聚类每个群组互无关系，都是数据集的一个子集层次聚类可以用层次树的结果来表示的群组划分聚类原始数据集划分聚类范例层次聚类p4p1p3p2p4p1p3p2p1

p2 p3

p4传统层次聚类树状结构p1

p2 p3

p4非传统层次聚类树状结构传统层次聚类非传统层次聚类群组类别分割群组基于中心的群组连续群组基于密度的群组分割群组组内任意数据相似度大，但是组间数据相似度小3个分割群组基于中心的群组组内数据更接近群组中心，组外数据离中心更远4个基于中心的群组连续群组组内数据至少与一个数据相似度大，组间数据相似度小8个连续群组基于密度的群组基于密度来划分群组，高密度的区域为群组，低密度的区域可能是误差6个基于密度的群组相似度以及距离欧式距离欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。余弦距离几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。曼哈顿距离想象你在曼哈顿要从一个路口开车到另外一个

路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。聚类算法K均值算法层次聚类基于密度的聚类K均值算法基本思想每个群组有一个中心点每个结点被分配到最近的中心点初始时确定群组个数算法随机选择K个结点作为初始中心点循环将所有结点放入与其距离（与中心点）最近的群组重新计算中心点当中心点位置不改变时停止K均值算法-2-1.5-1-0

50.511.520x1.510.50232.5y-2-1

5-12-0.5

0 0

5

1 1

5x00.511.522.53y次优化的聚类-2-1

5-11

52-0.5

0 0

5

1x00.511.522.53y最优化的聚类原始结点选取初始结点的重要性-2-1.5-10.511.52-0

5

0x00.511.522.53yIteration

1-2-1.5-10.511.52-0

5

0x00.511.522.53yIteration

2-2-1.5-10.511.52-0

5

0x00.511.522.53yIteration

3-2-1.5-10.511.52-0

5

0x00.511.522.53yIteration

4-2-1.5-10.511.52-0

5

0x00.511.522.53yIteration

5-2-1.5-10.511.52-0

5

0x00.511.522.53yIteration

6K均值算法的评估最常见的标准是误差平方和（SSE）–对于每个节点，误差指的是结点离最近群组的距离–X表示群组中的一个结点，Mi表示群组的中心点。

SSE

Ki1

xCii2dist

(m

,

x)如何选择初始中心点多次运行通过采样或者层次聚类等方法去确定初始中心点选取大于K个初始中心点，从这些结点中选取分布较大的结点聚类后处理二分K均值算法K均值算法的限制当群组有不同性质时，K均值算法工作不是很理想尺寸密度非球型形状K均值算法容易受异常数据影响K均值算法的限制：不同尺寸原始数据K均值(3个群组)K均值算法的限制：不同密度原始数据K均值(3个群组)K均值算法的限制：非球型形状原始数据K均值(2个群组)克服限制的方法原始数据K均值克服限制的方法原始数据K均值克服限制的方法原始数据K均值聚类算法K均值算法层次聚类基于密度的聚类层次聚类产生一组类似树状的层次嵌套的群组可以被可视化为一个树状图类别：凝聚&传统的层次聚类算法需要一个相似度或距离矩阵1

3

254600.050.10.150.213452612345层次聚类算法计算相似度矩阵假定每个数据都是一个群组循环合并两个最接近的群组跟新相似度矩阵当只剩一个群组时停止算法的关键是计算两个群组的相似度初始状态p1p2p3p4p5.p1p2p3p4p5..

...相似度矩阵...p1p2p3p4p9p10p11p12中间状态C1C4C2C5C3C1C2C3C4C5C1C2C3C4C5相似度矩阵...p1p2p3p4p9p10p11p12中间状态C1C4C2C5C3C1C2C3C4C5C1C2C3C4C5相似度矩阵...p1p2p3p4p9p10p11p12合并状态C1C4C2

UC5C3C2UC2

UC1C5C3C4C1?C5????C3?C4?相似度矩阵...p1p2p3p4p9p10p11p12如何确定群组间的相似度MINMAX组平均中心点距离其他测量函数p1p2p3p4p5.p1p2p3p4p5..

...相似度？相似度矩阵MINMINMAX组平均中心点距离其他测量函数p1p2p3p4p5.p1p2p3p4p5..

...相似度矩阵MIN优点原始数据点两个群组可以处理非椭圆的形状MIN限制原始数据点两个群组对噪音与异常点敏感MAXMINMAX组平均中心点距离其他测量函数p1p2p3p4p5.p1p2p3p4p5..

...相似度矩阵MAX优点原始数据点两个群组不容易受到噪音与异常点的影响MAX限制原始数据点两个群组会把大的群组分割成小的群组偏向于球状分割组平均MINMAX组平均中心点距离p1p2p3p4p5.p1p2p3p4p5..

...相似度矩阵j

j

|Clusteri

||Clusterj

|proximity(

Clusteri

,

Clusterj

)

proximity(

pi

,pj

)p

ClusterpiClusteri中心点距离MINMAX组平均中心点距离p1p2p3p4p5.p1p2p3p4p5..

...相似度矩阵层次聚类范例I1I2I3I4I5I11.000.900.100.650.20I20.901.000.700.600.50I30.100.701.000.400.30I40.650.600.401.000.80I50.200.500.300.801.0012

345聚类算法K均值算法层次聚类基于密度的聚类DBSCAN密度：指定半径范围Eps中的数据点数目结点Core

Point：当指定半径范围中包含的数据数目超过阈值MinPts的结点边界结点Border

Point：坐落于其他径范围的非 结点结点的指定半噪音结点Noise

Point：其他的非或边界的结点DBSCAN：、边界与噪音结点DBSCAN算法将所有结点标记为删除噪声点。点、边界点和噪声点为距离在EPS之内的所有 点之间赋予一条边每组连同的 点形成一个簇。将每个边界点指派到一个与之关联的 点的簇中。DBSCAN算法范例原始数据点数据点类型:与噪音,边界Eps

=10,

MinPts

=

4DBSCAN优点原始数据点聚类能够处理噪音与异常能够处理各种形状的数据DBSCAN缺点原始数据集密度不均匀数据(MinPts=4,

Eps=9.75).(MinPts=4,

Eps=9.92)基本概念1算法介绍3案例分析3数据预处理2为了 终端接入，一般会仿冒现网周边一个小区的PCI，导致现网小区出现切换、掉线等指标影响周边一圈 的性能指标，地理上呈圆形分布，因此适合用K均值算法实施聚类，结合ANR可找