常用線性分類器算法及基于Mathematica三維可視化

朱靜雯，向仕兵

（西南科技大學理學院，綿陽 621010）

常用線性分類器算法及基于Mathematica三維可視化

朱靜雯，向仕兵

（西南科技大學理學院，綿陽 621010）

線性分類是利用線性判別函數將不同類數據進行分類的方法，在模式識別中有著重要應用。介紹感知器算法、最小誤差平方算法、Fisher算法及支持向量機學習算法等常用線性分類算法。利用Mathematica編程實現計算及可視化三維線性分類，并對不同分類算法的分類效果進行對比。

線性分類器；分類算法；Mathematica；三維可視化；效果對比

0 引言

當要分類兩類樣本的時候，一個很自然的想法是找一個平面將其盡可能的分開，如能全部分類則稱線性可分，如不能全部分類，則應使錯誤分類的點數盡可能少。根據函數間隔最優確定分類超平面的方法稱為支持向量機。分類在現實中如模式識別和人工智能應用中被廣泛應用，具有重要實際意義，實現支持向量機的基本功能對學習和理解支持向量機及后續機器學習具有較大幫助。雖然目前的各種算法均已成熟，但在實際選取的時候各類算法仍會有各自的優缺點，且均以二維數據為例，以三維數據為例的文獻并不多見。本文介紹了常見分類算法并實現三維空間點分類及對不同算法的分類效果進行比較。

而Mathematica是一款集數值及符號運算、編程語言、數據操作與分析、可視化與圖形功能的優秀科學計算軟件，強大的數值解析能力為高維大批量數據的計算提供了強大的保障，具如二維及三維繪圖函數、圖元函數、密度圖、等高線等繪圖函數，在各類學科中均有重要運用，依托Mathematica[1]豐富的圖形呈現效果實現線性分類可視化可直觀呈現需要解決的分類問題解及分類效果、幫助人們更直觀的理解。

1 線性分類理器[2]

數據點分類在模式識別中運用較多，根據解析幾何知識可知，n維空間超平面H為：

滿足上述方程的點x=[x1，x2，…，xn]T在超平面上，將方程的左半部分定義為一個判別函數：

并由僅含一次項稱線性判別函數，令權值w={w1，w2，…，wn}，w0為偏置，則可將其寫作適量內積形式

線性分類器g（x）將特征空間劃分為兩個區域g（x）〉0&g（x）〈0所以給出常見的兩類已分類數據點ω1，ω2根據：

則可以訓練出該超平面g（x）=0。

2 常用線性分類學習算法

2.1 感知器算法

為方便表示，定義新矢量a=[wT，w0]T稱增廣權值矢量，訓練樣本集中每個樣本點也在最后增加一維常數1，并令ω2類樣本乘以-1，稱增廣和規范化訓練樣本

權值及樣本規范化后式（5）可表示稱統一形式：

不等式組（6）的解存在但并不唯一，若存在a使得不等式組（6）成立，分類器（3）能將所有數據正確分類，若存在aTyj〈0，j∈1，…，n，則增廣權值矢量a不能將第j個點正確分類。

計算最終權值，其中η〉0成為學習率。

2.2 最小誤差平方算法

當存在線性不可分的時候，感知器算法是不收斂的，所以不等式組（6）永遠得到不到穩定解，所以對每個訓練樣本給定一個整數bi〉0，使得不等式組yiTa〉ai〉0，i=1，…，m成立，并取b=[bi，b2，…，bn]T為常數矢量，yi=[yi1，yi2，…，yin]T，i=1，…，m為個已知分類點中的第i 個n維空間點，即可將不等式組化為矩陣方程：

由于式（9）一般為超定方程組，所以可以求取其最小二乘解a*=（YTY）-1YTb，并令Y+=（YTY）-1YT，所以a*= Y+b，并稱其為式（9）的偽逆解。

2.3 Fisher算法[3]

2.4 支持向量機學習算法

通過支持向量機學習算法確定最優分界面，并由優化準則函數間隔：

根據類別標識Zi∈{-1，1}確定最近函數間隔bmin，其幾何間隔γ=1/‖w‖取得最大時可確定最優分類超平面的優化準則及約束條件

對原始優化問題構造Lagrange函數：

3 基于Mathematica實現三維數據點分類

3.1 線性可分數據

本文基于兩類分類數據學習三維分割平面并將各個算法的分類效果進行對比，首先隨機生成待分類的兩類數據，并在兩個三維空間球域中隨機生成線性可分數據點，如圖1所示。

根據圖1中分類數據利用感知器算法確定該兩類數據的分類超平面如圖2所示，其中圖2中左邊部分藍色平面為隨機生成的初始平面，右邊棕色平面為經過感知器算法調整后的最終收斂三維平面，圖3為通過Fisher算法生成的三維分類效果圖，圖4為最小誤差平方法生成的分類效果圖。

