数据挖掘学习笔记--聚类分析（一）
unsupervised learning
unsupervised learning
unsupervised learning
基于聚类（clustering）的方法将物理或抽象对象的集合分为相似的对象类或簇的过程是一种无监督的学习方式【unsupervised learning
--基于划分
k-means 基本K均值方法
方法：
1.选择K个点作为初始质心
2.repeat
3. 将每个点指派到最近的质心，形成K个簇
4. 重新计算每个簇的质心
5.until 质心不再发生变化
优点：
聚类快
缺点：
a.常终止于局部最优
b.只适用于数值属性聚类
c.对噪声和异常值敏感
d.选择不同的初始值，可能产生不同的聚类结果
f.不适合发现非凸面的簇
**** 二分K均值
方法：
1.初始化簇表，使之包含由所有的点组成的簇
2.repeat
3. 从簇表中取出一个簇
4. {对选定的簇进行多次二分“试验”}
5. for i = 1 to 试验次数 do
6. 使用基本K均值，二分选定的簇
7. end for
8. 从二分试验中选择具有最小总SSE的两个簇
9. 将这两个簇添加到簇表中
10.until 簇表中包含K个簇
**
**
--基于层次
凝聚的过程是从每个单独的一点出发作为一个独立的小群体开始；随后逐步将两个最近的小群体进行合并。（需明确聚集体之间的邻近度计算方法）
splitting-based: Starting from a cluster that encompasses all the points, at each step, a cluster is split until only single-point clusters remain. (Determine which cluster to split at each step and how the splitting is performed.)
基本凝聚层次聚类算法：
1.如果需要，计算邻近度矩阵
2.repeat
3. 合并最接近的两个簇
4. 更新邻近性矩阵，以反映新的簇与原来的簇之间的邻近性
5.until 只剩下一个簇
--基于密度
通过基于密度的方法将簇被视为由低密度区域分隔开的高密度对象区域D_{\text{density}}(x), 可以用于去除异常点数据并识别具有任意形状的簇。
DBSCAN (Density-Based Spatial Clustering of Applications with Noise)
方法：
(1) Eps领域的最大扩展幅度 (2) MinPts被定义为一个核心对象在其Eps领域内至少拥有的顶点数目
1.将所有点标记为未访问(unvisited)
3. 随机选择一个未访问的点p
4. 将p标记为已访问 (visited)
5. 如果p的邻域（Eps为半径）至少有MinPts个点 （：则p是一个核心对象）
6. 创建一个新簇C，把p添加到C中
7. p的领域记为N(严格来说，N是p的密度可达域)
8. 对N中的每个点q
9. 如果q未访问
10. 将q标记为已访问
11. 如果q的邻域至少有MinPts个点，将这些点都添加到N中
12. 如果q还未属于任何一个簇，则将q添加到簇C中
13. 输出C
14. 否则将p标记为噪声点
15. until 所有点都标记为已访问
优点：
可以发现不同形状和不同大小的簇
缺点：
该模型的参数设置较为棘手，在实际应用中容易出现偏差。具体而言，在MinPts值的选择上存在一定的挑战性：当MinPts值设置偏小时（即MinPts值过低），可能会导致两个原本分开的簇被误认为是一个整体；反之，在MinPts值过大时，则可能出现将某些本来存在的簇误判为噪声点的情况。
b.无法发现数据集中密度不同的簇
学习资料：
《Introduction to Data Mining》由TAN Pang-Ning、STEINBACH Michael以及KUMAR Vipin等专家原著，并由FAN Ming与FAN Hongjian担任译者
深入浅出--基于密度的聚类方法