模擬退火結(jié)合Logistic算法在分類中的應(yīng)用

陳芝

摘 要：Logistic線性回歸算法是一種簡單而高效的二分類器，它能夠針對每個參數(shù)生成對應(yīng)的分類系數(shù)，最后結(jié)合系數(shù)計算出所在類別的概率；同時模擬退火算法是一種較好的全局尋優(yōu)算法。在門店分類中考慮到各個參數(shù)的不同權(quán)重，因此使用模擬退火算法來尋找適當(dāng)?shù)膮?shù)權(quán)重以期望得到最好Logistic分類結(jié)果。最后通過實驗來驗證算法的準(zhǔn)確率。

關(guān)鍵詞：Logistic線性回歸 模擬退火 門店分類

中圖分類號：TP301.6 文獻標(biāo)識碼：A 文章編號：1674-098X（2016）06（b）-0092-02

分類算法屬于預(yù)測式數(shù)據(jù)挖掘的一種數(shù)據(jù)分析方法，其目的是根據(jù)重要樣本數(shù)據(jù)集找出能準(zhǔn)確描述并區(qū)分?jǐn)?shù)據(jù)類或概念的模型，以便依據(jù)實體的屬性值及約束條件將其劃分到某個數(shù)據(jù)類別中去。Logistic回歸分析主要用在社會科學(xué)中，目前有將粗糙集與Logistic回歸進行結(jié)合構(gòu)造分類模型如文獻[2]，文獻[3]中提出的集成Logistic和SVM的分類模等。而模擬退火則作為一種有效的全局尋優(yōu)算法，目前主要是將其和其他算法結(jié)合以改進尋優(yōu)的質(zhì)量或者將模擬退火算法使用的特定的領(lǐng)域進行參數(shù)優(yōu)化。

在現(xiàn)在的商業(yè)系統(tǒng)中，門店分類是一個比較新的研究領(lǐng)域。在廠家的銷售過程中，經(jīng)常會將門店劃分為不同的等級，例如汽車行業(yè)的旗艦店，4S店等的區(qū)別。當(dāng)?shù)昝鏀?shù)量較少時可以采用人工劃分，但具有很強的主觀因素。因此考慮到在已有正確劃分的店面的基礎(chǔ)上運用一種好的分類方法，設(shè)計出分類器后在對未劃分的店面進行自動劃分。

1 基本知識

1.1 Logistic線性回歸

Logistic回歸延伸了多元線性回歸思想，即因變量yi是二值（為了方便起見通常設(shè)這些值為0和1）的情形。和在多元線性回歸中一樣，自變量X=[x1，x2， …，xk ]可以是類別變量或連續(xù)變量或是兩種類型的混合。在該文中我們主要使用Logistic進行二分類。Logistic函數(shù)公式如式（1），通過似然概率估計就可以計算出β=[β0，β1，…，βp ]，最后使用Logistic函數(shù)來計算X分類的概率：

求解β的具體過程如下：

（1）隨機初始化β0值和迭代的次數(shù)M；

（2）使用式（7）進行迭代得到βt+1；

（3）如果β值在一定步數(shù)內(nèi)不變或者迭代次數(shù)達到M就跳出否則跳轉(zhuǎn)到（2）。

當(dāng)求得β后則可以使用式（1）來對已知的數(shù)據(jù)X進行分類概率的計算，當(dāng)計算出來的概率π（X） < 0.5時將X分到第0類中，否則X為第1類。

1.2 模擬退火算法

模擬退火（Simulated Annealing）算法經(jīng)常被用來求解全局最優(yōu)解。SA算法其實是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當(dāng)前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，而求得全局的最優(yōu)解。模擬退火算法的偽代碼如下：

（1）隨機產(chǎn)生一個初始解X0，令Xbest = X0，并計算目標(biāo)函數(shù)值E（X0）；

（2）設(shè)置初始溫度T（0） = T0，迭代次數(shù)i= 1；

（3）Do while T（i） > Tmin

①for j = 1～k

②對當(dāng)前最優(yōu)解Xbest按照某一領(lǐng)域函數(shù)，產(chǎn)生一個新的解Xnew。計算新的目標(biāo)函數(shù)值E（Xnew），并計算目標(biāo)函數(shù)值的增量ΔE = E（Xnew） – E（Xbest）。

③如果ΔE < 0，則Xbest = Xnew；

④如果ΔE >0，則p = exp（-ΔE/T（i））；

i.如果 c = random[0，1] < p，Xbest = Xnew；否則Xbest = Xbest。

⑤End for

（4）i = i +1；

（5）End while；

（6）輸出當(dāng)前最優(yōu)點，計算結(jié)束。

2 實驗設(shè)計

2.1 實驗描述

本實驗根據(jù)某鞋企的店面銷售數(shù)據(jù)來對店面進行評級，店面的銷售數(shù)據(jù)信息格式如（D1，D2，D3，…，Dn，C）。Di表示第i種鞋子的銷售數(shù)據(jù)，Di的取值范圍變化比較大，從零到幾千的范圍都有可能。C表示此店面的等級，C的取值為0，1兩種。實驗給出38條已分類的門店數(shù)據(jù)，實驗的最終目的是通過這些數(shù)據(jù)來訓(xùn)練出一個分類模型。

2.2 算法設(shè)計