圖5對圖2-圖4中分類算法的分類效果的進行了對比[4]，可見當數據線性可分的時候，上述三種算法均可計算出可分分類平面，但是不同算法得到的分類界面有較大的差異，一方面體現了分類界面的不唯一性，另一方面體現了不同算法在線性分類上的差異，通過上述圖1所示隨機生成的數據及不同算法的分類效果可以看到最小誤差平方法一般能得到很好的效果，但是經過測試Fisher算法的分類效果受初始數據點的不同分布影響較大，在多次隨機生成三維空間點數據進行仿真時，Fisher算法出現線性可分數據訓練出不可分分界面的情況，具體原因尚待深究。最后圖6為支持向量機算法得到的分類效果圖，由于支持向量機理論即為確定最優分類界面，并可實證上述幾種分類算法中支持向量機的分類效果最好。

圖1 空間球體中兩類線性可分數據

圖2 感知器算法分類效果圖

3.2 線性不可分數據

由于在非線性可分的情況下，各算法根據準則函數進行判別，所以本文就非線性可分數據統計各個算法計算出的超平面的數據分類效果進行對比，由于數據不同，不同的實驗可能出現不一樣的結果，本文采用如圖7所示的非線性可分數據，其兩類點中紅色點54個、綠色點40個共計94個數據點。并定義定義C1與C2分別是正確分類的正例、負例個數，W1與W2分別為錯誤分類的正例、負例個數，實際正例數為P=C1+W2，實際負例數為N=C2+W1，實例總數為T=P+N。

圖3 Fisher算法分類效果圖

圖4 最小誤差平方法分類效果圖

圖5 三種算法分類效果綜合對比圖

圖6 支持向量機算法

圖7 非線性可分數據

圖8 感知器算法非線性可分分類效果

圖9 Fisher算法非線性可分分類效果

圖10 最小誤差平方發非線性可分分類效果

圖11 支持向量機算法非線性可分分類效果

表1 各算法所得平面的分類情況及對比

據表1總數據可知，線性可分的情況下上述四種算法均能得到分類界面，但在線性不可分時，感知算法對數據的分布較為敏感，一般得不到很好的效果，并隨迭代次數的增加權值不收斂且偏差較大。其余三種算法均能得到唯一分類超平面，就本次測試數據而言正確分類率均達到80%以上，Fisher算法使用數據降維投影法通過數據散步矩陣通過特征向量確定權值，支持向量機通過最大化函數間隔得到優化準則函數并通過對偶問題的解確定權值，可唯一確定分類界面，算法相對較穩定，其中穩定性最好為最小誤差平方法，準確度RC達91。49%，查準率PC1達93。75%，查全率RC1達90%，其數學本質為線性方程組的最小二乘解，后面三種算法以不同方式綜合考慮所有數據對分類面的平均影響，可解釋為什么相對分類效果較優。

4 結語

線性分類器是一種較為簡單的分類器，主要針對線性可分數據的時候能夠取得較好的分類效果，如果數據線性不可分以及存在多類數據的時候非線性分類器可得到更好的分類效果，非線性分類器的處理方法一般利用核函數將數據映射到高位空間實現線性可分，從某種意義上說非線性判別函數分類是線性函數分類的推廣，所以線性分類的基礎就尤為重要，本文通過介紹常用線性分類算法實現三維分類及支持向量機算法實現最優分類界面，并對這幾種算法通過非線性可分數據進行了算法優劣對比，本文所述的四種算法各有優劣，在實際運用的時候需綜合考慮數據分布以確定使用哪種分類算法。

[1]李路，江開忠，張學山.基于Mathematica的三維數據處理[J].上海工程技術大學學報，2008，22（4）:339-343.

[2]劉家峰，趙巍，朱海龍.模式識別[M].哈爾濱工業大學出版社，2014：72-93.

[3]李文斌，陳薿英，張娟.使用Fisher線性判別方法的提取分類器[J].計算機工程與應用，2010，46（10）：132-134.

[4]李艷芳.線性判別式的比較與優化方法研究[D].華東理工大學，2014：19-22.

[5]秦鋒，楊波，程澤凱.分類器性能評價標準研究[J].計算機技術與發展，2006，16（10）：85-87.

Commonly Used Linear Classification Algorithms and 3D Visualization Based on Mathematica

ZHU Jing-wen，XIANG Shi-bing
（School of Science，Southwest University of Science and Technology，Mianyang 621010）

Linear classification is a method to classify different kinds of data using linear discriminant function,which is of important significance for Pattern Recognition.Introduces the common linear classification algorithms such as Perceptron Algorithm,Least Error Square Algorithm and Fisher Algorithm.Achieves the data calculation of different algorithm and the 3D visualization of linear classification with scientific computing software Mathematica,and then compares the classification effect of different classification algorithms.

Linear Classifier;Classification Algorithm;Mathematica;3D Visualization;Effect Comparison

1007-1423（2017）10-0014-06

10.3969/j.issn.1007-1423.2017.10.004

朱靜雯（1996-），女，四川綿竹人，本科，研究方向為應用數學

2017-01-13

2017-04-02

向仕兵（1996-），男，四川宣漢人，本科，研究方向為計算數學