代表選舉的分類策略對(duì)比

師彥文 王軒 王森 王宏杰

摘要：有學(xué)者已提出了針對(duì)名詞型數(shù)據(jù)的基于代表的鄰域覆蓋的分類算法。在該算法中，當(dāng)有不止一個(gè)有效代表距未分類對(duì)象最近時(shí)，采取簡單的投票策略來決定待分類對(duì)象的類標(biāo)簽。簡單的投票策略忽略了每個(gè)代表對(duì)未分類對(duì)象的影響能力不同。針對(duì)這個(gè)問題本文提出了基于密度和基于規(guī)模的分類策略。通過實(shí)驗(yàn)對(duì)簡單的投票策略、基于密度的分類策略、基于規(guī)模的分類策略的分類性能做了對(duì)比。

關(guān)鍵詞：代表;鄰域覆蓋;分類策略;粗糙集

中圖分類號(hào)：D922文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

引用：師彥文， 王軒， 王森， 等. 代表選舉的分類策略對(duì)比[J]. 數(shù)碼設(shè)計(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.

引言

分類問題是一種有監(jiān)督^[1]的學(xué)習(xí)方法，是機(jī)器學(xué)習(xí)^[2][3]、模式識(shí)別^[4]和數(shù)據(jù)挖掘^[5]中的一個(gè)重要課題。目前分類算法已被應(yīng)用到了許多領(lǐng)域，包括銀行金融、客戶分類、文本分類、醫(yī)藥分類和搜索引擎分類等。當(dāng)前的分類算法主要有樸素貝葉斯^[6]、決策樹^[7]、線性回歸^[8]、支持向量機(jī)^[9]、神經(jīng)網(wǎng)絡(luò)^[10]等。

1982年Z.Pawlak首次提出了粗糙集理論^[11];接著Zakowski^[12]提出了基于鄰域覆蓋的粗糙集模型。Zhang^[13]等提出了基于代表的粗糙集覆蓋的分類算法——RC（Representative-Based Classification through Covering-Based Neighborhood Rough Set）。這個(gè)算法中包含兩個(gè)子算法：一個(gè)是鄰域覆蓋的代表選舉算法，一個(gè)基于代表的分類算法。

有多個(gè)代表距未分類對(duì)象距離最近時(shí)，文獻(xiàn)[13]采用簡單的投票來決定未分類對(duì)象的類標(biāo)簽。簡單的投票策略在分類時(shí)忽略了每個(gè)代表的影響能力不同。因此，用簡單的投票策略確定未分類對(duì)象的類標(biāo)簽可能會(huì)影響最終的分類精度。本文針對(duì)上述情況提出了一個(gè)相似度策略，并通過實(shí)驗(yàn)與原有的簡單投票分類策略進(jìn)行了對(duì)比。

1 ?理論概念

定義1（決策信息系統(tǒng)^[14]） 決策信息系統(tǒng)S為一個(gè)三元組，定義為：

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

這里U指對(duì)象集合，也就是整個(gè)論域;C表示所有條件屬性集合;d表示決策屬性。表1列出了一個(gè)決策信息系統(tǒng)。

定義2（相似度） 任意x， y ? U在A ? C中的相似度記為：

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

其中

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

本文選擇對(duì)象的全部屬性，即A = C。本文采用overlap算法來計(jì)算相似度，根據(jù)定義2，通過表1的決策信息系統(tǒng)可以計(jì)算出sim（x₂， x₃） = 3/6，sim（x₁， x₁₁） = 5/6. 這樣可以計(jì)算得到相似度，用以描述兩個(gè)對(duì)象之間的相似關(guān)系。

定義3（鄰域） 對(duì)于任意x ? S，都可以設(shè)置相似度閾值θ，θ?（0，1]，那么定義對(duì)象的鄰域?yàn)椋?/p>

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

相似度閾值θ指的是作為對(duì)象鄰居的最小的相似度值。相似度閾值不為0，相似度閾值等于0時(shí)對(duì)象的鄰域?yàn)檫@個(gè)論域。根據(jù)定義3，相似度閾值取值范圍為{1/|C|，2/|C|，3/|C|……，1}。

相似度閾值設(shè)置的越小，對(duì)象的鄰域越大;反

之，對(duì)象的鄰域越小。根據(jù)定義3由表1的決策信

