閔磊

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

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

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

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

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

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

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

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

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

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)領(lǐng)域一項(xiàng)十分重要的數(shù)據(jù)挖掘技術(shù)，它通過(guò)實(shí)體間的關(guān)聯(lián)關(guān)系將節(jié)點(diǎn)按照“物以類聚，人以群分”的機(jī)制進(jìn)行劃分，形成社區(qū)結(jié)構(gòu)。在社區(qū)發(fā)現(xiàn)中，實(shí)體被表示為網(wǎng)絡(luò)中的節(jié)點(diǎn)，實(shí)體之間的關(guān)聯(lián)關(guān)系被視為節(jié)點(diǎn)之間的連邊，以此構(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)簽傳播方法以其線性的時(shí)間復(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è)性化推薦時(shí)，首先需要構(gòu)建這樣的網(wǎng)絡(luò)。我們假定，當(dāng)用戶對(duì)物品進(jìn)行選擇、較高評(píng)分等操作時(shí)，表示他對(duì)物品具有一定偏好。如果用戶對(duì)m個(gè)物品具有偏好，則這m個(gè)物品之間的連邊權(quán)值加1（如果兩物品間之前無(wú)連邊，則建立權(quán)值為1的邊）。對(duì)于所有用戶，重復(fù)此過(guò)程，會(huì)得到所有物品所構(gòu)成的加權(quán)網(wǎng)絡(luò)。

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

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

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

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

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

輸出：對(duì)用戶u推薦的N個(gè)物品。

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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