針對Lasso問題的多維權重求解算法

陳善雄, 劉小娟, 陳春蓉,鄭方園

(1.西南大學 計算機與信息科學學院,重慶 400715; 2.貴州工程應用技術學院 信息工程學院,貴州 畢節 551700)

針對Lasso問題的多維權重求解算法

陳善雄1,2*, 劉小娟1,2, 陳春蓉1,鄭方園1

(1.西南大學 計算機與信息科學學院,重慶 400715; 2.貴州工程應用技術學院 信息工程學院,貴州 畢節 551700)

(*通信作者電子郵箱csxpml@163.com)

最小絕對收縮和選擇算子(Lasso)在數據維度約減、異常檢測方面有著較強的計算優勢。針對Lasso用于異常檢測中檢測精度不高的問題，提出了一種基于多維度權重的最小角回歸(LARS)算法解決Lasso問題。首先考慮每個回歸變量在回歸模型中所占權重不同，即此屬性變量在整體評價中的相對重要程度不同，故在LARS算法計算角分線時，將各回歸變量與剩余變量的聯合相關度納入考慮，用來區分不同屬性變量對檢測結果的影響;然后在LARS算法中加入主成分分析(PCA)、獨立權數法、基于Intercriteria相關性的指標的重要度評價(CRITIC) 法這三種權重估計方法，并進一步對LARS求解的前進方向和前進變量選擇進行優化。最后使用Pima Indians Diabetes數據集驗證算法的優良性。實驗結果表明，在更小閾值的約束條件下，加入多維權重后的LARS算法對Lasso問題的解具有更高的準確度，能更好地用于異常檢測。

最小絕對收縮和選擇算子；變量選擇； 最小角回歸；多元線性回歸；加權

0 引言

大數據時代，數據挖掘已展現出其魅力，如何使用數理統計模型從海量數據中挖掘有效信息越來越受到業界的關注。在建立模型初期，一般會選擇盡可能多的自變量(屬性集)減小因缺少重要自變量而出現的模型偏差，但建模過程中需要尋找對結果變量解釋力最強的自變量集合，即通過對自變量選擇來提高模型的預測精度與準確度[1]。統計學中常用的模型之一是線性回歸模型，而對線性回歸模型而言,模型的準確性主要取決于變量的選擇和回歸系數的取值。在Frank等[2]提出的 Ridge Regression算法和Bireman[3]提出的 Nonnegative Garrote算法的啟發下，Tibshirani[4]提出了一種稱之為最小絕對收縮和選擇算子(Least absolute shrinkage and selection operator, Lasso) 的新的變量選擇方法。該算法通過構造一個懲罰函數來壓縮系數，在回歸系數的絕對值之和小于一個常數的約束條件下，使殘差的平方最小化，Lasso方法作為一種壓縮估計，具有較高的檢測精度和較好的參數收斂一致性。進一步，Efron等[5]提出最小角回歸(Least Angle Regression, LARS)算法來支撐Lasso問題的解法，并進一步提出了修正的LARS算法，該算法通過消除了回歸系數β異號的情況來得到Lasso問題的解。修正的LARS算法采用逐步回歸，每一步路徑都保持當前的殘差與所有入選變量的相關性都相同，同時滿足Lasso解與當前逼近保持同向的要求，保證最優結果，降低算法復雜度[6-7]。但LARS算法在求解過程中，利用了自變量的均分的“角分線”方向對解向量進行逼近，并沒有考慮到不同變量對最終解的權重影響。

因此本文提出了采用多維權重的方式計算變量的權重，考慮到不是所有屬性項(變量)都影響著檢測結果，每個回歸變量在回歸模型中所占權重不同，即此屬性變量在整體評價中的相對重要程度不同，因此，在LARS算法計算“角分線”時，將各回歸變量與剩余變量的聯合相關度納入考慮，用來區分不同屬性變量對檢測結果的影響。實驗通過PimaIndiansDiabetes數據集，兩組評價指標對本文提出的方法進行了討論，其結果表明加入多維權重的LARS對Lasso問題的解答具有更高的準確性能。

