共享局部算法的數(shù)據(jù)分析

崔鵬宇

摘要：本文針對(duì)單一關(guān)系的數(shù)據(jù)挖掘方案不能精準(zhǔn)的發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的問題，通過提出異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)挖掘的算法達(dá)到網(wǎng)絡(luò)節(jié)點(diǎn)的初步劃分目標(biāo)的實(shí)并且能夠初步此得到各數(shù)據(jù)子集。

關(guān)鍵詞：異構(gòu)網(wǎng)絡(luò)；數(shù)據(jù)挖掘；共享局部結(jié)構(gòu)

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）01-0138-02

隨著社會(huì)網(wǎng)絡(luò)分析的進(jìn)一步發(fā)展，人們逐漸發(fā)現(xiàn)單一的關(guān)系網(wǎng)絡(luò)并不能很好的刻畫出實(shí)體間的真實(shí)結(jié)構(gòu)[1]。在現(xiàn)實(shí)的社會(huì)網(wǎng)絡(luò)中，實(shí)體之間往往是多種關(guān)系交織在一起的[2]。每種關(guān)系對(duì)應(yīng)一個(gè)關(guān)系圖，僅僅利用一種關(guān)系圖分析網(wǎng)絡(luò)結(jié)構(gòu)有可能會(huì)造成重要信息的缺失，從而不能精準(zhǔn)地挖掘其隱含的數(shù)據(jù)結(jié)構(gòu)[3-4]。將含有多種關(guān)系的網(wǎng)絡(luò)稱之為“異質(zhì)網(wǎng)絡(luò)”或者多關(guān)系網(wǎng)絡(luò)[5]。以信息共享為代表的各種異構(gòu)網(wǎng)絡(luò)應(yīng)用蓬勃發(fā)展，使得人們與互聯(lián)網(wǎng)間的聯(lián)系更加緊密與多向，由簡(jiǎn)單單項(xiàng)的信息檢索轉(zhuǎn)變?yōu)橐杂脩魹橹鲗?dǎo)的信息的創(chuàng)建與傳播。隨著用戶之間的互交越來越密切與深入，異構(gòu)網(wǎng)絡(luò)下的數(shù)據(jù)挖掘研究逐漸成為復(fù)雜網(wǎng)絡(luò)分析的一大熱點(diǎn)[6]。

本文提出一種基于共享局部結(jié)構(gòu)的異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)挖掘算法，該模型利用各維關(guān)系網(wǎng)絡(luò)間的共性信息，根據(jù)各關(guān)系圖的初始聚類結(jié)果，找出那些在多個(gè)關(guān)系網(wǎng)中都同屬于一個(gè)類型的節(jié)點(diǎn)簇，即數(shù)據(jù)子集，并對(duì)其中的節(jié)點(diǎn)進(jìn)行標(biāo)記，然后根據(jù)某種劃分原則依次將剩余未標(biāo)記的節(jié)點(diǎn)并入相應(yīng)的數(shù)據(jù)子集中，從而完成整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的劃分。通過在模擬計(jì)算機(jī)合成網(wǎng)絡(luò)數(shù)據(jù)集上的比較試驗(yàn)，證明了所提出算法的魯棒性和有效性。

1 異構(gòu)網(wǎng)絡(luò)下的數(shù)據(jù)結(jié)構(gòu)

一個(gè)包含種關(guān)系的異構(gòu)網(wǎng)絡(luò)可以抽象地表示為，，其中表示含有個(gè)元素的節(jié)點(diǎn)集合，表示第維關(guān)系網(wǎng)絡(luò)的鄰接矩陣。將異構(gòu)網(wǎng)絡(luò)中的不同關(guān)系看作是從不同角度對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的描述。此外，各維關(guān)系網(wǎng)并不是獨(dú)立存在的。本文的任務(wù)就綜合實(shí)體間的多種關(guān)系并從中挖掘其隱含的數(shù)據(jù)結(jié)構(gòu)，引入了共享局部結(jié)構(gòu)和節(jié)點(diǎn)簇凝聚度思想，提出了新的異構(gòu)網(wǎng)絡(luò)挖掘算法。

2 基于局部共享結(jié)構(gòu)的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)挖掘

2.1 共享局部信息的提取

異構(gòu)網(wǎng)絡(luò)的實(shí)體間存在的對(duì)應(yīng)的關(guān)系為。由網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)劃分可以得到如下集合：，這里—第維網(wǎng)絡(luò)劃分出來的數(shù)據(jù)結(jié)構(gòu)。如果將被假定的關(guān)系網(wǎng)格都劃分成為個(gè)數(shù)據(jù)集，并且在聚類時(shí)，隨機(jī)分配（1～k）數(shù)據(jù)標(biāo)號(hào)。

目標(biāo)是提取有關(guān)異質(zhì)網(wǎng)絡(luò)之間的共享信息，有必要找到在劃分的方式不盡相同的情況下的數(shù)據(jù)標(biāo)號(hào)的相互對(duì)應(yīng)關(guān)系，其公式如下：

