發(fā)布時(shí)間：2014-12-26 12:24

 

【摘要】 我們生活在一個(gè)錯(cuò)綜復(fù)雜的世界中,大部分的數(shù)據(jù)對(duì)象例如個(gè)體、組織或機(jī)構(gòu)等都是互相關(guān)聯(lián)和交互的,由此而形成了一個(gè)巨大的、互聯(lián)的復(fù)雜網(wǎng)絡(luò)。不失一般性,這種網(wǎng)絡(luò)可以被建模成為信息網(wǎng)絡(luò)。在現(xiàn)實(shí)世界中,信息網(wǎng)絡(luò)隨處可見,已經(jīng)成為現(xiàn)代信息基礎(chǔ)設(shè)施的重要組成部分。分析和挖掘信息網(wǎng)絡(luò)或其中的某幾種特殊類型的網(wǎng)絡(luò),例如社交網(wǎng)絡(luò)、電子商務(wù)網(wǎng)絡(luò)等,已經(jīng)成為計(jì)算機(jī)科學(xué)、社會(huì)學(xué)等領(lǐng)域的研究人員廣泛關(guān)注的課題。當(dāng)前在信息網(wǎng)絡(luò)上的研究按照信息網(wǎng)絡(luò)的不同可以分為同構(gòu)信息網(wǎng)絡(luò)的研究和異構(gòu)信息網(wǎng)絡(luò)的研究。在同構(gòu)信息網(wǎng)絡(luò)上,代表實(shí)體對(duì)象的節(jié)點(diǎn)都屬于同種類型,因而其上的邊也僅包含一種含義,例如在朋友關(guān)系網(wǎng)絡(luò)中,節(jié)點(diǎn)代表人,邊則描述了兩者之間的好友關(guān)系。至今在同構(gòu)信息網(wǎng)絡(luò)上已經(jīng)有了很多有影響力的算法和應(yīng)用,例如PageRank算法、社區(qū)發(fā)現(xiàn)等。但是現(xiàn)實(shí)中大部分網(wǎng)絡(luò)都是異構(gòu)的,也就是說節(jié)點(diǎn)屬于多種類型,因而連接不同類型節(jié)點(diǎn)的邊也蘊(yùn)含著不同的語義信息。例如在由人人網(wǎng)構(gòu)建的異構(gòu)網(wǎng)絡(luò)上,節(jié)點(diǎn)可能有個(gè)人、圖片、電影、小組等,在人與人之間的邊表示好友關(guān)系,而人與圖片之間可能是瀏覽、轉(zhuǎn)發(fā),或者是加標(biāo)簽的關(guān)系。類似的例子隨處可見,從社交媒體到科研網(wǎng)絡(luò)、在線交易系統(tǒng)等,異構(gòu)信息網(wǎng)絡(luò)為真實(shí)世界中的各種對(duì)象交互行為提供了強(qiáng)大的抽象和描述能力,而其上蘊(yùn)含的豐富信息也成為數(shù)據(jù)挖掘新的研究熱點(diǎn)。至今已經(jīng)涌現(xiàn)了很多針對(duì)異構(gòu)網(wǎng)絡(luò)挖掘分析的研究,相關(guān)性查詢是異構(gòu)信息網(wǎng)絡(luò)上一個(gè)基本但很重要的操作,可以應(yīng)用在諸如推薦、聚類、異常檢測(cè)等多個(gè)領(lǐng)域�，F(xiàn)有的異構(gòu)信息網(wǎng)絡(luò)上的相關(guān)性查詢方法主要關(guān)注的是同種類型對(duì)象間的相似性的度量,本文提出了在異構(gòu)信息網(wǎng)絡(luò)上結(jié)合元路徑選擇與用戶偏好的Top-k相關(guān)性查詢的方法來度量不同類型的對(duì)象間的相關(guān)度。該方法是一個(gè)兩階段過程,首先用成對(duì)隨機(jī)游走的思想,沿著給定的元路徑計(jì)算初始的相關(guān)度,之后求解利用用戶偏好建模的多目標(biāo)線性規(guī)劃問題,確定元路徑的權(quán)重組合,據(jù)此更新初始相關(guān)度得到最終結(jié)果。此外,本文提出了多種方法來保證算法的效率,包括圖劃分、分布式矩陣運(yùn)算和預(yù)物化等。最后通過實(shí)驗(yàn)度量本文提出的相關(guān)性查詢方法的查準(zhǔn)率、查全率以及計(jì)算用時(shí)等性能指標(biāo),結(jié)果表明本文提出的異構(gòu)信息網(wǎng)絡(luò)上的相關(guān)性查詢方法可以有效、準(zhǔn)確地實(shí)現(xiàn)查詢要求。 