息系統(tǒng)可以計(jì)算出，n（x₁， 1） = {x₁}，n（x₁， 5/6） = {x₁，x₆，x₁₁}.

定義4（最小相似度閾值）S = （U，C，d）代表一個(gè)名詞型決策信息系統(tǒng)，d = {1， 2， … ， k}，U / {d} = {X₁， X₂， … ， X_k}，那么任意x?X_i的最小相似度閾值θ⁺定義如下：

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

此時(shí)θ_x⁺由對(duì)象x和決策信息系統(tǒng)S共同決定。

定義5（最大鄰域）最小相似度閾值對(duì)應(yīng)的鄰域就是最大鄰域;對(duì)于任意x ? S的最大鄰域可記為：

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

最大鄰域就是在論域空間中類標(biāo)簽相同的情況下，覆蓋對(duì)象最多的鄰域。

圖1展示了一個(gè)對(duì)象計(jì)算最小相似度閾值及圈定其最大鄰域的過程。結(jié)合表1給定的決策信息系統(tǒng)，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; 當(dāng)相似度閾值設(shè)為2/6時(shí)，鄰域內(nèi)的對(duì)象的類標(biāo)簽不相同，所以回退到上一個(gè)相似度，即此時(shí)將最小相似度閾值θ_x⁺為3/6。

定義6（距離）：設(shè)x是一個(gè)未分類對(duì)象，它與另一個(gè)對(duì)象x之間的距離距離定義為：

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

由公式（7）可知，未分類對(duì)象與其他對(duì)象之間的相似度越低距離越大。并且此處定義的距離考慮到了x的相似度閾值，即此處定義的距離是相似度與相似度閾值之間的關(guān)系。

圖2顯示了對(duì)象之間的距離關(guān)系，將鄰域抽象成圓，鄰域的半徑是1/θ_x⁺。x₁與對(duì)象x的相似度小于對(duì)象x的最小相似度閾值所以落在鄰域外;x₂與對(duì)象x的相似度等于對(duì)象x的最小相似度閾值所以落在鄰域邊界上;x₁與對(duì)象x的相似度大于對(duì)象x的最小相似度閾值所以落在鄰域內(nèi)。

2 ?問題與算法

2.1 ?代表對(duì)象選舉算法

在訓(xùn)練階段，算法將依次對(duì)訓(xùn)練集進(jìn)行四步處理從而生成分類器。代表對(duì)象選舉算法步驟：

算法： 代表選舉算法

輸入： 決策信息系統(tǒng)S= {U，C，d }.

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

//初始化代表對(duì)象集、鄰域集

（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）

選擇當(dāng)前覆蓋對(duì)象最多的代表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）行，對(duì)各個(gè)用到的集合初始化;

第（2）行，計(jì)算每個(gè)對(duì)象的最小相似度閾值θ_x⁺和其最大鄰域n*（x）;

第（3）行，根據(jù)對(duì)象的決策屬性對(duì)其最大鄰域整個(gè)鄰域進(jìn)行分類。

第（4）-（11）行，采用貪心的策略，選出每次覆蓋當(dāng)前正域?qū)ο笞疃嗟泥徲颉?/p>

第（13）-（14）行，返回代表對(duì)象集和鄰域集

2.2? 三種分類策略

文獻(xiàn)[13]提出的RC算法中的類標(biāo)簽預(yù)測(cè)子算法中，針對(duì)有多個(gè)代表距離最近的問題采用簡單投票的方法進(jìn)行分類。本文提出兩種新的分類策略，即基于規(guī)模策略和基于密度策略。

簡單投票策略：幾個(gè)距離最近的代表投票來決定要分類對(duì)象的類標(biāo)簽。如圖3所示，根據(jù)定義6的距離公式，未分類對(duì)象x 落在三個(gè)代表x_1、x_2、x₃的鄰域邊界上，與代表之間的距離相同都為0。x₁、x₃的類標(biāo)簽是“+”，x₂的類標(biāo)簽是“-”，最終投票結(jié)果x 的類標(biāo)簽是“+”。

基于規(guī)模策略：再次比較代表鄰域的規(guī)模，鄰域規(guī)模更大的代表將決定未分類對(duì)象類標(biāo)簽。鄰域規(guī)模更大是指代表的鄰域覆蓋更多的對(duì)象。規(guī)模更大的代表影響力更強(qiáng)，所以規(guī)模大的代表決定類標(biāo)簽。