其中表示由關(guān)系劃分出來的標(biāo)號(hào)為的數(shù)據(jù)集，為節(jié)點(diǎn)被劃分到的概率而則表示節(jié)點(diǎn)在關(guān)系與關(guān)系中分別被劃分到與中的概率。

2.2 共享局部結(jié)構(gòu)的更新

將劃分的結(jié)果一并加入到各維網(wǎng)絡(luò)劃分的數(shù)據(jù)結(jié)構(gòu)的集合之中，這時(shí)分集合將擴(kuò)充為，算法的主要步驟可以歸納如下：

維度改進(jìn)算法：

輸入：維異質(zhì)關(guān)系網(wǎng)絡(luò)、數(shù)據(jù)集個(gè)數(shù)；

輸出：各節(jié)點(diǎn)所屬的數(shù)據(jù)集標(biāo)號(hào)；

（1）分別對(duì)各單維網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)集劃分，得到種不同的劃分結(jié)果；

For ；

（2）將未標(biāo)記節(jié)并入使節(jié)點(diǎn)簇的凝聚度增益最大的數(shù)據(jù)子集中；

（3）對(duì)未標(biāo)記節(jié)點(diǎn)進(jìn)行相應(yīng)劃分，將劃分結(jié)果也并入集合（）。

3 實(shí)驗(yàn)數(shù)據(jù)集及對(duì)比結(jié)果

通過對(duì)比實(shí)驗(yàn)來驗(yàn)證有效性及魯棒性。選取的方法有如下兩種方式：一、各單一的異構(gòu)網(wǎng)絡(luò)下的數(shù)據(jù)集挖掘；二、關(guān)系矩陣加權(quán)組合的方法WAMM以及PMM算法。

為了比較各算法的數(shù)據(jù)集劃分性能，我們使用了兩種經(jīng)典的指標(biāo)：歸一化互信息（NMI）與準(zhǔn)確率（Ac）。兩者的取值都在0-1之間，如果它們的值越大的話，說明結(jié)果越接近真實(shí)。

我們?cè)谟?jì)算機(jī)的合成數(shù)據(jù)上進(jìn)行試驗(yàn)分析的目的是為了驗(yàn)證算法是否有效。這種合成網(wǎng)絡(luò)一共包括350個(gè)節(jié)點(diǎn)，將其劃分成了三個(gè)大小各不相同的數(shù)據(jù)集，并且各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)間存在4種關(guān)系，各關(guān)系圖的可以用對(duì)應(yīng)圖1中的來表示。

圖2指出了每種算法在合成網(wǎng)絡(luò)中數(shù)據(jù)集劃分的性能，從圖中我們可以看出異質(zhì)網(wǎng)絡(luò)的算法性能明顯比單一的關(guān)系網(wǎng)的數(shù)據(jù)集挖掘性能要好，并且基本上能實(shí)現(xiàn)了正確的劃分。

4 結(jié)語

針對(duì)異構(gòu)網(wǎng)絡(luò)中多元化的節(jié)點(diǎn)關(guān)系，本文提出一種基于共享局部結(jié)構(gòu)的異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集挖掘算法。該算法將網(wǎng)絡(luò)節(jié)點(diǎn)通過提取多種關(guān)系間共享的局部信息基本實(shí)現(xiàn)了網(wǎng)絡(luò)節(jié)點(diǎn)的局部劃分，最后在通過在計(jì)算機(jī)合成的數(shù)據(jù)集上驗(yàn)證了該算法的有效性。

參考文獻(xiàn)

[1]張春英，郭景峰.集對(duì)社會(huì)網(wǎng)絡(luò)α關(guān)系社區(qū)及動(dòng)態(tài)挖掘算法[J].計(jì)算機(jī)學(xué)報(bào)，2013，（8）：1682-1692.

[2]孫榮德，邵峰晶，孫仁誠(chéng).一種基于復(fù)合網(wǎng)的面向微博關(guān)注的推薦算法[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2013，（24）：132-133.

[3]王會(huì)梅，鮮明，王國(guó)玉.基于擴(kuò)展網(wǎng)絡(luò)攻擊圖的網(wǎng)絡(luò)攻擊策略生成算法[J].電子與信息學(xué)報(bào)，2011，（12）：3015-3021.

[4]黃光球，李艷.基于粗糙圖的網(wǎng)絡(luò)風(fēng)險(xiǎn)評(píng)估模型[J].計(jì)算機(jī)應(yīng)用，2010，（1）：190-195.

[5]榮智海，吳枝喜，王文旭.共演博弈下網(wǎng)絡(luò)合作動(dòng)力學(xué)研究進(jìn)展[J].電子科技大學(xué)學(xué)報(bào)，2013，（1）：10-22.

[6]劉鈺峰，李仁發(fā).異構(gòu)信息網(wǎng)絡(luò)上基于圖正則化的半監(jiān)督學(xué)習(xí)[J].計(jì)算機(jī)研究與發(fā)展，2015，（3）：606-613.