張 戈

(中國社會科學院大學 計算機教研部,北京 102488)

在大學選課系統(tǒng)的“課程推薦預測”模塊中,系統(tǒng)需要根據(jù)學生的選課要求預測出最適合他的課程,并給出課程推薦建議.本研究的目標是通過對預測模型的參數(shù)優(yōu)化和算法改進,盡可能地提高模型評分即預測準確率,給出課程推薦的最優(yōu)解.

機器學習的預測算法眾多,根據(jù)樣本數(shù)據(jù)特征值的特性,本研究選擇 k 近鄰算法(k-Nearest Neighbors algorithm,k-NN)擬合模型進行預測.k-NN算法主要靠周圍有限的鄰近樣本,而不是靠判別類域的方法來確定目標點的所屬類別.由于本研究中原始樣本數(shù)據(jù)具有局部不均衡和數(shù)據(jù)疊交性,因此對于這種類域的交叉或重疊較多的樣本集來說,k-NN算法較其他算法更為適合.但是在不進行任何參數(shù)調整和算法改進的情況下,推薦課程的預測結果不能夠覆蓋學生對所選課程的要求,模型預測結果不夠準確.為了更好地解決這些問題,獲得推薦和預測結果的最優(yōu)解,本研究從k-NN算法類的選擇入手,逐步探討參數(shù)的調整方案,在分析了kd 樹搜索最近鄰算法之后,依據(jù)樣本數(shù)據(jù)特點研究和設計了“數(shù)據(jù)離散化算法”[1-3].

1 k-NN算法基本原理和研究采用的機器學習方式

在模式識別中,k-NN算法是一種用于分類和回歸的預測方法.在這兩種情況下,輸入由特征空間中k 個最鄰近的訓練實例組成.輸出則取決于k-NN 是用于分類還是回歸:在k-NN 分類中,搜索出和目標點最近鄰的k 個樣本點,按多數(shù)投票原則選出最多的分類作為目標點標簽.在k-NN 做回歸時,一般是用最鄰近的k 個樣本的分類標簽的平均值作為預測結果.

本研究使用Python 語言機器學習工具包scikitlearn 中的KNeighborsClassifier 類建立課程推薦預測模型,我們將圍繞預測模型參數(shù)優(yōu)化和數(shù)據(jù)離散化展開研究工作.

2 預測模型優(yōu)化方案和數(shù)據(jù)離散化算法設計

表1 列出了KNeighborsClassifier 類的主要參數(shù).其中n_neighbors 是近鄰值,即k 值,默認是5,分類器會選取5 個與新數(shù)據(jù)點最接近的樣本.Weights 是分類器在進行預測時用來計算樣本權重的函數(shù).如果該參數(shù)為“uniform”,則表示每個鄰域中的所有樣本的權重都是相等的.如果該參數(shù)為“distance”,則樣本的權重值與它距新數(shù)據(jù)點的距離成倒數(shù)關系.algorith 決定了k-N N 最近鄰的核心算法,該參數(shù)可以是“a u t o”、“brute”、“ball_tree”和“kd_tree”,分別代表自動選取算法、暴力搜索、球樹算法和kd 樹算法.metric 參數(shù)表示距離度量公式,可以是曼哈頓距離或歐氏距離[4-7].

2.1 最優(yōu)k 值選擇算法

本研究首先對k-NN 的重要指標k 值進行優(yōu)化.在優(yōu)化之前,我們采用交叉驗證方法對擬合模型進行準確性評估.圖1 是使用測試集對訓練樣本模型的評分結果,可以看到,在沒有任何參數(shù)調整和算法設計的情況下,擬合模型評分僅為0.67,即預測結果有67%的準確率,可以說模型的測評結果非常不理想.

