代表选举的分类策略对比

师彦文 王轩 王森 王宏杰

摘要：有学者已提出了针对名词型数据的基于代表的邻域覆盖的分类算法。在该算法中，当有不止一个有效代表距未分类对象最近时，采取简单的投票策略来决定待分类对象的类标签。简单的投票策略忽略了每个代表对未分类对象的影响能力不同。针对这个问题本文提出了基于密度和基于规模的分类策略。通过实验对简单的投票策略、基于密度的分类策略、基于规模的分类策略的分类性能做了对比。

关键词：代表;邻域覆盖;分类策略;粗糙集

中图分类号：D922文献标识码：A文章编号：1672-9129（2018）06-0243-03

Comparison of Classification Strategies for Representative Elections

SHI Yanwen¹， WANG Xuan²*， WANG Sen²， WANG Hongjie³

（1.School of Rail Transportation， Southwest Jiaotong University Hope College， Sichuan Chengdu， 610400， China; 2.School of Computer Science， Southwest Petroleum University， Sichuan Chengdu， 610500， China; 3.The peoples Government of Chengbei Town， Jiange County， Sichuan Guangyuan， 628300， China）

Abstract： The classification algorithm for noun data based on representative through neighborhood covering have been put forward by some scholars . In this algorithm， a simple vote strategy is used to determine the class labels of the object to be classified when there are not only one representatives are nearest. It forget the different effects of each representations in the simple voting strategy. Aiming at this problem， this paper proposes a density and scale based classification strategy. The performance of simple voting strategy， density-based classification strategy and scale-based classification strategy are compared through experiments.

Keywords：representative; neighborhood coverage; classification strategy; rough set

引用：师彦文， 王轩， 王森， 等. 代表选举的分类策略对比[J]. 数码设计， 2018， 7（6）： 243-245.

Cite：SHI Yanwen， WANG Xuan， WANG Sen， et al. Comparison of Classification Strategies for Representative Elections[J]. Peak Data Science， 2018， 7（6）： 243-245.

引言

分类问题是一种有监督^[1]的学习方法，是机器学习^[2][3]、模式识别^[4]和数据挖掘^[5]中的一个重要课题。目前分类算法已被应用到了许多领域，包括银行金融、客户分类、文本分类、医药分类和搜索引擎分类等。当前的分类算法主要有朴素贝叶斯^[6]、决策树^[7]、线性回归^[8]、支持向量机^[9]、神经网络^[10]等。

1982年Z.Pawlak首次提出了粗糙集理论^[11];接着Zakowski^[12]提出了基于邻域覆盖的粗糙集模型。Zhang^[13]等提出了基于代表的粗糙集覆盖的分类算法——RC（Representative-Based Classification through Covering-Based Neighborhood Rough Set）。这个算法中包含兩个子算法：一个是邻域覆盖的代表选举算法，一个基于代表的分类算法。

有多个代表距未分类对象距离最近时，文献[13]采用简单的投票来决定未分类对象的类标签。简单的投票策略在分类时忽略了每个代表的影响能力不同。因此，用简单的投票策略确定未分类对象的类标签可能会影响最终的分类精度。本文针对上述情况提出了一个相似度策略，并通过实验与原有的简单投票分类策略进行了对比。

1  理论概念

定义1（决策信息系统^[14]） 决策信息系统S为一个三元组，定义为：

                 S = （U，C，d），                       （1）

这里U指对象集合，也就是整个论域;C表示所有条件属性集合;d表示决策属性。表1列出了一个决策信息系统。

定义2（相似度） 任意x， y ? U在A ? C中的相似度记为：

  sim（x， y） = sam（x， y） /|A|，                 （2）

其中

sam（x， y） = |{a ? A | a（x） = a（y）}| （3）

本文选择对象的全部属性，即A = C。本文采用overlap算法来计算相似度，根据定义2，通过表1的决策信息系统可以计算出sim（x₂， x₃） = 3/6，sim（x₁， x₁₁） = 5/6. 这样可以计算得到相似度，用以描述两个对象之间的相似关系。

