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

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

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

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

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

1 一對(duì)一及一對(duì)多策略概述

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

1.1 一對(duì)一概述

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

1.2 一對(duì)多概述

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

2 OVO及OVA比較研究

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

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

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

采用OVO及OVA方式處理多分類問(wèn)題，首先進(jìn)行的是數(shù)據(jù)的劃分，數(shù)據(jù)有M類別，則劃分為M部分，每一部分代表一個(gè)類別，然后都采用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對(duì)OVO及OVA兩種解決多分類問(wèn)題的方法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)分兩組進(jìn)行，從不同角度比較OVO及OVA方法的優(yōu)劣性。

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

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

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

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

3 結(jié)論

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

參考文獻(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)編輯：唐一東]