第一章緒論

本文提出的在異構(gòu)信息網(wǎng)絡(luò)上的top-k相關(guān)性查詢方法，加入了對(duì)用戶偏好的考慮，一方面滿足對(duì)用戶的個(gè)性化查詢的需要，另一方面，通過將用戶偏好建模，來獲得不同元路徑的權(quán)重組合，實(shí)現(xiàn)優(yōu)化查詢結(jié)果的目的。此外，在算法實(shí)現(xiàn)階段，考慮到現(xiàn)有方法的效率問題，提出了圖劃分和分布式計(jì)算兩種解決方案。圖劃分方法是指利用現(xiàn)有的圖劃分方法將異構(gòu)信息網(wǎng)絡(luò)劃分為多個(gè)子網(wǎng)絡(luò)，利用剪枝的思想，只針對(duì)與源節(jié)點(diǎn)在同一子圖中的目標(biāo)節(jié)點(diǎn)進(jìn)行計(jì)算，從而減少計(jì)算量。剪枝可能導(dǎo)致查詢結(jié)果準(zhǔn)確率的降低，筆耕文化推薦期刊，是一種以準(zhǔn)確率換取效率的方法，這種方法可以在某些對(duì)準(zhǔn)確率要求不高、但是要求實(shí)時(shí)完成的任務(wù)中使用。而分布式計(jì)算方法是指將成對(duì)隨機(jī)游走的思想轉(zhuǎn)化為矩陣的運(yùn)算，通過分布式的矩陣的乘法和規(guī)范化計(jì)算來實(shí)現(xiàn)。雖然矩陣的運(yùn)算效率可以大大提高，但是矩陣的物化存儲(chǔ)又成為一個(gè)新的問題，對(duì)此本文也有相應(yīng)的描述和研究。在本文中，針對(duì)準(zhǔn)確性要求較高的任務(wù)，將釆用矩陣分布式計(jì)算的方法來進(jìn)行相關(guān)性查詢，而對(duì)實(shí)時(shí)性要求較高的任務(wù)則采用在劃分子圖上進(jìn)行分布式計(jì)算的方法來實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果表明相關(guān)性查詢方法和分布式計(jì)算的加速算法的有效性。
..........

第二章相關(guān)研究