1. Lasso問題及LARS算法

1.1Lasso問題描述

存在多維自變量設Xj∈Rn(j=1,2,…,m)，因變量y∈Rn，且每組自變量Xj都有對應的因變量y，用自變量Xj對因變量y進行線性回歸，在限定回歸系數β的L1范數小于t的情況下，求使得殘差平方和最小的回歸系數β的估值。因此，線性 Lasso 回歸模型可以表示為：

y=Xβ+e

(1)

其中:β是j維列向量，為待估參數;誤差向量e滿足E(e)=0，且 Var(e)=σ2。并且假定E(y|X)=β1x1+β2x2+…+βjxj。注意該模型是稀疏模型，即β1,β2,…,βj中有很多系數為零。變量選擇的目的就是根據獲取的數據來識別模型中哪些系數為零，并估計其他非零參數，即尋找構建稀疏模型的參數。需要求解的問題寫成矩陣表達式為：

(α,β)=arg min‖y-Xβ-α‖2； ‖β‖1≤t

(2)

1.2LARS算法

LARS算法很好地解決了Lasso問題，其建立在前向選擇算法和前向梯度算法的基礎上，逐步前進步長適中，降低計算復雜度的同時又盡可能地保留了信息相關性。LARS算法的基本步驟如下：

1)LARS算法判斷自變量xK與y的相關度，用相關度最大的xK對y進行逼近。

2)直到另一個xP具有相同的對y的相關度，即rxKy=rxPy，此時開始從xK與xP的“角分線”方向xU逼近y。

3)同樣的，當出現第三個xT對y相關度與xU相同時，將xT納入到逼近隊列中，選擇三個向量共同的“角分線”方向xU進行新一輪逼近，此時“角分線”表示高維空間中各向量的平分線。

4)逐步逼近直到殘差小于某個閾值或所有自變量都參與進逼近，算法結束。

圖1中，兩個自變量x1與x2與因變量y相關度rx1y>rx2y，用x1進行逼近，直至β1x1與y的殘差和x1、x2的相關度相同，即殘差處于x1與x2的角平分線上，此后用x1與x2的角平分線方向逼近因變量y。

圖1 LARS算法求解步驟

2 多維權重LARS方法

2.1 多維權重的LARS方法分析

在LARS逐步回歸過程中，將所有入選變量視為同等重要進行角回歸，每次逼近選擇與y最大相關度xj，考慮到每個回歸變量xj在回歸模型中所占權重不同，即此指標在整體評價中的相對重要程度不同，將自變量xj與剩余變量的聯合相關度納入考慮。每一次逼近，將xj與y的相關度及Xj在整體指標中所占重要程度同時作為選擇逼近特征的條件。

對于x1、x2，原LARS選擇對y逼近變量的條件是回歸變量對y的相關度，此時由rx1y>rx2y，將x1作為第一逼近變量；我們將自變量xj對整個系統的貢獻率作為逼近條件之一，此時新的相關度為：

(3)

其中：WXj為自變量xj對系統的貢獻率，計算方法將在下面詳細描述；u、v為常數。將自變量對y相關度與對系統的貢獻率的乘積作為逼近條件，必然會增加判斷條件的值域，為了保留系統逼近的穩定性，將乘積限制在某個值域范圍內，即規定在[v,u]內。

圖2 加入多維權重后X與y的相關性變化

圖3 加入多維權重后的X前進方向

將上述過程應用到多維高階系統，將m個特性指標及n個對象用矩陣表示為：

(4)

或者表示為：

(5)

則應變量Y用矩陣表示為：

(6)

回歸過程中，WXi有多種計算方法，本文采用以下三種權重確定方法來控制回歸過程。

1)主成分分析法。

