李浩 舒炫煜 何楚 田恬恬 王勝春 張錦

摘要：K近鄰算法是一種高效且易實(shí)現(xiàn)的監(jiān)督型機(jī)器學(xué)習(xí)算法。對于多分類問題通常將多分類任務(wù)拆解為多個二分類任務(wù)進(jìn)行求解，一般采取OVO（一對一）及OVA（一對多）兩種機(jī)制進(jìn)行解決。該文主要在鳶尾花數(shù)據(jù)集上，對兩種方式進(jìn)行比較，仿真結(jié)果表明，采用這兩種不同的方式處理多分類問題，結(jié)果是一致的，但各有優(yōu)劣。

關(guān)鍵詞：一對一策略;一對多策略;K近鄰算法

中圖分類號：TP18? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? 文章編號：1009-3044（2018）36-0230-02

Abstract：KNN algorithm is an efficient and easy to implement supervised machine learning algorithm. For multi-classification problems， multi-classification tasks are usually decomposed into multiple binary tasks to solve. OVO （one versus one） and OVA （one versus all） mechanisms are generally adopted to solve the problem. In this paper， we compare the two methods on Iris data set. The simulation results show that the two methods have the same results， but each has its own advantages.

Key words：One versus one strategy; One versus all? strategy; K nearest neighbor algorithm

在現(xiàn)實(shí)生活中會經(jīng)常遇到多分類問題，即待分類樣本類別大于2。目前，一般基于支持向量機(jī)的多分類問題研究居多?；赟VM的多分類方法主要有2類途徑，其中一類是拆解策略，即將一個多分類問題分解成多個二分類問題，通過構(gòu)造多個SVM二值分類器并將它們組合起來實(shí)現(xiàn)多類分類，如“一對一”，“一對多”，“DAG SVM ”等方法[1]。另一類是整體方法，即直接在一個優(yōu)化公式中同時考慮所有類別的參數(shù)優(yōu)化[2].整體方法慢，分類精度不占優(yōu)，所以，目前實(shí)際應(yīng)用中還是以“一對一”和“一對多”方法為主。在文獻(xiàn)[3]，提出決策有向無環(huán)圖和有向二叉樹來處理多分類問題。在文獻(xiàn)[4]提出了兩個新的K類（K>3）多分類算法：一對一對一即一對一對多算法，實(shí)驗(yàn)結(jié)果明顯提高了識別的精度，因此拆分策略有有效的。

本文利用處理多分類問題的兩種拆分策略在鳶尾花數(shù)據(jù)集上進(jìn)行對比研究，比較兩種拆分策略的優(yōu)劣性，為后續(xù)多分類問題的研究起到一定的指引作用。

1 一對一及一對多策略概述

通常對于多分類任務(wù)解決的基本思路是將多分類問題拆解為多個二分類任務(wù)進(jìn)行求解。具體來說，是先對多分類問題進(jìn)行拆分，然后為拆出的每個二分類任務(wù)訓(xùn)練一個分類器;在測試時，對這些分類器的預(yù)測結(jié)果進(jìn)行集成以獲得最終的多分類結(jié)果。通常采用兩種經(jīng)典且容易實(shí)現(xiàn)的拆分策略，即一對一（OVO）和一對多（OVA）。

1.1 一對一概述

一對一（OVO）拆分策略：將多分類問題進(jìn)行拆分，若樣本具有M個類別，則將數(shù)據(jù)集劃分為M部分，每一部分為一個類別，然后將這M部分兩兩配對，因此可形成M（M-1）/2個二分類任務(wù)，即可訓(xùn)練M（M-1）/2個分類器，可得到M（M-1）/2個預(yù)測結(jié)果，最后用投票法決定測試樣本的最終預(yù)測類別：把被預(yù)測得最多的類別作為最終的分類結(jié)果。

1.2 一對多概述

一對多（OVA）拆分策略：將多分類問題進(jìn)行拆分，若樣本具有M個類別，則將數(shù)據(jù)集劃分為M部分，每一部分為一個類別，與OVO不同的是，使用訓(xùn)練時的分類器數(shù)目與參與訓(xùn)練的數(shù)據(jù)不同。OVA只需要M個訓(xùn)練器，即只形成M個二分類任務(wù)，因此參與訓(xùn)練的數(shù)據(jù)與OVO不同，它是依次分別以每一類別為正類，其余類別的數(shù)據(jù)集統(tǒng)一帶上負(fù)類的標(biāo)簽，也就是將其余數(shù)據(jù)集的標(biāo)簽重新打上。若最終各個分類器的預(yù)測結(jié)果出現(xiàn)一正多負(fù)的情形，則將最終的預(yù)測類別附上所在正類的樣本標(biāo)簽;若出現(xiàn)結(jié)果為多正多負(fù)的情形，則最終的預(yù)測類別為置信度最高的正類樣本的標(biāo)簽。

