模糊粗糙集的LIFT数据分析

梁绍宸,徐苏平,窦慧莉,李洪梅,杨习贝,2

1(江苏科技大学 计算机学院,江苏 镇江 212003)2(南京理工大学 经济管理学院,南京 210094)

1 引 言

多标记学习[1]是针对现实世界中普遍存在的多义性对象而提出的一种学习框架,其主要目标是预测未知对象的标记集合.多义性对象是指拥有多个语义信息的对象,例如:一个文本对象可以同时包含“经济”和“新闻”两种语义信息[2];类似地,一个图像可以同时被标记为“天空”与“大海”[3,4].在多标记学习框架下,每一种语义信息都被刻画为一个标记,所有对象的语义信息就构成了输出空间(标记空间),同时,所有对象的特征构成了输入空间(示例空间).以输入空间作为分类依据,对一个对象在各个标记上的预测,都可被视作是一个二类分类问题.鉴于此,相关学者[5]针对每个标记,直接通过示例空间,分别构建分类器模型,从而可以得到未标记对象的标记集合[6].

然而,由直观经验可知每一个标记都有一些固有特性,而这些特性在帮助判断对象是否属于该标记时往往能够提供更有利的信息[7].因此,Zhang等人提出了基于标记类属属性的多标记学习算法LIFT,并且已有的实验结果表明,LIFT算法确实是有效的[8,9].但利用LIFT构建出的类属属性空间中存在冗余信息[10],这不仅增加了分类过程所消耗的时间,而且有可能对分类产生一定负面的影响.所以,寻找一种有效的方法来对类属属性空间进行特征选择是有着客观依据的[11,12].

自1990年Dubois提出模糊粗糙集[13]以来,国内外众多学者开始致力于模糊粗糙集的理论与应用方法的研究[14,15].其中,有些学者提出,利用粗糙集中的约简概念而产生的模糊粗糙集特征选择方法,不仅能够有效地处理各种类型的数据[16,17],而且可以最大限度地保持原始数据的分布信息[18-20].也正因为此,基于模糊粗糙集的特征选择才在生物信息学、管理科学与工程等领域中得到了广泛应用[21,22].

考虑到模糊粗糙集在实际应用中的有效性,笔者将借助模糊粗糙集模型,对由LIFT产生的类属属性空间进行特征选择.在此基础上,为进一步提升分类性能,采用了稳健模糊粗糙分类器[23,24].

本文主要内容安排如下:第二节介绍模糊粗糙集的基本知识,第三节给出多标记学习的算法LIFT,并针对LIFT算法存在的问题,设计了新算法FRS-LIFT,第四节通过实验数据验证了FRS-LIFT的有效性,第五节总结全文.

2 基础知识

给定决策系统,其中,论域U={x1,x2,…,xn}是全部对象的集合,A={a1,a2,…,am}用来描述对象的各个特征,D刻画了对象的所有决策.

不失一般性,若将B⊆A(B≠Ø)诱导的论域上的一个模糊二元关系记作RB,则当它至少满足自反性与对称性时,∀x,y∈U,RB(x,y)∈[0,1]可用来表示对象x与y关于特征集B的相似度.如无特别说明,本文所探讨的模糊二元关系都可用来刻画对象间的相似度.

2.1 模糊粗糙集模型

(1)

(2)

2.2 稳健模糊粗糙集模型

由于上式中的最大值和最小值的统计对数据噪声敏感,因此Hu等人定义了三种稳健的统计量代替上述的最大值和最小值.

定义2.[23]对于随机变量X={x1,x2,…,xn},假定X的元素按照升序排列,定义X的k-mean最小值和最大值分别为(x1+x2+…+xk)/k和(xn-k+1+xn-k+2+…+xn)/k,X的k-median最小值和最大值分别为{x1,x2,…xk}的中位数和{xn-k+1,xn-k+2,…,xn}的中位数,X的k-trimmed最小值和最大值分别为xk+1和xn-k.基于此,三种稳健模糊粗糙集的隶属函数分别为:

(3)

(4)

(5)

(6)

(7)

(8)

2.3 模糊粗糙分类器

