高伊騰 張雅迪 唐寧 李云云 周?chē)?guó)棟

摘? ?要：個(gè)性化推薦算法中一直存在新用戶(hù)的冷啟動(dòng)問(wèn)題，文章通過(guò)引入ID3算法來(lái)預(yù)測(cè)、分析新用戶(hù)的類(lèi)別選擇。首先，根據(jù)實(shí)驗(yàn)數(shù)據(jù)特征對(duì)ID3算法加以改進(jìn);其次，根據(jù)分析數(shù)據(jù)表中各字段的屬性確定試驗(yàn)參數(shù);最后，得出實(shí)驗(yàn)結(jié)果。

關(guān)鍵詞：推薦算法;冷啟動(dòng);決策樹(shù);聚類(lèi)分析

推薦系統(tǒng)是一種向目標(biāo)用戶(hù)建議可能感興趣物品的軟件和技術(shù)，主要服務(wù)于缺乏經(jīng)驗(yàn)和能力的用戶(hù)，他們通常無(wú)法從大量可供選擇的物品中選取感興趣的物品，如無(wú)法從某網(wǎng)站中選取感興趣的商品。目前，電商的推薦大多是個(gè)性化的，即不同用戶(hù)或用戶(hù)組所接收的建議不同。當(dāng)然，也存在非個(gè)性化推薦，但大都非常簡(jiǎn)單，通常出現(xiàn)在報(bào)紙或雜志上。

推薦系統(tǒng)中遇到的問(wèn)題有很多，包括新用戶(hù)與新圖書(shū)的冷啟動(dòng)問(wèn)題，即如何向新用戶(hù)進(jìn)行個(gè)性化推薦。目前，針對(duì)冷啟動(dòng)問(wèn)題進(jìn)行研究的文章，大多基于電子商務(wù)協(xié)同過(guò)濾推薦中的用戶(hù)和項(xiàng)目屬性[1]、新用戶(hù)回答問(wèn)題[2]、特征匹配等方法。其中，趙盼盼[3]采用聚類(lèi)、關(guān)聯(lián)規(guī)則的新圖書(shū)推薦方法以解決新圖書(shū)的推薦問(wèn)題，呂紅霞等[4]采用劃分類(lèi)別的方式為新讀者進(jìn)行推薦。

為提高向新用戶(hù)個(gè)性化推薦圖書(shū)的質(zhì)量，本文就新用戶(hù)的冷啟動(dòng)問(wèn)題，提出一種基于用戶(hù)聚類(lèi)的圖書(shū)推薦算法的解決辦法，采用決策樹(shù)中的ID3算法作為數(shù)據(jù)分析工具。首先，根據(jù)實(shí)驗(yàn)數(shù)據(jù)特征需要，對(duì)ID3算法進(jìn)行改進(jìn);其次，通過(guò)實(shí)驗(yàn)分析確定COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等參數(shù)。最后，使用決策樹(shù)得出實(shí)驗(yàn)結(jié)果。

1? ? 基于用戶(hù)聚類(lèi)的圖書(shū)推薦算法

1.1? 簡(jiǎn)要介紹

基于用戶(hù)聚類(lèi)的圖書(shū)推薦算法主要用于解決圖書(shū)推薦系統(tǒng)方面的冷啟動(dòng)問(wèn)題。本文使用ID3算法來(lái)解決系統(tǒng)冷啟動(dòng)問(wèn)題，通過(guò)實(shí)驗(yàn)分析，需要確定COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等參數(shù)，以達(dá)到最佳聚類(lèi)的效果。

本文通過(guò)確定描述屬性、類(lèi)別屬性、實(shí)驗(yàn)指標(biāo)等得出預(yù)測(cè)分析表，預(yù)測(cè)新用戶(hù)的喜好，進(jìn)行個(gè)性化推薦。“實(shí)驗(yàn)分析用戶(hù)”可以定義為：依據(jù)新用戶(hù)的描述屬性經(jīng)過(guò)一輪決策樹(shù)預(yù)測(cè)，向該用戶(hù)進(jìn)行圖書(shū)推薦，收藏推薦圖書(shū)的用戶(hù)即為實(shí)驗(yàn)分析用戶(hù)?；谟脩?hù)聚類(lèi)的圖書(shū)推薦算法，既完成了新用戶(hù)到實(shí)驗(yàn)分析用戶(hù)的轉(zhuǎn)變，提升用戶(hù)體驗(yàn)，又新增加了實(shí)驗(yàn)分析用戶(hù)，更有利于后續(xù)對(duì)新老用戶(hù)進(jìn)行準(zhǔn)確的聚類(lèi)分析。