2.1引言
信息網(wǎng)絡(luò)上僅存在兩種類型的節(jié)點(diǎn)。利用信息網(wǎng)絡(luò)特別是異構(gòu)信息網(wǎng)絡(luò)表示現(xiàn)實(shí)中實(shí)體對(duì)象及其之間的聯(lián)系后，可以充分利用現(xiàn)有的圖相關(guān)算法進(jìn)行挖掘，而且對(duì)邊上存在的潛在的關(guān)系語義實(shí)現(xiàn)更深入的挖掘利用。目前信息網(wǎng)絡(luò)的數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)工作己經(jīng)被廣泛的研究，傳統(tǒng)數(shù)據(jù)挖掘的算法如聚類、分類、排序、社區(qū)發(fā)現(xiàn)、關(guān)系預(yù)測(cè)以及異常檢測(cè)等有許多已經(jīng)成功應(yīng)用到信息網(wǎng)絡(luò)上來。異構(gòu)信息網(wǎng)絡(luò)上的相關(guān)性查詢，主要是針對(duì)輸入的源節(jié)點(diǎn)，在特定某種類型的目標(biāo)節(jié)點(diǎn)中查找與其最相關(guān)的個(gè)，通過對(duì)網(wǎng)絡(luò)和問題的有效建模，實(shí)現(xiàn)準(zhǔn)確高效的相關(guān)性查詢。異構(gòu)信息網(wǎng)絡(luò)上的相關(guān)性查詢是諸多應(yīng)用的關(guān)鍵所在，對(duì)后續(xù)的諸如社區(qū)發(fā)現(xiàn)搜索、推薦，、網(wǎng)站圖片自動(dòng)加標(biāo)簽等工作具有十分重要的應(yīng)用價(jià)值和現(xiàn)實(shí)意義。目前，國(guó)內(nèi)外專家學(xué)者已經(jīng)對(duì)信息網(wǎng)絡(luò)的數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)工作展幵了廣泛的研弁，而信息網(wǎng)絡(luò)上的相關(guān)性查詢工作也有了初步的發(fā)展。根據(jù)已有的研究成果，在信息網(wǎng)絡(luò)上，用相似性的概念來度量同種類型對(duì)象間的相近程度，而相關(guān)性則表示不同種類型對(duì)象間的相近程度。已有的相似性或相關(guān)性度量的定義方法是基于元路徑或者受路徑實(shí)例約束的，通過沿著這些給定的元路徑或路徑實(shí)例，結(jié)合成熟的圖上的游走思想進(jìn)行定義和計(jì)算。由于異構(gòu)網(wǎng)絡(luò)上存在多種類型的節(jié)點(diǎn)對(duì)象和蘊(yùn)含著豐富潛在語義的邊關(guān)系，可以代表極其復(fù)雜的實(shí)體聯(lián)系，使得其上的相關(guān)性查詢工作更具有普遍意義，同時(shí)也增加了查詢的難度。

2.2信息網(wǎng)絡(luò)上的相關(guān)性查詢研究
總體來說，在同構(gòu)信息網(wǎng)絡(luò)上的相似性查詢有兩種思路：一種是利用圖節(jié)點(diǎn)間的連接關(guān)系進(jìn)行迭代計(jì)算確定二者之間的相關(guān)性；另一種是利用節(jié)點(diǎn)的共同鄰節(jié)點(diǎn)來進(jìn)行度量。其中，使用連接關(guān)系計(jì)算的方法可以看做是圖上的隨機(jī)游走即從查詢節(jié)點(diǎn)幵始，模擬用戶的隨機(jī)訪問順序在同構(gòu)網(wǎng)絡(luò)上進(jìn)行隨機(jī)的游走，計(jì)算某點(diǎn)的可達(dá)概率。這種方法通常面臨著處理大規(guī)模矩陣運(yùn)算的問題，導(dǎo)致實(shí)時(shí)性較差。而利用節(jié)點(diǎn)的共同鄰節(jié)點(diǎn)進(jìn)行相關(guān)性的度量，每次僅能確定一條邊的兩個(gè)節(jié)點(diǎn)間的相關(guān)性，而對(duì)不鄰接的節(jié)點(diǎn)則無法度量�？偠�言之，在二分網(wǎng)絡(luò)上的相關(guān)性查詢算法不管是基于迭代思想還是隨機(jī)游走的方式，已經(jīng)開始出現(xiàn)異構(gòu)網(wǎng)絡(luò)上存在的效率問題了。而且，二分網(wǎng)絡(luò)在描述現(xiàn)實(shí)世界中實(shí)體對(duì)象間的聯(lián)系上表達(dá)能力遠(yuǎn)不如異構(gòu)信息網(wǎng)絡(luò)。總之，異構(gòu)網(wǎng)絡(luò)因?yàn)槠浒�含的相比較于同構(gòu)和二分網(wǎng)絡(luò)更加豐富的語義和連接信息，使得其上的挖掘更具有實(shí)際的應(yīng)用價(jià)值。目前的異構(gòu)網(wǎng)絡(luò)上的相關(guān)性度量的計(jì)算方法都是基于元路徑的隨機(jī)游走思想，效果雖好但是效率低下，也已有研究關(guān)注于效率問題，將在下一小節(jié)進(jìn)行闡述。

