使用knn方法的信息论聚类剖析.docx

使用knn方法的信息论聚类摘要我们发展了一种新的基于使用knn方法的密度聚类的隐式估计无参信息论聚类算法。相较于核函数算法，我们的分层knn方法关于参数选择方面是非常具有鲁棒性的，以及其一个关键的指标是能够探测不同规模的距离。尤其重要的是使用了两个不同的取决于聚类内部的熵或者交叉类的交叉熵决定的k值，和为了最终的聚类在不同的聚类方法里选择出一个聚类集合的使用。我们进行了聚类的实验和得到了满意的效果。Introduction聚类在模式识别和机器学习领域是基础、重要的组成部分。在这个领域，有大量的文献和聚类方法，例如参考文献[1][2]大体的介绍，或者是[3][9]再这个领域的特别的工作。很多方法都是采用局部的方法，就比较一对数据点的距离这方面来说，就有像单一链接的层次聚类[10]及其变体[11].众所周知的全局方法就是k-means，其在类[12]的方差方面优化了紧性准则。因此，这个方法仅仅采用了数据的二阶统计量。这些阐述关键的意义是最近的发展的基于信息论的全局聚类的成本函数，如熵、散度或者互信息，这同策略包含了更高阶的统计信息。如图例所示，一阶和二阶的统计在图一所示函数间是不足区别的。一些在这个方向做出尝试的包括[14][15],提出了确定的退火方法，即根据最大熵值概率分布，采样点和聚类代表相关。一个相关方法应该于两列聚类的研究被提出在[16],基于平均场理论近似于最小化的相对熵。类似的算法被[17]提出。最小化分区观测数据的期望熵提出在[18-20]，使用了高斯混合模型。最近一种基于互信息的方法已经收到高度关注。就是所谓的信息瓶颈方法[21],并推导泛化率失真理论。它已被广泛的应用于[22-27]。对于最近的互信息的聚类方法，请参阅[28,29]。在文本分类的背景下，一种基于詹森 - 香农散度聚类代价函数被提出[30-32]。也参阅[33]。上述信息论聚类方法的共同特点是他们的参数化性质，在这个意义上所期待的概率函数（pdfs）的形式是特定的。非参数信息论聚类（ITC），在另一方面，提出了在[34,35]，属于信息理论学习（ITL）方法的大家族（参看[36-38]和其中的参考文献）。采取的方法是使用梯度下降的方法去全局优化在基于Renyi的二阶熵[39]与隐含基于Parzen窗[40]对非参数密度估计聚类的散度。Parzen窗也被称为核密度估计[41]，包括一个带宽或者平滑度或参数的选择。所得到的结果是有潜力的，但显示了对核带宽选择的敏感性，特别是对于不同的聚类规模在类内的数据的扩散的意义。这个问题有内核算法出现得到一定的缓解，但产生了一个非常缓慢的过程与几个临界超参数。参照图2，一个玩具数据例子，其数据集包括上个不同规模的特性，对于例示类型的数据集这是有问题的基础上整个数据空间中的固定的内核带宽选择一个聚类方法。在这项工作中，我们感兴趣的是利用另一种众所周知的非参数密度估计方法，即k最近邻（KNN）方法[42]，在框架中信息论聚类[34,35]。这根据一个事实，knn是一个固有的适应于本地大规模数据的一个方法，相比于Parzen窗是更具有鲁棒性，其中的簇的规模不同于在数据空间时。使用KNN信息理论的方法已被证明给渐近无偏和均方一致估计[43,44]。另请参见[45]。在本文中，我们选择把重点放在分层方法来优化K-NN信息论代价函数，而不是大多数其他的方法的信息论聚类。有对这种方法的好处，作为层次结构本身可以提供关于数据的结构的信息。我们的工作包括新的贡献：我们改进了knn ITC的方法，而不是基于核方法（这基本框架下，所有其他ITL方法[36]的基础）。作为关键特性，我们表明，我们的方法能够检测和适应不同规模的集群。相对于其他k近邻方法，我们利用两个不同的k值，这取决于一个群集内部熵是否是被估计的，或一个横跨簇交叉熵估计。整个实验两个k值是固定的。没有必要对参数k调整。此外，该算法利用了基于效果的聚类的一个形式，在这个意义上，几种可能的聚类方案，基于成本函数，投票的值，以便最终聚类结果[46]。得到很好的结果。分层的Parzen窗的实现为基础的信息理论聚类应用，使与所提出的K-NN方法直接比较。在非参数信息论聚类K-NN文献是相当有限的。最接近我们的工作[47]，它改进了基于香农熵的一种划分的算法优化基于熵互信息，用一种特殊的K-NN估计，得到所有的k值。在我们的分层算法中，我们已经实验了类似的一种平均的K-NN估计，但并没有取得令人满意的结果。其他有些相关的方法是[48,49]，每个做层次聚类。本文的其余部分安排如下。我们首先在section2推导的基本的knn的无参数pdf估计。在section3，我们首先讨论的信息论将涉及我们的最终的聚类程序，并说明如何估计这些的量。接下来，我们介绍我们的聚类算法，基于构建一个信息论