决策系统的目标是利用已知决策的对象,构建上述模糊粗糙集模型,对未知对象的决策类进行预测.模糊粗糙分类器分类的方法如下:

给定决策系统,若D诱导的论域上的划分为U/IND(D)={d1,…,dp},则未知对象x的决策类为:

(9)

其中,*为classical,k-mean,k-median,或者k-trimmed.

2.4 基于模糊粗糙集的特征选择

现实世界中的数据往往存在冗余信息,利用特征重要度这一概念可以找到并删除这些冗余信息,例如将特征重要度小的特征视作冗余信息.此外,一个特征的特征重要度由衡量指标分别在有无该特征时取到的值之差度量.近似质量作为重要的衡量指标之一,它刻画了模糊粗糙集在现有知识水平下的确定性程度,其定义如下:

定义3.给定决策系统,∀B⊆A,若D诱导的论域上的划分为{d1,d2,…,dp},则在特征集合B下,模糊粗糙集的近似质量为:

(10)

根据如上定义,采用近似质量衡量特征重要度.∀ai∈A,其特征重要度可以用如下两种方式表示:

(11)

(12)

其中*为classical,k-mean,k-median,或者k-trimmed.在此基础上,使用正向启发式算法等可以进行特征选择.

3 多标记学习

在多标记学习中,特征集合A= {a1,a2,…,am},标记集合L={l1,l2,…,lq}.与此同时,使用T= {(xi,Yi)|i=1,2,…,n}表示多标记对象的训练集,其中xi=[fi(a1),fi(a2),…,fi(am)]刻画了对象xi的各个特征,Yi=[gi(l1),gi(l2),…,gi(lq)]描述了对象xi的标记情况.当xi具备lk标记时,gi(lk)=1,否则gi(lk)=-1.

3.1 LIFT算法

由于不同的标记有不同的特性,而这些特性更倾向于判断对象是否具有某个标记,因此已有学者[8]提出了LIFT算法来寻找各标记的类属属性,以期提高多标记学习的性能.LIFT首先分别按照是否具有标记lk∈L,把多标记对象分为正类样本Pk和负类样本Nk,形如:

Pk={xi|(xi,Yi)∈T,gi(lk)=1};

(13)

Nk={xi|(xi,Yi)∈T,gi(lk)=-1}.

(14)

然后分别在Pk和Nk上进行k-means聚类以获取正、负两类样本的内在结构.由于Pk和Nk的聚类信息可被视为同等重要[9],为此聚类中心的数目均设为mk,即有:

mk=「δ·min(|Pk|,|Nk|)⎤.

(15)

在此基础上,lk标记对应的类属属性空间按照如下方式构造:

(16)

其中,d(·,·)表示两向量间的距离,本文采用了欧氏距离.实际上,φk是从特征集合A构成的m维空间到新的2mk维类属属性空间LIFTk的映射.

最后LIFT在构建出来的q个类属属性空间中分别训练分类模型{h1,h2,…,hq}.参照形式化定义,∀lk∈L,可得到如下二类训练集BTk:

BTk={(φk(xi),gi(lk))|i=1,2,…n}.

(17)

进而使用任何一种二类分类算法都可以得到hk模型,对于未知对象x,其标记的预测集合为Y={lk|hk(φk(x))>0,1≤k≤q}.

3.2 FRS-LIFT算法

当类属属性维度较高时,分类模型构建较慢.为降低类属属性维度,笔者在保留了上述LIFT类属属性构建的方法基础之上,对所有二类训练集BTk分别进行基于模糊粗糙集的特征选择得到BTk′,再分别使用对应的模糊粗糙分类器预测未知对象是否具备标记lk,最终得到未知对象的标记集合.无论采用哪种模糊粗糙集模型,笔者将这一完整过程统称为FRS-LIFT算法,其具体流程如下:

算法1.FRS-LIFT

输入: 多标记对象训练集T,控制聚类个数的参数δ,近似质量变化的阈值ε,未知对象x;

输出: 预测出的未知对象的标记集合Y.

步骤1.对于每一个标记lk,重复步骤2到步骤11;