k 值(即n_neighbors)的選擇高度依賴于樣本數(shù)據(jù).一般來說如果k 值較大,則可以達到抑制噪聲的作用.當然k 值過大會使分類邊界不那么明顯,模型過于簡化,預測標簽會產(chǎn)生多個結果均可的情況.比如我們設定k 值為30,那么KNeighborsClassifier 分類器會選取30 個與新數(shù)據(jù)最接近的訓練樣本點,并按照最多投票原則,選取它們中的最多分類標簽作為預測標簽.相反,如果k 值過小,分類線會竭盡全力的包含到每一個該類的點,即使是噪點,也會被包含,預測模型變得復雜,容易產(chǎn)生過擬合現(xiàn)象.當k 為1 時,就只有一個最鄰近的樣本點被選中,它的標簽即為目標新數(shù)據(jù)的預測標簽.一旦該樣本點是個噪點,那么預測結果就是錯誤的,預測模型失去意義.

圖1 默認參數(shù)下的擬合模型測評結果

本研究對k 值的選擇不采取固定取值的方式,而是通過一個自定義函數(shù)完成k 值的自動選取,該函數(shù)的功能是在k 值的一定選取范圍內對預測模型進行交叉驗證,根據(jù)測評結果選出模型評分最高的k 值.圖2為選取最優(yōu)k 值的活動圖.算法首先給出一個k 的取值范圍,根據(jù)原始數(shù)據(jù)量設置為1 到50.使用交叉驗證方法建立訓練集和測試集,依次使用每個k 值建立擬合模型,比較它們的模型評分,將模型評分最高的k 值記錄下來,用該k 值擬合的模型獲取分類標簽結果.實驗數(shù)據(jù)可以證明k 值的選擇尤為重要.

圖2 選取最優(yōu)k 值算法活動圖

2.2 距離公式優(yōu)化

預測模型的參數(shù)Weights 的默認值是“uniform”,表示鄰域中的具有投票權利的各樣本點的權重都是相等的.這顯然是不合理的.目標新數(shù)據(jù)的標簽應盡量依據(jù)距離它最近鄰的樣本點的標簽給出,并且這些投票樣本點的標簽對最終結果的貢獻應該和它們與目標新數(shù)據(jù)的距離有關.本研究將該參數(shù)調整為“distance”,表示投票樣本點的權重和其距新數(shù)據(jù)點的距離相關(倒數(shù)關系),即距離越近的投票樣本點影響力越大.

本研究中k-NN 最近鄰使用的算法是kd_tree,kd_tree 中距離公式的選擇至關重要.預測模型默認采用“閔可夫斯基”距離公式:

當式(1)中的p 為2 時,即為歐幾里得距離,當p 為1 時,即為曼哈頓距離.

如果距離度量采用歐式距離(euclidean),分類器會計算樣本點和新數(shù)據(jù)點之間的絕對距離.本研究中樣本數(shù)據(jù)每個特征取值范圍較小,均是0 到5 區(qū)域內的整數(shù),那么新數(shù)據(jù)點距離每個特征的歐式距離值就非常相近,分類界線不明顯,歐式距離無法完成更好地分類作用,分類邊界模糊的情況仍舊沒有得到改善.式(2)是曼哈頓距離公式:

曼哈頓距離計算的是目標數(shù)據(jù)點和各個對應特征之間距離的總和.

我們從原始數(shù)據(jù)中隨機抽取300 條數(shù)據(jù)對上述兩種距離公式進行比較.圖3(只顯示部分樣本數(shù)據(jù))中分別計算了目標數(shù)據(jù)點和每個樣本數(shù)據(jù)的歐式距離和曼哈頓距離,歐式距離的樣本方差為1.4,曼哈頓距離的樣本方差為3.4.可以看出使用歐式距離度量的訓練集樣本點分布較密集,樣本點之間的差距不大,不利于分類.曼哈頓距離會分散樣本點分布,分類時的界線識別會略好于歐式距離.實驗數(shù)據(jù)驗證了采用曼哈頓距離的預測模型評分略高于采用歐式距離的評分[8-10].

2.3 數(shù)據(jù)離散化算法設計

k-NN 鄰近算法的核心規(guī)則在brute、kd_tree 和ball_tree 三種算法中進行選擇.本研究中,特征的維度不會超過20 個,因此我們采用更高效、速度更快的kd_tree 搜索最鄰近值.