基于密度策略：再次比較代表鄰域的密度，擁有更高密度的代表將決定未分類對(duì)象類標(biāo)簽?；诿芏炔呗耘c基于規(guī)模策略的區(qū)別在于前者是強(qiáng)調(diào)鄰域內(nèi)單位面積上的對(duì)象對(duì)象多，后者強(qiáng)調(diào)代表的鄰域覆蓋對(duì)象對(duì)象多。

規(guī)模策略和基于密度策略有部分交叉，但是并不相同?？偟膩碚f規(guī)模策略關(guān)注的是鄰域內(nèi)對(duì)象的數(shù)量，基于密度策略只考慮密度。如圖4所示，圖A規(guī)模策略會(huì)由代表x₁決定類標(biāo)簽，基于密度策略由代表x₂決定類標(biāo)簽。針對(duì)圖B、D，規(guī)模策略和基于密度策略是相同的，都是由x₁決定未分類對(duì)象的類標(biāo)簽。圖C兩種策略都是由x₂決定待分類對(duì)象的類標(biāo)簽。

3 ?實(shí)驗(yàn)與分析

通過實(shí)驗(yàn)解決下列問題：

1）本文提出的基于密度分類策略、基于規(guī)模的分類策略與原有的簡單投票的分類策略相比有沒有優(yōu)勢(shì)？

2）在實(shí)驗(yàn)所用數(shù)據(jù)及上，三種策略哪一個(gè)性能更優(yōu)？

3.1 ?對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)采用的UCI數(shù)據(jù)庫^[15]中的iris、sonar、zoo和voting數(shù)據(jù)集，數(shù)據(jù)描述如表2所示：

為了體現(xiàn)出不同訓(xùn)練集和測(cè)試集比例，實(shí)驗(yàn)隨機(jī)的將數(shù)據(jù)集劃分成兩部分。每個(gè)數(shù)據(jù)集實(shí)驗(yàn)設(shè)置的訓(xùn)練集規(guī)模為從1%到10%，每次遞增1%。實(shí)驗(yàn)觀察在訓(xùn)練集大小不同的情況下兩種策略的分類效果。測(cè)試集中對(duì)象的類標(biāo)簽不可見，直到所有的未分類對(duì)象都得到預(yù)測(cè)類標(biāo)簽。為降低實(shí)驗(yàn)的隨機(jī)性，每一個(gè)實(shí)驗(yàn)結(jié)果取10次相同實(shí)驗(yàn)的平均值。

其次，由于訓(xùn)練集和測(cè)試集是相對(duì)獨(dú)立的兩部分?jǐn)?shù)據(jù)，生成的規(guī)則不一定能和測(cè)試集完全匹配。因此，需要用三個(gè)指標(biāo)衡量分類器的性能，分別是分類精度、召回率、F-measure。分類精度指正確分類對(duì)象與需預(yù)測(cè)對(duì)象總數(shù)的比值;召回率是做出分類的對(duì)象數(shù)與需分類對(duì)象總數(shù)的比值;F-measure的定義如下：

F-measure =

3.2 ?實(shí)驗(yàn)分析

表3展示的是在所選的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。因?yàn)閷?shí)驗(yàn)中對(duì)需預(yù)測(cè)對(duì)象都做了分類，所以召回率為1。因此分類進(jìn)度與F-measure正相關(guān)，接下來本文對(duì)實(shí)驗(yàn)結(jié)果的F-measure做了對(duì)比分析。

表3中列舉了訓(xùn)練集比例分別設(shè)置為0.02、0.04、0.06、0.07、0.08、0.09、0.1等情況下的實(shí)驗(yàn)結(jié)果數(shù)據(jù)。其中，分類性能最好的結(jié)果用加粗區(qū)分;分類性能排第二時(shí)，用斜體區(qū)分。結(jié)果對(duì)比顯示：在iris數(shù)據(jù)集上，當(dāng)訓(xùn)練集比例設(shè)為0.03和0.09時(shí)，簡單投票策略的分類性能優(yōu)于基于規(guī)模、基于密度的分類策略。當(dāng)訓(xùn)練集比例設(shè)為0.06時(shí)，簡單投票策略的分類性能稍優(yōu)于基于規(guī)模的分類策略。其余情況本文提出的兩種策略都高于簡單的投票策略。其次，在9組實(shí)驗(yàn)中，基于密度的策略有6組分類性能最好，另外三組排第二;基于規(guī)模的策略有四組實(shí)驗(yàn)排第一。