步骤2.根据式(13)和(14)得到正类样本集Pk与负类样本集Nk;

步骤3.在Pk和Nk上分别使用k-means聚类,根据式(15)得到聚类个数mk;

步骤4.根据式(16),对于T中每个对象xi,创建映射φk(xi),进而得到lk标记下的类属属性空间LIFTk;

步骤5.根据式(10)计算γ*(Ak,lk),其中Ak为构成LIFTk空间的类属属性集;

步骤6.Bk←∅;

步骤13.若class*(x)=Pk,则Y←Y∪{lk};

步骤14.输出Y.

算法中,所有*都代表classical,k-mean,k-median,或者k-trimmed,它们全部取相同的值.步骤2到步骤4是原LIFT算法中构建类属属性的过程,步骤5到步骤10利用模糊粗糙集对类属属性空间进行了特征选择,步骤12根据式(9)预测了未知对象的各个标记,最终得到其标记集合.

4 多标记学习

本文选取了5组多标记数据集进行了实验,这些数据集涵盖了音乐、文本、生物等多个实际应用领域,它们的基本信息如表1所示.

表1 数据集信息Table 1 Data sets description

注:URL1:http://sci2s.ugr.es/keel/multilabel.phpURL2:http://mulan.sourceforge.net/datasets-mlc.html

4.1 实验设置

实验选用高斯核函数计算多标记对象间的相似度,高斯核参数以0.1为步长在[0,1]内调节,最终设定为0.7,根据文献[25]控制聚类个数的参数δ设为0.2,特征选择中控制近似质量变化的阈值取0.05.另外,由三个稳健模糊粗糙集模型的定义可知,在一定范围内,它们的参数越大,噪声样本对分类结果的影响越小,实验效果越好.同时,当k-median参数取奇数时,会与k-trimmed取某个参数时实验效果相同;当k-median的参数为2时,又会与k-mean的参数取2时的实验效果相同,因此为了不失一般性并体现出三个稳健模糊粗糙集模型各自的特点,本实验将三个稳健模糊粗糙集模型k-mean,k-median,k-trimmed的参数分别设置为3、4、2.

此外,所有实验都使用MATLAB R2014a开发环境.由于Enron数据集较大,因此将此数据集运行在两个2.13GHz的Intel处理器和16GB的内存空间中,其余实验都运行在1.90GHz的AMD处理器和8GB的内存空间中.

在此基础上,做了两组实验,第一组实验对比特征选择前后的类属属性空间的平均维度,第二组实验对比四个模糊粗糙分类器在特征选择前后的类属属性空间中的分类性能.

4.2 维度对比

分别采用四个模糊粗糙集模型对各标记构造出的类属属性空间LIFTk(1≤k≤q)特征选择,特征选择前后q个类属属性空间的平均维度,如表2所示.

4.3 分类效果对比

从表2中可以看出,在这5组数据集上,k-trimmed稳健模糊粗糙集模型降维效果始终最佳.同时可以看出有时类属属性空间维度较高,以Emotion数据集为例,它的特征选择前的类属属性空间的平均维度比原始数据的特征维度要大.

为了考察多标记学习系统的分类性能,在每个数据集中,将数据集分成十份,轮流将其中9份样本构成训练集,1份构成测试集,分类过程重复10次并记录10次实验的均值与方差.显然,精度、查准率等单标记指标不适用于度量多标记学习性能[6],因此,本文采用了5种多标记学习评价指标[2,26]来评价学习系统的性能,它们分别是Hamming Loss、Ranking Loss、One Error、Coverage、Average Precision.

值得注意的是,使用的四种模糊粗糙分类器,与特征选择时所用的模糊粗糙集模型对应.它们对各数据集的分类效果分别如表3至表6所示.另外,表格中,↓表示对应指标的值越小,该指标下的性能越好,↑表示对应指标的值越大,该指标下的性能越好,性能好的数据以加粗体标出.

表2 特征选择前后类属属性空间的平均维度对比Table 2 Comparison of average dimensionalities of label-specific feature spaces before and after feature selection

表3 传统模糊粗糙集分类性能Table 3 Predictive performance of classical fuzzy rough set

