[0035] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、详细地描述。所描述的实施例仅仅是本发明的一部分实施例。
[0036] 本发明的技术方案如下：
[0037] 参考图1，图1为本发明实施例提供的一种基于图聚类的高维文本数据特征选择方法流程图，具体包括：
[0038] 文本数据集具有高维小样本、高噪声、高冗余以及样本分布不均衡等特点，这些特点为相应的分析方法和工具的开发带来了极大的挑战。因此，本实施例中，主要采用文本数据来展开讨论。参考图2，图2为本发明实施例提供的高维文本数据特征选择方法流程图。
[0039] 如何评价待选特征是特征降维的关键问题之一。所述特征与类别间的关系，主要是利用改进的信息增益IG作为相关性度量准则。由于信息增益IG偏向于具有更多取值的特征，因此可通过规范化信息增益来确保其具有可比性。
[0040] 根据基于熵的信息理论概念，一个随机变量x的不确定性可以用熵H(x)衡量，如公式(1)所示，其中p(xi)为x的先验概率。
[0041]
[0042] 两个变量x和y，当y已知的条件下，变量x中剩余的不确定性用公式(2)条件熵H(x|y)表示，其中p(xi|yi)为x的条件概率。
[0043]
[0044] x熵值的变化反映了在给定y的条件下x的额外信息，并将其称为信息增益IG(x|y)，计算公式如(3)所示。
[0045]
[0046] 为了弥补信息增益对多值特征的偏差，并试图消除其随机性，可通过均值和标准差进行修正。其计算公式如(4)所示，其中μ，δ分别表示均值和标准差。其中Sim(x,y)∈[0,1]，对于任意的两个变量都具有对称性。当取值为1时，表明任一值的信息都可以完全预测出另外一个值，即两者完全相关，在数据集中所包含的信息量相同；当取值为0时，表示两者完全独立。由此可见，其值越大，表明两个特征间的依赖性越大，冗余性越大，所包含的相同信息也越多。用该公式能够分别计算出特征与类别间，以及特征间的相关性。
[0047]
[0048] 步骤1：首先计算特征与类别间的相关性。假设存在数据集D＝{F,C}，其中F＝{f1,f2,…,fn}特征集，n为特征维度，C为类别标签集。每个特征fi∈F，对于类别标签集C，利用相关性Sim(fi,C)衡量特征与类别间的关系，并进行降序排序；
[0049] 步骤2：剔除不相关特征。为了既能够选取适量的特征个数，降低时间复杂度提高算法性能，又兼顾特征相关性的分布情况，本发明采用双重阈值法剔除特征。即设定两个阈值T1，T2，其中T1用于控制算法性能，T2体现特征相关性的分布情况。阈值T1，T2分别设为和μ+δ。分别计算特征在两个阈值控制下剔除不相关特征后留下的特征个数m1，m2，则最终保留的特征个数为m＝min{m1，m2}，其中m<＝n；
[0050] 步骤3：构造无向加权图：参考图3，图3为本发明实施例提供的加权图G。将留下的特征集F＝{f1,f2,…,fm}，构造加权无向图G＝{V,E,W}。V＝{v1,v2,…,vm}为m个特征集合构成的顶点集，E＝{e1,e2,…,eq}为q条特征间边的集合构成加权边集，W＝{w1,w2,…,wq}为q条特征边的相关性Sim(fi,fj)集合构成的权值集。
[0051] 通过步骤3构建加权图G后，为了能快速构造出类簇间相关度低，类簇内相关度高的特征子集，并在一定程度上消除聚类的盲目性，本实施例采用社区发现算法进行聚类。该算法是基于图理论知识，能够反映特征内部分布结构，并在一定程度上消除聚类的盲目性。
[0052] 步骤4：对于社区网络加权图G＝{V,E,W}，其中V＝{v1,v2,…,vm}为顶点集合，E＝{e1,e2,…,eq}为q条加权边集合，W＝{w1,w2,…,wq}为q条加权边的权值集合。初始化每个特征，将每个特征视为一个独立类簇，得到类簇集S＝{s1,s2,…,sk}，其中k表示形成k个类簇；
[0053] 步骤5：依据Sim(fi,C)降序排序，选取max(Sim(fi,C))的特征作为起始点，搜索特征fi所有邻近特征所在的类簇sj，并分别计算该特征和各个邻近类簇的关联性增益如果 大于阈值T3，且为最大值，则将特征合并到该类簇中，形成新的类簇。此处设置T3＝0.5，该取值可视实验数据而定；反之，则不变：
[0054]
[0055] 其中∑Sim(fi,sj)表示特征fi与类簇sj中所关联边的权重之和；ΣSim(sj,)为所有与类簇sj相关联的边之权重和；ΣSim(fi,)为所有与特征fi相关联的边总权重；∑Sim为图G中所有特征边的权重总和；
[0056] 步骤6：重复执行步骤5，直到所有特征都被划分到新的类簇中，并更新G；
[0057] 步骤7：继续执行步骤4～6，直到各个类簇间的差异度ΔGlo_Sim最大。
[0058]
[0059] 其中 为特征fi所在的类簇号； 表示特征fi与fj是否同在一个类簇内，是则返回值为1，否则为0。用其来衡量聚类的质量，其值越大则说明聚类效果越好。
[0060] 步骤8：剔除冗余数据。通过步骤4～7将特征集F＝{f1,f2,…,fm}聚类得到类簇集合S＝{s1,s2,…,sk}，并进一步剔除每个类簇内的冗余特征。所述以“最大相关最小冗余”原则搜索类簇空间，剔除类簇内冗余特征。由于剔除冗余特征可提高数据质量和数据泛化能力。因此聚类后对于每个类簇sl，其中l∈[1,k]，分别依据“最大相关最小冗余”原则剔除冗余特征，旨在结合特征与类别综合评价冗余特征，从而有效地避免异常特征对分类结果的影响。换言之，如果对于fi∈sl， 存在Sim(fi,fj)<μ+δ&&Sim(fi,C)
[0061] 步骤9：挑选最佳特征子集。参考图4，图4为本发明实施例提供的最佳特征子集选择流程图。为了消除选择最佳特征子集个数的盲目性，所述根据特征与类别间的关系组合出最佳特征子集，主要是在剔除冗余特征后，在每个类簇内根据相关性Sim(fi,C)选择出Top w个特征组成最优特征子集。本实施例中设定w的取值大小为[1,10]，步长为1。所述w值的选取影响数据的分类精确度，同时不同的数据集所选取的w值也不同。据此，本实施例中考虑分类器在同一数据集下得到的最优分类精确度确定所选取的最终w值。
[0062] 所述分类精确度计算公式如下，其能够定量地评价算法的准确定和有效性。
[0063]
[0064] 其中TP：被判定为正样本，事实上也是正样本。TN：被判定为负样本，事实上也是负样本。FP：被判定为正样本，但事实上是负样本。FN：被判定为负样本，但事实上是正样本。
[0065] 以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。
