李 鑫, 張 偉, 張 蕾
(1. 吉林大學 校長辦公室, 長春 130012; 2. 吉林大學 發(fā)展規(guī)劃處, 長春 130012)
非負矩陣分解(nonnegative matrix factorization, NMF)是一種簡潔高效的矩陣分解算法[1]. 該算法是在矩陣中所有元素均為非負約束下的矩陣分解方法, 目標是使分解后的所有分量均為非負值并實現(xiàn)非線性維數(shù)約減[2]. 由于該算法不需要訓練樣本, 能自動發(fā)現(xiàn)數(shù)據(jù)中潛在的主題和基向量, 因此非負矩陣分解模型及其改進算法已廣泛應用于圖像處理[3]、 基因功能預測[4]、 推薦系統(tǒng)[5]和文本挖掘[6-7]等領(lǐng)域. 雖然非負矩陣分解具有簡便性、 結(jié)果可解釋性及空間算法復雜度低等優(yōu)點, 但傳統(tǒng)非負矩陣分解在求解過程中, 基向量矩陣和系數(shù)矩陣均需利用隨機函數(shù)初始化, 基向量數(shù)目和最大迭代次數(shù)均需專家指定或通過大量實驗進行確認. 文獻[3]和文獻[8]為解決隨機性問題, 設(shè)定了常數(shù)閾值并將迭代求解后求得的平均值作為最終結(jié)果, 在文本數(shù)據(jù)和急性髓細胞白血病數(shù)據(jù)分析上取得了較好的效果, 但上述方法均未考慮算法最大迭代次數(shù)對結(jié)果的影響, 而最大迭代次數(shù)參數(shù)選擇不當會降低基向量的代表性. 因此, 本文提出一種基于梯度下降的自適應策略, 并將其引入到非負矩陣分解方法中. 同時, 提出一種自適應非負矩陣分解算法(self-adaptive nonnegative matrix factorization, SANMF). 實驗結(jié)果表明, SANMF算法與傳統(tǒng)非負矩陣分解算法相比增強了魯棒性, 提高了分解的精度.
經(jīng)典非負矩陣分解算法描述為: 對任意給定的一個非負矩陣V∈F×N, 求解非負矩陣W∈F×T和H∈T×N, 使得
VF×N≈WF×T×HT×N.
(1)
非負矩陣分解是個NP難問題. 因此, 求解可簡化為優(yōu)化問題用迭代方法交替求解W和V. 令E表示重構(gòu)矩陣與原始矩陣V之間的誤差矩陣, 利用最大似然法求解, 即對下列目標函數(shù)取最小值:
(2)
其中,i和j分別表示矩陣中的行數(shù)和列數(shù).W和H在NMF求解過程中的更新規(guī)則[9]為
(3)
文獻[3]和文獻[8]在分析文本數(shù)據(jù)和急性髓細胞白血病數(shù)據(jù)時, 將最大迭代次數(shù)和基向量數(shù)目設(shè)為常數(shù), 但當處理不同規(guī)模和不同類型的數(shù)據(jù)時, 固定的常數(shù)閾值無法滿足實際需求.
2.1 梯度下降自適應策略 為降低經(jīng)典非負矩陣分解算法的最大迭代次數(shù)q對實驗結(jié)果的影響, 本文提出一種基于梯度下降的自適應策略. 該策略引入兩個與原始矩陣V中行數(shù)F相關(guān)的閾值變量, 分別為上界(θUp=2F)和下界(θDown=F). 則NMF算法中最大迭代次數(shù)求解過程通過引入約束簡化為有限域上的求解. 梯度下降自適應求解策略公式為
圖1 自適應非負矩陣分解算法流程
EDt+1=NMF(qt),
(4)
(5)
(6)
(7)
其中: NMF(q)表示以q為最大迭代次數(shù)的傳統(tǒng)非負矩陣方法;t為求解NMF的當前迭代次數(shù). 該方法能迭代求解出合適的NMF最大迭代次數(shù).
2.2 SANMF算法 自適應非負矩陣分解算法流程如圖1所示. 算法輸入為待分解的非負矩陣, 算法步驟如下:
1) 根據(jù)矩陣行數(shù)確認上界和下界;
2) 根據(jù)梯度下降自適應策略, 用式(4)~(7)更新上下界;
3) 用式(3)計算得出W和H;
4) ED=V-WH;
5) 比較ED和ED上界(q取上界時ED的值), ED下界(q取下界時ED的值), 如果ED同時小于ED上界和ED下界, 則表示SANMF算法結(jié)束, 輸出結(jié)果; 如果ED僅小于ED上界, 則用當前ED替換ED上界, 迭代執(zhí)行步驟2)梯度下降自適應策略, 同時在步驟2)中更新程序存儲的ED上界值; 如果ED僅小于ED下界, 則迭代執(zhí)行步驟2)梯度下降自適應策略, 并用當前ED值替換ED下界值, 同時在步驟2)中更新存儲的ED下界值;
6) 輸出算法運行結(jié)果ED,W和H.
為檢驗算法的有效性, 實驗發(fā)現(xiàn)學生中潛在的學習團體, 收集并整理吉林大學某學院264名學生2014—2018年度319門課程的成績, 課程包括基礎(chǔ)課、 必修課和選修課等, 其中五分制的課程評分全部折算為百分制(0~100分). 由于學生成績矩陣中包含選修課成績, 而通常情況學生選修課課程分布較廣, 所以成績矩陣中包含大量0元素. 經(jīng)統(tǒng)計確認課程中的13 429個成績?yōu)?分, 矩陣中0元素百分數(shù)為15.9%. 這些0元素所在向量直接影響了數(shù)據(jù)分析的結(jié)果, 運用非負矩陣分解可發(fā)現(xiàn)基向量, 從而有效減少稀疏向量的影響. 而直接用經(jīng)典算法(NMF)分解得到的矩陣誤差較大, 因此, 本文將自適應非負矩陣分解模型用于該數(shù)據(jù)分析中.
圖2為自適應非負矩陣分解算法(SANMF)與經(jīng)典算法(NMF)的比較結(jié)果, 其中基向量數(shù)量為6. 由圖2可見, 二者的聚類結(jié)果存在一定的差異. ED為重構(gòu)矩陣與原始矩陣之間的歐氏距離, 該值越小說明重構(gòu)矩陣與原矩陣之間的差距越小. 自適應非負矩陣分解算法得到的重構(gòu)矩陣誤差比經(jīng)典非負矩陣分解算法降低了20.16%, 因此, SANMF算法優(yōu)于傳統(tǒng)NMF算法.
圖2 傳統(tǒng)非負矩陣分解算法與自適應非負矩陣分解算法聚類結(jié)果比較
圖3 基于自適應非負矩陣分解的學生和課程聚類分析結(jié)果
圖3為自適應非負矩陣分解算法分解學生成績矩陣的結(jié)果. 其中: 圖3(A)~(C)為矩陣分解后課程層次聚類結(jié)果; 圖3(D)~(F)為學生層次聚類結(jié)果. 當選擇不同的基向量數(shù)目時, 聚類結(jié)果不同. 由圖3可見, 實驗分別選擇了4,5,6共3組不同的基向量數(shù)目, 該參數(shù)直接影響聚類結(jié)果. 盡管課程分為基礎(chǔ)課、 專業(yè)課和選修課, 但由圖3(A)~(C)可見, 當基向量為6時, 重構(gòu)矩陣誤差ED=2 815.68為最低, 比基向量取4和5時分別降低了33.17%和31.55%. 結(jié)果表明, 對該學院開設(shè)的課程可進一步細分或用其他分類方法. 由圖3(D)~(F)可見, 當基向量為6時, 重構(gòu)矩陣誤差ED=2 725.83為最低, 比基向量取4和5時分別降低了31.76%和24.1%. 該結(jié)果可為高校建設(shè)一流學科和優(yōu)勢特色專業(yè)、 優(yōu)化專業(yè)設(shè)置提供數(shù)據(jù)支持. 雖然這些學生只來自4個專業(yè), 但學生可根據(jù)自己的學習興趣和職業(yè)規(guī)劃不同劃分更細致的學習社團, 如可將學生劃分為6個學習社團. 要確定最佳基向量取值, 可將梯度下降自適應策略中的最大迭代次數(shù)變量用基向量替換, 從而得到面向基向量的自適應非負矩陣分解方法.
綜上可見, 給定一個矩陣后, 當其他參數(shù)不變時, 最大迭代次數(shù)越大矩陣分解的結(jié)果越接近原矩陣. 但當達到某一閾值后, 矩陣分解的誤差降低緩慢或不再降低. 同時, 隨著迭代次數(shù)的增大, 算法的計算時間也快速增加. 本文提出了一種基于梯度下降自適應策略的非負矩陣分解算法, 該方法將自適應策略引入到矩陣分解求解過程中, 自適應地尋找NMF計算過程中的最大迭代次數(shù)并提高重構(gòu)矩陣的精度, 使基于矩陣分解結(jié)構(gòu)的聚類魯棒性更強. 對吉林大學某學院學生成績數(shù)據(jù)進行驗證的實驗結(jié)果表明, 基于梯度下降自適應策略的非負矩陣分解算法可明顯提高矩陣分解的精度和魯棒性, 該研究結(jié)果可為優(yōu)化高校專業(yè)設(shè)置提供數(shù)據(jù)支持.