基于多分類問題處理機制的研究

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

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

關鍵詞：一對一策略;一對多策略;K近鄰算法

中圖分類號：TP18? ? ? ? 文獻標識碼：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

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

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

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

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

1.1 一對一概述

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

1.2 一對多概述

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

2 OVO及OVA比較研究

2.1 數據集介紹

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

2.2 一對一及一對多實驗流程

采用OVO及OVA方式處理多分類問題，首先進行的是數據的劃分，數據有M類別，則劃分為M部分，每一部分代表一個類別，然后都采用KNN算法作為分類器，因為K近鄰算法是一種高效且易實現的監督型機器學習算法。

2.3 結果分析

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

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

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

實驗2：固定K的取值，當K=5時，訓練集樣本不斷增加，比較兩種方式的識別精度。

分析：當K值固定時，隨著訓練集樣本數目的增加時，兩種方式所得到的實驗結果是一致的。

3 結論

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

參考文獻：

[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]. 貴州大學學報：自然科學版，2017（4）：59-63.

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

[通聯編輯：唐一東]