针对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