第三章結(jié)合元路徑與用戶偏好的top-k相關(guān)性查詢方法.....17
3.1異構(gòu)信息網(wǎng)絡(luò)的定義...................17
3.2問題定義和方法框架...........19
3.3基于元路徑的相關(guān)性度量的計(jì)算..........20
第四章相關(guān)性査詢方法的加速算法....26
4.1概述............26
4.2基于圖劃分的查詢加速算法...........27
第五章實(shí)驗(yàn)分析.....35
5.1實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集..........35
5.2方法的性能分析....36
5.3元路徑的長(zhǎng)度對(duì)結(jié)果的影響分析.....37
5.4圖劃分前后效率和效果的分析.............39

第五章實(shí)驗(yàn)分析

5.1實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集
實(shí)驗(yàn)首先用算法計(jì)算得到原始的相關(guān)性度量的值，得到一個(gè)矩陣，每一行都沿著相對(duì)應(yīng)的元路徑計(jì)算得到的相關(guān)度，每一列表示對(duì)應(yīng)的電影在給定的四條元路徑下做成對(duì)隨機(jī)游走計(jì)算得到的與源節(jié)點(diǎn)的相關(guān)性度量的初始值。根據(jù)公式，將通過歷宋數(shù)據(jù)分析得到的用戶偏好建模成為一個(gè)多目標(biāo)線性規(guī)劃問題并求解得到一個(gè)四維的行向量作為對(duì)應(yīng)的四條元路徑的權(quán)重。

5.2方法的性能分析
也就是說并不是與源節(jié)點(diǎn)的該流派下的電影所屬的其他流派下的其他電影也屬于源節(jié)點(diǎn)的流派，比如很多電影屬于愛情類，但是愛情類的電影有的是輕松幽默的喜劇，有的則是驚悚劇。元路徑長(zhǎng)度影響相關(guān)性查詢結(jié)果的準(zhǔn)確率是有原因。一方面，在異構(gòu)信息網(wǎng)絡(luò)上，不同的元路徑蘊(yùn)含不同的語義信息，可能某兩種類型的節(jié)點(diǎn)間的連接關(guān)系強(qiáng)度強(qiáng)于該節(jié)點(diǎn)與另外類型的節(jié)點(diǎn)間的關(guān)系強(qiáng)度，比如在5.1節(jié)末的例子中，電影與流派之間的關(guān)系強(qiáng)度就強(qiáng)于電影與觀影人群的關(guān)系強(qiáng)度；另一方面，直觀上來說，如果從源節(jié)點(diǎn)出發(fā)到達(dá)目標(biāo)節(jié)點(diǎn)要經(jīng)過的步數(shù)越多，二者之間的相關(guān)度越低。本章基于兩個(gè)數(shù)據(jù)集進(jìn)行了相關(guān)性查詢的實(shí)驗(yàn)，首先介紹了和數(shù)據(jù)集的網(wǎng)絡(luò)模式和由此構(gòu)建的異構(gòu)信息網(wǎng)絡(luò)的規(guī)模，之后從多方面對(duì)基于本文提出的相關(guān)性查詢的方法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)首先從準(zhǔn)確率、召回率和值三方面對(duì)比分析了本文提出的相關(guān)性查詢方法與已有方法的效果，之后展示了元路徑長(zhǎng)度對(duì)結(jié)果的影響，接下來對(duì)本文提出的加速方法的可行性作了對(duì)比實(shí)驗(yàn)。一系列的實(shí)驗(yàn)結(jié)果表明，本文提出的方法能夠有效地提高異構(gòu)信息網(wǎng)絡(luò)上相關(guān)性查詢的準(zhǔn)確度和效率。
...........

