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