使用knn方法的信息论聚类

使用knn方法的信息论聚类摘要我们发展了一种新的基于使用knn方法的密度聚类的隐式估计无参信息论聚类算法。相较于核函数算法，我们的分层knn方法关于参数选择方面是非常具有鲁棒性的，以及其一个关键的指标是能够探测不同规模的距离。尤其重要的是使用了两个不同的取决于聚类内部的熵或者交叉类的交叉熵决定的k值，和为了最终的聚类在不同的聚类方法里选择出一个聚类集合的使用。我们进行了聚类的实验和得到了满意的效果。1.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信息论代价函数，而不是大多数其他的方法的信息论聚类。有对这种方法的好处，作为层次结构本身可以提供关于数据的结构的信息。我们的工作包括新的贡献：我们改进了knnITC的方法，而不是基于核方法（这基本框架下，所有其他ITL方法[36]的基础）。作为关键特性，我们表明，我们的方法能够检测和适应不同规模的集群。相对于其他k近邻方法，我们利用两个不同的k值，这取决于一个群集内部熵是否是被估计的，或一个横跨簇交叉熵估计。整个实验两个k值是固定的。没有必要对参数k调整。此外，该算法利用了基于效果的聚类的一个形式，在这个意义上，几种可能的聚类方案，基于成本函数，投票的值，以便最终聚类结果[46]。得到很好的结果。分层的Parzen窗的实现为基础的信息理论聚类应用，使与所提出的K-NN方法直接比较。在非参数信息论聚类K-NN文献是相当有限的。最接近我们的工作[47]，它改进了基于香农熵的一种划分的算法优化基于熵互信息，用一种特殊的K-NN估计，得到所有的k值。在我们的分层算法中，我们已经实验了类似的一种平均的K-NN估计，但并没有取得令人满意的结果。其他有些相关的方法是[48,49]，每个做层次聚类。本文的其余部分安排如下。我们首先在section2推导的基本的knn的无参数pdf估计。在section3，我们首先讨论的信息论将涉及我们的最终的聚类程序，并说明如何估计这些的量。接下来，我们介绍我们的聚类算法，基于构建一个信息论的使用分层策略进行了优化成本函数。在各种聚类实验中获得的结果在section4展示。这些结果和使用Parzen窗估计算法进行了对比，。一些讨论是在section5中提供，section6是文章的总结。2.使用knn的无参密度估计假设一个d维数据集从概率密度函数（pdf）产生。作出无参数的假设的结构，一个k最近邻的密度估计被给定这里，是中心x的超体积上，其半径适应x和其第k个最近邻之间的距离。对于d维的超球，其体积为：其中，是伽玛函数和矢量从x到它的第K近邻的数据集的正态欧氏距离。直观地，估计器是直方图的一般化。然而，代替固定的块大小的，块被有效给定为变化的空间的，为了获得x的第k个最近邻。在一般情况下，对于k值的选择，不存在被广泛接受的标准。在K-NN估计表现非常不同于核密度估计[41]其中所谓Parzen窗是一个平滑固定的宽度直方图单元，其中宽度由确定。所述Parzen窗是密度本身，如高斯函数。存在的rule-of-thumb方法来选择窗口大小[50]。对于在D维多元数据，一个例子是Silverman的规则其中是标准偏差估计通过最大似然数据中获得的平均值，，其中有i行i列的经验协方差矩阵[51]。为了说明一些这两个非参数密度估计方法之间的差异，可以参考图3，一维数据是沿水平轴示出。在图中，使用数据的平均标准差的Parzen窗估计值显示为（橙色）的圆圈线。注意，估计在整个数据的空间是光滑的，但实际上太光滑，特别是在数据点密集的区域。对于（紫色）正方形线，Parzen窗宽度参数已经减少。在这种情况下，估计在致密区域得到改善。然而，该宽度是现在非常小，密度估计变得稀疏使各个数据点非常敏感。使用K-NN（k=3）密度估计采用体积捕获第k个邻居的宽度，我们观察到的（蓝色）三角形线能与真实的密度函数十分接近，虽然只是分段光滑。这是在区域密度和数据稀疏度都是真实的。3.k-nn信息论聚类在本节中，我们将简要提供在聚类方法中的信息论学习背景。然后，我们改进k近邻估计器用于有意义的包括聚类的成本函数。我们简要地Ÿ讨论了多类情况，并提供聚类算法优化伪代码。3.1简要的信息论学习背景信息论学习的关键量，所提出在[36,52,53]，是Renyi的二阶熵，由下式给出其中一个主要的因素是基于使用公式（3）的核密度估计（H（P））。对聚类特别有趣的是一种基于Renyi的二阶熵散度度量。散度的度量提供了量化的两个概率密度函数和接近程度的方式。一个这样的例子是柯西-施瓦茨（CS）的散度定义为，其中，注意的是这个方法是对称的。对于时，它就满足，因此。散度可能也会被表达成Renyi熵的形式，由于其中表示一个交叉熵的度量[36]。一般化到M个不同的pdfs的扩展形式为：其中是一个正则化因子使得散度量固定一个聚类的数量。3.2使用knn的经验散度测量为了利用基于一组数据样本的knn估计器的自适应性质，我们估计器代入式（6）（多簇扩展是直接的），得到一个经验基于knn的柯西-施瓦茨散度。假设一下集合从，描述于，同样的，描述于。1.使用knn估计熵值，注意。使用样本均值的估计器技术，我们有此外，当插入knnpdf估计器时，给定公式（1）得到：强调的是，我们使用符号计算超体积关于所述集合与相关联。以类似的方式用于估计器。2.使用k近邻估算交叉熵：当估计交叉熵，如上述类似的方法时，具有一定的差异。首先考虑。用样本均值逼近，我们有这里，表示超体积在点相关的和第k个最近邻在集合相关的的距离。注意的是，基于k-NN进行估计，在一般的时。因此，估计过程产生一个不对称的CS的散度量。出于这个原因，在k近邻估计，我们修改的CS散度量使其强制对称，如下：经验性的，这能是CS的散度修改的knn估计量为，其中基于k-NN此CS散度估计作为基础，服务我们新的无参数信息论聚类算法，在接下来的小节进行描述。扩展到多个聚类是以下的公式（8）的形式。3.3聚类策略和最优化算法我们采取的总体聚类策略如下：目的是要分配数据点到的集群中，使得所得簇的pdfs之间在CS散度最大化。所提出的K-NN过程将使用在所有的散度估计中。为了实现我们的聚类目标，我们采取迭代聚类和-重新聚类的方法创建群集分配的层次结构。为了解释该方法背后的基本原理，假设首先数据点的子集已被分配给组（这可以以各种方式来完成）。现在考虑未分配的数据点。它已经存在的集群应该这个数据点被分配到？我们的方法是这个数据点分配到集群这使整体的CS散度尽可能大，这是最直观的感觉。此外假设所有的数据点通过上述的方法都被聚成多个群集中。为了可以降低聚类的数目，如果一个应该删除一个簇中，然后重新聚类的成员，这簇我们应该选择？凭直觉，再次，我们的方法是在剩余类里CS散度最大那个类。我们的聚类算法开始由组成的Kinit类的数据的子集初始化聚类。这可以通过任何数目的聚类例程来完成。我们选择的Kinit种子的Ninit点聚类每个点由从一组种子点生长的聚类，在每个步骤分配的最近点到群集点，到初始组之一。这将创建集群。接着，一个簇被去除，它的成员被重新分配到剩余的类里。这由一个降低的类的数目。重复该过程迭代地如在算法1中描述，直到Kend类完成。此过程假定，Kend，是已知的。注意，算法1的3行和10，数据点被认为是一次一个的，用于分配给其中之一的现有在当前迭代的的类。所采取的方法是，找出最接近已经被聚类的点，并以该数据点分配给最大化散度的群集。该算法已经呈现的方式表明，有三个参数必须选择，分别是K，Kinit和Ninit命令。根据我们的经验，后两个参数不是关键的，只要它们是“合理的”;只要使用kinit不要太小的，在很广适用范围内的Kinit和Ninit，算法表现很好，（给算法几重集群步骤终止之前），Ninit是不是太小（人为给算法一个小的聚类种子）。接着，我们将回到开始说的地方。然而，k值是更关键的，就如基于Parzen窗聚类[34]的值一样关键。在接下来的小节中，我们讨论能够完全解决这个问题的方法。3.4两个不同的k值传统上，当使用knn作为积分部分作为被估计的成本函数，面临着一个选择k的问题。唯一的例外，据作者所知，是前面提到被[47]采用的平均法。在所提出的聚类方法，我们采取不同的方法。当使用单个值k实现CS聚类，我们所得到k的值是经历一定的敏感性，就是通常会有聚类出界的情况。为了缓解这个问题，我们提出了一个新的方面使用两个k值，这贯穿所有实验。这背后的想法是，我们的CS成本函数包括两个不同量时，在同一的方式下可能不一定依赖k值。一方面，knn过程通过用于估计一个交叉熵。显然，该区域在空间上是重要的聚焦当评估这部分跨类是类间的边界区域。为了得到一个可靠的估计，在边界区域，我们建议使用k=1为K-NN估计量。也就是说，对于在与关联的集合的任何数据点，超体积是基于最近的邻居与关联的集合计算的。有趣的是，这在一定程度上类似于在基于knn的单链路聚类[10]。当基于类内熵值估计，应该努力涵盖集群占据了整个区域。我们提出通过使用k=kmax用于knn估计量，其中Kmax是到有疑问数据点的最远的邻居。在某种意义上，这类似于完整链路聚类[11]，其中分析是基于点之间的最大距离。参照图4，用于选择两个不同的k。这些我们实验的选择给了极高的