統計學中，主成分分析(PrincipleComponentAnalysis,PCA)借用正交變換進行降維[8-9]，將數據變換到一個新的坐標系統中，使數據投影的最大方差處于第一坐標(稱為第一主成分)，第二方差處于第二坐標(稱為第二主成分)，依此類推。變換后，保留了數據集的低階主成分，忽略高階主成分，確定起支配作用的因素，通常保留總體信息利用率高于85%的前m個主成分。借用主成分分析法的思想，同時保留所有成分的評價值，確定每個成分的方差貢獻率，算法步驟如下:

對樣本進行如下標準化變換：

(7)

其中：

(8)

將相關系數矩陣R作為每個特征的信息利用率：

R=[rij]n×m=ZTZ/(n-1)

(9)

其中:

rij=∑zij·zij/(n-1)

(10)

2)獨立性權數法。

利用數據統計學中的多元回歸方法，對特征的復相關系數進行排序，復相關系數越大，所重復的信息越多，信息利用率響應越小，權重越小。計算方式如下：

(11)

(12)

由R與權重為負比例關系，取復相關系數的倒數作為評分，經歸一化處理得到權重系數，最終的權重表示為：

(13)

3)CRITIC法。

在獨立權數法的基礎上，更進一步，基于Intercriteria相關性的指標的重要度評價法(CRiteriaImportanceThoughIntercriteriaCorrelation,CRITIC)是由Diakoulaki[10]提出的一種客觀權重賦權法，它以確定指標的客觀權數來評價指標間的對比強度和沖突性為基礎。標準差的大小表明在同一指標內，各方案取值差距的大小，可用標準差表現對比強度；各指標間的沖突性是以指標之間的相關性為基礎，可用相關度表示沖突性[11]。計算步驟如下：

第j個指標與其他指標的沖突性量化指標為：

(14)

其中，rtj表示評價指標Xt和Xj之間的相關系數：

(15)

Cj表示第j個指標所包含的信息量：

(16)

Cj越大，表示j個評價指標所包含的信息量越大[12-13]，該指標的重要性也就越大，則第j個指標的客觀權重表示為：

(17)

以上所述三個方法得到權重后，將權重Rj集中化后表示權重對前進方向的影響：

(18)

2.2 算法步驟

為獲得穩定的數值解，對式(2)進行預處理和歸一化，消去常數α，并使結果向量y和自變量向量Xj(j=1,2,…,m)零均值且l2范數歸一。

定義指標集A={sj1xj1,sj2xj2,…,sjlxjl,…,sjkxjk}?{1,2,…,m}，存在從X中選出的滿足指標集A的列向量XA，使其與y同向。

XA=[sj1xj1,sj2xj2,…,sjlxjl,…,sjkxjk]∈Rn×k

(19)

其中sjl為符號變量：

(20)

定義XA中向量的“角分線”uA：

(21)

其中：1A為長度為|A|0所有元素為1的列向量；uA是角分線上的單位矢量；wA可理解為選中的變量集XA中每個屬性Xl對角分線的貢獻度。為改變前進方向與前進變量的選擇，對wA進行加權處理。

(22)

sj=sign{C}；j∈A

(23)

a=XTuA或aj=〈xj,uA〉

(24)

此時算法沿uA方向前進的長度為：

(25)

式中min上面的加號表示在此輪逼近中，只計算集合中正數的最小值。每個A中的自變向量相應增加γwA，同時加入權重控制逼近方向：

(26)

βA=βA+γw′

(27)

(28)

之后需要引入新的元素：

A+=A∪{j′}

(29)

其中j′是為式(25)取最小值的j，為了符合Lasso解要求與當前逼近保持同向，在最早出現異號的步長為：

(30)

輸入 自變量集X，因變量集Y，誤差項ε；

輸出 式(2)中的回歸系數β。

1)

程序準備;

2)

數據預處理，對X、Y歸一化；

3)

4)

5)

6)

7)

Rweight=PCA(X)或Rweight=IW(X)或Rweight=CRITIC(X)

8)

集中化Rweight;

9)

10)

LARS循環中rate=Rweight(1:row(w),:) ;w′=w*rate;

11)

循環結束;

12)

返回回歸系數β。

