谱聚类中基于熵排序的特征向量选择方法

李志伟

摘要：Ng-Jordan-Weiss（NJW）是使用最广泛的谱聚类算法之一。对于一个K类问题，该算法使用数据集标准化的亲合矩阵的最大的K个特征向量来划分数据。已经证明，K-way划分的谱放松解决方法在于对这K个最大的特征向量子空间的划分。然而，从大量实验表明，前K个最大的特征向量并不总能检测得出真实的模式识别问题的数据结构。所以，谱聚类中特征向量的选取变得很有必要。

关键词：谱聚类 特征向量选择 熵排列

中图分类号：TP301.6 文献标识码：A 文章编号：1007-9416（2016）07-0043-01

1 简介

聚类方法一直是模式识别和人工智能研究的重要焦点之一。聚类的目的在于将数据划分成预期的结果。比如，数据的聚类就是将相似的样本划分为一类，不相似的样本归到不同类中。在过去的几十年里，许多聚类算法得到了快速发展，这主要包括基于层次的聚类（如单链接、多链接等）和基于划分的聚类（如K-means、高斯融合模型、密度估计和模式选择等）。当数据集变的十分庞大，很多维数对应的属性对于聚类而言就经常变得不相关。为了克服这一问题，子空间学习算法被提出，用于将原始高维空间中的样本映射到低维空间中，得到一种更能够很好反应出原始数据样本的新属性。子空间学习应用已经应用到了很多研究领域，比如：费希尔线性降维分析扩展、流型学习、谱分析、核机器、张量机等领域。

谱分析方法已经成功用于解决大数据聚类和图像分割问题。近年来，由于谱聚类对于数据聚类具有高性能且具有使用简单的优点，吸引了越来越多的研究者的兴趣。这种方法已经成功应用于并行计算、VLSI设计、图像分割、语音分离等方面。谱聚类方法使用数据标准化的亲合矩阵的特征向量来划分数据。而NJW方法是最广泛使用的谱聚类算法之一。对于K个聚类问题，该方法使用数据集标准化的亲合矩阵的K个最大的特征向量划分数据。尽管标准割的谱放松解决方法在于对子空间中的特征向量的划分。但不能保证这K个最大的特征向量总能检测得出数据的结构。

基于熵排列的特征向量选择方法是根据特征向量对聚类的重要性对它们按序排列，然后从排列列表中得到合适的特征向量组合。在排列列表中选择特征向量时，有两种策略。其一，直接从排列列表中选择前K个特征向量。尽管这种方法使用了K个最重要的特征向量，但仍不是总能很好地检测出数据的结构。所以，这种方法的性能比NJW方法优越不多。由于谱聚类中选择的特征向量应该是一个组合优化问题，所以另外一种选择策略，即在排列列表中选择前Km（Km>K）特征向量的最优特征向量组合。基于在许多情况下，对于一个数据样本的抽样能够保留原始聚类的信息这种假设，这种策略先对原始数据集描绘出一种训练数据集，在排列列表的前Km（KM>K）特征向量中提取对应的训练数据，并使用一种特征向量组合评价标准找出合适的特征向量组合，这种策略称为间接特征向量选择策略。

2 基于熵排序的特征向量选择

假设K类数据集合，通过特征分解可以得到X的标准化的亲合矩阵L的特征向量。那么，基于熵的特征向量排序方法如下：

根据信息熵理论，Dash等人提出一种使用熵排序来反应数据的特征。设表示X的标准化的亲合矩阵L的所有的n个特征向量。将V视作包含具有n个特征的n个样本的数据集，V的第i行表示第i个样本数据，表示数据点的第j个特征。从熵理论得知，V的熵被定义为：

（1）

其中，表示样本的概率。实际应用中我们不可能获得每个样本的概率。此时，我们将通过相似度替代概率来计算熵。

（2）

其中，为样本和样本之间的相似性。，为样本和样本之间的距离，计算公式如下：

（3）

其中，和分别表示第k个特征向量的最大值和最小值，所以表示第k个特征向量的最大区间。

根据对的定义，若和相距越近，则它们之间的相似性就越高；反之，相似性就越低。但若较低或较高时，熵就越小；反之，则大。因此，若除去特征向量要比除去更能导致样本的无序，且熵满足，则要比的对谱聚类更重要。为了得到特征向量的排序，每个特征向量都要被移除并计算对应的熵。用表示排序后（降序）的特征向量。并将样本集合作为实例，若5个特征向量的熵满足时，则熵的排列列表为。所以，在这5个特征向量中第4个特征向量是最重要的。

在得到特征向量排序列表后，其中一个简单的特征向量选择方法就是直接选择列表中的前K个特征向量参与谱聚类。与NJW方法中的选取最大的K个特征向量有所不同，这K个特征向量而是通过熵排列得到的对聚类有重要作用的K个向量，称这种特征向量选取为直接选择策略。

另外一种选择策略是根据特征向量排序列表寻找合适的向量组合。众所周知，一个数据集的所有的数据点可看作是随即抽取的。所以，随即抽样的数据多数情况下都保留着原始聚类的信息。而实际应用中，获取某个数据的真实标记信息是可能的。因此，本文首先描述原始数据集的带有真实标记信息的训练数据，然后在排序列表中抽取对应训练数据集的前Km（Km>K）个特征向量，并借助特征向量组合评价指标在所有可能的向量组合中找出最佳的向量组合。我们认为这个最佳的特征向量在子空间中映射到的训练集合中的数据点能够反应得出原始数据的潜在数据结构。

排列列表中的前Km（）个特征向量被认为是对聚类最重要的特征向量。所以，我们的目的就在于在这Km个特征向量中获取K个最佳的特征向量组合。当K不大时（如），对数据聚类至关重要的这Km个特征向量就会更少，所以，在Km=10个特征向量中能够足够找出一个较好的特征向量组合。

3 结语

本文介绍的熵排列的特征向量选取方法是一种简单的特征排列方法，也可以选择一种多套特征向量排列方法用于特征向量的排序。本文旨在通过熵排序的特征向量选取方法，获取能够表征信息的最优特征。在将来的工作中将进一步在这个方向上研究。

参考文献

[1]Zhao F，Jiao L C，Liu H Q，et al. Spectral clustering with eigenvector selection based on entropy ranking[J]. Neurocomputing，2010，73（10）：1704-1717.