在sonar數(shù)據(jù)集上，訓(xùn)練集比例設(shè)置為0.02、0.07和0.1時(shí)簡單投票的分類性能最好。訓(xùn)練集比例設(shè)置為0.03、0.05、0.06、0.08和0.09時(shí)基于密度的策略分類效果最好?；谝?guī)模的策略分類性能大部分排在三種策略的第二位。在zoo、voting數(shù)據(jù)集上，基于密度的分類策略都是有六組實(shí)驗(yàn)數(shù)據(jù)排第一;簡單投票策略有兩組數(shù)據(jù)排第一。在這兩個(gè)數(shù)據(jù)集上，基于規(guī)模的策略分類性能最差。

總體來看，4個(gè)數(shù)據(jù)集上基于密度的分類策略性能優(yōu)于另外兩種策略;基于規(guī)模的策略稍優(yōu)于簡單投票策略。基于規(guī)模的策略和基于密度的策略的分類性能相差不大，出現(xiàn)多組實(shí)驗(yàn)數(shù)據(jù)分類性能相同。這說明實(shí)驗(yàn)所用數(shù)據(jù)比較均勻，密度大的鄰域?qū)?yīng)的代表往往影響的范圍也較大。

3.3 ?實(shí)驗(yàn)結(jié)論

現(xiàn)在回答本節(jié)開始提出的問題：實(shí)驗(yàn)所選用的四個(gè)數(shù)據(jù)集上，本文提出的策略對(duì)分類性能稍有提升，提升幅度不大。在實(shí)驗(yàn)所用數(shù)據(jù)集上，分類性能提升大部分都在1%以內(nèi)。在zoo、voting兩個(gè)數(shù)據(jù)集上，基于規(guī)模的策略和簡單投票策略分類性能基本一致。另外，因?yàn)榛诿芏炔呗院突谝?guī)模策略分類性能相差很小，從側(cè)面可以分析出來實(shí)驗(yàn)所用數(shù)據(jù)集比較均勻。

對(duì)于第二個(gè)問題：在實(shí)驗(yàn)所用數(shù)據(jù)集上，三種策略的排序?yàn)榛诿芏鹊牟呗浴⒒谝?guī)模的策略、簡單投票策略。但是三種策略分類性能相差并不大，基于密度的策略相對(duì)更優(yōu)。

4? 結(jié)束語

本文提出的兩種對(duì)RC算法的改進(jìn)策略對(duì)分類性能有提升，分類性能提升大部分在1%內(nèi)，其中基于密度的策略相對(duì)更優(yōu)。接下來的工作中，本研究將考慮代價(jià)敏感^[16]問題對(duì)分類的影響。

參考文獻(xiàn)：

[1]????? 陳耀東， 王挺， 陳火旺. 半監(jiān)督學(xué)習(xí)和主動(dòng)學(xué)習(xí)相結(jié)合的淺層語義分析[J]. 中文信息學(xué)報(bào)， 2008， 22（2）：70-75.

[2]????? 周志華， 王玨. 機(jī)器學(xué)習(xí)及其應(yīng)用2007[M]. 清華大學(xué)出版社， 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]????? 王光宏， 蔣平. 數(shù)據(jù)挖掘綜述[J]. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2004， 32（2）：246-252.

[6]????? 宮秀軍. 貝葉斯學(xué)習(xí)理論及其應(yīng)用研究[D]. 中國科學(xué)院計(jì)算技術(shù)研究所， 2002.

[7]????? 欒麗華， 吉根林. 決策樹分類技術(shù)研究[J]. 計(jì)算機(jī)工程， 2004， 30（9）：94-96.

[8]????? 王濟(jì)川， 郭志剛. Logistic回歸模型：方法與應(yīng)用[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. 神經(jīng)網(wǎng)絡(luò)原理 ： 第2版[M]. 機(jī)械工業(yè)出版社， 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]??? 劉福倫，閔帆，張本文.代價(jià)敏感代表選舉的鄰域覆蓋粗糙集分類方法[J].江蘇科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，31（02）：190-195.