表4 k-mean模糊粗糙集分类性能Table 4 Predictive performance of k-mean fuzzy rough set

表5 k-median模糊粗糙集分类性能Table 5 Predictive performance of k-median fuzzy rough set

表6 k-trimmed模糊粗糙集分类性能Table 6 Predictive performance of k-trimmed fuzzy rough set

观察表3至表6所示结果,不难发现无论使用哪种模糊粗糙分类器,在特征选择后的类属属性空间中,分类性能都有一定的提升.即使在少数情况下,在个别评价指标上特征选择后的类属属性空间中分类性能不如原始的类属属性空间,但是差别不大.以Bird数据集为例,经过特征选择后,k-trimmed分类器结果显示Ranking Loss值仅下降0.9%左右.综上所述,本文提出的FRS-LIFT算法是有效的.

5 结束语

LIFT试图探寻各个标记所具有的特性,并在新的构造出的类属属性空间中进行多标记学习,这突破了一直以来在原始示例空间中采用各种算法进行多标记学习的做法.从相关学者已有的大量实验数据可以看出,LIFT确实改进了多标记学习系统的性能.然而遗憾的是,LIFT忽略了类属属性空间中存在的冗余信息,没有考虑到这些冗余信息对多标记学习系统的学习性能会造成一定负面影响.因此笔者在提出的新算法中,对LIFT构造出的类属属性进行了特征选择.实验结果表明,除去类属属性空间的冗余信息能够使多标记学习系统性能得到进一步提升.

在本文工作的基础上,笔者下一步的工作是:

1)改进对类属属性特征选择的算法,减少特征选择所需的时间.

2)LIFT和FRS-LIFT都没有考虑各个标记之间的关系,能否将标记间的相关性考虑在内也是下一步的研究重点.

：

[1] Tsoumakas G,Katakis I.Multi-label classification:an overview [J].International Journal of Data Warehousing and Mining,2007,3(3):1-13.

[2] Schapire R E,Singer Y.BoosTexter:a boosting-based system for text categorization [J].Machine Learning,2000,39(2):135-168.

[3] Boutell M R,Luo Jie-bo,Shen Xi-peng,et al.Learning multi-label scene classification [J].Pattern Recognition,2004,37(9):1757-1771.

[4] Liang Xin-yan,Qian Yu-hua,Guo Qian,et al.Local rough sets for mutil-label learning [J].Journal of Nanjing University,2016,52(2):270-279.

[5] Yu Ying,Pedrycz W,Miao Duo-qian.Neighborhood rough sets based multi-label classification for automatic image annotation [J].International Journal of Approximate Reasoning,2013,54(9):1373-1387.

[6] Zhang Min-ling,Zhou Zhi-hua.A review on multi-label learning algorithms [J].IEEE Transactions on Knowledge and Data Engineering,2014,26(8):1819-1837.

[7] Wang Yu,Yang Zhi-rong,Yang Xi-bei.Local attribute reduction approach based on decision-theoretic rough set [J].Journal of Nanjing University of Sciences & Technology,2016,40(4):444-449.

[8] Wu Lei,Zhang Min-ling.Research of label-specific features on multi-label learning algorithm [J].Journal of Software,2014,25(9):1992-2001.

