首页 理论教育基于RNN的层次聚类算法介绍

基于RNN的层次聚类算法介绍

【摘要】:RNN算法对标准层次聚类的合并准则和相似度度量做了相应的改进,从而降低了其复杂度,使其更适用于大规模的数据集。当合并最近邻对得到一个新的簇时,需要重新计算该簇与其他各个簇的相似度,如果通过平均值的距离来度量两个簇的距离,其计算复杂度仅为O,但是由于本书采用的是平均距离,则需要通过更为有效的方法进一步降低复杂度。对于低维数据,还可以通过更为有效的最近邻搜索技术进一步降低复杂度。

RNN算法对标准层次聚类的合并准则和相似度度量做了相应的改进,从而降低了其复杂度,使其更适用于大规模的数据集。该算法的基本原理虽然在20多年前已经提出,但是直到最近几年才被应用在目标识别领域[127]。RNN算法的核心思想是构造相互最近邻对(Reciprocal Nearest Neighbor Pairs,RNNP),也就是一对互为最近邻的数据点,这就满足了聚类的可还原性——当两个簇CiCj进行合并之后,相对其他任意簇Ck的相似度要减小,其表达式如下:

simCiCj)≥sup(simCiCk),simCjCk))⇒

sup(simCiCk),simCjCk))≥simCiCjCk) (6-4)这就保证了合并最近邻对时不改变与任何其他簇的最邻近关系,而且该性质对于平均距离和平均值的距离两种簇间距离度量方法来说,都是完备的。令X={x(1),…,xN)}和Y={y(1),…,yM)}为两个簇,则这两种簇间距离度量的定义为

本书采用平均距离作为两个簇的相似度度量,在聚类过程中为任意一个数据点建立一条最近邻链(Nearest Neighbor Chain),通过最近邻链来简单有效地寻找到最近邻对。具体步骤如下:算法:基于最近邻链的RNN凝聚聚类

//随机选定一个数据点vV初始化链表L

//剩余的数据点都包含在集合R

//在集合R中搜索下一个最近邻点并计算相似度

//没有找到最近邻对,把s添加到最近邻链中

//找到最近邻对,合并链表最后两个节点

//丢弃当前链表

//重新随机选择一个数据点vR建立一个新链表

整个聚类过程需要3(N-1)次迭代,其搜索最近邻点的时间代价最低可以降到O(n)。当合并最近邻对得到一个新的簇时,需要重新计算该簇与其他各个簇的相似度,如果通过平均值的距离来度量两个簇的距离,其计算复杂度仅为On),但是由于本书采用的是平均距离,则需要通过更为有效的方法进一步降低复杂度。

μxμyσ2xσ2y分别为簇XY的平均值和方差,两个簇的平均距离(在欧氏空间中)可以用下面的公式表示:

采用这种形式来计算簇间距离,只需要储存每个簇的平均值和方差。当合并最近邻对产生新簇的时候,新簇的平均值和方差计算公式如下:

如此一来,算法的时间复杂度为O(n2),空间复杂度为O (n)。对于低维数据,还可以通过更为有效的最近邻搜索技术进一步降低复杂度。