决策依赖聚类的高维数据特征选择①

邓廷权，辛丽颖

哈尔滨工程大学 数学科学学院， 哈尔滨 150001

随着信息时代的高速发展， 大数据成为这个时代最具代表性的标志之一． 如何在规模庞大、结构复杂的高维数据中挖掘出最有价值的信息是研究人员和技术工作的热点关注问题． 特征选择是一种有效的高维数据预处理方法， 旨在去除数据中的冗余和不相关信息， 降低数据维度和学习算法的计算复杂度， 是人工智能基础理论中的热点研究主题．

特征选择[1]可分为嵌入式、封装式和过滤式等诸多方法． 嵌入式特征选择[2]将特征选择与学习器融合， 在学习器训练过程中自动地进行特征选择． 该方法缺乏特征选择的可解释性． 封装式特征选择[3]通过从初始特征集合中不断地选择特征子集和训练学习器， 根据学习器的性能来对子集进行评价， 直到选择出最佳的子集． 多次训练学习器导致封装式特征选择方法的计算复杂度很高． 过滤式方法[4]通过设计特征评估度量或相关统计量， 通过阈值法或启发式搜索方法选出具有代表性的特征． 常用的特征评估度量有熵、互信息、信息增益、基尼系数等等． 基于粗糙集[5]、邻域粗糙集[6]和模糊邻域粗糙集[7]的特征选择方法是一类重要的启发式特征选择方法， 通过设计具有良好性质的特征评价函数， 确保选出的特征子集保持甚至超过原始特征的分类能力， 因而得以广泛研究．

启发式特征选择方法需要多次遍历所有候选特征， 一些与分类无关或对分类不产生影响的冗余特征可能会被反复计算， 在数据维度很高的情况下消耗大量的计算资源． 鉴于此， 基于特征聚类的特征选择方法应运而生． 该类方法的主旨思想是通过构建描述数据特征间相似性和关联性的度量， 采用某种聚类方法对特征聚类， 并在各类簇中选择有代表性的特征作为特征选择子集． 文献[8]利用余弦函数刻画特征向量之间的相似性， 采用K-均值对特征聚类， 选择每一簇的中心特征构成特征子集． 该方法在特征聚类时仅考虑到特征间的相似性， 缺乏特征与决策间的依赖关系， 不能确保选出的特征子集具有独立性和最强的辨识能力． 文献[9]基于熵和信息增益概念构建集合间不确定性度量， 描述特征间的相关性和特征与决策间的关联性， 删除不确定度小于某一阈值的特征， 构建以剩余特征为顶点、以特征间的不确定度为边权的最小生成树， 通过阈值法获得特征的簇结构， 并在每个簇中选择一个与决策关联性最大的特征作为特征选择的特征子集． 该方法既考虑了特征间的相关性， 也分析了特征与决策间的关联性， 但缺少特征集与决策间的依赖性以及特征集中元素的冗余性等方面的探索．

针对上述现有特征聚类驱动的特征选择存在的缺陷， 本文提出一种决策依赖聚类的高维数据特征选择方法． 首先， 在邻域粗糙集模型基础上分析了决策关于特征对的依赖度与决策关于单一特征的依赖度间的关系， 构建了特征冗余度度量和特征冗余图， 依据图割理论获得特征划分子集． 为了获得最优的特征分割， 提出了一种簇内特征冗余度最大、簇间特征冗余度最小的聚类簇数评估方法． 通过分析聚类簇中特征关于决策的互信息及特征依存度度量， 提出一种中心度和依存度联合的特征子集确定策略， 实现高维数据的特征选择．

1 决策依赖特征聚类方法

基于聚类思想的特征选择方法是通过构建数据特征间相似性度量， 采用K-均值[10]或其他聚类方法将特征划分为不相交的子簇． 现有大部分方法在构建特征相似图时只考虑特征间的相似性， 忽略数据的标签信息， 导致数据特征与其对应决策类之间缺乏必要的关联性．