[9] Zhang Min-ling,Wu Lei.Lift:multi-label learning with label-specific features [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2015,37(1):107-120.

[10] Xu Su-ping,Yang Xi-bei,Qi Yun-song.Multi-label learning with label-specific feature reduction [J].Journal of Computer Applications,2015,35(11):3218-3221.

[11] Li Hua,Li De-yu,Wang Su-ge,et al.Multi-label learning with label-specific features based on rough sets [J].Journal of Chinese Computer Systems,2015,36(12):2730-2734.

[12] Duan Jie,Hu Qing-hua,Zhang Ling-jun,et al.Feature selection for multi-label classification based on neighborhood rough sets [J].Journal of Computer Research & Development,2015,52(1):56-65.

[13] Dubois D,Prade H.Rough fuzzy sets and fuzzy rough sets [J].International Journal of General System,1990,17(2-3):191-209.

[14] Wu Wei-zhi,Mi Ju-sheng,Zhang Wen-xiu,et al.Generalized fuzzy rough sets [J].Information Sciences,2003,151(3):263-282.

[15] Hu Bao-qing,Xian Yan-xia.Level characteristics of rough fuzzy sets and fuzzy rough sets [J].Fuzzy Systems and Mathematics,2006,20(6):108-114.

[16] Zeng An-ping,Li Tian-rui,Liu Dun,et al.A fuzzy rough set approach for incremental feature selection on hybrid information systems [J].Fuzzy Sets & Systems,2015,258(1):39-60.

[17] Zhang Xiao,Mei Chang-lin,Chen De-gang,et al.Feature selection in mixed data:A method using a novel fuzzy rough set-based information entropy [J].Pattern Recognition,2016,56(1):1-15.

[18] Bhatt R B,Gopal M.On fuzzy-rough sets approach to feature selection [J].Pattern Recognition Letters,2005,26(7):965-975.

[19] Hu Qing-hua,An Shuang,Yu Da-ren.Soft fuzzy rough sets for robust feature evaluation and selection [J].Information Sciences,2010,180(22):4384-4400.

[20] Chen De-gang,Zhao Su-yun.Local reduction of decision system with fuzzy rough sets [J].Fuzzy Sets & Systems,2010,161(13):1871-1883.

[21] Zhou Jun-yi.Research on customer churn prediction in telecommunication based on attribute selection of rough set [D].Zhenjiang:Jiangsu University of Science and Technology,2014:1-86.

[22] Xu Fei-fei,Wei Lai,Du Hai-zhou,et al.Fast approach to mutual information based gene selection with fuzzy rough sets [J].Computer Science,2013,40(7):216-221+235.

[23] Hu Qing-hua,Zhang Lei,An Shuang,et al.On robust fuzzy rough set models [J].IEEE Transactions on Fuzzy Systems,2012,20(4):636-651.

[24] Zhang Jing,Li De-yu,Wang Su-ge,et al.Multi-label text classification based on robust fuzzy rough set model [J].Computer Science,2015,42(7):270-275.

[25] Xu Su-ping,Yang Xi-bei,Yu Hua-long,et al.Multi-label learning with label-specific feature reduction [J].Knowledge-Based Systems,2016,104(1):52-61.

[26] Schapire R E,Singer Y.Improved boosting algorithms using confidence-rated predictions [J].Machine Learning,1999,37(3):297-336.

附中文参考文献：

[4] 梁新彦,钱宇华,郭 倩,等.面向多标记学习的局部粗糙集 [J].南京大学学报(自然科学),2016,52(2):270-279.

[7] 王 宇,杨志荣,杨习贝.决策粗糙集属性约简:一种局部视角方法 [J].南京理工大学学报(自然科学版),2016,40(4):444-449.

[8] 吴 磊,张敏灵.基于类属属性的多标记学习算法 [J].软件学报,2014,25(9):1992-2001.

[10] 徐苏平,杨习贝,祁云嵩.基于类属属性约简的多标记学习 [J].计算机应用,2015,35(11):3218-3221.

[11] 李 华,李德玉,王素格,等.基于粗糙集的多标记专属特征学习算法[J].小型微型计算机系统,2015,36(12):2730-2734.

[12] 段 洁,胡清华,张灵均,等.基于邻域粗糙集的多标记分类特征选择算法 [J].计算机研究与发展,2015,52(1):56-65.

[15] 胡宝清,咸艳霞.粗糙模糊集与模糊粗糙集的截集性质 [J].模糊系统与数学,2006,20(6):108-114.

[21] 周君仪.基于粗糙集特征选择的电信客户流失预测研究 [D].江苏科技大学,2014:1-86.

[22] 徐菲菲,魏 莱,杜海洲,等.一种基于互信息的模糊粗糙分类特征基因快速选取方法 [J].计算机科学,2013,40(7):216-221,235.

[24] 张 晶,李德玉,王素格,等.基于稳健模糊粗糙集模型的多标记文本分类 [J].计算机科学,2015,42(7):270-275.