第六章總結(jié)展望

異構(gòu)信息網(wǎng)絡(luò)上的相關(guān)性査詢可以用于多種應(yīng)用中，例如商品推薦、搜索以及自動(dòng)添加圖片標(biāo)簽等工作。目前在異構(gòu)信息網(wǎng)絡(luò)上的相關(guān)性査詢的研究還處于初級(jí)階段，主要是使用基于元路徑的成對(duì)隨機(jī)游走的思想，效率較低，且使用的元路徑來自于歷史經(jīng)驗(yàn)或者專家推薦，一次只支持一條元路徑的計(jì)算，準(zhǔn)確率也不夠理想。本文針對(duì)異構(gòu)信息網(wǎng)絡(luò)上相關(guān)性查詢中存在的問題進(jìn)行研究，主要研究成果如下：提出基于多條元路徑下相關(guān)性度量的計(jì)算方法，并給出根據(jù)用戶偏好確定元路徑權(quán)重組合的方法。一方面整合了多條元路徑的計(jì)算結(jié)果，另一方面充分利用了用戶容易輸入或通過對(duì)往期用戶歷史數(shù)據(jù)的挖掘易于獲得的的用戶偏好信息。通過將用戶偏好建模成為一個(gè)多目標(biāo)線性規(guī)劃問題，釆用遺傳算法求解確定元路徑的權(quán)重組合，并據(jù)此更新獲得的初始相關(guān)性度量的值。在頂和數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明通過多條元路徑的組合進(jìn)行相關(guān)性計(jì)算后得到的結(jié)果的準(zhǔn)確性更高。

..........

參考文獻(xiàn)：

[1] 于瀟.  基于J2EE框架和XML建模的人力資源數(shù)據(jù)分析與展現(xiàn)平臺(tái)架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[D]. 山東大學(xué) 2014
[2] 黃亮.  稅務(wù)海量數(shù)據(jù)倉庫的設(shè)計(jì)與優(yōu)化[D]. 山東大學(xué) 2014
[3] 郭亞寧.  基于哈希編碼的文本拷貝檢測(cè)算法優(yōu)化與實(shí)現(xiàn)[D]. 山東大學(xué) 2014
[4] 嚴(yán)沖.  石家莊聯(lián)通社區(qū)經(jīng)理服務(wù)滿意度調(diào)查系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)[D]. 山東大學(xué) 2014
[5] 許寧.  移動(dòng)通信網(wǎng)絡(luò)性能管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 山東大學(xué) 2014
[6] 姜飛.  基于加權(quán)異構(gòu)信息網(wǎng)絡(luò)的多維文本數(shù)據(jù)分析技術(shù)研究[D]. 山東大學(xué) 2014
[7] 莊緒良.  智能照明統(tǒng)計(jì)分析子系統(tǒng)的設(shè)計(jì)與開發(fā)[D]. 山東大學(xué) 2013
[8] 張靜.  信息網(wǎng)絡(luò)多維分析方法的研究[D]. 山東大學(xué) 2013
[9] 邢磊.  基于STRUTS框架的社會(huì)保險(xiǎn)網(wǎng)上查詢系統(tǒng)的數(shù)據(jù)庫設(shè)計(jì)與實(shí)現(xiàn)[D]. 山東大學(xué) 2013
[10] 張冬兵.  勝利農(nóng)村合作銀行計(jì)算機(jī)設(shè)備管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 山東大學(xué) 2013



本文編號(hào)：10894