應(yīng)用監(jiān)督局部線性嵌入算法的科技項(xiàng)目質(zhì)量評價(jià)

李　梁，李宗博

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶　400054)

?

應(yīng)用監(jiān)督局部線性嵌入算法的科技項(xiàng)目質(zhì)量評價(jià)

李梁，李宗博

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶400054)

摘要：針對科技項(xiàng)目管理指標(biāo)的數(shù)據(jù)維度高且相互影響而呈現(xiàn)出的復(fù)雜非線性關(guān)系為準(zhǔn)確評價(jià)和科學(xué)管理帶來挑戰(zhàn)的現(xiàn)狀，同時(shí)考慮到傳統(tǒng)數(shù)據(jù)降維算法大多對非線性數(shù)據(jù)映射效果較差，采用監(jiān)督局部線性嵌入算法，通過數(shù)據(jù)樣本類別信息修改距離公式進(jìn)行特征維數(shù)計(jì)算以獲得科技項(xiàng)目的真實(shí)低維數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明：與傳統(tǒng)算法相比，該算法預(yù)處理的樣本在分類方面具有較高的準(zhǔn)確率。

關(guān)鍵詞：科技項(xiàng)目；監(jiān)督；局部線性嵌入；距離公式

近年來，隨著經(jīng)濟(jì)的快速發(fā)展，可為管理部門提供決策信息、實(shí)現(xiàn)項(xiàng)目科學(xué)管理的科技項(xiàng)目質(zhì)量評價(jià)變得越來越重要。一般來說，科技項(xiàng)目管理指標(biāo)的特征較復(fù)雜，維數(shù)較高，呈現(xiàn)出復(fù)雜的非線性關(guān)系，為信息挖掘帶來了困難。處理“維數(shù)災(zāi)難”[1]是科技項(xiàng)目和其他特征提取工作的首要問題。通過數(shù)據(jù)降維可以減輕維數(shù)災(zāi)難和減少高維空間中的其他不相關(guān)屬性，進(jìn)而促進(jìn)高維數(shù)據(jù)的分類、可視化及壓縮[2]。文獻(xiàn)[3]未對數(shù)據(jù)集進(jìn)行約簡，直接使用神經(jīng)網(wǎng)絡(luò)對數(shù)據(jù)進(jìn)行計(jì)算，獲得了一定的預(yù)測結(jié)果，但該處理方法應(yīng)用范圍較小，只針對小樣本數(shù)據(jù)。為了獲得更佳的處理效果，必要的特征維數(shù)約簡成為關(guān)鍵，數(shù)據(jù)降維在許多領(lǐng)域起著越來越重要的作用。文獻(xiàn)[4]采用PCA算法對喬木高光譜遙感數(shù)據(jù)進(jìn)行降維處理，獲得了效果提升的最佳主成分，避免了高維度容易導(dǎo)致的Hughes現(xiàn)象。文獻(xiàn)[5]將核函數(shù)引入PCA算法進(jìn)行改進(jìn)，使得高維數(shù)據(jù)降維效果得到改善。文獻(xiàn)[6]在解決文檔按主題分類問題時(shí)，利用線性判別式提取每類的正負(fù)特征詞進(jìn)行降維。上述方法基本屬于線性降維的范疇，雖然能獲得一定效果，但算法復(fù)雜度較高，且降維映射過程中會產(chǎn)生較大偏差，無法發(fā)現(xiàn)數(shù)據(jù)間的真實(shí)結(jié)構(gòu)。可見，由于受到項(xiàng)目指標(biāo)特征多且相互影響的限制，傳統(tǒng)數(shù)據(jù)降維方法(尤其是大數(shù)據(jù)下的降維方法)的運(yùn)算代價(jià)和所需存儲空間均受到了挑戰(zhàn)。

目前，基于流形的降維方法已成為機(jī)器學(xué)習(xí)、模式識別等領(lǐng)域的研究熱點(diǎn)，并成功應(yīng)用到多個領(lǐng)域[7-9]。本文嘗試使用監(jiān)督局部線性嵌入代替?zhèn)鹘y(tǒng)局部線性嵌入算法，對樣本數(shù)據(jù)實(shí)現(xiàn)目標(biāo)特征降維，保證樣本類別特征在低維映射中的作用，并結(jié)合多分類支持向量機(jī)分類器進(jìn)行分類試驗(yàn)。試驗(yàn)結(jié)果表明：本文方法的分類正確率有了進(jìn)一步提高，方法有效，可為相關(guān)科技項(xiàng)目質(zhì)量評價(jià)提供參考。