圖3 樣本點兩種距離度量比較

kd_tree 搜索最鄰近算法首先會找出方差最大的特征向量,然后將其作為當前分割維度,按中位數(shù)分割該維度空間,在當前維度上小于中位數(shù)的數(shù)據(jù)集作為左子樹的數(shù)據(jù)集,大于等于中位數(shù)的數(shù)據(jù)集作為右子樹的數(shù)據(jù)集,依次重復遞歸直到建立一棵kd 樹,從而可以搜索最近鄰的點[11,12].

可以看出,特征向量的權重依據(jù)它們各自的數(shù)據(jù)方差.本研究中的6 個特征向量取值范圍均為0～5.從收集的樣本數(shù)據(jù)來看,“對課程通過率重視程度”和“對課程趣味性的重視程度”兩個特征相比其他特征向量,其數(shù)據(jù)更集中在3～5 之間,數(shù)據(jù)更密集,方差更小.如果按照kd 樹算法的空間分割依據(jù),這兩個特征向量會最后被分割,也就是它們的權重排序是最后兩位.但實際上,我們希望上述兩個特征向量的權重排序分別為第4 位和第5 位.因此我們設計了“數(shù)據(jù)離散化算法”,以期達到“人為”修改6 個特征向量方差的目標,從而讓模型按我們希望的特征權重排序進行分類.如果采用傳統(tǒng)的標準化數(shù)據(jù)的方法,可以將6 個特征向量數(shù)據(jù)統(tǒng)一映射到[0,1]區(qū)間上,但是它不能改變特征向量的權重,其特征向量方差的排序仍舊沒有改變.

本研究建立了“數(shù)據(jù)離散化算法”的核心公式:

每個特征向量的所有樣本數(shù)據(jù)均通過該公式進行預處理.在式(3)中,X 是原始數(shù)據(jù),X*是離散化后的數(shù)據(jù).原始數(shù)據(jù)X 乘以一個倍數(shù)后發(fā)生離散,該倍數(shù)等于樣本數(shù)據(jù)最大值減去樣本數(shù)據(jù)均值乘以系數(shù)λ.λ 系數(shù)為人工給出的期望權重值,取值范圍在[0,1]之間,其作用是降低數(shù)據(jù)分布密集在[3,5]之間的兩個特征的均值.經(jīng)過該離散化公式的處理,原樣本數(shù)據(jù)各個特征向量的方差排序變?yōu)榱宋覀兿Ｍ呐判蝽樞?但是如果考慮到分布區(qū)間內數(shù)據(jù)點的純度對改變特征權重排序的影響,我們需要進一步引入信息熵并研究其對數(shù)據(jù)離散化的作用[13-15].

3 實驗分析

本研究使用Python 語言工具包scikit-learn v0.21.3 對采集的Excel 格式的近千條樣本數(shù)據(jù)擬合預測模型,按3:1 的比例抽取訓練集train 和測試集test 數(shù)據(jù),通過交叉驗證方法評測預測模型,給出模型準確率評分.代碼編輯和輸出結果在jupyter notebook環(huán)境下完成.

3.1 最優(yōu)k 值選擇實驗

本研究首先設計了最優(yōu)化k 值的算法,功能通過自定義函數(shù)selectK()實現(xiàn).圖4 是函數(shù)的代碼及模型測評結果,可以看到當k=7 時,模型評分最高,未進行任何優(yōu)化前的模型評分為0.67,現(xiàn)在為0.76,提高了約13 個百分點.

圖4 選取最優(yōu)k 值實驗及測評結果

3.2 距離公式優(yōu)化實驗

經(jīng)過分析后,距離度量公式采用曼哈頓距離,即p=1,weights 改為“distance”,從圖5 可以看出調整距離公式參數(shù)后,模型評分從0.76 變?yōu)?.79,提高了約4 個百分點.使用曼哈頓距離度量提高了kd 樹搜索算法在建樹過程中分割特征空間時的辨識度,一定程度地提高了預測分類的準確度.但是它對模型測評分提升效果并不明顯.從實驗結果可以看出,樣本數(shù)據(jù)的特征維度在20 以內、樣本數(shù)據(jù)量較大時,采用歐式距離還是曼哈頓距離對最終模型預測結果的影響力沒有參數(shù)k 值最優(yōu)化的影響力大.

