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

    谱聚类中基于熵排序的特征向量选择方法    李志伟Summary：Ng-Jordan-Weiss（NJW）是使用最广泛的谱聚类算法之一对于一个K类问题，该算法使用数据集标准化的亲合矩阵的最大的K个特征向量来划分数据已经证明，K-way划分的谱放松解决方法在于对这K个最大的特征向量子空间的划分然而，从大量实验表明，前K个最大的特征向量并不总能检测得出真实的模式识别问题的数据结构所以，谱聚类中特征向量的选取变得很有必要Key：谱聚类 特征向量选择 熵排列：TP301.6 ：A ：1007-9416（2016）07-0043-011 简介聚类方法一直是模式识别和人工智能研究的重要焦点之一聚类的目的在于将数据划分成预期的结果比如，数据的聚类就是将相似的样本划分为一类，不相似的样本归到不同类中在过去的几十年里，许多聚类算法得到了快速发展，这主要包括基于层次的聚类（如单链接、多链接等）和基于划分的聚类（如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 结语本文介绍的熵排列的特征向量选取方法是一种简单的特征排列方法，也可以选择一种多套特征向量排列方法用于特征向量的排序本文旨在通过熵排序的特征向量选取方法，获取能够表征信息的最优特征在将来的工作中将进一步在这个方向上研究Reference[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.数字技术与应用2016年7期数字技术与应用的其它文章基于决策导向非循环图支持向量机的脱机手写体汉字识别一种快速的基于模板差分的红外行人跟踪算法网络打印机的网络安全防护分析计算机人工智能识别技术的应用瓶颈计算机网络安全数据加密技术的实践应用谱聚类算法学术论文研究与探讨  -全文完-。