1局部線性嵌入算法

LLE(locally linear embedding)算法[10]是流形學(xué)習(xí)中使用最廣泛的一種算法。LLE的基本思想是：假設(shè)樣本集分布在高位空間的非線性流形上，但在局部范圍內(nèi)，樣本數(shù)據(jù)具有線性結(jié)構(gòu)的特點(diǎn)，給定任意一個樣本均可以利用其自身的近鄰樣本構(gòu)成的鄰域集合進(jìn)行線性組合，且這種線性關(guān)系在映射降維的過程中保持不變，即低維樣本的線性重構(gòu)系數(shù)(權(quán)值)和高維樣本相同。根據(jù)上述思想可以通過求解稀疏矩陣特征向量來獲取LLE的低維流形。

給定數(shù)據(jù)集X={x1,x2,…,xn}，xi∈RD，以歐式距離為基礎(chǔ)得到各樣本間的距離Dij(i,j∈1,2,…,n)，為每個樣本數(shù)據(jù)xi找到它的k個近鄰構(gòu)成其自身的重構(gòu)鄰域。

利用數(shù)據(jù)的重構(gòu)鄰域進(jìn)行重構(gòu)權(quán)值wij的計(jì)算，并使得重構(gòu)函數(shù)minε(w)的代價(jià)最小

(1)

(2)

式(2)中：n為樣本總數(shù)；yi是xi的低維映射表示；y為yi構(gòu)成的n×d矩陣；w為wij構(gòu)成的n×n方陣，則在矩陣M中最小的第2至第(d+1)個特征向量值就是所求的低維流形y。

鄰域點(diǎn)數(shù)k直接定義了流形的最佳分割，若鄰域點(diǎn)數(shù)k過小，則不能體現(xiàn)各類別的流形特征；若過大，又會增加冗余運(yùn)算，降低數(shù)據(jù)的降維性能。k值以及最終低維流形的空間維數(shù)d都會對最終降維結(jié)果產(chǎn)生影響[11]。

2監(jiān)督局部線性嵌入

LLE作為一種非監(jiān)督流形降維算法，未能充分利用已有樣本數(shù)據(jù)的類別屬性信息[12]，因此，使用映射后的低維流形提升分類器的性能有待進(jìn)一步加強(qiáng)。為克服LLE的不足，在傳統(tǒng)算法中融入樣本類別屬性，保持樣本間類別信息在低維流形的穩(wěn)定性是充分挖掘樣本數(shù)據(jù)的有效途徑。監(jiān)督局部線性嵌入(S-LLE)基于同類樣本點(diǎn)間距離小于異類樣本點(diǎn)間距離的假設(shè)，將樣本類別計(jì)入樣本間距離中去，從而修正距離并改進(jìn)替換傳統(tǒng)LLE算法中的歐式距離，使得同類樣本點(diǎn)鄰域的構(gòu)成能更準(zhǔn)確地體現(xiàn)在低維流形中。

樣本距離公式修正為

(3)

其中：Dij為樣本xi與xj的歐式距離；Die滿足Die=max(Diu),u=1,2,…,n；λ為修正調(diào)節(jié)程度參數(shù)，取值范圍為[0,1]；δij為修正參數(shù)，用于說明樣本點(diǎn)是否屬于同類，若樣本xi與xj屬于同類，則δij=0，否則δij=1。

當(dāng)λ=0時(shí)，算法退化為傳統(tǒng)的LLE算法；當(dāng)λ≠0且逐漸增大時(shí)，同類樣本間距逐漸小于異類樣本間距，使得樣本鄰域盡可能多地由同類樣本構(gòu)成，達(dá)到“類間離散，類內(nèi)聚合”的效果，最終增強(qiáng)高維映射的精度。使用修正后的距離求解樣本數(shù)據(jù)的鄰域，進(jìn)而結(jié)合LLE的后續(xù)1、2步驟，即可求出帶有樣本類別信息的降維后的低維流形數(shù)據(jù)。

3測試樣本降維