3.3 數(shù)據(jù)離散化算法實驗

到目前為止模型的評分并沒有超過0.8,在模型優(yōu)化工作之后,我們的重點轉到對樣本數(shù)據(jù)的離散化上.表2 是數(shù)據(jù)離散化前后的各個特征向量方差及其排序對比.可以看到我們最為關心的兩個分布較密集的特征,其方差排序由之前的第6 位和第5 位,變?yōu)楝F(xiàn)在的第4 位和第5 位,特征向量的權重排序也因此而變?yōu)榱宋覀兿Ｍ臋嘀嘏判?

圖5 采用曼哈頓距離公式實驗測評結果

圖6 是數(shù)據(jù)離散化后的模型測評得分,以及對新數(shù)據(jù)點[2,4,5,2,0,2]進行預測的結果.可以看到此時的預測模型得分為0.85,即預測準確率為85%.而且模型給出了正確的課程預測結果,推薦課程準確.

表2 數(shù)據(jù)離散化實驗前后方差和特征權重對比

圖6 數(shù)據(jù)離散化實驗結果

表3 是本研究在模型未優(yōu)化時和經(jīng)過最優(yōu)化k 值、距離公式優(yōu)化、數(shù)據(jù)離散化幾個過程的預測模型測評分對比.可以看到k 值的自動選取函數(shù)對預測準確率的提升貢獻最大.其次是數(shù)據(jù)的離散化處理使模型測評準確率提高了7.4%.那么可以看到距離公式的優(yōu)化對提高模型準確率只貢獻了不到4 個百分點,這個和樣本數(shù)據(jù)的特征維度個數(shù)有關.在經(jīng)過了預測模型參數(shù)優(yōu)化和數(shù)據(jù)離散化過程后,模型預測準確率由0.67 提高到了最后的0.85,效果非常顯著.

表3 各個優(yōu)化過程模型測評分對比

4 結論與展望

為了在學生選課時給他們推薦更適合他們的課程,本研究建立了課程推薦預測模型.在對樣本數(shù)據(jù)的特點進行詳細分析之后,本研究設計了一套預測模型優(yōu)化方案和數(shù)據(jù)離散化算法,使預測模型的準確率評分提高了約26.8%.

本研究在進行過程中發(fā)現(xiàn)了一些問題和需要進一步探討的內容.首先,距離公式參數(shù)調整對提高模型準確率效果不顯著,隨著數(shù)據(jù)量和特征的增加,距離公式的影響權重需做進一步的研究.第二,實驗證明了數(shù)據(jù)離散化對模型優(yōu)化的顯著效果,但是還有一些問題需要做進一步的思考.例如兩個分布較密集的特征向量其區(qū)間明顯被分割為[0,2]和[3,5]兩個分布.相對于區(qū)間[3,5]的數(shù)據(jù)來說,區(qū)間[0,2]的數(shù)據(jù)點是否可以看做異常點被“拋棄”? 區(qū)間數(shù)據(jù)的純度對數(shù)據(jù)有什么影響?如何改進“數(shù)據(jù)離散化”公式,用一個新的算法自動給出合理的λ 值,而不是人工給出λ 值.第三,樣本數(shù)據(jù)本身是否合理是本研究進行過程中最困擾研究者的一個問題.從實驗結果能夠看到,在做出了預測模型優(yōu)化和離散化數(shù)據(jù)處理之后,模型的評分仍沒有達到0.9 以上,更不要說接近1 的高模型評分.究其原因,原始樣本數(shù)據(jù)在特征向量設計上存在優(yōu)先級不明確、課程的特征屬性相互疊交的情況,一條含糊不清的特征數(shù)據(jù),可能對應1 到2 個標簽結果,并且這兩個結果均合理.如何讓樣本數(shù)據(jù)更可用是下一步要進行的研究.