課程推薦預(yù)測模型優(yōu)化方案及數(shù)據(jù)離散化算法①

張 戈

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

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

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

1 k-NN算法基本原理和研究采用的機(jī)器學(xué)習(xí)方式

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

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

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

表1 列出了KNeighborsClassifier 類的主要參數(shù).其中n_neighbors 是近鄰值,即k 值,默認(rèn)是5,分類器會選取5 個與新數(shù)據(jù)點(diǎn)最接近的樣本.Weights 是分類器在進(jìn)行預(yù)測時用來計算樣本權(quán)重的函數(shù).如果該參數(shù)為“uniform”,則表示每個鄰域中的所有樣本的權(quán)重都是相等的.如果該參數(shù)為“distance”,則樣本的權(quán)重值與它距新數(shù)據(jù)點(diǎn)的距離成倒數(shù)關(guān)系.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 的重要指標(biāo)k 值進(jìn)行優(yōu)化.在優(yōu)化之前,我們采用交叉驗證方法對擬合模型進(jìn)行準(zhǔn)確性評估.圖1 是使用測試集對訓(xùn)練樣本模型的評分結(jié)果,可以看到,在沒有任何參數(shù)調(diào)整和算法設(shè)計的情況下,擬合模型評分僅為0.67,即預(yù)測結(jié)果有67%的準(zhǔn)確率,可以說模型的測評結(jié)果非常不理想.

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

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

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

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

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

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

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

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

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

曼哈頓距離計算的是目標(biāo)數(shù)據(jù)點(diǎn)和各個對應(yīng)特征之間距離的總和.

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

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

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

圖3 樣本點(diǎn)兩種距離度量比較

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

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

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

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

3 實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論與展望

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

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