基于用戶聚類的圖書推薦算法設計與實現

高伊騰 張雅迪 唐寧 李云云 周國棟

摘? ?要：個性化推薦算法中一直存在新用戶的冷啟動問題，文章通過引入ID3算法來預測、分析新用戶的類別選擇。首先，根據實驗數據特征對ID3算法加以改進;其次，根據分析數據表中各字段的屬性確定試驗參數;最后，得出實驗結果。

關鍵詞：推薦算法;冷啟動;決策樹;聚類分析

推薦系統是一種向目標用戶建議可能感興趣物品的軟件和技術，主要服務于缺乏經驗和能力的用戶，他們通常無法從大量可供選擇的物品中選取感興趣的物品，如無法從某網站中選取感興趣的商品。目前，電商的推薦大多是個性化的，即不同用戶或用戶組所接收的建議不同。當然，也存在非個性化推薦，但大都非常簡單，通常出現在報紙或雜志上。

推薦系統中遇到的問題有很多，包括新用戶與新圖書的冷啟動問題，即如何向新用戶進行個性化推薦。目前，針對冷啟動問題進行研究的文章，大多基于電子商務協同過濾推薦中的用戶和項目屬性[1]、新用戶回答問題[2]、特征匹配等方法。其中，趙盼盼[3]采用聚類、關聯規則的新圖書推薦方法以解決新圖書的推薦問題，呂紅霞等[4]采用劃分類別的方式為新讀者進行推薦。

為提高向新用戶個性化推薦圖書的質量，本文就新用戶的冷啟動問題，提出一種基于用戶聚類的圖書推薦算法的解決辦法，采用決策樹中的ID3算法作為數據分析工具。首先，根據實驗數據特征需要，對ID3算法進行改進;其次，通過實驗分析確定COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等參數。最后，使用決策樹得出實驗結果。

1? ? 基于用戶聚類的圖書推薦算法

1.1? 簡要介紹

基于用戶聚類的圖書推薦算法主要用于解決圖書推薦系統方面的冷啟動問題。本文使用ID3算法來解決系統冷啟動問題，通過實驗分析，需要確定COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等參數，以達到最佳聚類的效果。

本文通過確定描述屬性、類別屬性、實驗指標等得出預測分析表，預測新用戶的喜好，進行個性化推薦?！皩嶒灧治鲇脩簟笨梢远x為：依據新用戶的描述屬性經過一輪決策樹預測，向該用戶進行圖書推薦，收藏推薦圖書的用戶即為實驗分析用戶。基于用戶聚類的圖書推薦算法，既完成了新用戶到實驗分析用戶的轉變，提升用戶體驗，又新增加了實驗分析用戶，更有利于后續對新老用戶進行準確的聚類分析。

1.2? ID3算法

1.2.1? ID3算法的定義及構造方法

ID3算法在構造決策樹時，對于數據集S，根據其中信息增益最大的屬性Ai劃分成若干個子區域，其中，某個子區域停止劃分樣本的方式是：如果Sj中所有樣本的類別相同（假設為aij），則停止劃分樣本（以aij類別作為葉子結點）。如果沒有剩余屬性可以用來進一步劃分數據集，則使用多數表決，取Sj中多數樣本的類別作為葉子結點的類別。如果Sj為空，以S中的多數類別作為葉子結點的類別。

1.2.2? 信息增益

假設訓練數據集是關系數據表S，共有n個元組和m+1個屬性，其中，描述屬性有A1，A2，…，Am。類別屬性C的類別數為u，其值域為（c1，c2…，cu），類別屬性C取值為ci（1≤i≤u）的元組個數為si。對于描述屬性Ak（1≤k≤m），它的不同取值個數為v，其值域為（a1，a2，...av）。在類別屬性C取值為ci（1≤i≤u）的子區域中，描述屬性Ak取aj（1≤j≤v）的元組個數為sij。

定義1：類別屬性C的無條件熵E（C）定義為：

其中，p（ci）為C=ci（1≤i≤u）的概率。E（C）反映了屬性C取值的不確定性，當所有p（ci）相同時，E（C）最大，呈現最大的不確定性;當有一個p（ci）=1時，C（X）最小即為0，呈現最小的不確定性。

定義2：對于描述屬性Ak（1≤j≤m），類別屬性C的條件熵E（C，Ak）定義為：

條件熵E（C，Ak）表示在已知描述屬性Ak的情況下，類別屬性C對訓練數據集S的分類能力。

定義3：給定描述屬性Ak（1≤k≤m），對應類別屬性C的信息增益定義為：

G（C，Ak）表示在已知描述屬性Ak的情況下，類別屬性C對訓練數據集S分類能力增加的程度。

1.2.3? 算法執行步驟

建立決策樹的ID3算法Gennerate_decision_tree（S，A）如下：

輸入：訓練數據集S，描述屬性A和類別屬性C。

輸出：決策樹（以Node為根節點）。

step1：如果S中的樣本屬于同一類別c，則以c標識Node并將它作為葉子結點。

step2：如果A為空，則以S中占多數的樣本類別c標識Node并將它作為葉子結點。

step3：for（屬性集合A中每個屬性Ak）計算G（C，Ak）=E（C）-E（C，Ak）。

Ai=MAX{G（C，Ak）}，Ai的Node數大于等于MINIMUM_SUPPORT則繼續拆分。

