基于社區(qū)發(fā)現(xiàn)的個性化推薦技術(shù)研究

閔磊

摘? 要：隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)上各平臺的數(shù)據(jù)規(guī)模日益增大，由此產(chǎn)生了信息過載問題，個性化推薦技術(shù)是解決該問題的一種有效手段。該文利用社區(qū)發(fā)現(xiàn)技術(shù)“物以類聚、人以群分”的特點，將可能使人們產(chǎn)生相似興趣的物品進(jìn)行聚類，并在此基礎(chǔ)上研究了基于社區(qū)結(jié)構(gòu)的個性化推薦算法。該算法可對推薦物品的新穎性進(jìn)行調(diào)節(jié)，并可以緩解冷啟動問題。

關(guān)鍵詞：社區(qū)結(jié)構(gòu)? 社區(qū)發(fā)現(xiàn)? 個性化推薦? 聚類算法

中圖分類號：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A文章編號：1672-3791（2020）10（c）-0217-03

Abstract： With the development of the Internet， the data scale of platforms on the network is increasing， which leads to the problem of information overload. In this paper， we take advantage of the aggregation for similar objects in community， in which clustering items may arouse similar interests of people， and propose a personalized recommendation algorithm based on community structure. The algorithm is effective for regulating novelty and relieving cold-start problem of recommendation.

Key Words： Community structure; Community detection; Personalized recommendation; Clustering algorithm

在互聯(lián)網(wǎng)高速發(fā)展的背景下，眾多行業(yè)迎來了前所未有的發(fā)展機(jī)遇，“互聯(lián)網(wǎng)+X”正逐漸成為促進(jìn)社會經(jīng)濟(jì)前進(jìn)的重要因素。網(wǎng)絡(luò)在為各行業(yè)帶來契機(jī)的同時，其不斷增長的數(shù)據(jù)規(guī)模也迫使人們不得不面對一些急需解決的問題。例如，對于線上電子商城中數(shù)以萬計的商品，如何推送給真正需要它的顧客;在線教育環(huán)境下，學(xué)習(xí)者怎樣在海量資料中準(zhǔn)確找到對自己確實有幫助的學(xué)習(xí)資源;浩如煙海的新聞資訊應(yīng)用中，用戶如何高效定位自己感興趣的報道等。

對于這些由于龐大的數(shù)據(jù)規(guī)模所帶來的信息爆炸問題，如果能夠采用智能的方式進(jìn)行自動推薦，那么可以在很大程度上將用戶從信息過載的迷茫中解放出來。這種對用戶進(jìn)行的智能推薦，被稱為個性化推薦技術(shù)[1]。目前，個性化推薦技術(shù)在很多方面已取得成功，例如，亞馬遜網(wǎng)上商城通過該技術(shù)明顯提升了銷售量，大規(guī)模在線教育平臺上對個性化推薦技術(shù)的應(yīng)用也極大地促進(jìn)了個性化學(xué)習(xí)模式的發(fā)展等。

1? 個性化推薦技術(shù)分析

按照實現(xiàn)的基本原理，個性化推薦技術(shù)一般分為基于內(nèi)容的推薦、基于協(xié)同過濾的推薦以及基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦[2]等。基于內(nèi)容的推薦技術(shù)，對物品或者用戶的屬性特征進(jìn)行分析，依據(jù)屬性的相似性進(jìn)行推薦，由于該方法對屬性數(shù)據(jù)的要求較高，因此在屬性數(shù)據(jù)不易獲取的場景下其應(yīng)用受到一定限制。基于協(xié)同過濾的推薦是目前使用較為廣泛的一種技術(shù)，它通過物品或者用戶彼此之間的協(xié)同信息挖掘?qū)⒂杏猛扑]項過濾過來，該方法準(zhǔn)確度較高，但對剛進(jìn)入系統(tǒng)的實體存在冷啟動問題。基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦，是近年來發(fā)展較為迅速的一類方法，它通過網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)體現(xiàn)實體之間的關(guān)聯(lián)關(guān)系，其直觀性和有效性使其具有較大的發(fā)展?jié)摿Α?/p>

該文基于網(wǎng)絡(luò)結(jié)構(gòu)，分析了一種利用社區(qū)發(fā)現(xiàn)進(jìn)行個性化推薦的方法。該方法充分利用了社區(qū)發(fā)現(xiàn)算法中“物以類聚，人以群分”的特點，將被用戶同時感興趣的物品進(jìn)行聚類，以直觀可解釋的方式向用戶推薦感興趣的物品。由于聚類物品本身蘊(yùn)含著較強(qiáng)的共現(xiàn)關(guān)系，因此對于剛進(jìn)入系統(tǒng)的用戶，也可通過較少的歷史興趣數(shù)據(jù)進(jìn)行推薦，在一定程度上可以緩解個性化推薦算法的冷啟動問題。

2? 基于社區(qū)結(jié)構(gòu)的個性化推薦算法