2 OVO及OVA比較研究

2.1 數(shù)據(jù)集介紹

此次研究選取UCI標(biāo)準(zhǔn)數(shù)據(jù)庫中的鳶尾花數(shù)據(jù)集，該數(shù)據(jù)集是常用于分類的，是一類多重變量分析的數(shù)據(jù)集，數(shù)據(jù)集具有150個樣本，其中有三個類別，依次是山鳶尾、雜色鳶尾以及維吉尼亞鳶尾，它有四個屬性，分別由花萼長度、花萼寬度、花瓣長度及花瓣寬度構(gòu)成，類別比值為50：50：50，所用的鳶尾花數(shù)據(jù)集部分?jǐn)?shù)據(jù)如表1所示。

2.2 一對一及一對多實(shí)驗(yàn)流程

采用OVO及OVA方式處理多分類問題，首先進(jìn)行的是數(shù)據(jù)的劃分，數(shù)據(jù)有M類別，則劃分為M部分，每一部分代表一個類別，然后都采用KNN算法作為分類器，因?yàn)镵近鄰算法是一種高效且易實(shí)現(xiàn)的監(jiān)督型機(jī)器學(xué)習(xí)算法。

2.3 結(jié)果分析

本文所有實(shí)驗(yàn)全部在 Windows 7操作系統(tǒng)下完成，選用 UCI數(shù)據(jù)集上的鳶尾花數(shù)據(jù)集，基于MATLAB對OVO及OVA兩種解決多分類問題的方法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)分兩組進(jìn)行，從不同角度比較OVO及OVA方法的優(yōu)劣性。

實(shí)驗(yàn)1：實(shí)驗(yàn)選取90個鳶尾花訓(xùn)練樣本集，60個鳶尾花測試樣本集，固定訓(xùn)練集與樣本集的數(shù)目，取不同K近鄰數(shù)目，比較兩種方式在不同K值下的識別精度。

分析：當(dāng)訓(xùn)練集數(shù)目固定時，在訓(xùn)練集樣本為90個，測試集樣本為60個時，兩種方式所得到的實(shí)驗(yàn)結(jié)果是一樣的，但是在采用OVO方式處理問題時，可能會出現(xiàn)投票數(shù)相同的情況，則對最終的預(yù)測結(jié)果產(chǎn)生影響，而OVA的方式則不會出現(xiàn)此種情況，當(dāng)出現(xiàn)時則將置信度大的類別判為最終預(yù)測類別。

實(shí)驗(yàn)2：固定K的取值，當(dāng)K=5時，訓(xùn)練集樣本不斷增加，比較兩種方式的識別精度。

分析：當(dāng)K值固定時，隨著訓(xùn)練集樣本數(shù)目的增加時，兩種方式所得到的實(shí)驗(yàn)結(jié)果是一致的。

3 結(jié)論

在鳶尾花數(shù)據(jù)集上用兩種處理多分類問題的方式，進(jìn)行比較研究，發(fā)現(xiàn)兩種方式的結(jié)果是一樣的，但當(dāng)數(shù)據(jù)集增大，類別增多時，用OVO方式處理多分類問題較為復(fù)雜，因?yàn)橐?xùn)練M（M-1）/2個分類器，也易在投票環(huán)節(jié)出現(xiàn)最多類票數(shù)相同情況，而用OVA方式去處理多分類問題，其分類器的個數(shù)在減少，但在訓(xùn)練模型的時候，正類數(shù)據(jù)與負(fù)類數(shù)據(jù)會出現(xiàn)不平衡情況，當(dāng)這種不平衡比例增大時，會影響分類的結(jié)果。因此，在一般情況下，兩種方式處理多分類問題，效果差不多，但兩種方法各有優(yōu)劣。在后一階段的工作中，看能否尋找一種結(jié)合兩者優(yōu)勢的方式去解決多分類問題。

參考文獻(xiàn)：

[1] HsuChih-wei，LinChih-jen.A comparisonof methodsfor multiclasssupportvectormachines[J].IEEE Transactionson NeuralNetworks，2002，13（2）：415-425.

[2] Bredensteiner E J ， Bennett K P. Multicategory Classification by Support Vector Machines[J]. Computational Optimization and Applications， 1999， 12（1-3）：53-79.

[3] 任進(jìn)軍，陳軍. 基于層次結(jié)構(gòu)的多分類算法研究[J]. 貴州大學(xué)學(xué)報(bào)：自然科學(xué)版，2017（4）：59-63.

[4] 翟佳，胡毅慶，成小偉.基于三分類支持向量機(jī)的多分類算法研究[J].中北大學(xué)學(xué)報(bào)：自然科學(xué)版，2015（5）：520-525.

[通聯(lián)編輯：唐一東]