測試樣本對于衡量分類器性能至關(guān)重要。LLE算法對新加入的樣本非常敏感，認(rèn)為這會破壞訓(xùn)練樣本原有的拓?fù)浣Y(jié)構(gòu)，嚴(yán)格來說應(yīng)對所有測試樣本重新求解鄰域關(guān)系。由于本文測試樣本數(shù)量少于訓(xùn)練樣本，且考慮到算法運(yùn)行時(shí)的效率問題以及算法假設(shè)數(shù)據(jù)自身帶有局部線性特征，最后采取線性近似的方法求解測試樣本的低維流形數(shù)據(jù)。大致過程如下：首先，在訓(xùn)練樣本鄰域的基礎(chǔ)上計(jì)算測試樣本的近鄰點(diǎn)；然后，同樣以重構(gòu)函數(shù)代價(jià)最小為目的計(jì)算測試樣本的重構(gòu)權(quán)值，并保持該權(quán)值不變；最后，依靠訓(xùn)練樣本對應(yīng)的低維流形求出測試樣本的低維流形。

4分類實(shí)驗(yàn)

4.1實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證算法在評價(jià)應(yīng)用方面的有效性，特地選取某高校科研項(xiàng)目管理平臺中的部分?jǐn)?shù)據(jù)作為數(shù)據(jù)集。該數(shù)據(jù)集包含60個項(xiàng)目樣本，其中每個樣本的特征有30個。對于空缺值用均值填充，項(xiàng)目評價(jià)類別共分為4個等級(優(yōu)A、良B、一般C、差D)。

4.2實(shí)驗(yàn)方法

在分類器選取方面，采用泛化能力較好的支持向量機(jī)進(jìn)行分類[13-14]，提高分類精度。多分類支持向量機(jī)在分類時(shí)通常有2種方法，即“一對多”法和“一對一”法[15]。由于“一對多”法考慮全局優(yōu)化致使計(jì)算復(fù)雜度增大，所以可行性較低。本文使用“一對一”法，將多類問題轉(zhuǎn)化為多個二類問題，建立4×(4-1)/2=6個二類支持向量機(jī)，輸入測試樣本得到各自的類別概率。分類最終結(jié)果由較大的概率值決定。

實(shí)驗(yàn)分類步驟如下所示：

步驟1數(shù)據(jù)集按0.8比例隨機(jī)劃分為訓(xùn)練集、測試集。

步驟2對訓(xùn)練集應(yīng)用S-LLE算法進(jìn)行降維，保存權(quán)值矩陣，并利用該矩陣對測試集進(jìn)行映射轉(zhuǎn)換，與約減后的訓(xùn)練集特征數(shù)目一致。

步驟3將約減訓(xùn)練集輸入多分類支持向量機(jī)，訓(xùn)練相應(yīng)參數(shù)得到相應(yīng)模型。

步驟4利用訓(xùn)練模型，針對對應(yīng)的轉(zhuǎn)換測試集進(jìn)行測試分類，保存分類結(jié)果。

步驟5重復(fù)上述1、2、3、4步驟5次，計(jì)算分類的平均正確率。

其中：步驟2對數(shù)據(jù)高維空間降維時(shí)，對于式(3)中的調(diào)節(jié)參數(shù)λ設(shè)定初始值為0.1，并以步長0.2增加，鄰域點(diǎn)數(shù)k以訓(xùn)練樣本的25%作為最大上限，即k=15，k的下限取10，設(shè)定以步長1逐漸增加。低維空間維數(shù)d定為特征總數(shù)的70%。

利用上述參數(shù)對分類實(shí)驗(yàn)重復(fù)5次，獲得使用降維數(shù)據(jù)分類后的平均正確率，結(jié)果如表1所示。

表1　分類后的平均正確率

S-LLE算法受參數(shù)λ、k的影響較大，不同的參數(shù)組合會產(chǎn)生不同的低維映射，進(jìn)而影響到分類器性能。由表1的數(shù)據(jù)可知：隨著鄰域點(diǎn)數(shù)k與調(diào)節(jié)參數(shù)λ逐漸增大，項(xiàng)目分類的正確率會緩慢上升。當(dāng)組合參數(shù)為k=13、λ=0.3時(shí)，分類器性能最佳，之后正確率下降，分類器性能受到限制。