本节将基于邻域粗糙集理论构建一种决策依赖的特征聚类方法． 在回顾邻域粗糙集及相关概念基础上， 提出一种基于决策依赖度的邻域依赖度增益的构造方法， 并探讨了其性质． 基于特征间邻域依赖度度量构建特征相似图， 采用谱聚类方法获得特征的类簇结构． 为了获得特征的最优聚类簇数， 我们结合簇内冗余度和簇间冗余度给出一种最优特征簇的选择方法．

1.1 邻域粗糙集基本概念

设DIS=〈U，A，V，D〉为一个决策信息系统， 其中U={x1，x2， …，xn}为非空论域，A={a1，a2， …，am}为条件属性集， 也称特征集，V是对象关于属性的(实数)值集，D为决策属性． 对∀x∈U，B⊆A，x由B确定的δ邻域信息粒[6]为

对任意X⊆U，B⊆A和δ>0，X的关于B的δ下近似和δ上近似[6]分别定义为

下近似可以理解为由邻域信息粒完全包含在X中的对象构成， 上近似包含邻域信息粒可能属于X的对象全体． 在知识发现中， 上近似和下近似被用于对集合X做逼近描述．

在决策信息系统DIS=〈U，A，V，D〉中， 记U关于决策属性集D的划分为U/D={D1，D2， …，DM}， 则对任意B⊆A和δ>0， 决策属性集D的关于B的δ上近似、下近似和边界[11]可分别表示为

决策属性集D关于条件属性子集B的δ正域和依赖度[11]分别定义为

1.2 决策依赖特征关联性度量

依赖度反映的是决策属性与条件属性间的依赖关系． 为了探讨属性对间的关系及其对决策产生的影响， 本文构建决策依赖属性(特征)间的相似度度量． 该度量既描述决策属性与特征对的依赖性， 又刻画特征间的关联性和相似性．

(1)

为特征ai和aj的平均邻域依赖度增益．

证明： 显然．

性质3表明： 特征ai，aj以及二者的联合{ai，aj}产生的邻域信息粒关于决策的认识是相同的(下近似相同)． 在这种情况下， 两个特征存在冗余性， 最多仅需一个特征即可刻画对象的决策特性．

1.3 基于冗余度的特征聚类

基于1.2节的分析， 如果两个特征的联合依赖度增益低， 该特征对具有高的冗余度． 反之， 如果其联合依赖度增益越高， 则特征对决策分类越是必要的， 且这两个特征的冗余性越低． 鉴于此， 本文构建特征冗余图， 并借助图割理论对特征做划分， 形成特征冗余簇．

定义2给定一个决策信息系统DIS=〈U，A，V，D〉，δ>0， 记W=(wij)m×m， 其中

(2)

称W为特征冗余度矩阵．

显然，W是一个相似矩阵， 也可修正W， 将其对角线元素全赋值为0， 表明特征和自身不存在冗余性问题． 在后续的特征冗余图图割划分中， 特征冗余度矩阵修正与否对后续结果没有实质影响． 将特征集A中的元素作为顶点， 将任意两个特征间的冗余度wij作为对应顶点间的边权值， 形成一个特征冗余图G． 该图是一个加权无向图．

假设将特征冗余图G划分成k个连通子图A1，A2，…，Ak， 构建图割损失函数[12]

(3)

称H=(hij)m×k为指标矩阵， 其满足H′H=Ik×k． 这样， (3)式可转化为如下的矩阵形式

Loss(A1， …，Ak)=tr(H′LH)

(4)

其中L=Λ-W， 称之为图G的拉普拉斯矩阵，Λ为对角矩阵， 其对角线元素分别为冗余度矩阵W对应的行元素之和．

求解(3)式或(4)式的极小值问题是一个NP难问题． 将损失函数(4)连续化， 根据Rayleigh-Ritz定理[13]， 目标函数(4)的最优解H为L的前k个最小非零特征值对应的特征向量按列组成的矩阵．

矩阵H的每个列向量实质上就是图G顶点被分割后的簇标． 为了获取明确的簇标特征， 采用常用的K-均值聚类方法对矩阵H的行向量聚类． K-均值聚类结果代表了特征的类簇结构．

1.4 最优特征簇结构

由于K-均值聚类方法需要事先给定类簇数， 但数据特征的类簇数并不明确． 为了获得特征的最优聚类结果， 引入一种特征聚类簇数的评估度量方法指导特征类簇数的选取．

