基于標準誤差的最小二乘線性分類器

王剛剛，趙禮峰，謝亞利

(1.南京郵電大學 理學院,江蘇 南京 210003；2.上海師范大學 數理學院,上海 200234)

基于標準誤差的最小二乘線性分類器

王剛剛1，趙禮峰1，謝亞利2

(1.南京郵電大學 理學院,江蘇 南京 210003；2.上海師范大學 數理學院,上海 200234)

大數據時代下數據結構的多樣性嚴重影響人們對數據分類的判斷。有效解決數據分類問題并提高分類準確率是大數據時代背景下亟待解決的難題。分類問題是將數據按照某種特征進行劃分,并根據分類結果的準確性來判斷分類特征的優劣。現有的模式識別中處理無監督分類問題的方法都有著自身固有缺陷。人為主觀選擇分類特征會降低模型的擬合效果。為此，提出一種將標準誤差作為分類特征的線性分類器。該分類器在對樣本進行分類的過程中，可保證分類的標準誤差最小，從而保證了模型最終分類結果的準確性最高。基于該分類器進行了建模仿真驗證。仿真實驗結果表明，該分類器對樣本分類的標準誤差較小，準確率較高且復雜度也相對較低。相對于其他線性分類器，該分類器具有高效性和實效性的優勢。

K-means聚類分析；最小二乘法；標準誤差；分類器

0 引 言

分類問題是大數據時代一個重要的組成部分，分類在各行各業都有廣泛的應用，比如超市商品的分配擺放、文本數據的情感分析、微博數據的網絡圖模形等都需要利用分類方法來處理。分類方法可分為監督分類法和無監督分類法。各行業中的數據大多數屬于無監督分類數據。徐鵬等采用C4.5決策樹的流量分類方法完成對未知網絡流樣本的分類[1]；張建萍等以兒童生長發育時期的數據為例，通過聚類分析軟件和改進的K-means算法來闡述聚類分析在數據挖掘中的實踐應用[2]。這些案例都是利用沒有預先分類的數據對數據進行挖掘探索，進行有效分析并產生了良好的效果。在對數據進行分類時，需要選取特定的指標。張高胤等采用K近鄰分類算法，以距離為分類依據，對搜索到的網頁進行主題分類[3]；平源采用支持向量機聚類算法，對具有任意形狀或不規則的數據集進行劃分處理[4]；張婷等在使用ISODATA算法時,設計了一種自適應參數確定算法，降低了圖像關鍵點特征維數并縮短了檢索時間[5]。

常用的處理無監督數據的分類方法有K-means聚類分析、ISODATA集群算法和CLARANS算法。K-means聚類分析[6]是MacQueen提出的一種聚類算法，該算法以距離為分類指標對數據進行分類；ISODATA集群算法[7]是J. C. Dunn提出的應用模糊數學判據的算法，該算法通過不斷修改聚類中心的位置來進行分類；Raymond T. Ng提出了CLARANS算法[8]，它是分割方法中基于隨機搜索的大型應用聚類算法。這些經典分類法[6-8]都有一定的局限性，統計指標的選取比較主觀，沒有考慮如何在分類過程中減小分類誤差。

現有文獻都是闡述如何選取特定的統計指標以及相應的分類方法對樣本進行分類，而沒有闡述如何在分類過程中控制分類誤差，對于無監督數據的分類，無法從分類結果計算分類準確性，同時不同分類指標的選取也會影響分類結果的準確性，導致無法了解分類的效果，因此只有在分類過程中降低樣本分類的錯判率才能提高分類結果的準確性。為此，提出了一種將標準誤差作為分類特征的最小二乘線性分類器，在分類過程中對分類樣本數據的誤差進行控制并保證樣本分類的標準誤差最小。

1 基礎知識

1.1K-means聚類分析

K-means算法以空間中k個點為中心進行聚類，對最靠近它們的對象進行歸類[9]。

算法流程如下：

(1)從n個樣本點中任意選擇k個對象作為初始聚類中心；

(2)對于剩下的樣本點，根據它們與這些聚類中心的距離，分別將它們分配給與其最相似的聚類中心所在的類別；

(3)計算每個新類的聚類中心；

(4)不斷重復步驟2和步驟3，直到所有樣本點的分類不再改變或類中心不再改變為止。

1.2最小二乘估計模型