4.3降維算法對比實(shí)驗(yàn)

為了驗(yàn)證S-LLE算法與傳統(tǒng)線性降維算法PCA、非線性降維算法LLE的降維效果，三種算法均相應(yīng)地對劃分后的訓(xùn)練集合進(jìn)行獨(dú)立降維，之后結(jié)合4.2中實(shí)驗(yàn)方法的步驟3～5進(jìn)行分類。其中，對于S-LLE而言，組合參數(shù)選定為k=13、λ=0.3。低維空間維數(shù)下限設(shè)定為15，并以步長1增加到25。分類實(shí)驗(yàn)之前，首先對48個樣本分別使用3種算法進(jìn)行降維，得到二維可視結(jié)果，如圖1所示。feature1和feature2為降維算法自動選擇的2個特征。

利用上述方法實(shí)現(xiàn)降維的數(shù)據(jù)集獲取分類特征，從而實(shí)現(xiàn)分類。每個實(shí)驗(yàn)重復(fù)5次，得到不同維數(shù)下不同降維算法的分類結(jié)果。圖2展示了通過各個降維算法處理后的數(shù)據(jù)集經(jīng)相同分類器分類后的最終結(jié)果。

圖1　樣本降維結(jié)果比較

圖2　SVM分類結(jié)果

4.4實(shí)驗(yàn)結(jié)果與分析

由圖1可以看出：PCA和LLE對數(shù)據(jù)的聚合效果較差；S-LLE由于融合了樣本類別信息，使得噪聲樣本在一定程度上得到了抑制，因此聚類效果更加明顯。

由圖2可知：相應(yīng)的降維算法均可實(shí)現(xiàn)相關(guān)數(shù)據(jù)特征的提取，縮小待處理數(shù)據(jù)的規(guī)模，進(jìn)而提升分類效果。另外，隨著降維特征數(shù)目的增加，3條曲線緩慢上升，之后基本保持不變的趨勢，總體都在21或22個特征時(shí)，SVM的分類準(zhǔn)確率達(dá)到最優(yōu)。

傳統(tǒng)線性降維算法PCA單純地以保留樣本最大方差為準(zhǔn)則實(shí)現(xiàn)降維，未充分使用與其他樣本間的相關(guān)性；LLE與S-LLE算法均為非線性降維算法，在樣本間局部線性的前提下進(jìn)行線性相似表示實(shí)現(xiàn)降維，描述出降維后各樣本間的真實(shí)拓?fù)浣Y(jié)構(gòu)，保留了更多的價(jià)值信息，因而分類準(zhǔn)確率高于PCA；S-LLE由于將樣本類別融入距離公式進(jìn)行距離修正，使得同類樣本點(diǎn)優(yōu)先進(jìn)入鄰域進(jìn)行低維映射計(jì)算，最后達(dá)到“類間離散，類內(nèi)聚合”的效果，實(shí)現(xiàn)了監(jiān)督分類，因此分類準(zhǔn)確率最高?？梢?，相比其他算法， S-LLE算法可以提高項(xiàng)目分類的準(zhǔn)確率，適合作為科技項(xiàng)目分類問題的預(yù)處理算法。

5結(jié)束語

由于受到科技項(xiàng)目指標(biāo)多且數(shù)據(jù)復(fù)雜的影響，對傳統(tǒng)LLE降維算法進(jìn)行了相應(yīng)改進(jìn)，并使用處理后的數(shù)據(jù)進(jìn)行分類，提升了項(xiàng)目分類的效果。關(guān)于如何選取參數(shù)組合是今后研究的重點(diǎn)。

參考文獻(xiàn)：

[1]畢達(dá)天，邱長波，張晗.數(shù)據(jù)降維技術(shù)研究現(xiàn)狀及其進(jìn)展 [J].情報(bào)理論與實(shí)踐，2013，36(2):125-128.

[2]吳曉婷，閆德勤.數(shù)據(jù)降維方法分析與研究[J].計(jì)算機(jī)應(yīng)用研究，2009,26(8):2832-2835.