1.2? ID3算法

1.2.1? ID3算法的定義及構(gòu)造方法

ID3算法在構(gòu)造決策樹(shù)時(shí)，對(duì)于數(shù)據(jù)集S，根據(jù)其中信息增益最大的屬性Ai劃分成若干個(gè)子區(qū)域，其中，某個(gè)子區(qū)域停止劃分樣本的方式是：如果Sj中所有樣本的類(lèi)別相同（假設(shè)為aij），則停止劃分樣本（以aij類(lèi)別作為葉子結(jié)點(diǎn)）。如果沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分?jǐn)?shù)據(jù)集，則使用多數(shù)表決，取Sj中多數(shù)樣本的類(lèi)別作為葉子結(jié)點(diǎn)的類(lèi)別。如果Sj為空，以S中的多數(shù)類(lèi)別作為葉子結(jié)點(diǎn)的類(lèi)別。

1.2.2? 信息增益

假設(shè)訓(xùn)練數(shù)據(jù)集是關(guān)系數(shù)據(jù)表S，共有n個(gè)元組和m+1個(gè)屬性，其中，描述屬性有A1，A2，…，Am。類(lèi)別屬性C的類(lèi)別數(shù)為u，其值域?yàn)椋╟1，c2…，cu），類(lèi)別屬性C取值為ci（1≤i≤u）的元組個(gè)數(shù)為si。對(duì)于描述屬性Ak（1≤k≤m），它的不同取值個(gè)數(shù)為v，其值域?yàn)椋╝1，a2，...av）。在類(lèi)別屬性C取值為ci（1≤i≤u）的子區(qū)域中，描述屬性Ak取aj（1≤j≤v）的元組個(gè)數(shù)為sij。

定義1：類(lèi)別屬性C的無(wú)條件熵E（C）定義為：

其中，p（ci）為C=ci（1≤i≤u）的概率。E（C）反映了屬性C取值的不確定性，當(dāng)所有p（ci）相同時(shí)，E（C）最大，呈現(xiàn)最大的不確定性;當(dāng)有一個(gè)p（ci）=1時(shí)，C（X）最小即為0，呈現(xiàn)最小的不確定性。

定義2：對(duì)于描述屬性Ak（1≤j≤m），類(lèi)別屬性C的條件熵E（C，Ak）定義為：

條件熵E（C，Ak）表示在已知描述屬性Ak的情況下，類(lèi)別屬性C對(duì)訓(xùn)練數(shù)據(jù)集S的分類(lèi)能力。

定義3：給定描述屬性Ak（1≤k≤m），對(duì)應(yīng)類(lèi)別屬性C的信息增益定義為：

G（C，Ak）表示在已知描述屬性Ak的情況下，類(lèi)別屬性C對(duì)訓(xùn)練數(shù)據(jù)集S分類(lèi)能力增加的程度。

1.2.3? 算法執(zhí)行步驟

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

輸入：訓(xùn)練數(shù)據(jù)集S，描述屬性A和類(lèi)別屬性C。

輸出：決策樹(shù)（以Node為根節(jié)點(diǎn)）。

step1：如果S中的樣本屬于同一類(lèi)別c，則以c標(biāo)識(shí)Node并將它作為葉子結(jié)點(diǎn)。

step2：如果A為空，則以S中占多數(shù)的樣本類(lèi)別c標(biāo)識(shí)Node并將它作為葉子結(jié)點(diǎn)。

step3：for（屬性集合A中每個(gè)屬性Ak）計(jì)算G（C，Ak）=E（C）-E（C，Ak）。

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