最小二乘法通過最小化誤差平方和尋找數據的最佳函數匹配，使得實際數據與預測數據之間的誤差平方和最小。

多元線性回歸模型的一般形式為：

y=β0+β1x1+…+βpxp+ε

(1)

其中，β0,β1,…,βp為p+1個未知參數，β0稱為回歸參數，β1,…,βp稱為回歸系數；y為因變量；x1,x2,…,xp為自變量；ε為隨機誤差

當p≥2時稱式(1)為多元線性回歸模型。對于多元線性回歸模型，若獲得n組可觀測樣本xi1,xi2,…,xip,yi，則多元線性模型可表示為[10]：

yi=β0+β1xi1+…+βpxip+εi,i=1,2,…,n

(2)

擬合后的多元線性回歸模型的一般形式為：

(3)

多元線性回歸方程的標準誤差為：

(4)

2 最小二乘線性分類器的構造

2.1構造思想

最小二乘線性分類器通過構造若干個最小二乘線性回歸方程，計算出各個方程的標準誤差，以標準誤差為分類依據將數據劃分為若干類。

首先利用樣本數據擬合一條多元線性回歸方程，然后采用K-means聚類分析法將數據分為k類，并擬合得到k個最小二乘線性方程，有效地降低了樣本數據擬合的標準誤差。然后對k個最小二乘線性方程進行歸一化處理，即賦予每一個線性回歸方程一定的權重，歸一化線性方程為每個線性方程的加權和。因此可以計算歸一化線性方程的標準誤差和以總樣本數據擬合的線性方程的標準誤差，比較兩者所得到的標準誤差大小，以此對樣本進行分類，標準誤差較小的樣本數據可劃分到對應的線性方程那一類。

上述兩條線性方程至多只能將數據分為三類：{樣本點離歸一化線性方程較近}，{樣本點離以總樣本數據擬合的線性方程較近}，{樣本與兩線性方程距離相等}，顯然不滿足類別較多的需求。當樣本屬性類別較多時，可將由k類線性方程得到的標準誤差進行排序，根據順序對k類線性方程分組，對每組內的線性方程進行歸一化處理，得到若干個歸一化的線性回歸方程。以標準誤差為分類指標對樣本進行分類。

針對樣本較多，計算量較大的情況，利用K-means聚類分析法，通過比較類間標準誤差的大小對樣本進行分類。新分類器在對樣本數據處理的過程中，以標準誤差為分類依據，保證了每一類樣本數據誤差最小；對數據進行聚類分析處理，類標準誤差相對總體標準誤差變小了，同時也減少了數據分類的計算量。

2.2構造流程

數據特征的選取決定數據的分類情況，數據分類模型的準確性是評判模型優劣的重要標準。提出了一種將標準誤差作為分類特征的線性分類器，該分類器保證模型分類結果的標準誤差最小，即保證模型分類結果的錯判率最低。

最小二乘線性分類器的具體構造流程如下：

(1)利用總體樣本數據，擬合線性回歸方程；

(2)對總體樣本數據進行K-means聚類處理，并對每一類(k類)樣本進行線性回歸方程的擬合；

(3)在對k個線性回歸方程歸一化處理之前，設定每一類(k類)線性方程的權重；

(4)對k類線性回歸方程進行歸一化處理；

(5)計算步驟1～4得出的線性方程，擬合步驟2中k類樣本數據所得到的預測值與真實值之間的標準誤差；

(6)根據步驟5所得到的標準誤差對數據進行分類。

2.2.1 線性回歸方程的擬合

采用K-means聚類分析法對該樣本數據進行分析，將數據分為k類[11]。假設k類樣本數據量分別為n1,n2,…,nk。利用k類樣本數據，采用最小二乘法擬合得到k個線性回歸方程：

(5)

k個線性回歸方程權重的設定:將第k類數據帶入第m個線性回歸方程，得到預測值，計算其與真實值間的標準誤差，結果如表1所示。

表1 標準誤差

計算表1內所有標準誤差值之和，記為總標準誤差；計算第k行除去對角線上元素的標準誤差之和，記為類間擬合誤差。類間擬合誤差越小，表明第m類線性方程擬合的效果越好，設定的權重就越高，該權重值等于總標準誤差減去類間擬合誤差的值與總標準誤差之比，取αm表示第m類線性回歸方程的權重。

m=1,2,…,k

(6)

(7)

(8)

2.2.2 分類特征的選取與計算