[3]鄭永，陳艷.基于BP神經(jīng)網(wǎng)絡(luò)的高校教師教學(xué)質(zhì)量評價(jià)模型 [J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2015，29(1):85-90.

[4]藏卓，林輝，楊敏華.利用PCA算法進(jìn)行喬木樹種高光譜數(shù)據(jù)降維與分類[J].測繪科學(xué)，2014,39(2):146-149.

[5]王瀛，郭雷，梁楠.基于優(yōu)選樣本的KPCA高光譜圖像降維方法[J].光子學(xué)報(bào)，2011，40(6)：847-851.

[6]徐敏，張麗萍，朱梧槚.基于Fisher線性判別式的層次文檔分類[J].南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2005，29(4)：460-463.

[7]向丹，葛爽.基于EMD樣本熵和流形學(xué)習(xí)的故障特征提取方法 [J].航空動力學(xué)報(bào)，2014,29(7):1533-1540.

[8]倪志偉，薛永堅(jiān)，倪麗萍，等.基于流形學(xué)習(xí)的多核SVM財(cái)務(wù)預(yù)警方法研究 [J].系統(tǒng)工程理論與實(shí)踐，2014，34(10)：2666-2674.

[9]湯寶平，馬婧華.多準(zhǔn)則融合敏感特征選擇和自適應(yīng)鄰域的流形學(xué)習(xí)故障診斷[J].儀器儀表學(xué)報(bào)，2014，35(11)：2413-2420.

[10]ROWELS S T,SAUL L K.Nonlinear dimensionality reduction by locally linear embedding [J].Science,2000,290(5500):2323-2326.

[11]文貴華，包麗，丁月華.局部線性嵌入算法中參數(shù)的選取 [J].計(jì)算機(jī)應(yīng)用研究，2007,43(9):179-183.

[12]董安，潘宏俠，龔明.基于局部線性嵌入算法的柴油機(jī)故障診斷研究 [J].計(jì)算機(jī)工程與應(yīng)用，2013,49(22):236-240.

[13]GENTLE J E，HARDLE W K，MORI Y C.Handbook of Computational Statistics:Concepts and Methods[M]． Second Edition:Springer Press，2012:883-926.

[14]李利杰，張君華，熊偉清，等.一種改進(jìn)的支持向量機(jī)模型優(yōu)化算法 [J].計(jì)算機(jī)技術(shù)與發(fā)展，2014(12):22-26.

[15]韓兆洲，林少萍，鄭博儒.多類支持向量機(jī)分類技術(shù)及實(shí)證 [J].統(tǒng)計(jì)與決策，2015(19):10-13.

(責(zé)任編輯楊黎麗)

Evaluation of the Quality of Technology Projects Based on Supervised Locally Linear Embedded Algorithm

LI Liang, LI Zong-bo

(College of Computer Science and Engineering,Chongqing University of Technology, Chongqing 400054, China)

Abstract:Dimension of indicators data about technology project is the higher, and has interaction influence, and shows complex nonlinear relationship, which brings challenges for the accurate evaluation of scientific management. Considering that most of traditional reduction algorithms about data dimension are poor for nonlinear effects of mapping data, so that we used supervised locally linear embedding algorithm to modify the distance formula according to data sample classification information, finally we calculated the feature and got the real low-dimensional data. The experimental results show that compared with the traditional algorithm, the sample data preprocessed algorithm has a higher accuracy on the performance of classification.

Key words:technology project; supervision; locally linear embedding; distance formula

文章編號：1674-8425(2016)04-0097-05

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A

doi:10.3969/j.issn.1674-8425(z).2016.04.017

作者簡介：李梁(1964—)，男，重慶人，副教授，主要從事數(shù)據(jù)挖掘和數(shù)據(jù)倉庫、數(shù)據(jù)庫技術(shù)研究；李宗博(1986—)，男，河北滄州人，碩士研究生，主要從事數(shù)據(jù)管理技術(shù)研究。

基金項(xiàng)目：重慶市應(yīng)用開發(fā)計(jì)劃項(xiàng)目(CSTC2013yykfA40002)

收稿日期：2015-11-28

引用格式：李梁，李宗博.應(yīng)用監(jiān)督局部線性嵌入算法的科技項(xiàng)目質(zhì)量評價(jià)[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2016(4):97-101.

Citation format：LI Liang, LI Zong-bo.Evaluation of the Quality of Technology Projects Based on Supervised Locally Linear Embedded Algorithm[J].Journal of Chongqing University of Technology(Natural Science)，2016(4):97-101.