模擬退火結合Logistic算法在分類中的應用

陳芝

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

關鍵詞：Logistic線性回歸 模擬退火 門店分類

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

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

在現在的商業系統中，門店分類是一個比較新的研究領域。在廠家的銷售過程中，經常會將門店劃分為不同的等級，例如汽車行業的旗艦店，4S店等的區別。當店面數量較少時可以采用人工劃分，但具有很強的主觀因素。因此考慮到在已有正確劃分的店面的基礎上運用一種好的分類方法，設計出分類器后在對未劃分的店面進行自動劃分。

1 基本知識

1.1 Logistic線性回歸

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

求解β的具體過程如下：

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

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

（3）如果β值在一定步數內不變或者迭代次數達到M就跳出否則跳轉到（2）。

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

1.2 模擬退火算法

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

（1）隨機產生一個初始解X0，令Xbest = X0，并計算目標函數值E（X0）；

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

（3）Do while T（i） > Tmin

①for j = 1～k

②對當前最優解Xbest按照某一領域函數，產生一個新的解Xnew。計算新的目標函數值E（Xnew），并計算目標函數值的增量Δ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）輸出當前最優點，計算結束。

2 實驗設計

2.1 實驗描述

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

2.2 算法設計

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

2.3 數據預處理

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

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

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

2.4 算法流程

在數據預處理后，接下來就需要使用模擬退火算法結合Logistic線性回歸來尋找一組合適的數據權重值。

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

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

經過計算，最后得到一組包含n個數據的權重數據組和一組包含n+1個數據的Logistic函數參數的數據組。

3 實驗分析

在實驗中發現使用實驗中的訓練數據得出的分類模型能夠將驗證數據進行100%正確的分類。出現這樣的原因可能有如下幾點：（1）數據規模太小，使得驗證數據不能很好地測試到數據可能的分布；（2）數據屬性太少，導致較少的測試數據就能很好地擬合到線性回歸的參數。

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

4 結語

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

參考文獻

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

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

[3] 謝玲.集成Logistic和SVM的分類算法研究[D].重慶：重慶大學，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.