定义3（邻域） 对于任意x ? S，都可以设置相似度阈值θ，θ?（0，1]，那么定义对象的邻域为：

n（x，θ） = {y?U|sim（x，y） ≥θ}.           （4）

相似度阈值θ指的是作为对象邻居的最小的相似度值。相似度阈值不为0，相似度阈值等于0时对象的邻域为这个论域。根据定义3，相似度阈值取值范围为{1/|C|，2/|C|，3/|C|……，1}。

相似度阈值设置的越小，对象的邻域越大;反

之，对象的邻域越小。根据定义3由表1的决策信

息系统可以计算出，n（x₁， 1） = {x₁}，n（x₁， 5/6） = {x₁，x₆，x₁₁}.

定义4（最小相似度阈值）S = （U，C，d）代表一个名词型决策信息系统，d = {1， 2， … ， k}，U / {d} = {X₁， X₂， … ， X_k}，那么任意x?X_i的最小相似度阈值θ⁺定义如下：

θ_x⁺ = min{0 < θ ? 1 | n（x， θ） ? X_i}             （5）

此時θ_x⁺由对象x和决策信息系统S共同决定。

定义5（最大邻域）最小相似度阈值对应的邻域就是最大邻域;对于任意x ? S的最大邻域可记为：

n*（x）=n（x，θ_x⁺）                     （6）

最大鄰域就是在论域空间中类标签相同的情况下，覆盖对象最多的邻域。

图1展示了一个对象计算最小相似度阈值及圈定其最大邻域的过程。结合表1给定的决策信息系统，n（x₁， 1） = {x₁}，n（x₁， 1） ?X_Yes;n（x₁， 5/6） = {x₁，x₆，x₁₁}，n（x₁， 5/6） ?X_Yes;n（x₁， 4/6） = {x₁，x₂， x₄，x₆，x₁₁}，n（x₁， 4/6） ?X_Yes;n（x₁， 3/6） = {x₁，x₂，x₃， x₄，x₅，x₆，x₁₁}，n（x₁， 3/6） ?X_Yes;n（x₁， 2/6） = {x₁，x₂，x₃， x₄，x₅，x₆，x₉，x₁₀，x₁₁}，d（x₁） ?d（x₉），n（x₁， 2/6） ?X_Yes; 当相似度阈值设为2/6时，邻域内的对象的类标签不相同，所以回退到上一个相似度，即此时将最小相似度阈值θ_x⁺为3/6。

定义6（距离）：设x是一个未分类对象，它与另一个对象x之间的距离距离定义为：

distance = 1/sim（x，x）-1/θ _x⁺;               （7）

由公式（7）可知，未分类对象与其他对象之间的相似度越低距离越大。并且此处定义的距离考虑到了x的相似度阈值，即此处定义的距离是相似度与相似度阈值之间的关系。

图2显示了对象之间的距离关系，将邻域抽象成圆，邻域的半径是1/θ_x⁺。x₁与对象x的相似度小于对象x的最小相似度阈值所以落在邻域外;x₂与对象x的相似度等于对象x的最小相似度阈值所以落在邻域边界上;x₁与对象x的相似度大于对象x的最小相似度阈值所以落在邻域内。

2  问题与算法

2.1  代表对象选举算法

在训练阶段，算法将依次对训练集进行四步处理从而生成分类器。代表对象选举算法步骤：

算法： 代表选举算法

输入： 决策信息系统S= {U，C，d }.

输出： 代表集合Y及代表覆盖域CR={（x，θ_x⁺） |x?Y}.

//初始化代表对象集、邻域集

（1）

Y=?，CR=?;

（2）

Computeθ_x⁺和n*（x）;

（3）

正域U = U/d = {X₁，X₂，…， X_|m|};

（4）

for（i= 1 tom） do

（5）

X=X_i;

（6）

whileX≠? do;

（7）

選择当前覆盖对象最多的代表x;

（8）

X=X–n^*（x_j）;

（9）

Y =Y+ {x};

（10）

