基于代表的留一法集成学习分类

王 轩,张 林,高 磊,蒋昊坤

(西南石油大学 计算机科学学院, 成都 610500)(*通信作者电子邮箱linzhang8080@163.com)

0 引言

分类是机器学习[1]的一个基本问题。1982年Pawlak提出了粗糙集理论[2],进而衍生出了覆盖粗糙集[3-4]和邻域粗糙集[5]。在覆盖粗糙集的理论基础上,Zhang等[6]提出了基于代表的粗糙集覆盖分类算法——RBC-CBNRS(Representative-Based Classification through Covering-Based Neighborhood Rough Set)。

RBC-CBNRS算法对于分类问题已经能取得较高的分类精度,在某些分类问题上分类精度超过ID3[7]、J48[8]等经典分类算法。然而,RBC-CBNRS算法在模型构建过程中,受训练集抽样不均匀影响,导致某些正常对象成为离群对象或边界对象。而这些离群对象会影响代表的选举过程,进而影响最终分类结果;或者有可能成为代表,直接导致周围对象都分类错误。

集成学习[9]通过结合多个学习器来完成学习任务,通常能取得更优越的性能。受集成学习思想的启发,为限制离群对象或边界对象对RBC-CBNRS算法分类精度的影响,本文提出了一种留一法集成学习算法——LOOELCA (Leave-One-Out Ensemble Learning Classification Algorithm)。LOOELCA以RBC-CBNRS算法为基分类算法,采用留一法[10]构造一系列同质基分类器,对离群对象与对应的基分类器进行标记。这些被标记的基分类器和基于全集的RBC-CBNRS分类器共同构成委员会,并对未分类对象进行标签预测。如委员会表决一致,则直接给该未分类对象贴上类标签;否则,基于k最近邻(k-Nearest Neighbor, kNN)算法并利用标注对象对未分类对象分类。

实验在UCI的dermatology、zoo、wdbc、ionosphere、wine、 penbased、tic-tac-toe、sonar、mushroom等9个数据集上进行,测试了LOOELCA在不同训练集规模下的分类精度。实验结果表明,LOOELCA较RBC-CBNRS算法分类精度有提升,且与ID3、J48、Naïve Bayes[11]、OneR[12]等经典的分类算法相比,通常能得到更高的分类精度。

1 相关工作

本文的基本数据模型为决策信息系统,涉及到覆盖粗糙集和邻域粗糙集等相关概念。

1.1 决策信息系统

定义1 决策信息系统[13]。决策信息系统S为一个五元组,定义为:

S=(U,C,d,V,I)

(1)

其中:U是整个论域;C表示条件属性集合;d表示决策属性；V={Va|a∈C∪d}是属性值域集合;I={Ia|a∈C∪d}表示U→Va的信息函数。表1是一个决策信息系统。本文只讨论单决策的名词型决策信息系统。

表1 决策信息系统示例Tab. 1 Examples of decision system

定义2 相似度。任意x,y∈U在A⊂C中的相似度记为:

sim(x,y,A)=sam(x,y,A)/|A|

(2)

其中:

sam(x,y,A)=|{a∈A|a(x)=a(y)}|

(3)

因为本文选择对象的全部属性,即A=C,因此可用sim(x,y)表示sim(x,y,A)。本文采用overlap算法计算对象之间相似度。根据定义2,由表1的决策信息系统可计算出sim(x1,x6)=5/6。同理可计算出各对象之间的相似度。

1.2 邻域

定义3 邻域。任意x∈S,设置相似度阈值θ(θ∈(0,1]),那么定义对象的邻域为:

n(x,θ)={y∈U|sim(x,y) ≥θ}

(4)

相似度阈值θ指的是作为对象的邻居所要满足的最小相似度值。根据定义2, 相似度阈值取值范围为{1/|C|,2/|C|,…,1}。如设定的相似度阈值介于两个有效相似度之间,相似度阈值向上取值。例如,根据表1给出的决策信息系统C=6,如设定相似度阈值为3/7,此时2/6<3/7<3/6,那么相似度阈值取3/6。相似度阈值设置得越小,对象的邻域越大;反之,对象的邻域越小。结合表1并根据式(2)、(4)可知,n(x1, 4/6)={x1,x2,x4,x6,x11},n(x1, 5/6)={x1,x6,x11}。

定义4 最小相似度阈值。给定决策信息系统S=(U,C,d,V,I),d={1,2,…,k},U/ {d}={X1,X2, …,Xk},那么任意x∈Xi的最小相似度阈值θ+定义如下:

θx+=min{0<θ≤1|n(x,θ)⊆Xi}

(5)