step4：for（Ai的每個(gè)可能取值aij） 產(chǎn)生S的一個(gè)子集Sij。

step5：if（Sj為空） 創(chuàng)建對(duì)應(yīng)的sj的結(jié)點(diǎn)Nodej; 以S中占多數(shù)的樣本類(lèi)別c標(biāo)識(shí)Nodej。

將Nodej作為葉子結(jié)點(diǎn)形成Node的一個(gè)分支。

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

1.3? 獲取推薦結(jié)果

經(jīng)過(guò)在Microsoft Visual Studio 2008中導(dǎo)入數(shù)據(jù)表S和預(yù)測(cè)分析表S1，定義數(shù)據(jù)源視圖，建立挖掘結(jié)構(gòu)，設(shè)置COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等參數(shù)，部署一系列步驟。最終在挖掘模型查看器得出一張預(yù)測(cè)分析表，表中描述了類(lèi)別屬性與描述屬性之間的關(guān)系。

2? ? 數(shù)據(jù)測(cè)試及結(jié)果分析

2.1? 實(shí)驗(yàn)環(huán)境配置

本文使用SQL Server 2008作為數(shù)據(jù)源，使用Microsoft Visual Studio 2008作為決策樹(shù)分析工具，在JetBrains PyCharm 5.0.3+Microsoft Excel 2010編程環(huán)境中實(shí)現(xiàn)了ID3算法，用于得到?jīng)Q策樹(shù)模型。

2.2? 獲取數(shù)據(jù)源

實(shí)驗(yàn)開(kāi)始前，通過(guò)采用數(shù)據(jù)仿真模擬的方法獲得所需要的數(shù)據(jù)，創(chuàng)建一個(gè)Users表，包含編號(hào)、姓名、性別、年級(jí)、學(xué)院、專(zhuān)業(yè)、書(shū)名、書(shū)類(lèi)等8個(gè)字段。表中數(shù)據(jù)來(lái)源通過(guò)以下兩種途徑進(jìn)行獲取。

從咸陽(yáng)師范學(xué)院圖書(shū)館獲取計(jì)算機(jī)學(xué)院、資歷學(xué)院、建筑學(xué)院、經(jīng)管學(xué)院4個(gè)學(xué)院的2015級(jí)、2016級(jí)學(xué)生及教師（為了能夠顯著分析實(shí)驗(yàn)結(jié)果，在表中定義教師為2000級(jí)）的姓名、性別、年級(jí)、學(xué)院、專(zhuān)業(yè)。根據(jù)實(shí)驗(yàn)設(shè)備條件，在實(shí)驗(yàn)分析階段，將所到的數(shù)據(jù)同比例縮小。

上述學(xué)院包含的專(zhuān)業(yè)有：計(jì)算機(jī)學(xué)院（所屬專(zhuān)業(yè)有：計(jì)科、軟件、物聯(lián)），資歷學(xué)院（所屬專(zhuān)業(yè)有：地理科學(xué)、歷史學(xué)），建筑學(xué)院（所屬專(zhuān)業(yè)有：建筑學(xué)、城鄉(xiāng)規(guī)劃、城市規(guī)劃），經(jīng)管學(xué)院（所屬專(zhuān)業(yè)有：經(jīng)濟(jì)學(xué)、財(cái)務(wù)管理、經(jīng)管學(xué)）。

書(shū)籍名稱(chēng)以及書(shū)籍類(lèi)別以正當(dāng)途徑通過(guò)當(dāng)當(dāng)網(wǎng)來(lái)爬取。

2.3? 實(shí)驗(yàn)參數(shù)設(shè)置指標(biāo)及參數(shù)的選取

根據(jù)Microsoft決策樹(shù)算法技術(shù)參考，在使用ID3算法進(jìn)行決策樹(shù)分析時(shí)，需要設(shè)置以下3個(gè)主要算法參數(shù)。

2.3.1? COMPLEXITY_PENALTY

