【正文】 個性化推薦系統(tǒng)設(shè)計(jì)畢業(yè)論文目錄1 研究目的 1 研究背景及意義 1 推薦系統(tǒng)現(xiàn)狀 2 論文內(nèi)容與章節(jié)安排 32 理論支持與相關(guān)技術(shù)的應(yīng)用與背景 4 相應(yīng)的推薦算法及數(shù)學(xué)原理 4 Weka的技術(shù)介紹與應(yīng)用 15 Weka系統(tǒng)簡介 15 Weka系統(tǒng)的特點(diǎn)與應(yīng)用 153 習(xí)題個性化推薦系統(tǒng)的設(shè)計(jì)原理 19 研究難題解決 19 基于記憶的過濾 20 基于用戶的協(xié)同過濾 20 基于內(nèi)容的協(xié)同過濾 22 基于規(guī)則的過濾 22 通過比例因子進(jìn)行優(yōu)化 244 系統(tǒng)的實(shí)現(xiàn) 25 需求分析 25 概要設(shè)計(jì) 26 數(shù)據(jù)采集與預(yù)處理階段 26 數(shù)據(jù)處理階段 26 數(shù)據(jù)庫的設(shè)計(jì) 28 推薦系統(tǒng)的總體結(jié)構(gòu) 30 系統(tǒng)詳細(xì)設(shè)計(jì) 31 用戶信息管理模塊 31 用戶推薦模塊 34 用戶搜索模塊 36 系統(tǒng)的開發(fā)環(huán)境 365 總結(jié) 42參考文獻(xiàn) 44致謝辭 45附錄 46附錄1 英文原文 46附錄2 中文原文 54附錄3 部分代碼 591 研究目的智能在線學(xué)習(xí)系統(tǒng)[1]是個性化推薦的一種應(yīng)用，本文介紹的是基于OJ數(shù)據(jù)的習(xí)題個性化推薦系統(tǒng)，本章簡要介紹個性化推薦的概念、背景與國內(nèi)外研究現(xiàn)狀，并且針對目前流行的推薦方法予以介紹。近年來，隨著互聯(lián)網(wǎng)、移動設(shè)備等信息技術(shù)的迅猛發(fā)展，除了企業(yè)業(yè)務(wù)運(yùn)營中不斷積累的交易等業(yè)務(wù)數(shù)據(jù)之外，遍布全球的傳感器無時無刻不在探測和收集物理世界的各種信息，移動互聯(lián)網(wǎng)則在不斷收集用戶的地理位置信息，各種社會媒體中的數(shù)以億計(jì)的用戶也在隨時隨地地產(chǎn)生交互信息，這些數(shù)據(jù)不僅是數(shù)量巨大（以TB甚至PB為單位），而且形式繁多，除了企業(yè)業(yè)務(wù)運(yùn)營信息系統(tǒng)中的結(jié)構(gòu)化數(shù)據(jù)之外，各種文本、聲音、圖片、視頻、地理位置等各種不同類型的數(shù)據(jù)決定了數(shù)據(jù)的多樣性。同時，這些時刻變化的來自各種數(shù)據(jù)源的數(shù)據(jù)有充滿了噪音，對這些數(shù)據(jù)的管理和分析已經(jīng)超出了傳統(tǒng)的數(shù)據(jù)管理技術(shù)的能力，因此，人們稱其為大數(shù)據(jù)[2]。在教育領(lǐng)域，智能教學(xué)系統(tǒng)（Intellectual Tutoring System）利用人工智能和計(jì)算機(jī)技術(shù)來模擬現(xiàn)實(shí)教學(xué)過程，使得該系統(tǒng)具備了人力教學(xué)所不具備的高效率、高存儲、個性化等特點(diǎn)。其廣闊的發(fā)展前景使得越來越多的專家開始投入到對ITS的研究中，希望可以憑借計(jì)算機(jī)對知識的有效處理，由計(jì)算機(jī)代替老師來提高學(xué)生學(xué)習(xí)效率，并最終實(shí)現(xiàn)人類對其自身認(rèn)知過程的終極解碼。智能教學(xué)系統(tǒng)作為一種輔助教學(xué)手段，其中運(yùn)用傳統(tǒng)的個性化推薦方法有其局限性，對于基于用戶的協(xié)同過濾,推薦的原則必須要求用戶會喜歡那些和他有相同喜好的用戶喜歡的東西；對于基于內(nèi)容的協(xié)同過濾則有個前提，就是用戶會喜歡和他以前喜歡的東西相似的東西，那么我們可以計(jì)算一個用戶喜歡的物品的自相似度。一個用戶喜歡物品的自相似度大，就說明他喜歡的東西都是比較相似的，只有在這種情況下，該方法才會具有較高的推薦效率。為了能夠提高個性化推薦系統(tǒng)的準(zhǔn)確率，本論文摒棄單一的協(xié)同過濾方法，提出新的推薦方法思路并將其理論應(yīng)用智能在線學(xué)習(xí)系統(tǒng)中，更大的發(fā)揮在線學(xué)習(xí)系統(tǒng)個性化推薦的作用，為學(xué)生提供更優(yōu)質(zhì)的服務(wù)。目前對于個性化推薦系統(tǒng)的研究正處于高速發(fā)展期,相關(guān)的推薦算法也已在電子商務(wù)領(lǐng)域、個性化搜索等領(lǐng)域得到一定程度的發(fā)展和應(yīng)用。傳統(tǒng)的個性化推薦算法包括基于內(nèi)容的推薦、基于行為的推薦、以及混合推薦算法，其中基于行為的個性化推薦算法憑借其出色的行為分析和興趣建模，得到了業(yè)內(nèi)專家學(xué)者的廣泛研究。但具體到在線學(xué)習(xí)系統(tǒng)領(lǐng)域，系統(tǒng)本身包含的知識評測系統(tǒng)、以及知識表示系統(tǒng)決定了ITS中的個性化推薦模塊對知識的依賴多余對用戶學(xué)習(xí)行為的依賴。相比于利益驅(qū)動的電子商務(wù)領(lǐng)域個性化推薦算法的蓬勃發(fā)展，主要應(yīng)用于教育領(lǐng)域的個性化推薦算法的研究則相對疲軟。由于教育領(lǐng)域內(nèi)知識本身具有很強(qiáng)的語義關(guān)系，軟件對用戶的輔導(dǎo)更多地是強(qiáng)調(diào)用戶在認(rèn)知學(xué)習(xí)中對知識語義間聯(lián)系的掌握。而應(yīng)用較為廣泛基于行為的個性化推薦算法，其原理則是通過構(gòu)建鄰居矩陣來判斷用戶的興趣來為用戶進(jìn)行資源推薦，對于智能教輔而言，單一的基于用戶的協(xié)同過濾和基于內(nèi)容的協(xié)同過濾算法推薦結(jié)果忽略了用戶在進(jìn)行知識學(xué)習(xí)時表現(xiàn)出的認(rèn)知特點(diǎn)，其準(zhǔn)確度勢必降低。因此，本文將在前人的基礎(chǔ)上，研究基于記憶的個性化推薦算法，在本系統(tǒng)中，包含兩個緯度：其一，基于用戶（學(xué)生）的協(xié)同過濾[4]，其二，基于內(nèi)容（習(xí)題）的協(xié)同過濾，兩者都是利用學(xué)生用戶過去使用在線學(xué)習(xí)系統(tǒng)的歷史提交記錄，從而對學(xué)生進(jìn)行習(xí)題個性化推薦。將算法研究重點(diǎn)放到對知識結(jié)構(gòu)與習(xí)題資源本身的信息的利用和處理上，以解決在ITS系統(tǒng)中為學(xué)生從海量資源中進(jìn)行個性化資源推薦的問題，并將通過實(shí)驗(yàn)證明該算法和系統(tǒng)的理論價(jià)值與應(yīng)用價(jià)值。對于介紹基于OJ數(shù)據(jù)的習(xí)題個性化推薦系統(tǒng)論文以下內(nèi)容安排如下：第二部分側(cè)重介紹本系統(tǒng)數(shù)據(jù)處理過程中依據(jù)的理論知識背景及技術(shù)應(yīng)用；第三部分講述了習(xí)題推薦系統(tǒng)實(shí)現(xiàn)過程中遇到的難題及整個系統(tǒng)的設(shè)計(jì)思路；第四部分描述系統(tǒng)實(shí)現(xiàn)的詳細(xì)步驟；第五部分總結(jié)了本系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)過程中的心得與體會。2 理論支持與相關(guān)技術(shù)的應(yīng)用與背景習(xí)題個性化推薦系統(tǒng)所運(yùn)用的理論來源于集體智慧，本系統(tǒng)中實(shí)現(xiàn)該理論的具體方法是基于記憶的協(xié)同過濾和基于規(guī)則的協(xié)同過濾。鑒于開源軟件Weka的強(qiáng)大功能和對Java應(yīng)用程序的支持，我們采用Java作為開發(fā)語言，調(diào)用Weka程序返回的數(shù)據(jù)。下面對這些方法的數(shù)學(xué)原理和工具或平臺做具體介紹。集體智慧 (Collective Intelligence) [7]，大家在Web應(yīng)用中利用集體智慧構(gòu)建更加有趣的應(yīng)用或者得到更好的用戶體驗(yàn)。集體智慧是指在大量的人群的行為和數(shù)據(jù)中收集答案，幫助你對整個人群得到統(tǒng)計(jì)意義上的結(jié)論，這些結(jié)論是我們在單個個體上無法得到的，它往往是某種趨勢或者人群中共性的部分。協(xié)同過濾是利用集體智慧的一個典型方法。要理解什么是協(xié)同過濾 (Collaborative Filtering, 簡稱 CF) [5]，首先想一個簡單的問題，如果你現(xiàn)在想看個電影，但你不知道具體看哪部，你會怎么做？大部分的人會問問周圍的朋友，看看最近有什么好看的電影推薦，而我們一般更傾向于從口味比較類似的朋友那里得到推薦。這就是協(xié)同過濾的核心思想。協(xié)同過濾一般是在海量的用戶中發(fā)掘出一小部分和你品位比較類似的，在協(xié)同過濾中，這些用戶成為鄰居，然后根據(jù)他們喜歡的其他東西組織成一個排序的目錄作為推薦給你。當(dāng)然其中有一個核心的問題：①如何確定一個用戶是不是和你有相似的品位？②如何將鄰居們的喜好組織成一個排序的目錄？協(xié)同過濾相對于集體智慧而言，它從一定程度上保留了個體的特征，就是你的品位偏好，所以它更多可以作為個性化推薦的算法思想。可以想象，這種推薦策略在 Web 的長尾中是很重要的，將大眾流行的東西推薦給長尾中的人怎么可能得到好的效果，這也回到推薦系統(tǒng)的一個核心問題：了解你的用戶，然后才能給出更好的推薦(1)基于用戶的協(xié)同過濾 首先，要實(shí)現(xiàn)協(xié)同過濾，需要以下3個核心步驟：①收集用戶偏好:從用戶的行為和偏好中發(fā)現(xiàn)規(guī)律，并基于此給予推薦，如何收集用戶的偏好信息成為系統(tǒng)推薦效果最基礎(chǔ)的決定因素。用戶有很多方式向系統(tǒng)提供自己的偏好信息，而且不同的應(yīng)用也可能大不相同。收集了用戶行為數(shù)據(jù)，我們還需要對數(shù)據(jù)進(jìn)行一定的預(yù)處理，其中最核心的工作就是：減噪和歸一化[2]。減噪：用戶行為數(shù)據(jù)是用戶在使用應(yīng)用過程中產(chǎn)生的，它可能存在大量的噪音和用戶的誤操作，我們可以通過經(jīng)典的數(shù)據(jù)挖掘算法過濾掉行為數(shù)據(jù)中的噪音，這樣可以是我們的分析更加精確。歸一化：如前面講到的，在計(jì)算用戶對物品的喜好程度時，可能需要對不同的行為數(shù)據(jù)進(jìn)行加權(quán)。但可以想象，不同行為的數(shù)據(jù)取值可能相差很大，比如，用戶的查看數(shù)據(jù)必然比購買數(shù)據(jù)大的多，如何將各個行為的數(shù)據(jù)統(tǒng)一在一個相同的取值范圍中，從而使得加權(quán)求和得到的總體喜好更加精確，就需要我們進(jìn)行歸一化處理。最簡單的歸一化處理，就是將各類數(shù)據(jù)除以此類中的最大值，以保證歸一化后的數(shù)據(jù)取值在 [0,1] 范中。進(jìn)行的預(yù)處理后，根據(jù)不同應(yīng)用的行為分析方法，可以選擇分組或者加權(quán)處理，之后我們可以得到一個用戶偏好的二維矩陣，一維是用戶列表，另一維是物品列表，值是用戶對物品的偏好，一般是 [0,1] 或者 [1, 1] 的浮點(diǎn)數(shù)值。②找到相似的用戶(通過相似度找到相似用戶):相似度的計(jì)算關(guān)于相似度的計(jì)算，現(xiàn)有的幾種基本方法都是基于向量（Vector）的，其實(shí)也就是計(jì)算兩個向量的距離，距離越近相似度越大。在推薦的場景中，在用戶 物品偏好的二維矩陣中，我們可以將一個用戶對所有物品的偏好作為一個向量來計(jì)算用戶之間的相似度，或者將所有用戶對某個物品的偏好作為一個向量來計(jì)算物品之間的相似度。下面我們詳細(xì)介紹幾種常用的相似度計(jì)算方法：a歐幾里德距離（Euclidean Distance）[6]最初用于計(jì)算歐幾里德空間中兩個點(diǎn)的距離，假設(shè) x，y 是 n 維空間的兩個點(diǎn)，它們之間的歐幾里德距離是：可以看出，當(dāng) n=2 時，歐幾里德距離就是平面上兩個點(diǎn)的距離。當(dāng)用歐幾里德距離表示相似度，一般采用以下公式進(jìn)行轉(zhuǎn)換：距離越小，相似度越大。b皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient）皮爾遜相關(guān)系數(shù)一般用于計(jì)算兩個定距變量間聯(lián)系的緊密程度，它的取值在 [1，+1] 之間。sx, sy是 x 和 y 的樣品標(biāo)準(zhǔn)偏差。相似鄰居的計(jì)算介紹完相似度的計(jì)算方法，下面我們看看如何根據(jù)相似度找到用戶 物品的鄰居，常用的挑選鄰居的原則可以分為兩類：圖 給出了二維平面空間上點(diǎn)集的示意圖。固定數(shù)量的鄰居：Kneighborhoods 或者 Fixsize neighborhoods不論鄰居的“遠(yuǎn)近”，只取最近的K個，作為其鄰居。，假設(shè)要計(jì)算點(diǎn)1的5個鄰居，那么根據(jù)點(diǎn)之間的距離，我們?nèi)∽罱?個點(diǎn)，分別是點(diǎn)2，點(diǎn)3，點(diǎn)4，點(diǎn)7和點(diǎn)5。但很明顯我們可以看出，這種方法對于孤立點(diǎn)的計(jì)算效果不好，因?yàn)橐」潭▊€數(shù)的鄰居，當(dāng)它附近沒有足夠多比較相似的點(diǎn)，就被迫取一些不太相似的點(diǎn)作為鄰居，這樣就影響了鄰居相似的程度，比如圖1中，點(diǎn)1和點(diǎn)5其實(shí)并不是很相似?；谙嗨贫乳T檻的鄰居：Thresholdbased neighborhoods與計(jì)算固定數(shù)量的鄰居的原則不同，基于相似度門檻的鄰居計(jì)算是對鄰居的遠(yuǎn)近進(jìn)行最大值的限制，落在以當(dāng)前點(diǎn)為中心，距離為 K 的區(qū)域中的所有點(diǎn)都作為當(dāng)前點(diǎn)的鄰居，這種方法計(jì)算得到的鄰居個數(shù)不確定，但相似度不會出現(xiàn)較大的誤差。如圖 1 中的 B，從點(diǎn)1出發(fā)，計(jì)算相似度在 K內(nèi)的鄰居，得到點(diǎn)2，點(diǎn)3，點(diǎn)4和點(diǎn)7，這種方法計(jì)算出的鄰居的相似度程度比前一種優(yōu)，尤其是對孤立點(diǎn)的處理。固定聚類數(shù)的鄰居: Kmeans算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個對象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。對應(yīng)的元素同樣可以找到自己的鄰居，本系統(tǒng)采用EM聚類分析算法，以下對KMeans聚類分析與EM聚類分析比較：在聚類問題中，給我們的訓(xùn)練樣本是，每個，沒有了y。Kmeans算法是將樣本聚類成k個簇（cluster），具體算法描述如下： 隨機(jī)選取k個聚類質(zhì)心點(diǎn)（cluster centroids）為。 重復(fù)下面過程直到收斂 {對于每一個樣例i，計(jì)算其應(yīng)該屬于的類對于每一個類j，重新計(jì)算該類的質(zhì)心}如上圖所示，K是我們事先給定的聚類數(shù)，代表樣例i與k個類中距離最近的那個類，的值是1到k中的一個。質(zhì)心代表我們對屬于同一個類的樣本中心點(diǎn)的猜測，拿星團(tuán)模型來解釋就是要將所有的星星聚成k個星團(tuán)，首先隨機(jī)選取k個宇宙中的點(diǎn)（或者k個星星）作為k個星團(tuán)的質(zhì)心，然后第一步對于每一個星星計(jì)算其到k個質(zhì)心中每一個的距離，然后選取距離最近的那個星團(tuán)作為，這樣經(jīng)過第一步每一個星星都有了所屬的星團(tuán)；第二步對于每一個星團(tuán)，重新計(jì)算它的質(zhì)心（對里面所有的星星坐標(biāo)求平均）。重復(fù)迭代第一步和第二步直到質(zhì)心不變或者變化很小。Kmeans面對的第一個問題是如何保證收斂，前面的算法中強(qiáng)調(diào)結(jié)束條件就是收斂，可以證明的是Kmeans完全可以保證收斂性。下面我們定性的描述一下收斂性，我們定義畸變函數(shù)（distortion function）如下：J函數(shù)表示每個樣本點(diǎn)到其質(zhì)心的距離平方和。Kmeans是要將J調(diào)整到最小。假設(shè)當(dāng)前J沒有達(dá)到最小值，那么首先可以固定每個類的質(zhì)心，調(diào)整每個樣例的所屬的類別來讓J函數(shù)減少，同樣，固定，調(diào)整每個類的質(zhì)心也可以使J減小。這兩個過程就是內(nèi)循環(huán)中使J單調(diào)遞減的過程。當(dāng)J遞減到最小時，和c也同時收斂。（在理論上，可以有多組不同的和c值能夠使得J取得最小值，但這種現(xiàn)象實(shí)際上很少見）。由于畸變函數(shù)J是非凸函數(shù)，意味著我們不能保證取得的最小值是全局最小值，也就是說kmeans對質(zhì)心初始位置的選取比較感冒，但一般情況下kmeans達(dá)到的局部最優(yōu)已經(jīng)滿足需求。但如果你怕陷入局部最優(yōu)，那么可以選取不同的初始值跑多遍kmeans，然后取其中最小的J對應(yīng)的和c輸出。下面累述一下Kmeans與EM的關(guān)系，首先回到初始問題，我們目的是將樣本分成k個類，其實(shí)說白了就是求每個樣例x的隱含類別y，然后利用隱含類別將x歸類。由于我們事先不知道類別y，那么我們首先可以對每個樣例假定一個y吧，但是怎么知道假定的對不對呢？怎么評價(jià)假定的好不好呢？我們使用樣本的極大似然估計(jì)來度量，這里是就是x和y的聯(lián)合分布P(x,y)了。如果找到的y能夠使P(x,y)最大，那么我們找到的y就是樣例x的最佳類別了，x順手就聚類了。但是我們第一次指定的y不一定會讓P(x,y)最大，而