根據(jù)實際情況考慮給不同種類鞋子賦予不同的權(quán)重值，訓(xùn)練時先將每種鞋類的數(shù)量乘以數(shù)據(jù)權(quán)重值，再將修正后的數(shù)據(jù)用來訓(xùn)練Logistic線性回歸模型用來評定未知門店的等級。因此使用模擬退火算法來找到一組好的權(quán)重值是本實驗中最關(guān)鍵的步驟。

2.3 數(shù)據(jù)預(yù)處理

在訓(xùn)練數(shù)據(jù)時先將原始數(shù)據(jù)進行歸一化，通過歸一化可以把需要處理的數(shù)據(jù)限制在一定范圍。以保證程序在運行Logistic線性回歸算法時加快收斂。

該文將每種鞋子的銷售數(shù)量采用式進行歸一化。其中Dmin表示一種鞋的最小銷量，Dmax表示鞋的最大銷量，Dmin表示歸一化前鞋的銷量。歸一化后的銷售數(shù)量Dnew分布在0～10之間。

考慮到實驗的數(shù)據(jù)數(shù)目比較小，實驗中需要將數(shù)據(jù)按照2∶1的比例劃分出訓(xùn)練集和測試集，且采用多次驗證求均值的方法，排除隨機分配出現(xiàn)的偶然性以保證驗證時的準(zhǔn)確性。

2.4 算法流程

在數(shù)據(jù)預(yù)處理后，接下來就需要使用模擬退火算法結(jié)合Logistic線性回歸來尋找一組合適的數(shù)據(jù)權(quán)重值。

用一組包含n個數(shù)據(jù)的數(shù)據(jù)組i，初始的數(shù)據(jù)組是通過隨機函數(shù)來生成的。元組j是在它的前一個數(shù)據(jù)組的基礎(chǔ)上通過隨機函數(shù)選擇它中間的一個數(shù)據(jù)進行+0.01或者-0.01的操作得到的。

適應(yīng)度的計算則是采用前面介紹的Logistic線性回歸來計算。將新產(chǎn)生的權(quán)重數(shù)據(jù)與源數(shù)據(jù)相乘后得到新的新數(shù)據(jù)，然后利用新數(shù)據(jù)中的2/3來訓(xùn)練Logistic線性回歸，得到一個分類器。用剩下1/3的新數(shù)據(jù)來驗證分類器的正確率。最終的正確率采用測試十次求平均值的方法求得。

經(jīng)過計算，最后得到一組包含n個數(shù)據(jù)的權(quán)重數(shù)據(jù)組和一組包含n+1個數(shù)據(jù)的Logistic函數(shù)參數(shù)的數(shù)據(jù)組。

3 實驗分析

在實驗中發(fā)現(xiàn)使用實驗中的訓(xùn)練數(shù)據(jù)得出的分類模型能夠?qū)Ⅱ炞C數(shù)據(jù)進行100%正確的分類。出現(xiàn)這樣的原因可能有如下幾點：（1）數(shù)據(jù)規(guī)模太小，使得驗證數(shù)據(jù)不能很好地測試到數(shù)據(jù)可能的分布；（2）數(shù)據(jù)屬性太少，導(dǎo)致較少的測試數(shù)據(jù)就能很好地擬合到線性回歸的參數(shù)。

針對上面的情況，在試驗中將訓(xùn)練數(shù)據(jù)設(shè)置為數(shù)據(jù)集的45%，這樣就有更多的驗證數(shù)據(jù)。同時通過調(diào)節(jié)初始溫度、溫度下降速度和內(nèi)層循環(huán)的次數(shù)來驗證試驗結(jié)果。在初始溫度較高，溫度下降速度較慢和內(nèi)存循環(huán)大于20的情況下，最后得到的權(quán)重數(shù)據(jù)組趨向一個比較穩(wěn)定的數(shù)據(jù)，與剛開始隨機生成的數(shù)據(jù)權(quán)重數(shù)據(jù)的關(guān)系更小。最后利用模擬退火得到的權(quán)重值對源數(shù)據(jù)進行調(diào)整。通過比較發(fā)現(xiàn)，調(diào)整后的模型在準(zhǔn)確率上有一定程度的提高。

4 結(jié)語

通過該文的工作，得到了一個利用Logistic線性回歸改進的模擬退火算法。利用此算法以期望尋找一組權(quán)重值，使得Logistic線性回歸的在門店分類中的準(zhǔn)確率得到提升。門店的分類作為商業(yè)運作中重要的一種智能算法，以后可能得到更廣泛的應(yīng)用。

參考文獻

[1] 張軍，詹志輝.計算智能[M].北京：清華大學(xué)出版社，2009：195-201.

[2] 葉明全，伍長榮，胡學(xué)鋼.一種集成粗糙集與Logistic回歸的分類模型[C].中國儀器儀表學(xué)會微型計算機應(yīng)用學(xué)會，2009.

[3] 謝玲.集成Logistic和SVM的分類算法研究[D].重慶：重慶大學(xué)，2011：39.

[4] WangZhi. Computing Maximun Likelihood Estimates for Logistic Regression Coefficients[J].Mathematical Theory and Applications，2009（4）：86-90.

[5] Ronghua Luo， Hansheng Wang.A Composite Logistic Regression Approach for Ordinal Panel Data Regresson[J].Data Analysis and Strategies，2008，1（1）：29-43.

[6] David W.Hosmer， Stanley Lemeshow. Applied Logistic regression[M].AWiley-Interscience Publication，2000.

[7] W Ben-Ameur.Computing the initial temperature of simulated annealing[J]. Computational Optimization and Applications，2004，29（3）：369-385.