end while

（11）

Y = Y∪Y;

（12）

end for

（13）

CR= {（x，θ_x⁺） |x?Y};

（14）

returnY，CR;

第（1）行，对各个用到的集合初始化;

第（2）行，计算每个对象的最小相似度阈值θ_x⁺和其最大邻域n*（x）;

第（3）行，根据对象的决策属性对其最大邻域整个邻域进行分类。

第（4）-（11）行，采用贪心的策略，选出每次覆盖当前正域对象最多的邻域。

第（13）-（14）行，返回代表对象集和邻域集

2.2  三种分类策略

文献[13]提出的RC算法中的类标签预测子算法中，针对有多个代表距离最近的问题采用简单投票的方法进行分类。本文提出两种新的分类策略，即基于规模策略和基于密度策略。

简单投票策略：几个距离最近的代表投票来决定要分类对象的类标签。如图3所示，根据定义6的距离公式，未分类对象x 落在三个代表x_1、x_2、x₃的邻域边界上，与代表之间的距离相同都为0。x₁、x₃的类标签是“+”，x₂的类标签是“-”，最终投票结果x 的类标签是“+”。

基于规模策略：再次比较代表邻域的规模，邻域规模更大的代表将决定未分类对象类标签。邻域规模更大是指代表的邻域覆盖更多的对象。规模更大的代表影响力更强，所以规模大的代表决定类标签。

基于密度策略：再次比较代表邻域的密度，拥有更高密度的代表将决定未分类对象类标签。基于密度策略与基于规模策略的区别在于前者是强调邻域内单位面积上的对象对象多，后者强调代表的邻域覆盖对象对象多。

规模策略和基于密度策略有部分交叉，但是并不相同。总的来说规模策略关注的是邻域内对象的数量，基于密度策略只考虑密度。如图4所示，图A规模策略会由代表x₁决定类标签，基于密度策略由代表x₂决定类标签。针对图B、D，规模策略和基于密度策略是相同的，都是由x₁决定未分类对象的类标签。图C两种策略都是由x₂决定待分类对象的类标签。

3  实验与分析

通过实验解决下列问题：

1）本文提出的基于密度分类策略、基于规模的分类策略与原有的简单投票的分类策略相比有没有优势？

2）在实验所用数据及上，三种策略哪一个性能更优？

3.1  对比实验

实验采用的UCI数据库^[15]中的iris、sonar、zoo和voting数据集，数据描述如表2所示：

为了体现出不同训练集和测试集比例，实验随机的将数据集划分成两部分。每个数据集实验设置的训练集规模为从1%到10%，每次递增1%。实验观察在训练集大小不同的情况下两种策略的分类效果。测试集中对象的类标签不可见，直到所有的未分类对象都得到预测类标签。为降低实验的随机性，每一个实验结果取10次相同实验的平均值。

其次，由于训练集和测试集是相对独立的两部分数据，生成的规则不一定能和测试集完全匹配。因此，需要用三个指标衡量分类器的性能，分别是分类精度、召回率、F-measure。分类精度指正确分类对象与需预测对象总数的比值;召回率是做出分类的对象数与需分类对象总数的比值;F-measure的定义如下：

F-measure =

3.2  实验分析

表3展示的是在所选的数据集上的实验结果。因为实验中对需预测对象都做了分類，所以召回率为1。因此分类进度与F-measure正相关，接下来本文对实验结果的F-measure做了对比分析。

表3中列举了训练集比例分别设置为0.02、0.04、0.06、0.07、0.08、0.09、0.1等情况下的实验结果数据。其中，分类性能最好的结果用加粗区分;分类性能排第二时，用斜体区分。结果对比显示：在iris数据集上，当训练集比例设为0.03和0.09时，简单投票策略的分类性能优于基于规模、基于密度的分类策略。当训练集比例设为0.06时，简单投票策略的分类性能稍优于基于规模的分类策略。其余情况本文提出的两种策略都高于简单的投票策略。其次，在9组实验中，基于密度的策略有6组分类性能最好，另外三组排第二;基于规模的策略有四组实验排第一。