算法加入權重分析，增加了計算步驟，使得計算時間增加，但統計模型中各自變向量與因變向量的前進機制不變，空間復雜度與原算法保持一致。

3 實驗結果與分析

3.1 數據集

數據集采用美國約翰·霍普金斯大學應用物理實驗室(AppliedPhysicsLaboratory,TheJohnsHopkinsUniversity)提供的皮馬印第安人糖尿病數據集(PimaIndiansDiabetesDataSet)[14]。該數據記錄了768個體征性能描述與糖尿病陰陽性樣本，包括8個屬性變量和一個分類值，分類值中“1”表示檢測結果為陽性，“0”表示檢測結果為陰性。將8個不同屬性值作為輸入自變量Xj，是否患病作為輸出因變量Y驗證算法，檢測目標是在原LARS算法結果上對檢測結果準確度加以改進。

3.2 驗證條件

為了更直觀地對本文提出的方法性能進行評估比較，本文采用ROC曲線展示結果。參與者糖尿病檢測陰陽性為二元分類問題，檢測的結果有以下四種類型：

1)真陽性(TruePositive,TP)：檢測為陽性，實際上也為陽性。2)偽陽性(FalsePositive,FP)：檢測為陽性，實際卻為陰性。3)真陰性(TrueNegative,TN)：檢測為陰性，實際上也為陰性。4)偽陰性(FalseNegative,FN)：檢測為陰性，實際卻為陽性。

通過ROC空間四個基礎類型統計，P表示正例，N表示負例，采用以下三個性質作為檢查標準：

1)準確度(ACCuracy,ACC):

ACC=(TP+TN)/(P+N)

2)真陰性率(TruePositiveRatio,TPR)：

TPR=TP/P=TP/(TP+FN)

3)陰性預測值(NegativePredictiveValue,NPV)：

NPV=TN/(TN+FN)

3.3 實驗結果

對于閾值t，從0開始以0.01為步長進行增加至1，以陰陽性為因變量，8個屬性特征性能值為自變量，繪出準確度、陽性預測值、真陰性率的變化曲線。

圖4展示了在PimaIndiansDiabetes數據集下，Lasso算法每輪循環后準確度以及Lasso算法每輪循環后的三項檢查指標的綜合最優值。

NPV表示檢測為陽性的人中實際為陽性即檢測正確的比例，圖4中顯示，加入權重后Lasso解法的NPV均有所提高，其中，加入主成分分析后NPV提高5.16個百分點，采用獨立權數法NPV提高5.58個百分點，采用CRITIC法NPV提高5.1個百分點。

與NPV相比較，真陰性率(TPR)又稱命中率，表示檢測為陽性的人中檢測正確的比例。圖4中顯示，PCA對算法前進方向的改變使得TPR提高13個百分點，獨立權數法使TPR提高14個百分點，CRITIC使TPR提高13個百分點。

準確度(ACC)表示在因變量陽性和陰性的總和中，經Lasso求解判斷正確的個體點的個數，即檢測為陽性、實際也陽性與檢測為陰性、實際也為陰性的人數的總和，可以看出，加入主成分分析使得ACC增加了0.32個百分點，加入CRITIC法對ACC無影響，加入獨立權數法后的Lasso解法使得ACC提高了0.32個百分點，三個方法都使ACC保持不變或有所提高。

綜合以上三個指標，可以發現加入多維度權重的前進方向后，系統最優解的閾值減小，代表系統回歸系數絕對值之和小于某一更小的閾值，即在更苛刻的閾值范圍內滿足要求。

圖 4 不同檢測標準曲線

圖5展示了在PimaIndiansDiabetes數據集下，Lasso算法每輪循環因變量與角分線方向的殘量的平方和(SumofSquaredResiduals,SSR)，而SSR平穩的轉折點就對應了Lasso在PimaIndiansDiabetes數據集中進行回歸的最佳自變量系數。

圖5 因變量與角分線方向的殘量的平方曲線