θx+由对象x和决策信息系统S共同决定。具体示例如图1所示。

定义5 最大邻域。最小相似度阈值对应的邻域就是最大邻域;对于任意x∈S的最大邻域可记为:

n*(x)=n(x,θx+)

(6)

最大邻域就是在决策一致的情况下,覆盖对象最多的邻域。

图1 n*(x1)的定义示例Fig. 1 Example of n*(x1)

2 问题描述及LOOELCA

本章首先介绍LOOELCA的基算法RBC-CBNRS算法,并对RBC-CBNRS算法进行时间复杂度分析;接着介绍集成学习策略的框架和过程,并对LOOELCA进行算法分析。

2.1 问题描述

受抽样不均匀的影响,部分正常对象可能会成为边界对象或者离群对象,这些点会影响代表选择的过程。例如,这类对象会影响其他点的邻域圈定过程，还有可能成为有效代表，这样会影响RBC-CBNRS算法的分类精度。因此,离群对象或边界对象对应的分类器具有研究价值。

2.2 基于代表选举的分类算法

本文的LOOELCA的基算法是RBC-CBNRS算法。RBC-CBNRS算法分为两个子算法,分别是代表生成算法和标签预测算法。

2.2.1 代表生成算法

这个阶段主要选举出能够作为代表的对象,并将代表保存下来。下面给出代表选举过程的伪代码。

输入 决策信息系统DS={U,C,{d},V,I}。

输出 代表集合R及相似度阈值集合T。

1)

R=∅,T=∅;

2)

根据式(2)计算sim(x,y), 其中(x,y)∈(U×U);

3)

for (eachx∈U) do

4)

计算θx+;

5)

计算n*(x);

6)

end for

7)

计算正域U/d={X1,X2, …,Xk};

8)

for (i=1 tok) do

9)

X=Xi;

10)

whileX≠∅ do

11)

选择当前覆盖对象最多的代表x∈U∩Xi;

12)

Ri=Ri∪{x};

13)

X=X-n*(x);

14)

end while

15)

R=R∪Ri;

16)

end for

17)

T={nr+|r∈R};

18)

returnR和T;

其中：

第1)行,定义代表集合R和相似度阈值集合T。

第2)行,根据式(2)计算每两个对象之间的相似度。

第3)～6)行,根据式(5)计算对象x的最小相似度阈值θx+。根据式(6)计算x最大邻域n*(x)。

第7)行,U是论域,X是U的子集,共分成k个子集。

第8)～16)行,选出当前覆盖正域对象最多的对象x,也就是|n*(x)|最大的对象x。它就是本轮选出的代表,然后从当前正域X中删除x的邻域包含的所有对象，并将选出来的代表x及对应邻域n*(x)保存。循环此步骤直至论域U被全部覆盖。

第17)～18)行,返回代表集合R及代表对应邻域的相似度阈值集合T。

2.2.2 标签预测算法

定义6 距离。设x是未分类对象,它与代表r之间的距离定义为:

distance=1/sim(x,r) -1 /θr+;

(7)

显然,未分类对象与代表对象之间的相似度和距离成反比。一般认为未分类对象与距离最近的代表保持决策一致。与未分类对象拥有最小距离的代表组成的集合称为有效代表集。有效代表集记为:

E={r∈R|distance(x,r)=mindis(x,R)}

(8)

其中:

mindis(x,R)=min{distance(x,r) |r∈R}

(9)

根据有效代表可以对未分类对象的类标签进行预测:只有一个有效代表时,未分类对象与有效代表的类标签一致;有多个有效代表时,通过所有有效代表的类标签投票来决定未分类对象类标签。

下面给出标签预测算法的伪代码描述。

输入 未分类对象x, 代表集合R。

输出 预测的类标签d′(x)。

1)

E=∅;

2)

mindis=MAX_VALUE;

3)

for (eachr∈Y) do

4)

计算sim(x,r);

5)

计算distance(x,r);

6)

if (distance(x,r)

7)

mindis=distance(x,r);

8)

E={r};

9)

else then

10)

E=E∪{r};

11)

end if

12)

end for

13)

Getd′(x);

14)

returnd′(x);

其中：

第1)～2)行,初始化有效代表集合E和最小距离。

第4)～5)行,根据式(7)计算未分类对象与代表之间的距离。

第6)～10)行,根据式(8)～(9)找出与未分类对象距离最小的有效代表集合E。

第13)～14)行,有效代表投票决定未预测对象类标签并返回。

2.3 集成学习策略

