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

朱靜雯，向仕兵

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

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

朱靜雯，向仕兵

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

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

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

0 引言

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

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

1 線性分類理器[2]

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

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

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

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

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

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

2.1 感知器算法

為方便表示，定義新矢量a=[wT，w0]T稱增廣權(quán)值矢量，訓(xùn)練樣本集中每個(gè)樣本點(diǎ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個(gè)點(diǎn)正確分類。

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

2.2 最小誤差平方算法

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

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

2.3 Fisher算法[3]

2.4 支持向量機(jī)學(xué)習(xí)算法

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

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

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

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

3.1 線性可分?jǐn)?shù)據(jù)

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

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

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

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

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

3.2 線性不可分?jǐn)?shù)據(jù)

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

圖3 Fisher算法分類效果圖

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

圖5 三種算法分類效果綜合對(duì)比圖

圖6 支持向量機(jī)算法

圖7 非線性可分?jǐn)?shù)據(jù)

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

[5]秦鋒，楊波，程澤凱.分類器性能評(píng)價(jià)標(biāo)準(zhǔn)研究[J].計(jì)算機(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àn)閼?yīng)用數(shù)學(xué)

2017-01-13

2017-04-02

向仕兵（1996-），男，四川宣漢人，本科，研究方向?yàn)橛?jì)算數(shù)學(xué)