2.1 社區(qū)發(fā)現(xiàn)技術(shù)

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)領(lǐng)域一項十分重要的數(shù)據(jù)挖掘技術(shù)，它通過實體間的關(guān)聯(lián)關(guān)系將節(jié)點按照“物以類聚，人以群分”的機(jī)制進(jìn)行劃分，形成社區(qū)結(jié)構(gòu)。在社區(qū)發(fā)現(xiàn)中，實體被表示為網(wǎng)絡(luò)中的節(jié)點，實體之間的關(guān)聯(lián)關(guān)系被視為節(jié)點之間的連邊，以此構(gòu)建蘊(yùn)含復(fù)雜邏輯的網(wǎng)絡(luò)結(jié)構(gòu)。

目前社區(qū)發(fā)現(xiàn)技術(shù)較為成熟，包括GN算法、譜分析方法、基于模塊度的優(yōu)化方法、標(biāo)簽傳播方法[3-4]等。其中標(biāo)簽傳播方法以其線性的時間復(fù)雜度，使其成為一種較為高效的算法。考慮到互聯(lián)網(wǎng)數(shù)據(jù)的規(guī)模性，該文推薦采用標(biāo)簽傳播算法進(jìn)行社區(qū)發(fā)現(xiàn)。

2.2 網(wǎng)絡(luò)結(jié)構(gòu)的構(gòu)建

具備蘊(yùn)含關(guān)聯(lián)關(guān)系的網(wǎng)絡(luò)結(jié)構(gòu)，是進(jìn)行社區(qū)發(fā)現(xiàn)的數(shù)據(jù)基礎(chǔ)。因此，在利用社區(qū)結(jié)構(gòu)進(jìn)行個性化推薦時，首先需要構(gòu)建這樣的網(wǎng)絡(luò)。我們假定，當(dāng)用戶對物品進(jìn)行選擇、較高評分等操作時，表示他對物品具有一定偏好。如果用戶對m個物品具有偏好，則這m個物品之間的連邊權(quán)值加1（如果兩物品間之前無連邊，則建立權(quán)值為1的邊）。對于所有用戶，重復(fù)此過程，會得到所有物品所構(gòu)成的加權(quán)網(wǎng)絡(luò)。

在這樣的加權(quán)網(wǎng)絡(luò)中，節(jié)點表示物品，兩節(jié)點間如果存在連邊則表示它們被相同用戶感興趣。節(jié)點之間連邊權(quán)值越大，說明他們被用戶同時感興趣的概率越大。按照社區(qū)發(fā)現(xiàn)的基本特征，同一社區(qū)中節(jié)點之間的連邊較為稠密，不同社區(qū)節(jié)點之間連邊較為稀疏。因此，依據(jù)這種性質(zhì)的網(wǎng)絡(luò)進(jìn)行社區(qū)挖掘，那么同一社區(qū)中的節(jié)點（物品）被用戶同時具備偏好的可能性相對較大。

2.3 利用社區(qū)結(jié)構(gòu)進(jìn)行個性化推薦

對于蘊(yùn)含節(jié)點（物品）共現(xiàn)關(guān)系的網(wǎng)絡(luò)，我們采用加權(quán)社區(qū)發(fā)現(xiàn)算法進(jìn)行社區(qū)結(jié)構(gòu)的挖掘。這里對標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法進(jìn)行改進(jìn)，使之能應(yīng)用于加權(quán)網(wǎng)絡(luò)。首先，對網(wǎng)絡(luò)中的各節(jié)點賦予不同的標(biāo)簽。然后，按照隨機(jī)序列對網(wǎng)絡(luò)中的各節(jié)點進(jìn)行異步標(biāo)簽更新。更新標(biāo)簽時，對鄰居節(jié)點中各標(biāo)簽按照一定概率進(jìn)行選擇，該概率值為相同標(biāo)簽對應(yīng)權(quán)值之和與當(dāng)前節(jié)點所有鄰居節(jié)點對應(yīng)權(quán)值之和的比值。最后，在標(biāo)簽更新過程達(dá)到穩(wěn)態(tài)或者更新震蕩幅度小于一定閾值時，更新過程結(jié)束。此時，不同標(biāo)簽所對應(yīng)的區(qū)域即為社區(qū)劃分的結(jié)果。

完成了網(wǎng)絡(luò)構(gòu)建和社區(qū)發(fā)現(xiàn)之后，我們會得到兩類數(shù)據(jù)。一是能體現(xiàn)節(jié)點（物品）共現(xiàn)關(guān)系的加權(quán)網(wǎng)絡(luò);二是能體現(xiàn)物品共現(xiàn)密集性的社區(qū)結(jié)構(gòu)。基于社區(qū)結(jié)構(gòu)的個性化推薦過程，即是依據(jù)這兩類數(shù)據(jù)進(jìn)行。推薦算法描述如下。

輸入：加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)、社區(qū)發(fā)現(xiàn)結(jié)果、用戶u及其所偏好的物品（節(jié)點）集合{Vi}、需要對用戶u推薦的物品個數(shù)N。

