王剛剛，趙禮峰，謝亞利

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

基于標(biāo)準(zhǔn)誤差的最小二乘線性分類器

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

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

大數(shù)據(jù)時(shí)代下數(shù)據(jù)結(jié)構(gòu)的多樣性嚴(yán)重影響人們對數(shù)據(jù)分類的判斷。有效解決數(shù)據(jù)分類問題并提高分類準(zhǔn)確率是大數(shù)據(jù)時(shí)代背景下亟待解決的難題。分類問題是將數(shù)據(jù)按照某種特征進(jìn)行劃分,并根據(jù)分類結(jié)果的準(zhǔn)確性來判斷分類特征的優(yōu)劣?，F(xiàn)有的模式識別中處理無監(jiān)督分類問題的方法都有著自身固有缺陷。人為主觀選擇分類特征會降低模型的擬合效果。為此，提出一種將標(biāo)準(zhǔn)誤差作為分類特征的線性分類器。該分類器在對樣本進(jìn)行分類的過程中，可保證分類的標(biāo)準(zhǔn)誤差最小，從而保證了模型最終分類結(jié)果的準(zhǔn)確性最高?；谠摲诸惼鬟M(jìn)行了建模仿真驗(yàn)證。仿真實(shí)驗(yàn)結(jié)果表明，該分類器對樣本分類的標(biāo)準(zhǔn)誤差較小，準(zhǔn)確率較高且復(fù)雜度也相對較低。相對于其他線性分類器，該分類器具有高效性和實(shí)效性的優(yōu)勢。

K-means聚類分析；最小二乘法；標(biāo)準(zhǔn)誤差；分類器

0 引 言

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

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

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

1 基礎(chǔ)知識

1.1K-means聚類分析

K-means算法以空間中k個(gè)點(diǎn)為中心進(jìn)行聚類，對最靠近它們的對象進(jìn)行歸類[9]。

算法流程如下：

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

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

(3)計(jì)算每個(gè)新類的聚類中心；

(4)不斷重復(fù)步驟2和步驟3，直到所有樣本點(diǎn)的分類不再改變或類中心不再改變?yōu)橹埂?/p>

1.2最小二乘估計(jì)模型

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

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

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

(1)

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

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

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

(2)

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

(3)

多元線性回歸方程的標(biāo)準(zhǔn)誤差為：

(4)

2 最小二乘線性分類器的構(gòu)造

2.1構(gòu)造思想

最小二乘線性分類器通過構(gòu)造若干個(gè)最小二乘線性回歸方程，計(jì)算出各個(gè)方程的標(biāo)準(zhǔn)誤差，以標(biāo)準(zhǔn)誤差為分類依據(jù)將數(shù)據(jù)劃分為若干類。

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

上述兩條線性方程至多只能將數(shù)據(jù)分為三類：{樣本點(diǎn)離歸一化線性方程較近}，{樣本點(diǎn)離以總樣本數(shù)據(jù)擬合的線性方程較近}，{樣本與兩線性方程距離相等}，顯然不滿足類別較多的需求。當(dāng)樣本屬性類別較多時(shí)，可將由k類線性方程得到的標(biāo)準(zhǔn)誤差進(jìn)行排序，根據(jù)順序?qū)類線性方程分組，對每組內(nèi)的線性方程進(jìn)行歸一化處理，得到若干個(gè)歸一化的線性回歸方程。以標(biāo)準(zhǔn)誤差為分類指標(biāo)對樣本進(jìn)行分類。

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

2.2構(gòu)造流程

數(shù)據(jù)特征的選取決定數(shù)據(jù)的分類情況，數(shù)據(jù)分類模型的準(zhǔn)確性是評判模型優(yōu)劣的重要標(biāo)準(zhǔn)。提出了一種將標(biāo)準(zhǔn)誤差作為分類特征的線性分類器，該分類器保證模型分類結(jié)果的標(biāo)準(zhǔn)誤差最小，即保證模型分類結(jié)果的錯判率最低。

最小二乘線性分類器的具體構(gòu)造流程如下：

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

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

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

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

(5)計(jì)算步驟1～4得出的線性方程，擬合步驟2中k類樣本數(shù)據(jù)所得到的預(yù)測值與真實(shí)值之間的標(biāo)準(zhǔn)誤差；

(6)根據(jù)步驟5所得到的標(biāo)準(zhǔn)誤差對數(shù)據(jù)進(jìn)行分類。

2.2.1 線性回歸方程的擬合

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

(5)