step4：for（Ai的每個可能取值aij） 產生S的一個子集Sij。

step5：if（Sj為空） 創建對應的sj的結點Nodej; 以S中占多數的樣本類別c標識Nodej。

將Nodej作為葉子結點形成Node的一個分支。

step6：else Gennerate_decision_tree（Sj，A-{Aj}）。

1.3? 獲取推薦結果

經過在Microsoft Visual Studio 2008中導入數據表S和預測分析表S1，定義數據源視圖，建立挖掘結構，設置COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等參數，部署一系列步驟。最終在挖掘模型查看器得出一張預測分析表，表中描述了類別屬性與描述屬性之間的關系。

2? ? 數據測試及結果分析

2.1? 實驗環境配置

本文使用SQL Server 2008作為數據源，使用Microsoft Visual Studio 2008作為決策樹分析工具，在JetBrains PyCharm 5.0.3+Microsoft Excel 2010編程環境中實現了ID3算法，用于得到決策樹模型。

2.2? 獲取數據源

實驗開始前，通過采用數據仿真模擬的方法獲得所需要的數據，創建一個Users表，包含編號、姓名、性別、年級、學院、專業、書名、書類等8個字段。表中數據來源通過以下兩種途徑進行獲取。

從咸陽師范學院圖書館獲取計算機學院、資歷學院、建筑學院、經管學院4個學院的2015級、2016級學生及教師（為了能夠顯著分析實驗結果，在表中定義教師為2000級）的姓名、性別、年級、學院、專業。根據實驗設備條件，在實驗分析階段，將所到的數據同比例縮小。

上述學院包含的專業有：計算機學院（所屬專業有：計科、軟件、物聯），資歷學院（所屬專業有：地理科學、歷史學），建筑學院（所屬專業有：建筑學、城鄉規劃、城市規劃），經管學院（所屬專業有：經濟學、財務管理、經管學）。

書籍名稱以及書籍類別以正當途徑通過當當網來爬取。

2.3? 實驗參數設置指標及參數的選取

根據Microsoft決策樹算法技術參考，在使用ID3算法進行決策樹分析時，需要設置以下3個主要算法參數。

2.3.1? COMPLEXITY_PENALTY

COMPLEXITY_PENALTY控制決策樹的增長。該值較低時，會增加拆分數;該值較高時，會減少拆分數。默認值基于特定模型的屬性數，參照3個范圍設置參數：（1）對于1～9個屬性，默認值為0.5。（2）對于10～99個屬性，默認值為0.9。（3）對于100或更多個屬性，默認值為0.99。本文實驗數據集有4個屬性，因此，根據上述規則，本文的ID3算法COMPLEXITY_PENALTY設置為0.5。

2.3.2? MINIMUM_SUPPORT

MINIMUM_SUPPORT確定在決策樹中生成拆分所需的葉實例的最少數量。一般而言，MINIMUM_SUPPORT的值是描述屬性的個數。因此，將MINIMUM_SUPPORT設置為3。

2.3.3? SCORE_METHOD

SCORE_METHOD確定用于計算拆分分數的方法?？捎眠x項包括：（1）Entropy。（2）Bayesian with K2 Prior。（3）Bayesian Dirichlet Equivalent（BDE） with uniform prior（默認值），其中，Entropy為信息熵。本文采用信息熵作為屬性選擇的啟發信息，因此，將SCORE_METHOD設置為1。

2.3.4? SPLIT_METHOD

SPLIT_METHOD確定用于拆分節點的方法。可用選項包括：（1）Binary：指無論屬性值的實際數量是多少，樹都拆分為兩個分支。（2）Complete：指示樹可以創建與屬性值數目相同的分叉。（3）Both：指定Analysis Services可確定應使用binary還是complete，以獲得最佳結果（默認值）。本文將SPLIT_METHOD設置為2。

2.4? 實驗結果

本文選取部分挖掘模型預測分析表，如圖1所示，由于篇幅限制，這里只對部分實驗結果進行展示，對滿足專業屬性對應的各類別屬性進行統計整理。實驗發現：70%的類別屬性與所屬院系教學內容高相關。30%的類別屬性與所屬院系低相關。

在JetBrains PyCharm 5.0.3+Microsoft Excel 2010編程環境下編寫的ID3算法構造出來的決策樹如圖2所示，其分類的效果達到預期目的?？梢钥闯觯?個描述屬性很好地對類別屬性進行樣本空間的劃分。

3? ? 結語

本文針對新用戶冷啟動問題，綜合考慮性別、年級、專業等主要描述屬性，依據ID3算法提出一種基于用戶聚類的圖書推薦算法。實驗結果表明，本算法能夠充分解決新用戶的圖書推薦問題。

[參考文獻]

[1]李轉運，孫翠敏.基于項目屬性權重的協同過濾推薦算法[J].新鄉學院學報，2019（3）：30-33.

[2]鄧明通，劉學軍，李斌.基于用戶偏好和動態興趣的多樣性推薦方法[J].小型微型計算機系統，2018（9）：2029-2034.

[3]趙盼盼.基于云填充和蟻群聚類的協同過濾技術在圖書推薦中的應用研究[D].阜新：遼寧工程技術大學，2016.

[4]呂紅霞，王文憲，蒲松，等.基于聚類分析的鐵路出行旅客類別劃分[J].交通運輸系統工程與信息，2016（1）：129-134.