輸出：對用戶u推薦的N個物品。

步驟1：根據(jù)實際情況設(shè)置合適的參數(shù)α。α表示推薦時偏向于選擇同一社區(qū)的程度，取值范圍可設(shè)定為[1]，值越大表示越偏向于選擇同一社區(qū)的物品進(jìn)行推薦，當(dāng)值為0.5時，表示不考慮社區(qū)的影響。

步驟2：對于網(wǎng)絡(luò)中除節(jié)點集合{Vi}之外的所有節(jié)點Vj，按照公式1計算用戶對它的偏好值大小βj。

步驟3：對于集合{Vj}中的所有節(jié)點，按照βj值進(jìn)行倒序排序，取前N個作為推薦輸出。

為了考慮社區(qū)結(jié)構(gòu)對推薦結(jié)果的影響，算法對當(dāng)前計算的節(jié)點與用戶已偏好的節(jié)點在同一社區(qū)時的權(quán)值貢獻(xiàn)進(jìn)行了系數(shù)處理。該系數(shù)α用于衡量社區(qū)結(jié)構(gòu)對于推薦力度的影響程度，值越大越偏向于推薦同一社區(qū)的物品。設(shè)定該系數(shù)的目的在于，根據(jù)實際需求可以選擇對社區(qū)結(jié)構(gòu)的作用進(jìn)行強(qiáng)化，或者為了提高推薦的新穎性而降低社區(qū)結(jié)構(gòu)對推薦結(jié)果的正向作用。因此，該算法可對推薦的新穎性進(jìn)行可控調(diào)節(jié)。

此外，對于較為缺乏偏好數(shù)據(jù)的用戶，該算法也可以進(jìn)行有效推薦。在僅知道用戶較少偏好物品的情況下，由于已經(jīng)計算出社區(qū)結(jié)構(gòu)，因此對于處于同一社區(qū)中的物品自然存在較高的推薦概率，可以按照該算法進(jìn)行推薦。對于這類用戶進(jìn)行的有效推薦，實際上緩解了歷史數(shù)據(jù)欠缺情況下的冷啟動問題。

2.4 算法時間復(fù)雜度分析

該算法的計算工作主要集中在網(wǎng)絡(luò)結(jié)構(gòu)的建立、社區(qū)發(fā)現(xiàn)以及推薦程度的計算和排序上。對于網(wǎng)絡(luò)結(jié)構(gòu)的建立，如果有N個節(jié)點，每個用戶平均偏好M的物品，則網(wǎng)絡(luò)結(jié)構(gòu)建立的時間復(fù)雜度為O（MN）;對于社區(qū)發(fā)現(xiàn)過程，由于采用了近似線性的標(biāo)簽傳播算法，因此時間復(fù)雜度近似于O（N）;對推薦程度的計算和排序，時間主要用于排序上，排序算法時間可以達(dá)到O（Nlog（N））。因此，該算法總的時間復(fù)雜度近似為O（MN）+O（N）+O（Nlog（N）），即O（MN）+O（Nlog（N））。

3 結(jié)語

在互聯(lián)網(wǎng)時代，海量數(shù)據(jù)所帶來的信息過載問題，極大地影響了信息技術(shù)的應(yīng)用效率。而個性化推薦技術(shù)，是解決該問題的一種有效方式。該文利用社區(qū)發(fā)現(xiàn)技術(shù)“物以類聚、人以群分”的特點，將共現(xiàn)性較強(qiáng)的物品進(jìn)行聚類，并利用該聚類性質(zhì)進(jìn)行個性化的推薦。該算法除了可以提供有效的推薦外，還可對推薦的新穎性進(jìn)行調(diào)節(jié)，并可在一定程度上對冷啟動問題進(jìn)行緩解。

參考文獻(xiàn)

[1] 王紹卿，李鑫鑫，孫福振，等.個性化新聞推薦技術(shù)研究綜述[J].計算機(jī)科學(xué)與探索，2020，14（1）：18-29.

[2] 黃樂樂，馬慧芳，李寧，等.基于二分圖劃分聯(lián)合聚類的協(xié)同過濾推薦算法[J].計算機(jī)工程與科學(xué)，2019，41（11）：2040-2047.

[3] 張蕾，錢峰，趙姝，等.基于邊權(quán)的穩(wěn)定標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J].小型微型計算機(jī)系統(tǒng)，2019，40（2）：314-319.

[4] 鄭文萍，車晨浩，錢宇華，等.一種基于標(biāo)簽傳播的兩階段社區(qū)發(fā)現(xiàn)算法[J].計算機(jī)研究與發(fā)展，2018，55（9）：1959-1971.

[5] 檀亞寧，金澤明，陳輝.基于項目協(xié)同過濾的電視產(chǎn)品營銷推薦模型[J].科技資訊，2019，17（32）：214-215，217.

[6] 肖小月.淺談個性化推薦系統(tǒng)[J].科技創(chuàng)新導(dǎo)報，2018，15（2）：148，150.