·416· 智能系统学报 第13卷 2.2集成属性重要度 4)for r=Itok 算法1在迭代过程中，求解属性重要度是利用 Ya,∈AT-seq,计算属性a,在决策系统DS,上 全体样本所得到的依赖度差异，如式(8)。但这种重 的重要度Sig(a。ATD): 要度计算方法忽视了数据扰动对重要度计算产生的 end for 影响，当样本集发生变化时，属性重要度势必也会 5)Ya,∈AT-seq,融合属性a,在各个决策系统 发生相应的变化，从而导致约简变化。如何降低样 上的重要度： 本集变化所引起的约简变化程度，其本质是期望所 求约简应尽可能稳定、鲁棒，因此需要重新考察属 sig.(dAT.D) 性重要度的计算方法。 Sig(ai,AT,D)= 从分类学习的角度来看，不同样本对学习性能 6)选择a,满足Sig(a,seq,D)Fmax{Sig(a,seq, 的贡献程度是不相同的。一般来说，那些对于学习性 D:Ya,∈AT-seq},令seq=seqU{a,返▣3)： 能影响比较重要的样本大都分布在边界区域上s。 7)输出seq。 从这一考虑出发，可以将边界区域的样本挑选出 在邻域粗糙集上求解属性重要度的时间复杂度 来，作为计算属性重要度的依据。一个可行且直观 为O(U×n),其中U表示论域中对象个数，n代表条 的办法是采用聚类算法对原始样本集进行聚类，在 件属性个数，算法1的时间复杂度为O(UP×n)。k 各类簇中挑选出距离类簇中心较远的样本，将这些 means聚类的时间复杂度为O(NxTxU),N为类簇个 样本组合成一个新的决策系统，这实际上是一个采 数，T为迭代次数。算法3的时间消耗为k×N×T×U+ 样的过程（具体描述如算法2所示）。又因为传统的 k×[U×m,其中[U刀是一个不确定集，表示每次k 聚类算法，如k-means聚类的结果并不稳定，其初始 means聚类采样的对象个数，聚类次数k为常数，故 类簇中心是随机选取的，故可以在原始样本集上通 算法3的时间复杂度为O([U×n)。通过大量实验 过多次聚类后得到多个决策系统，分别在这多个决 表明[U)<U,所以在聚类次数较少的前提下，算法 策系统上求得各个属性的重要度并进行融合，最后 3的时间消耗一般小于算法1。 选择融合重要度较高的属性，其具体描述如算法 3实验分析 3所示。 算法2基于k-means聚类的采样 为了验证所提算法的有效性，本文从UCI数据 输入邻域决策系统DS=(U,ATUD)。 集中选择了9组数据，数据的基本描述如表1所 输出采样后的决策系统DS'。 示。实验中取k=5,即进行5次聚类采样，由算法 1)U'=0; 3得到的属性序列不仅和传统的启发式算法比较， 2)利用k-means聚类获得U上的类簇C= 而且和王熙照等1提出的基于样例选取的求解属 C,C2,…,Cw,其中N为决策类的个数： 性重要度算法对比分析。 3)for j=1 to N 表1实验数据的基本信息 ①计算类簇C中每个样本到类簇中心的平均 Table 1 Data sets description 距离d: 数据集 ②将C,中到类簇中心的距离大于平均距离 数据集名称 样本数属性数决策类数 编号 d的样本挑选出来加人U'; Dermatology 366 35 6 end for Diabetic Retinopathy 2 1151 20 4)输出DS'。 Debrecen 算法3重要度集成的启发式算法 2 Ecoli 336 8 输入邻域决策系统DS=(U,ATUD),采样次 Ionosphere 351 35 数k 5 Iris 150 输出属性排序seq。 Parkinson Multiple 1)seq-0,y(seq,D)0; 6 1208 27 Sound Recordings 2)for r=1to k 7 Pima Indians Diabetes 768 9 2 利用算法2进行采样得到决策系统DS: Tic-Tac-Toe Endgame 958 9 2 end for 9 Yeast 1484 9 10 3)若AT-seq=0,则转至7)，否则转至4)：2.2 集成属性重要度 算法 1 在迭代过程中，求解属性重要度是利用 全体样本所得到的依赖度差异，如式 (8)。但这种重 要度计算方法忽视了数据扰动对重要度计算产生的 影响，当样本集发生变化时，属性重要度势必也会 发生相应的变化，从而导致约简变化。如何降低样 本集变化所引起的约简变化程度，其本质是期望所 求约简应尽可能稳定、鲁棒，因此需要重新考察属 性重要度的计算方法。 从分类学习的角度来看，不同样本对学习性能 的贡献程度是不相同的。一般来说，那些对于学习性 能影响比较重要的样本大都分布在边界区域上[15-16]。 从这一考虑出发，可以将边界区域的样本挑选出 来，作为计算属性重要度的依据。一个可行且直观 的办法是采用聚类算法对原始样本集进行聚类，在 各类簇中挑选出距离类簇中心较远的样本，将这些 样本组合成一个新的决策系统，这实际上是一个采 样的过程 (具体描述如算法 2 所示)。又因为传统的 聚类算法，如 k-means 聚类的结果并不稳定，其初始 类簇中心是随机选取的，故可以在原始样本集上通 过多次聚类后得到多个决策系统，分别在这多个决 策系统上求得各个属性的重要度并进行融合，最后 选择融合重要度较高的属性，其具体描述如算法 3 所示。 算法 2 基于 k-means 聚类的采样 输入 邻域决策系统 DS = ⟨U,AT∪ D⟩。 DS 输出 采样后的决策系统 ′。 U ′ 1) = Ø ； {C1,C2,··· ,CN} 2) 利用 k-means 聚类获得 U 上的类簇 C = ，其中 N 为决策类的个数； 3) for j = 1 to N dj ①计算类簇 Cj 中每个样本到类簇中心的平均 距离 ； dj U ′ ②将 Cj 中到类簇中心的距离大于平均距离 的样本挑选出来加入 ； end for DS′ 4) 输出 。 算法 3 重要度集成的启发式算法 输入 邻域决策系统 DS = ⟨U,AT∪ D⟩ ，采样次 数 k； 输出 属性排序 seq。 1) seq←Ø，γ(seq, D)=0； 2) for r = 1 to k 利用算法 2 进行采样得到决策系统 DSr； end for 3) 若 AT–seq = Ø，则转至 7)，否则转至 4)； 4) for r = 1 to k ∀ ai∈AT–seq，计算属性 ai 在决策系统 DSr 上 的重要度 Sigr (ai , AT, D)； end for 5) ∀ ai∈AT– seq，融合属性 ai 在各个决策系统 上的重要度： Sig(ai ,AT,D) = ∑K r=1 Sigr(ai ,AT,D) k ; ∀ 6) 选择 aj，满足 Sig(aj , seq, D)=max{Sig(ai , seq, D)： ai∈AT–seq}，令 seq=seq∪{aj}，返回 3)； 7) 输出 seq。 U 2 U 2 n 3 k×N ×T ×U+ k×[U] 2 ×n 3 [U] 2 ×n 3 在邻域粗糙集上求解属性重要度的时间复杂度 为 O( ×n)，其中 U 表示论域中对象个数，n 代表条 件属性个数，算法 1 的时间复杂度为 O( × )。k￾means 聚类的时间复杂度为 O(N×T×U)，N 为类簇个 数，T 为迭代次数。算法 3 的时间消耗为 ，其中[U]是一个不确定集，表示每次 k￾means 聚类采样的对象个数，聚类次数 k 为常数，故 算法 3 的时间复杂度为 O( )。通过大量实验 表明[U]<U，所以在聚类次数较少的前提下，算法 3 的时间消耗一般小于算法 1。 3 实验分析 为了验证所提算法的有效性，本文从 UCI 数据 集中选择了 9 组数据，数据的基本描述如表 1 所 示。实验中取 k=5，即进行 5 次聚类采样，由算法 3 得到的属性序列不仅和传统的启发式算法比较， 而且和王熙照等 [15]提出的基于样例选取的求解属 性重要度算法对比分析。 表 1 实验数据的基本信息 Table 1 Data sets description 数据集 编号 数据集名称 样本数 属性数 决策类数 1 Dermatology 366 35 6 2 Diabetic Retinopathy Debrecen 1 151 20 2 3 Ecoli 336 8 8 4 Ionosphere 351 35 2 5 Iris 150 4 3 6 Parkinson Multiple Sound Recordings 1 208 27 2 7 Pima Indians Diabetes 768 9 2 8 Tic-Tac-Toe Endgame 958 9 2 9 Yeast 1 484 9 10 ·416· 智 能 系 统 学 报 第 13 卷