假设特征集A的聚类结果为FC={A1，A2， …，Ak}， 其中Ai={ai1，ai2， …，ai|Ai|}为A的第i簇特征集， 称

(5)

为Ai的簇内平均冗余度； 称

(6)

为两个特征簇Ai={ai1，ai2， …，ai|Ai|}和Aj={aj1，aj2， …，aj|Aj|}的簇间平均冗余度．

最优聚类结果应具有簇内特征冗余度最大而簇间特征最不相关的特点， 也即簇内平均冗余度最大而簇间平均冗余度最小． 因此， 构造如下最优类簇结构评估指标：

(7)

2 簇内特征选择机制

在特征聚类基础上， 本节将探讨簇内特征选择策略． 互信息是度量两个随机变量间相关性的重要指标[14]； 本文提出一种基于互信息的簇内特征选择方法．

假设特征集A的聚类结果为FC={A1，A2， …，Ak}， 对任意特征ai∈A， 存在唯一类簇Aj， 使得ai∈Aj， 称

(8)

为特征ai的依存度．

特征的依存度表示该特征与其簇内其他特征的平均冗余度． 特别地， 如果某一特征簇中仅有一个元素， 则该元素的依存度为0．

设对象集关于决策属性D的划分为U/D={D1，D2， …，DM}， 对任意特征ai∈A， 存在唯一类簇Aj， 使得ai∈Aj，ai关于决策D的互信息可表示为

(9)

中心特征是与决策具有最大互信息的特征， 是该簇中最具代表性特征． 根据聚类思想， 中心特征与该簇中其余特征间具有最大的冗余性． 另一方面， 不同簇中的中心特征具有最小的冗余性和最大的独立性， 而且， 由于特征类簇是按照特征簇内冗余度最大、簇间冗余度最小确定的最优特征分割模式， 将每个簇的中心特征作为特征选择子集是合理的， 也是足够的． 简记这种特征选择方法为RDCFS．

下面我们以一个具体实例说明中心特征与其依存度和中心度间的关联性． 从UCI数据库中选取glass数据集， 并从中随机抽取6个样本， 如下表1．

表1 glass数据集中部分数据

记其特征为A={a1，a2， …，a10}， 将数据归一化后， 按照第1节方法得到特征聚类结果：A1={a1，a6}，A2={a2，a4，a7，a9，a10}，A3={a3，a5，a8}． 根据式(8)和(9)分别计算10个特征的依存度和中心度， 见图1． 在该图中， 同一个类簇中的特征用同一种符号和相同颜色的点表示， 不同簇中特征用不同符号和不同颜色表示．

图1 特征依存度和中心度分布

从图1可以看出， 在同一个簇内， 中心度越大的特征， 在该簇内的依存度也越大， 中心特征的依存度最大． 易见，a6，a2和a3的中心度和依存度在对应簇中最大， 它们分别就是簇A1，A2和A3的中心特征． 因此， {a2，a3，a6}是A的最优特征选择子集．

综合上述分析， 下面给出决策系统的基于决策依赖聚类的特征选择算法．

算法1 基于决策依赖聚类的特征选择算法(RDCFS)

输入: 训练数据集IS=, m为特征数, 邻域参数δ, 指定聚类个数范围Ξ; 输出: 特征子集S. BEGIN1.初始化被选特征子集S=Φ, 全部特征集合为F; 2.for each k∈Ξ; // Ξ: 指定聚类个数范围3.基于公式(4)实现特征聚类; 4.计算公式(5),(6),(7); 5.end for6.k'=arg minkC(k)index ; // 选出最优簇类数7.FC={A1, A2, …, Ak'}; 8.for each Ai∈FC9.for each ai∈Aj, 计算中心度(9); 10. bi=arg maxai∈Aj I(ai; D); // 选出每个簇内中心度最大的特征11. end for12.end for13.特征子集S={b1, b2, …, bk'}.END

3 模拟实验及结果分析

为了验证本文提出的特征选择方法的合理性和有效性， 从UCI数据库中选取8个数值型数据集， 详细信息见表2． 利用这8个数据集验证本文所提特征选择方法选出的特征子集在分类精度上的性能．