(9)

(10)

(11)

2.2.3 標準誤差的比較與分類器的建立

對比ERRORm與Errorm的關系，其大小即為所設計的最小二乘線性分類器對樣本進行分類的依據。ERRORm和Errorm至多存在3種關系，即Errorm>ERRORm，Errorm

3 實值仿真和比較

3.1實值仿真

利用R語言編程環境實現算法，選取聯合循環發電廠數據集進行仿真實驗[12]。該數據集包含了9 568個數據點以及5個屬性特征，分別是溫度(AT)、排氣真空(V)、環境壓(AP)、相對濕度(RH)和網每小時輸出的電能(EP)。分別以x1,x2,x3,x4替代前四個屬性變量，作為解釋變量；y替代網每小時輸出的電能，作為被解釋變量。

首先對該數據集進行相關性檢驗，發現該數據集滿足最小二乘的假設條件。利用R軟件對該數據集作擬合處理，得出線性回歸方程：

0.233 916x2-0.062 083x3-0.158 054x4

(12)

采用K-means聚類分析法對該數據集進行分類，通過對數據集的觀測以及資料閱讀[13]，發現將該數據集化為4類較佳，利用R軟件采用K-means聚類分析4類數據[14]，每一類數據集詳情如表2所示。

表2 分類數據樣本

分別對這4類樣本采用最小二乘法作線性回歸處理，得到線性回歸模型如下：

0.240 20x3-0.145 43x4

0.082 47x3-0.171 64x4

0.279 35x3-0.079 06x4

0.071 87x3-0.204 59x4

(13)

表3 線性回歸方程擬合誤差

根據式(6)可確定4個線性回歸方程的權重，如表4所示。

表4 權重值

重新構造的最小二乘估計線性回歸方程為k個線性回歸方程的加權之和：

1.580 130 3x1-0.173 724 4x2+

0.143 711 4x3-0.147 273 8x4

(14)

通過未分類的線性回歸方程和分類后歸一化的線性回歸方程，可計算分類樣本的標準誤差，結果如表5所示。

表5 分類樣本的標準誤差

利用R軟件對算法進行編譯并繪制分類樣本的標準誤差及差值圖，如圖1所示。

圖1 標準誤差及差值

因此該最小二乘線性分類器方程為：

0.062 083x3-0.158 054x4

(15)

聯立上述線性回歸方程即可得出兩個超平面相交的部分。

根據圖1可以看出，在設置標準誤差閾值為0.1的條件下：分類1和分類3:ERROR>Error；分類2：ERROR=Error；分類4：ERROR

表6 分類器重新分類結果

3.2新分類器與經典分類器的比較

3.2.1 復雜度

處理一個樣本數為n的數據集，利用K-means聚類分析法和ISODATA算法處理n個樣本數，假設需要進行p次迭代，每個樣本點需要操作m次，則其復雜度為O(pmn)；利用CLARANS算法處理n個樣本，其復雜度為O(n2)；利用最小二乘線性分類器處理數據，假設對數據進行處理得到M條線性方程，復雜度為O(n)，每個樣本與M條線性方程的標準誤差復雜度不超過O(Mn)，其復雜度為O((M+1)n)。當M=3時，樣本最多可分為7類，可以滿足分類類別的需求；而p和m值不小于2，pm最小為9，因此最小二乘線性分類器的復雜度較低。

3.2.2 準確率

無監督數據分類結果無法判斷分類的準確率，經查閱文獻，根據最小二乘法的性質可知，采用最小二乘法得到的線性回歸方程的估計誤差最小[15]。新分類器在對無監督樣本處理的過程中，以標準誤差為分類依據，保證了每一類樣本標準誤差最小，即新分類器相比較經典分類器的準確率較高。

4 結束語

大數據的涌現使人們在處理復雜的數據對象時面臨巨大的挑戰。數據的多源異構、質量的良莠不齊使得傳統的機器學習法不能有效地處理。對于模式識別中無監督數據的處理問題，單從主觀性選取數據特征對數據做分類處理無法保證分類模型的準確度。因此立足于研究分析的目的，選擇合適的量化指標才能有效地建立以數據為中心的分類模型。