由圖5可以看出，加入不同權重判定后，SSR的整體走向完全一致，且最佳系數處對應的殘量基本保持一致，加入權重后不會改變Lasso解法原有的優點。最佳自變量系數有明顯的增大，此時所對應的因變量與角分線方向的殘量有所變化，其中：加入主成分分析法的Lasso解法增加了5.1個百分點的殘量，加入獨立權數法降低了2.1個百分點的殘量，加入CRITIC法降低了2.1個百分點的殘量，即加入獨立權數法和CRITIC法后最后的回歸結果更接近真實因變量。

綜合以上指標，加入獨立權數法后Lasso解的準確性最高，其次是CRITIC法和主成分分析法。加入權重通過改變回歸系數方向提高解準確性，表1展示了原始的回歸系數β以及加入主成分分析法后的β-PCA，加入獨立權數法后的β-IW，加入CRITIC法后的β-CRITIC。從表1中可以看出，β-IW對應的回歸系數相對于原始回歸系數有一定減小，取值區間變窄，但其收斂性沒有改變，而且從圖5中可以看出，其回歸結果更加準確。

表1 不同方法回歸系數

4 結語

本文針對Lasso問題的解法即LARS算法的選擇變量與前進方向過程，提出了基于多維權重的LARS算法，提高了Lasso問題解的準確性，并且保持原Lasso的參數估計具有穩定的回歸系數、較少參數數量的同時具有較好的參數收斂一致性，并采用PimaIndiansDiabetes數據集驗證算法的有效性。由于自變量集維數較大，計算權重的準確度存在瑕疵，因此以后研究中需要進一步優化嵌入的確定權重的算法，以提升回歸算法在利用權重改變前進變量和前進方向選擇時的精度和準確度。

)

[1] 馬景義,張辛連,蘇治，等.廣義線性模型組LASSO路徑算法[J].中國科學:數學，2015,45(10):1725-1738.(MAJY,ZHANGXL,SUZ,etal.AnalgorithmfortheestimationofregularizationpathsofgeneralizedlinearmodelswithgroupLASSOpenalty[J].SCIENTIASINICAMathematica, 2015, 45(10): 1725-1738.)

[2]FRANKIE,FRIEDMANJH.Astatisticalviewofsomechemometricsregressiontools[J].Technometrics, 1993, 35(2): 109-135.

[3]BREIMANL.Bettersubsetregressionusingthenonnegativegarrote[J].Technometrics, 1995, 37(4): 373-384.

[4]TIBSHIRANIR.RegressionshrinkageandselectionviatheLasso[J].JournaloftheRoyalStatisticalSociety.SeriesB(Methodological), 1996, 58(1): 267-288.

[5]EFRONB,HASTIET,JOHNSTONEI,etal.Leastangleregression[J].TheAnnalsofStatistics, 2004, 32(2): 407-499.

[6] 李鋒,蓋玉潔,盧一強.測量誤差模型的自適應LASSO變量選擇方法研究[J].中國科學:數學,2014,44(9):983-1006.(LIF,GAIYJ,LUYQ.AdaptiveLASSOformeasurementerrormodels[J].SCIENTIASINICAMathematica, 2014, 44(9): 983-1006.)

[7]MARAHIELMA.IntroducingLassopeptidesasamolecularscaffoldfordrugdesign[J].JournalofPeptideScience, 2014, 20:S27-S28.

[8]SHAHBEIGS,POURGHASSEMH.Fastandautomaticalgorithmforopticdiscextractioninretinalimagesusingprinciple-component-analysis-basedpreprocessingandcurvelettransform[J].JournaloftheOpticalSocietyofAmericaA—OpticsImageScienceandVision, 2013, 30(1): 13-21.

[9]WANGJ,WANGJ.Forecastingstockmarketindexesusingprinciplecomponentanalysisandstochastictimeeffectiveneuralnetworks[J].Neurocomputing, 2015, 156: 68-78.

[10]DIAKOULAKID,MAVROTASG,PAPAYANNAKISL.Determiningobjectiveweightsinmultiplecriteriaproblems:theCRITICmethod[J].Computers&OperationsResearch, 1995, 22(7): 763-770。