COMPLEXITY_PENALTY控制決策樹(shù)的增長(zhǎng)。該值較低時(shí)，會(huì)增加拆分?jǐn)?shù);該值較高時(shí)，會(huì)減少拆分?jǐn)?shù)。默認(rèn)值基于特定模型的屬性數(shù)，參照3個(gè)范圍設(shè)置參數(shù)：（1）對(duì)于1～9個(gè)屬性，默認(rèn)值為0.5。（2）對(duì)于10～99個(gè)屬性，默認(rèn)值為0.9。（3）對(duì)于100或更多個(gè)屬性，默認(rèn)值為0.99。本文實(shí)驗(yàn)數(shù)據(jù)集有4個(gè)屬性，因此，根據(jù)上述規(guī)則，本文的ID3算法COMPLEXITY_PENALTY設(shè)置為0.5。

2.3.2? MINIMUM_SUPPORT

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

2.3.3? SCORE_METHOD

SCORE_METHOD確定用于計(jì)算拆分分?jǐn)?shù)的方法?？捎眠x項(xiàng)包括：（1）Entropy。（2）Bayesian with K2 Prior。（3）Bayesian Dirichlet Equivalent（BDE） with uniform prior（默認(rèn)值），其中，Entropy為信息熵。本文采用信息熵作為屬性選擇的啟發(fā)信息，因此，將SCORE_METHOD設(shè)置為1。

2.3.4? SPLIT_METHOD

SPLIT_METHOD確定用于拆分節(jié)點(diǎn)的方法?？捎眠x項(xiàng)包括：（1）Binary：指無(wú)論屬性值的實(shí)際數(shù)量是多少，樹(shù)都拆分為兩個(gè)分支。（2）Complete：指示樹(shù)可以創(chuàng)建與屬性值數(shù)目相同的分叉。（3）Both：指定Analysis Services可確定應(yīng)使用binary還是complete，以獲得最佳結(jié)果（默認(rèn)值）。本文將SPLIT_METHOD設(shè)置為2。

2.4? 實(shí)驗(yàn)結(jié)果

本文選取部分挖掘模型預(yù)測(cè)分析表，如圖1所示，由于篇幅限制，這里只對(duì)部分實(shí)驗(yàn)結(jié)果進(jìn)行展示，對(duì)滿(mǎn)足專(zhuān)業(yè)屬性對(duì)應(yīng)的各類(lèi)別屬性進(jìn)行統(tǒng)計(jì)整理。實(shí)驗(yàn)發(fā)現(xiàn)：70%的類(lèi)別屬性與所屬院系教學(xué)內(nèi)容高相關(guān)。30%的類(lèi)別屬性與所屬院系低相關(guān)。

在JetBrains PyCharm 5.0.3+Microsoft Excel 2010編程環(huán)境下編寫(xiě)的ID3算法構(gòu)造出來(lái)的決策樹(shù)如圖2所示，其分類(lèi)的效果達(dá)到預(yù)期目的?？梢钥闯?，3個(gè)描述屬性很好地對(duì)類(lèi)別屬性進(jìn)行樣本空間的劃分。

3? ? 結(jié)語(yǔ)

本文針對(duì)新用戶(hù)冷啟動(dòng)問(wèn)題，綜合考慮性別、年級(jí)、專(zhuān)業(yè)等主要描述屬性，依據(jù)ID3算法提出一種基于用戶(hù)聚類(lèi)的圖書(shū)推薦算法。實(shí)驗(yàn)結(jié)果表明，本算法能夠充分解決新用戶(hù)的圖書(shū)推薦問(wèn)題。

[參考文獻(xiàn)]

[1]李轉(zhuǎn)運(yùn)，孫翠敏.基于項(xiàng)目屬性權(quán)重的協(xié)同過(guò)濾推薦算法[J].新鄉(xiāng)學(xué)院學(xué)報(bào)，2019（3）：30-33.

[2]鄧明通，劉學(xué)軍，李斌.基于用戶(hù)偏好和動(dòng)態(tài)興趣的多樣性推薦方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2018（9）：2029-2034.

[3]趙盼盼.基于云填充和蟻群聚類(lèi)的協(xié)同過(guò)濾技術(shù)在圖書(shū)推薦中的應(yīng)用研究[D].阜新：遼寧工程技術(shù)大學(xué)，2016.

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