現有的模式識別中處理分類問題的方法通常會選擇樣本均值、樣本眾數、樣本中位數作為分類特征，并計算最終樣本分類結果的錯判率來判斷該分類特征的優劣性，然而這種方法并不能保證樣本分類結果的錯判率最小，人為主觀選擇分類特征會降低模型的擬合效果。針對這一不足，提出了一種利用標準誤差作為分類特征的線性分類器。分類模型的標準誤差的大小反映了分類結果的錯判率高低，保證分類模型中標準誤差最小也就是保證樣本分類模型的錯判率最小，該方法可以高效地對樣本進行分類。實驗結果表明，該分類器得到的分類模型準確率較高。

[1] 徐 鵬,林 森.基于C4.5決策樹的流量分類方法[J].軟件學報,2009,20(10):2692-2704.

[2] 張建萍,劉希玉.基于聚類分析的K-means算法研究及應用[J].計算機應用研究,2007,24(5):166-168.

[3] 張高胤,譚成翔,汪海航.基于K-近鄰算法的網頁自動分類系統的研究及實現[J].計算機技術與發展,2007,17(1):21-23.

[4] 平 源.基于支持向量機的聚類及文本分類研究[D].北京:北京郵電大學,2012.

[5] 張 婷,戴 芳,郭文艷.基于ISODATA聚類的詞匯樹圖像檢索算法[J].計算機科學,2014,41(11A):123-127.

[6] 李 飛,薛 彬,黃亞樓.初始中心優化的K-Means聚類算法[J].計算機科學,2002,29(7):94-96.

[7] 錢夕元,邵志清.模糊ISODATA聚類分析算法的實現及其應用研究[J].計算機工程與應用,2004,40(15):70-71.

[8] Ng R T,Han J.CLARANS:a method for clustering objects for spatial data mining[J].IEEE Transactions on Knowledge & Data Engineering,2002,14(5):1003-1016.

[9] 黃 韜,劉勝輝,譚艷娜.基于k-means聚類算法的研究[J].計算機技術與發展,2011,21(7):54-57.

[10] 高學軍,王振友.多元統計回歸模型在醫療保障基金數額分配中的應用[J].統計與決策,2009(9):145-146.

[11] Everitt B.Cluster analysis[J].Quality & Quantity,1980,14(1):75-100.

[12] Tufekci P,Kaya H.Combined cycle power plant data set[DB/OL].(2014-03-26)[2016-05-02].http://archive.ics.uci.edu/ml/datasets/Combined%20Cycle%20Power%20Plant.

[13] 朱佳賢.無指導學習環境下基于屬性相關性分析和聚類算法的屬性選擇問題研究[J].管理學報,2005,2(S):162-165.

[14] German D M,Adams B,Hassan A E.The evolution of the R software ecosystem[C]//17th European conference on software maintenance and reengineering.[s.l.]:IEEE,2013:243-252.

[15] 丁克良,沈云中,歐吉坤.整體最小二乘法直線擬合[J].遼寧工程技術大學學報:自然科學版,2010,29(1):44-47.

ALeastSquareLinearClassifierwithStandardError

WANG Gang-gang1,ZHAO Li-feng1,XIE Ya-li2

(1.School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210003,China；2.College of Mathematics and Physics,Shanghai Normal University,Shanghai 200234,China)

The diversity of the data structure in the era of big data can seriously affect the people’s judgment of the data classification,which will be an urgent difficulty to solve data classification effectively and improve the accuracy of classification under the background of big data.Classification is to classify the data according to some characteristics and to judge the merits of classification characteristics by the accuracy of the classification results.The methods dealing with unsupervised learning classification in existing pattern recognition have their own inherent defects.Artificial subjective selection of classification characteristics will reduce the model fitting effect.Therefore,a linear classifier is proposed that the standard error is used as the classification feature to classify the data.In the process of classifying samples,it can ensure the minimum standard error of the classification,thus ensuring the highest accuracy of the final classification results.The simulation shows that it has less standard error,higher accuracy and lower complexity.Compared with other linear classifiers,it has the advantages of high efficiency and effectiveness.

K-means clustering analysis;least square method;standard error;classifier

TP181

A

1673-629X(2017)10-0078-05

2016-09-21

2016-12-27 < class="emphasis_bold">網絡出版時間

時間：2017-07-11

國家自然科學青年基金項目(61304169)

王剛剛(1992-)，男，碩士研究生，研究方向為信息統計與數據挖掘；趙禮峰，教授，碩士研究生導師，研究方向為應用數學。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1454.030.html

10.3969/j.issn.1673-629X.2017.10.017