图9－4K－Means不适用的情况高斯混合模型具有比K－Means更好的灵活性。使用GMM，需要假设数据点是高斯分布，相对于环形的数据而言，这个假设的严格程度与均值相比弱很多。因此，每个高斯分布会被分配到单一的聚类簇。基于这些概率，我们为高斯分布计算了一组新的参数，这样就可以最大化集群中数据点的概率。......
2025-09-29
基于RNN的层次聚类算法介绍
【摘要】：RNN算法对标准层次聚类的合并准则和相似度度量做了相应的改进，从而降低了其复杂度，使其更适用于大规模的数据集。当合并最近邻对得到一个新的簇时，需要重新计算该簇与其他各个簇的相似度，如果通过平均值的距离来度量两个簇的距离，其计算复杂度仅为O，但是由于本书采用的是平均距离，则需要通过更为有效的方法进一步降低复杂度。对于低维数据，还可以通过更为有效的最近邻搜索技术进一步降低复杂度。
RNN算法对标准层次聚类的合并准则和相似度度量做了相应的改进，从而降低了其复杂度，使其更适用于大规模的数据集。该算法的基本原理虽然在20多年前已经提出，但是直到最近几年才被应用在目标识别领域［127］。RNN算法的核心思想是构造相互最近邻对（Reciprocal Nearest Neighbor Pairs，RNNP），也就是一对互为最近邻的数据点，这就满足了聚类的可还原性——当两个簇Ci和Cj进行合并之后，相对其他任意簇Ck的相似度要减小，其表达式如下：
sim（Ci，Cj）≥sup（sim（Ci，Ck），sim（Cj，Ck））⇒
sup（sim（Ci，Ck），sim（Cj，Ck））≥sim（Ci∪Cj，Ck） （6-4）这就保证了合并最近邻对时不改变与任何其他簇的最邻近关系，而且该性质对于平均距离和平均值的距离两种簇间距离度量方法来说，都是完备的。令X=｛x（1），…，x（N）｝和Y=｛y（1），…，y（M）｝为两个簇，则这两种簇间距离度量的定义为
本书采用平均距离作为两个簇的相似度度量，在聚类过程中为任意一个数据点建立一条最近邻链（Nearest Neighbor Chain），通过最近邻链来简单有效地寻找到最近邻对。具体步骤如下：算法：基于最近邻链的RNN凝聚聚类
／／随机选定一个数据点v∈V初始化链表L
／／剩余的数据点都包含在集合R中
／／在集合R中搜索下一个最近邻点并计算相似度
／／没有找到最近邻对，把s添加到最近邻链中(https://www.chuimin.cn)
／／找到最近邻对，合并链表最后两个节点
／／丢弃当前链表
／／重新随机选择一个数据点v∈R建立一个新链表
整个聚类过程需要3(N-1)次迭代，其搜索最近邻点的时间代价最低可以降到O(n)。当合并最近邻对得到一个新的簇时，需要重新计算该簇与其他各个簇的相似度，如果通过平均值的距离来度量两个簇的距离，其计算复杂度仅为O（n），但是由于本书采用的是平均距离，则需要通过更为有效的方法进一步降低复杂度。
设μx，μy和σ2x，σ2y分别为簇X，Y的平均值和方差，两个簇的平均距离（在欧氏空间中）可以用下面的公式表示：
采用这种形式来计算簇间距离，只需要储存每个簇的平均值和方差。当合并最近邻对产生新簇的时候，新簇的平均值和方差计算公式如下：
如此一来，算法的时间复杂度为O(n2)，空间复杂度为O (n)。对于低维数据，还可以通过更为有效的最近邻搜索技术进一步降低复杂度。
相关文章
- 详细阅读
-
聚类算法与特异性发现算法的比较详细阅读
聚类分析发现强相关的对象组，而特异检测发现不与其他对象强相关的对象。图3.8K-means聚类方法与CpecuFind发现特异数据能力ROC曲线K-means聚类；CpecuFind表3.6K-means与CpecuFind发现特异数据能力ROC曲线面积对比上述对比说明，只简单地以簇类大小和对象与类心距离来评估对象的特异程度结果很粗糙，其评价特异数据的能力远不如Cpecu Find方法。......
2025-09-29
-
基本概念：DBSCAN密度聚类算法详细阅读
图9－2DBSCAN基本概念(见彩插)图9－3“直接密度可达”和“密度可达”概念示意描述根据前面基本概念的描述知道:由于有标记的各点M、P、O和R的Eps近邻均包含三个以上的点，因此它们都是核对象；M是从P“直接密度可达”；而Q则是从M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。......
2025-09-29
-
K-Means 聚类算法优化简介详细阅读
算法9.1K－Means聚类选择一些类/组，并随机初始化它们各自的中心点，中心点是与每个数据点向量长度相同的位置。K－Means采用的启发式方式很简单，用下面一组图就可以形象地描述。图9－1K－Means的启发式方式(见彩插)......
2025-09-29
-
Mean-Shift聚类算法详解详细阅读
Mean－Shift聚类是一个基于滑窗的算法，其目的是尝试找到数据点密集的区域。算法9.2M ean－Shift聚类确定滑动窗口半径r，以随机选取的中心点为C、半径为r的圆形滑动窗口开始滑动。Mean－Shift聚类的优点如下:不同于K－Means算法，均值漂移聚类算法不需要知道有多少类/组。基于密度的算法相比于K－Means受均值影响较小。Mean－Shift聚类的缺点:窗口半径r的选择可能是不重要的。......
2025-09-29
-
基于梯度分布的描述子方案介绍详细阅读
Lowe提出的SIFT描述子对后来的许多基于梯度分布的特征描述子都产生了深远的影响。圆形的高斯窗尽量减小那些远离特征区域中心的梯度值影响，这样就避免了微小变化引起的描述子突变。图4-6 由邻域梯度信息生成特征向量图4-6的右图所示的描述符是基于一个2×2个梯度方向直方图，Lowe建议在实际应用中采用16个直方图进行描述效果最好。基于梯度分布的特征描述子都可以较稳健的对发生几何形变、退化、受噪声干扰的图像局部特征进行准确的匹配。......
2025-09-29
-
基于W-O算法的谱估计方法详细阅读
对于双窗系统，EN不再恒等于1，但具有“倒余弦”形状，这样W-O分析谱中在每点都产生旁瓣。同古典谱估计方法相比，由于AR模型是一个有理分式，因而估计出的谱比古典谱估计法估计出的谱平滑。由式易知，X0在k=0时的权值为N，即阶数越高，W-O谱线分辨力越强。图6-9 传统信号加窗与W-O谱分析由图6-9可以看出，用W-O方法得到的信号频谱比用传统加窗方法具有更少、更低的旁瓣干扰。......
2025-09-29
-
聚类的方法：优化数据分析过程详细阅读
聚类的定义与待处理对象特征有关。聚类的方法很多，不同的方法对于同一数据集聚类的结果可能不同。根据层次分解形式的方式，层次聚类方法可划分为凝聚的层次聚类和分裂的层次聚类方法。绝大多数层次聚类方法属于这一类，它们的不同表现在簇内与簇间相似度的定义不同。目前，一般将基于层次的聚类方法和其他聚类技术进行集成以形成多阶段聚类，从而提高聚类质量。它是一种结构辅助聚类的方法，在大型数据库中的速度和伸缩性较好。......
2025-09-29
相关推荐