[11]ALHAMZAWIR,YUKM.BayesianLasso-mixedquantileregression[J].JournalofStatisticalComputationandSimulation, 2014, 84(4): 868-880.

[12]KAULA.Lassowithlongmemoryregressionerrors[J].JournalofStatisticalPlanningandInference, 2014, 153: 11-26.

[13]LILH,MOR.Acomprehensivedecision-makingapproachbasedonhierarchicalattributemodelforinformationfusionalgorithms’performanceevaluation[J].MathematicalProblemsinEngineering, 2014, 2014:ArticleID124156.

[14]BACHEK,LICHMANM.UCImachinelearningrepository[DB/OL].Irvine,CA:UniversityofCalifornia. [2016- 09- 20].http://archive.ics.uci.edu/ml.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61303227),thePlanofGuizhouProvincialScienceandTechnologyTalentsinUniversities(KEHEKY[2016]098),theJointFundofGuizhouScienceandTechnologyAgency(KEHELH[2016]7053).

CHEN Shanxiong, born in 1981, Ph.D., associate professor. His research interests include compressed sensing, anomaly detection, pattern recognition.

LIU Xiaojuan, born in 1990, M. S., assistant. Her research interests include pattern recognition, neural network.

CHEN Chunrong, born in 1995, M. S. candidate. Her research interest include data mining, intelligent information processing.

ZHENG Fangyuan, born in 1994, M. S. candidate. His research interest include anomaly detection, network security.

Method for solving Lasso problem by utilizing multi-dimensional weight

CHEN Shanxiong1,2*, LIU Xiaojuan1,2, CHEN Chunrong1, ZHENG fangyuan1

(1.CollegeofComputerandInformationScience,SouthwestUniversity,Chongqing400715,China; 2.SchoolofInformationEngineering,GuizhouUniversityofEngineeringScience,BijieGuizhou551700,China)

Least absolute shrinkage and selection operator (Lasso) has performance superiority in dimension reduction of data and anomaly detection. Concerning the problem that the accuracy is low in anomaly detection based on Lasso, a Least Angle Regression (LARS) algorithm based on multi-dimensional weight was proposed. Firstly, the problem was considered that each regression variable had different weight in the regression model. Namely, the importance of the attribute variable was different in the overall evaluation. So, in calculating angular bisector of LARS algorithm, the united correlation of regression variable and residual vector was introduced to distinguish the effect of different attribute variables on detection results. Then, the three weight estimation methods of Principal Component Analysis (PCA), independent weight evaluation and CRiteria Importance Though Intercriteria Correlation (CRITIC) were added into LARS algorithm respectively. The approach direction and approach variable selection in the solution of LARS were further optimized. Finally, the Pima Indians Diabetes dataset was used to prove the optimal property of the proposed algorithm. The experimental results show that, the LARS algorithm based on multi-dimensional weight has a higher accuracy than the traditional LARS under the same constraint condition with smaller threshold value, and can be more suitable for anomaly detection.

Least absolute shrinkage and selection operator (Lasso); variable selection; Least Angle Regression (LARS); Multiple Linear Regression (MLR); weighting

2016- 11- 07;

2017- 01- 12。 基金項目:國家自然科學基金資助項目(61303227)；貴州省普通高等學校科技拔尖人才支持計劃項目(黔教合KY字[2016] 098)；貴州省科技廳聯合基金資助項目(黔科合LH字[2016]7053) 。

陳善雄(1981—)，男，重慶人，副教授，博士，主要研究方向：壓縮感知、異常檢測、模式識別; 劉小娟(1990—)，女，四川廣安人，助教，碩士，主要研究方向：模式識別、神經網絡； 陳春蓉(1995—)，女，重慶人，碩士研究生，主要研究方向：數據挖掘、智能信息處理;鄭方園(1994—)，男，河南焦作人，碩士研究生，主要研究方向:異常檢測、網絡安全。

1001- 9081(2017)06- 1674- 06

10.11772/j.issn.1001- 9081.2017.06.1674

TP181;TP301.6

A