表2 数据描述及特征选择结果

首先以表2中前4个数据集为例验证根据式(7)选取聚类数的合理性． 实验采取十折交叉验证的方法． 根据邻域粗糙集特征选择方法邻域参数的一般选取规则， 本文中δ在区间[0.01， 0.5]内取值． 给定类簇数的取值范围， 以一定步长通过遍历方法得到使式(7)达到最小的聚类数目． 在聚类基础上， 在每个簇内选择中心度最高的特征形成特征子集． 采用如下所述邻域投票精度作为特征选择有效性的度量指标．

(10)

图2绘出了表2中前4个数据集特征对的不同聚类数目对应的类簇结构评价指标和邻域投票精度的变化情况． 其中不同线形、 不同颜色分别代表数据的类簇结构评价指标和邻域投票精度的变化情况．

由图2分析可知， 给定一定的聚类数目范围： 在CT和wpbc两个数据集上， 类簇结构评价指标达到极小， 即将特征分别聚成17类和14类时， 邻域投票精度达到最高； 在sonar和autovalve_B两个数据集的类簇结构评价指标达到极小时， 所选特征的邻域投票精度达到次最高， 且当聚类数目逐渐增加时， 邻域投票精度呈现下降趋势． 这说明， 我们构造的类簇结构评价指标能够驱动确定有效的聚类数目， 从而促进特征选择的精度提高．

图2 类簇结构评价指标和精度的变化

为了进一步验证本文提出方法的优势， 分别与联合谱聚类与邻域互信息的特征选择算法(SCNMI)[15]、基于特征聚类的特征选择方法(FSFC)[16]、模糊粗糙测度特征选择(FRSE)[17]和模糊邻域粗糙集特征选择(FNRS)[7]4种特征选择方法在8个数据集上进行模拟实验比较． 表3给出了5种特征选择方法对8个数据集做出的特征选择结果， 其中的数值代表最终特征选择子集中的特征数．

从表3可以看出， 在8个数据集的实验中， 本文所提方法(RDCDS)在7个数据集上都选出了最优(最小)特征子集， 尤其对高维数据集具有更好的降维作用．

表3 特征子集中的特征数

为了验证特征子集的分类能力， 分别采用KNN分类器(本文取K=3)和支持向量机分类器(SVM)对数据集在特征选择前后的分类效果进行了对比实验， 各个方法在不同数据集上的分类精度如表4和表5所示．

从表4和表5可以看出， 不论采用KNN分类器还是SVM分类器， 在8个数据集的实验中本文所提方法(RDCDS)在5个数据集上取得了最高的分类精度． FNRS在2个数据集上取得了最高KNN分类精度， FSFC只在一个数据集上取得最高KNN分类精度， 而SCNMI和FRSE表现最差． 同时， FSFC，FRSE和FNRS分别仅在一个数据集上取得最高的SVM分类精度， SCNMI依然表现最差．

表4 KNN分类器(K=3)下的分类精度

表5 SVM分类器下的分类精度

尽管如此， 特征选择后的数据分类精度都高于原始数据的分类精度． 这一事实说明原始数据包含冗余和不相关信息， 扰乱了对数据的分类学习， 进一步证实特征选择的必要性． 上述对比实验表明， 从统计学意义上讲， 本文提出的特征选择方法得到的特征子集不仅紧凑， 数据分类精度还得以显著提高．

4 结论

本文基于邻域粗糙集模型建立了一种特征聚类驱动的特征选择方法． 该方法不同于现有启发式特征选择和基于特征聚类的特征选择， 从特征依赖度出发构建了特征冗余图， 给出了最优特征冗余图聚类准则和聚类方法． 在此基础上， 通过引入簇内特征依存度和中心度的概念， 给出了特征依赖聚类的特征选择算法． 理论分析和多个数据集上的对比实验结果表明新提出的特征选择方法不仅可以选出特征数更小的特征子集， 其对应的分类精度还得以提高．

本文中最优特征簇结构的评估指标通过遍历方式得到， 探索一种特征类簇数自适应确定方法是很有意义的． 通过分析特征与特征间的因果关联， 基于有向特征图图割的特征选择方法是一个值得深入研究的问题．