在sonar数据集上，训练集比例设置为0.02、0.07和0.1时简单投票的分类性能最好。训练集比例设置为0.03、0.05、0.06、0.08和0.09时基于密度的策略分类效果最好。基于规模的策略分类性能大部分排在三种策略的第二位。在zoo、voting数据集上，基于密度的分类策略都是有六组实验数据排第一;简单投票策略有两组数据排第一。在这两个数据集上，基于规模的策略分类性能最差。

总体来看，4个数据集上基于密度的分类策略性能优于另外两种策略;基于规模的策略稍优于简单投票策略。基于规模的策略和基于密度的策略的分类性能相差不大，出现多组实验数据分类性能相同。这说明实验所用数据比较均匀，密度大的邻域对应的代表往往影响的范围也较大。

3.3  实验结论

现在回答本节开始提出的问题：实验所选用的四个数据集上，本文提出的策略对分类性能稍有提升，提升幅度不大。在实验所用数据集上，分类性能提升大部分都在1%以内。在zoo、voting两个数据集上，基于规模的策略和简单投票策略分类性能基本一致。另外，因为基于密度策略和基于规模策略分类性能相差很小，从侧面可以分析出来实验所用数据集比较均匀。

对于第二个问题：在实验所用数据集上，三种策略的排序为基于密度的策略、基于规模的策略、简单投票策略。但是三种策略分类性能相差并不大，基于密度的策略相对更优。

4  结束语

本文提出的两种对RC算法的改进策略对分类性能有提升，分类性能提升大部分在1%内，其中基于密度的策略相对更优。接下来的工作中，本研究将考虑代价敏感^[16]问题对分类的影响。

参考文献：

[1]      陈耀东， 王挺， 陈火旺. 半监督学习和主动学习相结合的浅层语义分析[J]. 中文信息学报， 2008， 22（2）：70-75.

[2]      周志华， 王珏. 机器学习及其应用2007[M]. 清华大学出版社， 2007.

[3]       Mitchell. Machine Learning[M]. McGraw-Hill， 2003.

[4]       Witten I H， Frank E. Data mining ：practical machine learning tools and techniques[J]. Acm Sigmod Record， 2011， 31（1）：76-77.

[5]      王光宏， 蒋平. 数据挖掘综述[J]. 同济大学学报（自然科学版）， 2004， 32（2）：246-252.

[6]      宫秀军. 贝叶斯学习理论及其应用研究[D]. 中国科学院计算技术研究所， 2002.

[7]      栾丽华， 吉根林. 决策树分类技术研究[J]. 计算机工程， 2004， 30（9）：94-96.

[8]      王济川， 郭志刚. Logistic回归模型：方法与应用[M]. 高等教育出版社， 2001.

[9]       Schuldt C， Laptev I， Caputo B. Recognizing Human Actions： A Local SVM Approach[C]// Proceedings of the 17th International Conference on Pattern Recognition， Volume 3. 2004：32-36.

[10]    SIMON HAYKIN. 神经网络原理 ： 第2版[M]. 机械工业出版社， 2006.

[11]    Pawlak Z. Rough sets[J]. Communications of the ACM， 1995， 38（11）：88-95.

[12]    Zakowski W. Approximation in the space（μ，π）[J]. Demonstration Mathematics，1983，16：761-769.

[13]    Zhang B W， Min F， Ciucci D. Representative-based classification through covering-based neighborhood rough sets[J]. Applied Intelligence， 2015， 43（4）：840-854.

[14]    Min F， Zhu W. A competition strategy to cost-sensitive decision trees[C]// Proceedings of the 7th international conference on Rough Sets and Knowledge Technology. 2012：359-368.

[15]    Blake C. UCI repository of machine learning databases[C]// Neural Information Processing Systems. 1998.

[16]    劉福伦，闵帆，张本文.代价敏感代表选举的邻域覆盖粗糙集分类方法[J].江苏科技大学学报（自然科学版），2017，31（02）：190-195.