本文提出的LOOELCA主要分为以下5个步骤:1)把带类标签的训练集随机等分成n份;2)依照留一法的思想进行重采样,形成n组〈训练集-1,测试集〉;3)调用RBC-CBNRS算法构建基分类器;4)根据第3)步构建的分类器组成委员会;5)通过委员会对测试集中的对象进行标签预测。

2.3.1 留一法

留一法把训练集TR分层采样为n份容量为n-1但互斥的子集,每次将1个子集作为训练集,预留出来的1个对象作为测试。正如图2的基分类器构建阶段、RBC-CBNRS分类阶段描述:用第一个子训练集预测对象x1,第二个子训练集预测对象x2,依此类推直至预测出xn。其中对预留对象进行预测时,采用的是RBC-CBNRS算法。

对于预测错误的预留对象进行标记,并将其放入离群池,如图2中所示的对象x2、x3。在离群对象选择阶段,所有被标记的对象放入离群池。离群池中的对象用于对委员会决策不一致对象分类。

2.3.2 集成策略

把留一法构建出来的基分类器进行集成。若留一法中RBC-CBNRS算法对预留出的对象分类错误,那么算法认为预留对象是训练集随机抽样时产生的离群对象。对预留对象分类错误：一方面表明这个分类器有缺陷;另一方面说明这个预留对象有特点。因此这类对象对应的子训练集比较有研究价值。如图2所示,所有离群对象对应的分类器和原始训练集对应的分类器一起组成委员会。

LOOELCA根据基分类器构成的委员会决定测试集中未分类对象的标签。会有两种情况:委员会中成员决策一致,那么此时未分类对象和委员会保持决策一致;另一种情况,委员会中各成员决策不一致,利用outlier pool中的对象采用kNN算法对未分类对象分类。

2.4 LOOELCA算法分析

LOOELCA的基分类器是RBC-CBNRS算法,因此要分析算法复杂度就需先分析RBC-CBNRS算法的复杂度。下面对RBC-CBNRS算法的两个阶段进行复杂度分析。

代表选举子算法阶段:计算相似度时每个对象有a个属性,每个对象需要与其他n-1个对象计算相似度,此步的复杂度为an(n-1)，记为O(n2)。计算最小相似度阈值θx+时,每个对象需要与其余n-1个对象比较相似度,此步的复杂度为n(n-1)，记为O(n2)。采用贪心算法对已生成的邻域进行覆盖时,需要比较选出代表后的其余对象。选出零个代表时需要计算n次,当选出1个代表时需要计算n-1次,依此类推,当选出p个代表时, 算法复杂度为n+(n-1)+…+(n-p+1)=p(2n-p+1)/2,记为O(np)。综上所述该阶段的复杂度为:

O(n2)+O(n2)+O(np)=O(n2)

标签预测子算法阶段:同样选出的有效代表为p个,测试集有m个对象。每个未预测对象需要与p个代表计算距离,因此需计算相似度。由上一步计算可知,计算相似度时的复杂度为O(n2)，所以该阶段的复杂度为O(n2mp)。算出距离之后需要找出最小距离,即每个未预测对象需与每一个代表比较距离,所以复杂度为O(mp)。标签预测阶段只需计算相似度和距离,而简单的投票阶段可以忽略。因此该阶段的复杂度为:

O(n2mp)+O(mp)=O(mpn2)

综上所述,RBC-CBNRS的算法复杂度为O(mpn2)。本文LOOELCA需要对基分类器进行集成,假设集成的基分类器数目为t。最简单的情况委员会中只有原始训练集构成的一个分类器,此时算法的复杂度与RBC-CBNRS算法复杂度相同,可记为O(mpn2)。最复杂的情况是所有的基分类器都进入委员会,此时共有(n+1)个分类器。这时LOOELCA的复杂度为mpn2(n+1),可记为O(mpn3)。综上所述,LOOELCA的复杂度介于两者之间为:

O(mpn2) ≤O(tmpn2) ≤O(mpn3)

图2 集成学习策略示意图Fig. 2 Schematic diagram of ensemble learning strategy

3 实验与分析

3.1 数据集

实验在UCI的9个数据集上与RBC-CBNRS算法作了内部对比。另外,本文提出的LOOELCA也和J48、ID3、Naïve Bayes、OneR等算法作了比较。实验所用数据集详细信息如表2所列。

3.2 与RBC-CBNRS算法对比

首先,实验将LOOELCA与RBC-CBNRS算法进行了对比,实验结果如表3～4所示。整体上来看,在实验所用的9个数据集上,LOOELCA比RBC-CBNRS算法分类精度有提升，精度平均提升0.35～2.76个百分点。其中精度平均提升是指对应数据集上各组实验精度提升值总和除以实验组数。