k個(gè)線性回歸方程權(quán)重的設(shè)定:將第k類數(shù)據(jù)帶入第m個(gè)線性回歸方程，得到預(yù)測值，計(jì)算其與真實(shí)值間的標(biāo)準(zhǔn)誤差，結(jié)果如表1所示。

表1 標(biāo)準(zhǔn)誤差

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

m=1,2,…,k

(6)

(7)

(8)

2.2.2 分類特征的選取與計(jì)算

(9)

(10)

(11)

2.2.3 標(biāo)準(zhǔn)誤差的比較與分類器的建立

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

3 實(shí)值仿真和比較

3.1實(shí)值仿真

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

首先對該數(shù)據(jù)集進(jìn)行相關(guān)性檢驗(yàn)，發(fā)現(xiàn)該數(shù)據(jù)集滿足最小二乘的假設(shè)條件。利用R軟件對該數(shù)據(jù)集作擬合處理，得出線性回歸方程：

0.233 916x2-0.062 083x3-0.158 054x4

(12)

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

表2 分類數(shù)據(jù)樣本

分別對這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 線性回歸方程擬合誤差

根據(jù)式(6)可確定4個(gè)線性回歸方程的權(quán)重，如表4所示。

表4 權(quán)重值

重新構(gòu)造的最小二乘估計(jì)線性回歸方程為k個(gè)線性回歸方程的加權(quán)之和：

1.580 130 3x1-0.173 724 4x2+

0.143 711 4x3-0.147 273 8x4

(14)

通過未分類的線性回歸方程和分類后歸一化的線性回歸方程，可計(jì)算分類樣本的標(biāo)準(zhǔn)誤差，結(jié)果如表5所示。

表5 分類樣本的標(biāo)準(zhǔn)誤差

利用R軟件對算法進(jìn)行編譯并繪制分類樣本的標(biāo)準(zhǔn)誤差及差值圖，如圖1所示。

圖1 標(biāo)準(zhǔn)誤差及差值

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

0.062 083x3-0.158 054x4

(15)

聯(lián)立上述線性回歸方程即可得出兩個(gè)超平面相交的部分。

根據(jù)圖1可以看出，在設(shè)置標(biāo)準(zhǔn)誤差閾值為0.1的條件下：分類1和分類3:ERROR>Error；分類2：ERROR=Error；分類4：ERROR

表6 分類器重新分類結(jié)果

3.2新分類器與經(jīng)典分類器的比較

3.2.1 復(fù)雜度

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

3.2.2 準(zhǔn)確率

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

4 結(jié)束語

大數(shù)據(jù)的涌現(xiàn)使人們在處理復(fù)雜的數(shù)據(jù)對象時(shí)面臨巨大的挑戰(zhàn)。數(shù)據(jù)的多源異構(gòu)、質(zhì)量的良莠不齊使得傳統(tǒng)的機(jī)器學(xué)習(xí)法不能有效地處理。對于模式識別中無監(jiān)督數(shù)據(jù)的處理問題，單從主觀性選取數(shù)據(jù)特征對數(shù)據(jù)做分類處理無法保證分類模型的準(zhǔn)確度。因此立足于研究分析的目的，選擇合適的量化指標(biāo)才能有效地建立以數(shù)據(jù)為中心的分類模型。

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

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

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

[3] 張高胤,譚成翔,汪海航.基于K-近鄰算法的網(wǎng)頁自動分類系統(tǒng)的研究及實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(1):21-23.

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

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

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

[7] 錢夕元,邵志清.模糊ISODATA聚類分析算法的實(shí)現(xiàn)及其應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用,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].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(7):54-57.

[10] 高學(xué)軍,王振友.多元統(tǒng)計(jì)回歸模型在醫(yī)療保障基金數(shù)額分配中的應(yīng)用[J].統(tǒng)計(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] 朱佳賢.無指導(dǎo)學(xué)習(xí)環(huán)境下基于屬性相關(guān)性分析和聚類算法的屬性選擇問題研究[J].管理學(xué)報(bào),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].遼寧工程技術(shù)大學(xué)學(xué)報(bào):自然科學(xué)版,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">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-11

國家自然科學(xué)青年基金項(xiàng)目(61304169)

王剛剛(1992-)，男，碩士研究生，研究方向?yàn)樾畔⒔y(tǒng)計(jì)與數(shù)據(jù)挖掘；趙禮峰，教授，碩士研究生導(dǎo)師，研究方向?yàn)閼?yīng)用數(shù)學(xué)。

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

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