denclue 聚类_【读书笔记-数据挖掘概念与技术】聚类分析：基本概念和方法
主要的聚类方法可以划分为以下几类：
划分方法
层次方法
基于密度的方法
基于网格的方法
聚类是典型的无监督学习。
wiki：数据聚类方法主要可分为结构化或分散型。其中一类依赖于先前成功的聚类工具进行分类处理；另一类则是一次性地确定所有类别划分。这些结构化方法可以在自上而下或自下而上的方向进行操作；其中自下而上的策略则将每个对象单独作为初始分类开始，并逐步融合相近的对象；而自上而下的策略则是将所有对象作为一个整体进行分类处理，并逐步细化成更小规模的子类别群。另外一种分割式聚类方法是一种预先决定生成类别数量的方法；它已经被成功应用于自下而上的层次聚类技术中。基于密度分布的聚类技术旨在识别数据空间中具有高密度区域的类别；其中DBSCAN与OPTICS被认为是两种最具代表性的基于密度的方法；这些技术通常需要预先估计合适的参数值才能实现有效的应用
划分方法：把对象组织成多个互斥的组或簇
K-means——K-均值
优点：简单
缺点：受离群点影响较大，因为它基于形心
在初始阶段，在C中随机设定3个中心点；所有数据点尚未参与聚类过程，并且都被默认标记为红色；如图所示。
开始第一次迭代：将每个数据点根据初始中心点位置进行着色这一操作由代码中的第41至43行实现。随后，在第45至47行中会重新计算三个新的中心点的位置，并将结果展示在下图中。
可以看出，在选定的中心点位置上进行随机选择所得的结果并不十分理想。而经过下一轮迭代计算后得到的新结果则更为优化。
观察者得以初步勾勒出物体的大致形状。经过两次迭代后系统趋于稳定状态。最终结果如下：
不过就如前面所述 k-means 也并非无懈可劲 尽管在多数情况下也能收敛至一个令人较为满意的解 但是一旦碰上某些特殊场景或随机初始化效果欠佳 可能会导致模型陷入并不理想的局部最优解 比如说我们可以尝试选择以下这些初始聚类中心作为参考
最终会收敛到这样的结果：
不得不承认这是一个不太令人满意的结果。不过实际上大多数情况下 k-means 的结果都很令人满意；它是一种简单高效且广泛应用的聚类方法。
K-中心点
把均值换成了中心，围绕中心点的划分(PAM)。
如何运用在大数据集？
层次方法
值得注意的是，在层次聚类过程中存在不可逆性特征。具体而言，在采用凝聚法将两个数据集合并之后，在分立法下无法恢复它们先前的状态；反之亦然。此外，在应用层次聚集体方法时研究者必须明确何时终止聚集体过程以便获得预期数量的类别划分结果；最后在无故情况下切勿滥用该方法最好将其应用于潜在具有层级结构的数据类型中
该方法中的簇之间存在层次结构关系。如图所示，在该层级下有5个具体的簇群：其中第一层包含了数据样本1号至2号；第二层则包括数据样本4号至5号；随着我们从下往上遍历整个分类树时会逐步减少这些簇的数量；由于整个分类树被完整保存下来因此方便用户了解不同层级上的分组情况
基于凝聚的层次聚类方法从小单元开始逐步合并：每个单独的对象最初自成一个簇，并通过迭代合并的方式逐渐形成规模更大的簇——AGNES算法
分层聚类技术：从小到大的逆过程始于将所有对象归入一个单一的簇中作为层次结构中的根节点——DIANA
wiki：层次聚类算法有两种主要类型：一种是自底向上的凝聚型算法（bottom-up），其过程是从单个数据点出发逐步合并成簇；另一种则是自顶向下的分裂型算法（top-down），它则基于某种相似性度量指标进行数据点间的分割
所有正数指标均可用于评估一对观测值间的相似程度。
决定一个类别是否分裂或合并的一个关键标准是一个连续性的基准。
它是基于两两观测值间距离计算得出的数值指标。
在一个指定高度上切割此树，可以得到一个相应精度的分类。
聚集型层次聚类
Raw data
它的层次聚类树如下图
Traditional representation
簇与簇之间的连接度量：
在层次聚类中被普遍采用的是凝聚式方法。在过程运行中会生成一系列划分阶段：最开始时有n个独立的一人群组；随后逐步形成多层级次结构；最终形成的群组将整合所有研究对象。虽然凝聚式聚类有多种实现方式，但其核心操作机制在本质上具有相似性，在每一次迭代步骤中都会系统地将当前最近距离的对象或类别进行合并；具体实现的不同主要源于对个体间或群体间关联程度计算策略的不同选择。
单连接聚类算法（single-linkage clustering method），又称最近邻（nearest-neighbor）方法。该算法基于数据的距离矩阵进行操作，并通过计算两类之间数据点之间的最小距离来定义类间距离。值得注意的是该方法忽略了各类之间的结构信息可能导致结果出现混乱的情况特别是在处理大规模数据时可能会出现所谓的链式效应即当两个类别之间存在中间点时它们可能会被错误地归为一类为此该算法也常用于分裂型聚类以便于区分那些彼此间最接近但又与其它类别关系较远的数据点
全连接算法（complete linkage algorithm），又称最远邻（farthest neighbour）方法。（此处"neight"应为"neighbor"）该方法同样基于相似度矩阵或距离矩阵进行计算，在其中两组之间的距离被定义为其最大间距，并未考虑各类之间的内在结构其结果往往呈现出较为紧密的类别分布
BIRCH：使用聚类特征树的多阶段聚类
集合平均连结（group average linkage），即为UPGMA（Unweighted Pair-Group Method using the Average approach）。与前面两种方法类似，在相似度矩阵或距离矩阵的基础上展开分析。然而，在计算过程中采用的是两类数据间的两两平均距离作为基础衡量标准。（距离）处于单连锁法与全连锁法之间的中间位置。该算法倾向于优先合并差异较小的类别群。
质心连锁(centroid linkage)，又称为UPGMC(Unweighted Pair-Group Method using Centroid approach)。与之前的方法不同之处在于其计算基础是距离矩阵以及原始数据信息。具体而言，在计算个体与其他组别之间的相似性时，默认采用的是个体与各组重心（即所有组员数据均值计算得出）之间的平方欧几里得距离（也可以采用其他度量方法)，这种方法虽然能够有效避免因缺少原始数据而产生的解释模糊性（如"重心"概念本身的问题），但可能会对某些特殊情况下的数据分析产生一定影响
中值连锁（median clustering），也被称为WPGMC（Weighted Pair-Group Method using Centroid approach）。与之前的不同之处在于，在计算群集质心时，将合成该群集的两个组成部分（group-group, individual and group？）采用相同的权重进行计算。换句话说，所得到的结果实际上就是这两个组成部分质心平均值的结果。
Chameleon：采用基于动态建模的多阶段层次聚类方法实现凝聚层次聚类算法。通过子簇间的相似度进行反向合并，并且其中每个簇的互联性和邻近性由指标RI和RC来衡量。
概率层次聚类：通过概率模型量化簇间差异，在实际应用中能够有效规避传统层次聚类方法遇到的一些局限性：1)在实际场景中选择合适的距离度量往往面临诸多难题；2)当应用该方法时要求数据对象必须完整无缺；3)大多数基于启发式的算法在每一步都需要进行有效的合并与划分操作, 因此其优化标准不够明确.
步骤：
1：假定数据点符合某种分布；
2：求出模型生成的概率；
3：求模型生成的似然；
4：使得似然最大，求出分布中的参数；
5：求出两簇之间的距离；
基于密度的方法——用于发现任意形状的簇
DBSCAN,OPTICS,DENCLUE
DBSCAN:一种基于高密度连通区域的基于密度的聚类 概念：
半径；(用户给定)
核心对象的领域中要求的最少点数；(用户给定)
领域的密度可以简单地用领域内的对象数度量；
直接密度可达；
密度相连；
OPTICS：通过点排序识别聚类结构 概念：
核心距离；
可达距离；
DENCLUE:基于密度分布函数的聚类
基于网格的方法——空间驱动 优点：处理速度快
STING：考察存储在网格单元中的统计信息
CLIQUE：基于网格和密度的聚类方法，用于高维数据空间中的子空间聚类
STING:统计信息网格——基于网格的多分辨率的聚类技术
CLIQUE：一种类似于Apriori的子空间聚类方法
聚类评估
推断或预测聚类趋势——在该数据集上进行聚类分析是有意义的, 当且仅当观察到显著的非随机结构特征 霍普金斯统计量用于检验空间分布中变量是否存在空间随机性
确定簇数 法1：
法2：
确定聚类质量 外在方法——监督方法
核心：给定基准，对聚类赋予评分
同质性：簇越纯越好
完全性：属于相同类别的对象分配到相同的簇
碎布袋：无法与其他对象混合的类别，在将异种对象放入单一的簇中应当受到比混合放置更大的惩罚
小簇保持性：在聚类过程中若未能正确划分小类别，则会导致它们更容易被忽视。
度量：BCubed精度和召回率
内在方法——无监督方法
没有基准可用
轮廓系数：考察簇的分离情况和簇的紧凑情况