由表3～4可以看出,在penbased、ionosphere、mushroom、wdbc、zoo、dermatology六个数据集上,当训练集设定比例较小时,LOOELCA较RBC-CBNRS算法分类精度提升更高。这说明当选定训练集较小时,更容易产生离群对象或边界对象。在RBC-CBNRS算法中训练集较小时,离群对象对分类精确度的影响较大;随着数据集的不断变大,离群对象使RBC-CBNRS算法分类错误的影响被限制了。

在tic-tac-toe数据集上,LOOELCA对RBC-CBNRS算法精度提升不受训练集比例影响。说明这个数据集数据分布比较均匀,离群对象或边界对象对分类精确度的影响相对稳定。

有少数组实验数据分类精度不升反降，其他的几组实验分类精度有提升。同样，在sonar数据集上,第一组实验数据分类精度提升不明显。说明在对应数据集上，训练集较小时,离群对象对分类精度的影响不大，此时训练集对象较少,有正常对象被LOOELCA当成离群对象,反而影响了分类精度。随着训练集的增大,离群对象对RBC-CBNRS算法分类精度的影响凸显出来,因此LOOELCA对分类精度的提升也更明显。

3.3 与经典算法对比

实验在UCI的9个数据集上和J48、Naïve Bayes、ID3、OneR等经典算法作了对比。图3绘出了9个数据集上各分类算法精度的对比图。

在mushroom数据集上Naïve Bayes算法的分类精度约为92%；在penbased数据集上OneR算法的精度约为35%；在dermatology数据集上OneR算法的精度约为45%。为了绘图清晰，图3(a)、(c)、(i)只绘出了四种算法的精度对比。

表2 数据集信息Tab. 2 Data set information

表3 小数据集上LOOELCA相对于RBC-CBNRS的分类精度提升百分点Tab. 3 Classification accuracy’s percentage point increase of LOOELCA relative to RBC-CBNRS on small data sets

表4 较大数据集上LOOELCA相对于RBC-CBNRS的分类精度提升百分点Tab. 4 Classification accuracy’s percentage point increase of LOOELCA relative to RBC-CBNRS on larger data sets

图3 LOOELCA与经典算法对比Fig. 3 Comparison of LOOELCA and classical algorithms

从总体上看,在实验所用数据集上,LOOELCA分类精度高于参与对比的经典算法。部分数据集上优势不明显,例如mushroom、wdbc两个数据集。由于数据集本身对象较多,属性较多,所以大部分分类算法都能取得不错的分类效果。

图3(d)、(g)、(i)显示,在对应数据集上LOOELCA并不能优于所有算法,但总体上看分类精度优于大部分参与对比的算法。其他子图显示,对应数据集上LOOELCA分类精度优于其他参与对比的经典算法。

如表5所示,列出了9个数据集上参与对比的五种算法的排名。便于对比,当分类精度平均值相差小于0.5%时,排名相同。从平均排名看LOOELCA排名最靠前,排名第二的Naïve Bayes算法平均排名与LOOELCA差值为1。

表5 每个数据集上的各算法排名Tab. 5 Ranking of each algorithm on each data set

3.4 结果分析

本文提出的LOOELCA分类精度较RBC-CBNRS算法有提升,且分类性能优于J48等经典分类算法。实验结果可看出,离群对象、边界对象对RBC-CBNRS算法分类效果造成显著影响。本文提出的LOOELCA有效地减小了该影响,提升了分类精度。从大部分数据集来看,训练集规模小时,LOOELCA对RBC-CBNRS算法的精度提升更明显。这也说明当训练集规模小时，抽样不均匀对算法的影响更大。在数据集较大的mushroom、wdbc两个数据集上,LOOELCA较RBC-CBNRS算法精度也有提升。这说明就算有足够的训练集数据,也存在离群对象或边界对象对分类精度影响的问题。

与Naïve Bayes等经典算法的对比实验可以看出:在实验所用的大部分数据集上,LOOELCA分类精度更高。结合实验结果和表2可以看出，在数据集对象超过300时,LOOELCA总能获得较好的分类效果。在实验所用数据集上,LOOELCA分类精度变化平缓,分类性能稳定。

4 结语

RBC-CBNRS算法中,受抽样不均匀影响会出现离群对象或边界对象。为了应对离群对象或边界对象对分类精度的影响,本文提出了一种基于RBC-CBNRS算法的留一法的集成学习策略。实验结果表明,本文提出的集成策略对算法的分类精度有提升。在进一步的工作中,将研究代价敏感[14-15]问题对RBC-CBNRS算法的影响,如考虑测试代价、误分类代价等因素。