朱靜雯，向仕兵

（西南科技大學(xué)理學(xué)院，綿陽 621010）

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

朱靜雯，向仕兵

（西南科技大學(xué)理學(xué)院，綿陽 621010）

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

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

0 引言

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

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

1 線性分類理器[2]

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

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

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

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

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

2 常用線性分類學(xué)習(xí)算法

2.1 感知器算法

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

權(quán)值及樣本規(guī)范化后式（5）可表示稱統(tǒng)一形式：

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

計算最終權(quán)值，其中η〉0成為學(xué)習(xí)率。

2.2 最小誤差平方算法

當(dāng)存在線性不可分的時候，感知器算法是不收斂的，所以不等式組（6）永遠得到不到穩(wěn)定解，所以對每個訓(xùn)練樣本給定一個整數(shù)bi〉0，使得不等式組yiTa〉ai〉0，i=1，…，m成立，并取b=[bi，b2，…，bn]T為常數(shù)矢量，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 支持向量機學(xué)習(xí)算法

通過支持向量機學(xué)習(xí)算法確定最優(yōu)分界面，并由優(yōu)化準(zhǔn)則函數(shù)間隔：

根據(jù)類別標(biāo)識Zi∈{-1，1}確定最近函數(shù)間隔bmin，其幾何間隔γ=1/‖w‖取得最大時可確定最優(yōu)分類超平面的優(yōu)化準(zhǔn)則及約束條件

對原始優(yōu)化問題構(gòu)造Lagrange函數(shù)：

3 基于Mathematica實現(xiàn)三維數(shù)據(jù)點分類

3.1 線性可分數(shù)據(jù)

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

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

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

圖1 空間球體中兩類線性可分數(shù)據(jù)

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

3.2 線性不可分數(shù)據(jù)

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

圖3 Fisher算法分類效果圖

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

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

圖6 支持向量機算法

圖7 非線性可分數(shù)據(jù)

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

[5]秦鋒，楊波，程澤凱.分類器性能評價標(biāo)準(zhǔn)研究[J].計算機技術(shù)與發(fā)展，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-），女，四川綿竹人，本科，研究方向為應(yīng)用數(shù)學(xué)

2017-01-13

2017-04-02

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