數(shù)據(jù)挖掘課程論文

1、面向社會(huì)網(wǎng)絡(luò)分析的數(shù)據(jù)挖掘方法研究摘要隨著信息技術(shù)的發(fā)展，越來(lái)越多的社會(huì)關(guān)系數(shù)據(jù)被收集。如果能夠有效地對(duì) 它們進(jìn)行分析，必將加深人們對(duì)社會(huì)學(xué)的理解， 促進(jìn)社會(huì)學(xué)的發(fā)展。但是數(shù)據(jù)量 的增大同時(shí)對(duì)分析技術(shù)提出了巨大的挑戰(zhàn)。 如今社會(huì)網(wǎng)絡(luò)的規(guī)模早已超出了原有 分析手段的處理能力，必須借助更為有效的工具才能完成分析任務(wù)。數(shù)據(jù)挖掘作 為一種幫助人們從海量數(shù)據(jù)中發(fā)現(xiàn)潛在有用的知識(shí)的工具，在很多領(lǐng)域發(fā)揮了重 要的作用。社會(huì)網(wǎng)絡(luò)分析又稱為鏈接挖掘，是指用數(shù)據(jù)挖掘的方法處理社會(huì)網(wǎng)絡(luò) 中的關(guān)系數(shù)據(jù)。本文對(duì)數(shù)據(jù)挖掘和社會(huì)網(wǎng)絡(luò)分析中的一些方法進(jìn)行了介紹并對(duì)數(shù) 據(jù)挖掘算法在社會(huì)網(wǎng)絡(luò)分析的應(yīng)用進(jìn)行了概括。關(guān)鍵詞：設(shè)會(huì)網(wǎng)絡(luò)

2、分析；數(shù)據(jù)挖掘；鏈接挖掘RESEARCH ON SOCIAL NETWORK ANALYSIS-ORIENTED DATAMINING METHODABSTRACTWith the development of information technology, more and more social relation data have been collected. Effectively analyzing these data will help the human understand the properties of society, and promote the develop

3、ment of sociology. However, the growth of data presented a huge challenge to the analysis method. Now the scale of social network has already gone beyond the scope of the handling capacity of the original analytical methods. Some more effective tool should be utilized to complete the analysis tasks.

4、 Data Mining helps people find a potentially useful knowledge from Massive Data, and play an important role in many fields. Social network analysis is also called linking mining. It use methods of data mining to deal with relational data in social network. This paper briefly introduces some methods

5、in the areas of data mining and social network analysis, and generalizes the application of data mining using in social network analysis.KEY WORD：S social network analysis; data mining; link mining目錄1.引言 4.2.社會(huì)網(wǎng)絡(luò)和數(shù)據(jù)挖掘方法介紹 5.2.1 社會(huì)網(wǎng)絡(luò)分析方法 5.2.1.1 用戶用戶網(wǎng)絡(luò)模型 5.2.1.2 用戶事件網(wǎng)絡(luò)模型 7.2.2 數(shù)據(jù)挖掘方法 8.2.2.1 關(guān)聯(lián)規(guī)則分析 9

6、.2.2.2 聚類分析 1.03.數(shù)據(jù)挖掘在社會(huì)網(wǎng)絡(luò)分析中的應(yīng)用 1.23.1 基于相似度度量方法 1.23.2 基于統(tǒng)計(jì)的方法 1.53.3 基于頻繁模式挖掘的方法 1.84.總結(jié) 1.8.1.引言傳統(tǒng)的機(jī)器學(xué)習(xí)處理的社會(huì)學(xué)中的對(duì)象是單獨(dú)的數(shù)據(jù)實(shí)例， 這些數(shù)據(jù)實(shí)例往 往可以用一個(gè)包含多個(gè)屬性值的向量來(lái)表示， 同時(shí)這些數(shù)據(jù)實(shí)例之間假設(shè)是統(tǒng)計(jì) 上獨(dú)立的。 例如要訓(xùn)練一個(gè)疾病診斷系統(tǒng)， 它的任務(wù)是診斷一個(gè)被試者是否患有 某種傳染病。 傳統(tǒng)的學(xué)習(xí)算法用一個(gè)向量來(lái)表示一個(gè)被試者， 同時(shí)假設(shè)兩個(gè)被試 者之間的患病情況是相互獨(dú)立的， 即知道一個(gè)確診病人對(duì)于診斷其他被試者是否 患病不能提供任何幫助。 直觀經(jīng)

7、驗(yàn)告訴我們這種假設(shè)是不合理的。 直到二十世紀(jì) 30年代，Jacob More no和哈佛大學(xué)的一組研究人員分別提出了社會(huì)網(wǎng)絡(luò)模型來(lái) 分析社會(huì)學(xué)中的現(xiàn)象和問(wèn)題。 現(xiàn)代社會(huì)學(xué)主要研究現(xiàn)代社會(huì)的發(fā)展和社會(huì)中的組 織性或者團(tuán)體性行為。 社會(huì)學(xué)家發(fā)現(xiàn)社會(huì)實(shí)體之間存在著相互的依賴和聯(lián)系， 并 且這種聯(lián)系對(duì)于每個(gè)社會(huì)實(shí)體有著重要的影響。 基于這樣的觀察， 他們通過(guò)網(wǎng)絡(luò) 模型來(lái)刻畫社會(huì)實(shí)體之間的關(guān)系， 并進(jìn)一步用來(lái)分析社會(huì)關(guān)系之間的模式和隱含 規(guī)律。為了更好的研究這個(gè)問(wèn)題，他們?cè)噲D用圖結(jié)構(gòu)來(lái)刻畫這種社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)。 一個(gè)社會(huì)網(wǎng)絡(luò)由很多節(jié)點(diǎn)（node）和連接這些節(jié)點(diǎn)的一種或多種特定的鏈接（link） 所組成。節(jié)點(diǎn)

8、往往表示了個(gè)人或團(tuán)體， 也即傳統(tǒng)數(shù)據(jù)挖掘中的數(shù)據(jù)實(shí)例， 鏈接則 表示了他們之間存在的各種關(guān)系 （ relation ） ，如朋友關(guān)系、親屬關(guān)系、貿(mào)易關(guān)系、 性關(guān)系等。由于數(shù)據(jù)收集方式的限制， 早期的社會(huì)網(wǎng)絡(luò)局限于一個(gè)小的團(tuán)體之內(nèi)， 往往 僅包含幾十個(gè)結(jié)點(diǎn)。 借助于圖論和概率統(tǒng)計(jì)的知識(shí)， 人工處理可以從中分析出一 些簡(jiǎn)單的性質(zhì)和模式。 但是，隨著現(xiàn)代的通信技術(shù)的發(fā)展， 越來(lái)越多的數(shù)據(jù)被收 集和整合在一起， 建立一個(gè)大的社會(huì)網(wǎng)絡(luò)成為可能。 例如， 可以通過(guò)電子郵件的 日志來(lái)建立使用者之間的聯(lián)系網(wǎng)絡(luò)， 或者通過(guò)網(wǎng)絡(luò)日志及網(wǎng)絡(luò)通訊錄等方式將用 戶提交的聯(lián)系人信息建立社會(huì)網(wǎng)絡(luò)。 所以，現(xiàn)在的社會(huì)網(wǎng)絡(luò)規(guī)模

9、比早期網(wǎng)絡(luò)龐大， 通常包含幾千或者幾萬(wàn)的結(jié)點(diǎn)， 甚至有多達(dá)百萬(wàn)個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)。 面對(duì)這樣龐大復(fù) 雜的網(wǎng)絡(luò)， 簡(jiǎn)單的數(shù)學(xué)知識(shí)和原始的人工處理已經(jīng)不可能進(jìn)行有效的分析。 數(shù)據(jù) 挖掘是從巨量數(shù)據(jù)中發(fā)現(xiàn)有效的、 新穎的、潛在有用的并且最終可理解的模式的 非平凡過(guò)程。 數(shù)據(jù)挖掘就是為了解決當(dāng)今擁有大量數(shù)據(jù)， 但缺乏有效分析手段的 困境而出現(xiàn)的研究領(lǐng)域。 目前，已經(jīng)在包括生物信息學(xué)， 自然語(yǔ)言處理等許多方 面發(fā)揮了巨大的作用。與傳統(tǒng)的數(shù)據(jù)挖掘只關(guān)注數(shù)據(jù)實(shí)例不同， 社會(huì)網(wǎng)絡(luò)分析對(duì)鏈接同樣關(guān)注。 從 數(shù)據(jù)挖掘角度，社會(huì)網(wǎng)絡(luò)分析又稱為鏈接挖掘(link mining)。通過(guò)對(duì)鏈接的挖掘 我們可以獲得關(guān)于實(shí)例更豐富

10、 (如某個(gè)實(shí)例在整個(gè)網(wǎng)絡(luò)中的重要性) 、更準(zhǔn)確(如 預(yù)測(cè)某個(gè)實(shí)例所屬的類別)的關(guān)系數(shù)據(jù)( relational data) 。社會(huì)網(wǎng)絡(luò)分析是關(guān)系數(shù)據(jù)挖掘的主要應(yīng)用。 關(guān)系數(shù)據(jù)挖掘的發(fā)展為社會(huì)網(wǎng)絡(luò) 分析提供了更有力的工具， 促進(jìn)了社會(huì)網(wǎng)絡(luò)分析的發(fā)展。 本文分析了社會(huì)網(wǎng)絡(luò)分 析數(shù)據(jù)的方法以及任務(wù)和需求，介紹了幾類適于社會(huì)網(wǎng)絡(luò)分析的數(shù)據(jù)挖掘算法。2.社會(huì)網(wǎng)絡(luò)和數(shù)據(jù)挖掘方法介紹2.1 社會(huì)網(wǎng)絡(luò)分析方法社會(huì)網(wǎng)絡(luò)分析是一套用來(lái)分析多個(gè)個(gè)體通過(guò)相互聯(lián)系構(gòu)成的網(wǎng)絡(luò)的結(jié)構(gòu)， 性 質(zhì)以及其他用于描述這個(gè)網(wǎng)絡(luò)的屬性的分析方法的集合。 如社會(huì)網(wǎng)絡(luò)分析方法提 供了根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的聯(lián)系緊密情況將網(wǎng)絡(luò)分層的方法， 網(wǎng)絡(luò)中節(jié)

11、點(diǎn)相互作用模 式識(shí)別，將網(wǎng)絡(luò)分塊，給用戶評(píng)級(jí)，信息擴(kuò)散，對(duì)社會(huì)網(wǎng)絡(luò)提供圖形描述，中心 度的分布等。 下面我們介紹社會(huì)網(wǎng)絡(luò)分析最重要的兩個(gè)模型， 用戶用戶網(wǎng)絡(luò) 模型和用戶事件網(wǎng)絡(luò)模型2.1.1 用戶用戶網(wǎng)絡(luò)模型在網(wǎng)絡(luò)模型中，我們把用戶作為節(jié)點(diǎn)， 用戶之間的聯(lián)系作為節(jié)點(diǎn)之間的連線， 構(gòu)成一個(gè)社會(huì)網(wǎng)絡(luò)。 用戶之間產(chǎn)生聯(lián)系， 一個(gè)用戶對(duì)另一個(gè)用戶的連接可以是一 次也可以是多次， 并且是帶有方向的， 因此這是一個(gè)帶有數(shù)值的有向網(wǎng)絡(luò)。 如果 用戶A指向用戶B，則產(chǎn)生弧AB,這條弧由A指向B，連接的次數(shù)就是這條 弧的值。整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量用l表示。每個(gè)結(jié)點(diǎn)用V i表示。V 2圖2.1用戶一一用戶網(wǎng)絡(luò)示意圖

12、圖2.1給出了一個(gè)由6個(gè)用戶構(gòu)成的簡(jiǎn)單的“用戶一一用戶網(wǎng)絡(luò)”示意圖。 圖2.1中，結(jié)點(diǎn)V 1到V 2有1條弧，值為3,表示用戶V 1與用戶V 2有3次連接。 結(jié)點(diǎn)V2與V3之間是雙向弧，值為1和3，表示用戶V2與用戶V3有1次連接，表示用戶V 3與用戶V 2有3次連接，以此類推。威望度計(jì)算：在一個(gè)有向帶值得網(wǎng)絡(luò)中，一個(gè)結(jié)點(diǎn)的威望度是指這個(gè)結(jié)點(diǎn)的 入度與所有節(jié)點(diǎn)的入度和的比值6。X i -昨)一(式 2.1)Z Xi -1式2.1是威望度的計(jì)算公式，其中Xi-表示節(jié)點(diǎn)v i的入度。入度是指所有指 向該結(jié)點(diǎn)的弧上的值的和。如圖2.1中，節(jié)點(diǎn)v 3的入度為2+3=5，威望度為5/14=0.385 ;

13、節(jié)點(diǎn)v 6的入度為1，威望度為1/14=0.077 ;結(jié)點(diǎn)v 1的入度為0， 威望度為0/13=0。一個(gè)結(jié)點(diǎn)的威望度越高，該結(jié)點(diǎn)所代表的用戶被其他用戶連 接的次數(shù)就越多，該用戶在網(wǎng)絡(luò)模型所處的位置就越重要。計(jì)算表明在節(jié)點(diǎn)數(shù)量 巨大的網(wǎng)絡(luò)中所有的節(jié)點(diǎn)符合幕律分布而不是隨機(jī)網(wǎng)絡(luò)中的正態(tài)分布鐘形曲線。 我們將其記作N(k)，根據(jù)公式N(k)k，其中參數(shù) 就是冪次數(shù)。例如，在計(jì)算 過(guò)的萬(wàn)維網(wǎng)文檔上的外指鏈接后，其鏈接符合公式N(k)k，其中 =2.57。中心度計(jì)算：在一個(gè)有向帶值的網(wǎng)絡(luò)中，一個(gè)結(jié)點(diǎn)的中心度是指這個(gè)結(jié)點(diǎn)的 出度與所有結(jié)點(diǎn)的出度和的比值 Xi 亠CD（vi）=（式 2.2）7 Xi1式2.

14、2是中心度的計(jì)算公式，其中Xi+表示節(jié)點(diǎn)v i的出度。出度是指所有該 節(jié)點(diǎn)指向其他結(jié)點(diǎn)的所有弧上的值的和。如圖2.1中結(jié)點(diǎn)v i的出度為2+3+2=7,中心度為7/14=0.538，結(jié)點(diǎn)v 3的出度為1+1+1=3，中心度為3/14=0.154。一個(gè) 結(jié)點(diǎn)的中心度越高，表示該結(jié)點(diǎn)連接別人的次數(shù)就越多， 說(shuō)明該用戶在網(wǎng)絡(luò)模型 中越活躍。2.1.2用戶一一事件網(wǎng)絡(luò)模型在網(wǎng)絡(luò)模型中，用戶之間除了連接這種聯(lián)系以外，用戶還因?yàn)橥瑫r(shí)參與一個(gè) 事件而聯(lián)系，而事件也因有相同的用戶參與而聯(lián)系。在模型中，通過(guò)用戶與事件之間的聯(lián)系構(gòu)建網(wǎng)絡(luò)拓?fù)鋱D，假如用戶 v參與了事件e，則在v和e之間連線， 因?yàn)槲覀冞@里主要研究事

15、件傳播的廣度，因此我們不考慮用戶對(duì)同一事件的多次 參與，又因?yàn)檫@種聯(lián)系只在兩種不同類型的對(duì)象（用戶和事件）之間存在，所以 方向已經(jīng)沒(méi)有意義，因此這是一個(gè)不帶值的無(wú)向圖4。圖2.2用戶一一事件網(wǎng)絡(luò)示意圖圖2.2給出了一個(gè)由6個(gè)用戶和5個(gè)事件構(gòu)成的簡(jiǎn)單的“用戶一一事件網(wǎng) 絡(luò)”示意圖。圖中，左邊的6個(gè)圓球表示6個(gè)用戶，由v i標(biāo)出，i從1到6;右 邊的5個(gè)圓球表示5個(gè)事件，由ei標(biāo)出，i從1到5。圖中的線連接用戶與事件， 如v 1到8有一條連線，表示用戶v 1參與了事件e1,以此類推。事件的中心度計(jì)算：事件的中心度是指參與該事件的人數(shù)與總?cè)藬?shù)個(gè)數(shù)的比XiCE(ei)(式 2.3)n式(2.3)為事件

16、中心度計(jì)算公式，其中x i表示參與ei事件的用戶，n表示該 圖中總的用戶個(gè)數(shù)。如圖2.2中e2事件的參與人數(shù)為3,事件中心度為3/6=0.5。事件之間的聯(lián)系。在圖2.2中，事件之間沒(méi)有直接聯(lián)系，但是卻存在間接聯(lián) 系，我們認(rèn)為擁有相同的用戶參與的兩個(gè)事件之間存在聯(lián)系，擁有相同用戶的數(shù)量越多則兩個(gè)事件聯(lián)系越緊密。如，事件 ei和e2擁有一個(gè)相同的用戶(v 1)，則 它們的聯(lián)系強(qiáng)度為1；事件e2和e3擁有2個(gè)相同的用戶(V 3, V 4)，則它們的聯(lián) 系強(qiáng)度為2。通過(guò)這種方式建立只有事件之間的聯(lián)系而把用戶從網(wǎng)絡(luò)中剝離出來(lái) 得到新的“事件一一事件網(wǎng)絡(luò)”模型，可以很方便的找出聯(lián)系最緊密的事件。 2.2數(shù)

17、據(jù)挖掘方法數(shù)據(jù)挖掘(Data Mining)就是從大量的、不完全的、有噪聲的、模糊的、隨 機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用 的信息和知識(shí)的過(guò)程。與數(shù)據(jù)挖掘相近的同義詞有數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)(KDDKnowledge Discovery in Database)、數(shù)據(jù)分析、數(shù)據(jù)融合以及決策支持等。這 個(gè)定義包括好幾層含義：數(shù)據(jù)源必須是真實(shí)的、大量的、含噪聲的；發(fā)現(xiàn)的是用 戶感興趣的知識(shí)；發(fā)現(xiàn)的知識(shí)要可接受、可理解、可運(yùn)用；并不要求發(fā)現(xiàn)放之四 海皆準(zhǔn)的知識(shí)，僅支持特定的發(fā)現(xiàn)問(wèn)題。即所有發(fā)現(xiàn)的知識(shí)都是相對(duì)的，是有特 定前提和約束條件，面向特定領(lǐng)域的，同時(shí)還要能夠易

18、于被用戶理解。最好能用 自然語(yǔ)言表達(dá)所發(fā)現(xiàn)的結(jié)果。數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式。 模式有很多 種，按功能可分為兩大類：預(yù)測(cè)型模式和描述型模式。第一種是預(yù)測(cè)型模式，即 可以根據(jù)數(shù)據(jù)項(xiàng)的值精確確定某種結(jié)果的模式。挖掘預(yù)測(cè)型模式所使用的數(shù)據(jù)也都是可以明確知道結(jié)果的。第二種是描述型模式，即對(duì)數(shù)據(jù)中存在的規(guī)則做一種 描述，或者根據(jù)數(shù)據(jù)的相似性把數(shù)據(jù)分組。 描述型模式不能直接用于預(yù)測(cè)。 數(shù)據(jù) 挖掘涉及多學(xué)科技術(shù)的集成，包括數(shù)據(jù)庫(kù)技術(shù)、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、高性能計(jì)算、 模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)可視化、信息檢索、圖像于信息處理和空間數(shù)據(jù)分析 1。這里主要介紹關(guān)聯(lián)規(guī)則分析和聚類分析。2.2.1關(guān)聯(lián)規(guī)則分析在J

19、iawei Han的數(shù)據(jù)挖掘概念與技術(shù)中將關(guān)聯(lián)規(guī)則的定義如下：設(shè) 匸Il,l2，;Im是項(xiàng)的集合。設(shè)任務(wù)相關(guān)的數(shù)據(jù) D是數(shù)據(jù)庫(kù)事務(wù)的集合，其中每個(gè) 事物T是項(xiàng)的集合，使得T I。每一個(gè)事務(wù)有一個(gè)標(biāo)識(shí)符，稱作 TID。設(shè)A是一 個(gè)項(xiàng)集，事務(wù)T包含A當(dāng)且僅當(dāng)A T。關(guān)聯(lián)規(guī)則是形如 A B的蘊(yùn)涵式，其中 A I，B I，并且A B=?。規(guī)則A B在事務(wù)D中成立，具有支持度s,其中s 是D中事務(wù)包含A B (即集合A與B的并或A和B二者)的百分比。它是概率 P(A B)。規(guī)則 A B在事務(wù)D中具有置信度c,其中c是D中包含A的事務(wù)同時(shí) 包含B的百分比這是條件概率P(BA)5。即Support(A二 B

20、)=P(A B)Con fide nce(X B)= P(BA)同時(shí)滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則。也說(shuō)這樣的關(guān)聯(lián)規(guī)則是有趣的。一般來(lái)說(shuō)關(guān)聯(lián)規(guī)則的挖掘可以看成兩步的過(guò)程：找出所有的頻繁項(xiàng)集：根據(jù)定義，這些項(xiàng)集的每一個(gè)出現(xiàn)的頻繁性至少與預(yù) 定義的最小支持計(jì)數(shù)一樣。由頻繁項(xiàng)集產(chǎn)生的強(qiáng)關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和 最小置信度。關(guān)聯(lián)規(guī)則的主要算法有Apriori算法Apriori算法是一種以概率為基礎(chǔ)的具有影響的挖掘布爾型關(guān)聯(lián)規(guī)則頻繁 項(xiàng)集的算法。其利用循序漸進(jìn)的方式，找出數(shù)據(jù)庫(kù)中項(xiàng)目的關(guān)系，以形成規(guī)則。其過(guò)程分為兩步：一為連接(類矩陣運(yùn)算)，二為剪枝(去掉

21、那些沒(méi)必要的中間結(jié) 果)。在此算法中常出現(xiàn)項(xiàng)集的概念。項(xiàng)集(itemset)簡(jiǎn)單地說(shuō)就是項(xiàng)的集合。包含K個(gè)項(xiàng)的集合為k項(xiàng)集。項(xiàng)集的出現(xiàn)頻率是包含項(xiàng)集的事務(wù)數(shù)，稱為項(xiàng)集的頻率。如果項(xiàng)集滿足最小支持度，則稱它為頻繁項(xiàng)集。頻繁k項(xiàng)集的集合計(jì)作LK.步驟說(shuō)明(1) 制定最小支持度及最小置信度。(2)Apriori 算法使用了候選項(xiàng)集的概念 , 首先產(chǎn)生出物項(xiàng)集合 , 稱為候選項(xiàng) 集,若候選項(xiàng)集的支持度大于或等于最小支持度 , 則該候選物項(xiàng)集合為頻繁項(xiàng)集 合 (Large Itemset).(3) 在 Apriori 算法的過(guò)程中 , 首先由數(shù)據(jù)庫(kù)讀入所有的數(shù)據(jù) , 得出候選 1 項(xiàng) 集合 C1(Can

22、didate 1-itemset) 的 支持度 , 再找 出頻繁 1 項(xiàng)集合 L1(Large 1-itemset), 并利用這些頻繁 1 項(xiàng)集合的結(jié)合 , 產(chǎn)生候選 2 項(xiàng)集合 C2(Candidate 2-itemset).(4) 再掃描數(shù)據(jù)庫(kù),得出候選2項(xiàng)集合C2的支持度以后,再找出頻繁2項(xiàng)集合 L2,并利用這些頻繁2項(xiàng)集合L2的結(jié)合,產(chǎn)生候選3項(xiàng)集合C3(5) 重復(fù)掃描數(shù)據(jù)庫(kù)、與最小支持度比較 , 產(chǎn)生更高層次的頻繁項(xiàng)集合 , 再結(jié) 合產(chǎn)生下一級(jí)候選項(xiàng)集 , 直到不再結(jié)合產(chǎn)生出新的候選項(xiàng)集為止。在此算法中要不斷地重復(fù)兩個(gè)步驟 , 連接步和剪枝步。其具體內(nèi)容如下。 連接步為找 Lk, 通

23、過(guò) Lk-1 與自己連接產(chǎn)生候選 k 項(xiàng)目集的集合。該候選項(xiàng)的集合記 做G。為方便起見(jiàn)，Apriori假定事務(wù)或項(xiàng)集中的項(xiàng)按字典次序排序。對(duì)于(k-1)項(xiàng)集l i，意味著將項(xiàng)排序，使得I i1< l i2< , < l ik-1。設(shè)l i和丨2是Lk-i中 的項(xiàng)集。記號(hào)lij表示li的第j項(xiàng)。執(zhí)行連接Lk-i ?L-i,其中Lk-i的元素l i和丨2 是可以連接的，如果(l i1 =l 21) n (l i2 =l 22) n, (l ik-2 =l 2k-2)n(l ik-i<l 2k-i) 連接產(chǎn)生的結(jié)果項(xiàng)集是 l iil i2,l ik- il 2k- i 。剪枝

24、步G的成員可以是也可以不是頻繁的，但所有的頻繁k項(xiàng)目集都包含在G中。 掃描數(shù)據(jù)庫(kù),確定G中每個(gè)候選集計(jì)數(shù)(設(shè)置一個(gè)標(biāo)志位Flag)。從而確定Lk (即 根據(jù)定義，計(jì)算值不小于最小支持度計(jì)數(shù)的所有候選是頻繁的，從而屬于Lk)。2.2.2聚類分析聚類分析將數(shù)據(jù)劃分成有意義或有用的組。 聚類分析僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的 描述對(duì)象及其關(guān)系的信息， 將數(shù)據(jù)對(duì)象分組。 其目標(biāo)是， 組內(nèi)的對(duì)象相互之間是 相似的（相關(guān)的） ，而不同組中的對(duì)象是不同的 （不相關(guān)的 ） 。組內(nèi)的相似性越大， 組間差別越大，聚類就越好。聚類的方法通常有K均值算法，凝聚層次聚類，DBSCANK均值是基于原型的，劃分的聚類技術(shù)。它試圖發(fā)現(xiàn)

25、用戶指定個(gè)數(shù)（K）的簇 基本 K 均值的算法為：1）選擇 K 個(gè)點(diǎn)作為初始質(zhì)心。2）repeat3）將每個(gè)點(diǎn)指派到最近的質(zhì)心，形成 K 個(gè)簇。4）重新計(jì)算每個(gè)簇的質(zhì)心。5）until 質(zhì)心不發(fā)生變化。凝聚層次聚類：首先將每一個(gè)點(diǎn)作為單點(diǎn)簇； 然后重復(fù)的合并兩個(gè)最近的簇， 直到產(chǎn)生單個(gè)的，包含所有點(diǎn)的簇。具體算法如下：1）將每一個(gè)點(diǎn)分為一個(gè)簇。2）計(jì)算鄰近度矩陣。3）repeat4）合并最接近的兩個(gè)簇。5）更新鄰近度矩陣，以反映新的簇與原來(lái)簇之間的鄰近性。6）until 剩下需要個(gè)數(shù)的簇。步驟 2 中計(jì)算兩個(gè)點(diǎn)的鄰近度的方法很多， 最常用的是計(jì)算歐幾米德距離， 平方歐幾米德距離，夾角余弦，皮爾遜

26、相關(guān)系數(shù)等。步驟 4 中合并最接近的兩個(gè)簇可以有多種選擇方案： 組間連接，合并兩類的結(jié)果使所有原本屬于兩類的兩兩點(diǎn)對(duì)之間的平均距離 最小。組內(nèi)連接，兩類合并為一類后，類中所有點(diǎn)與點(diǎn)之間的平均距離最小。 最短距離法，兩類之間的最近點(diǎn)代表兩類的距離。最遠(yuǎn)距離法，兩類之間的最遠(yuǎn)點(diǎn)代表兩類的距離廠圖2.3組間距離基于圖的定義在圖2.3中，如果用a, b 之間的距離代表組 A, B之間的距離，則是最 短距離法，如果用c, d之間的距離代表組A ,B之間的距離，則是最遠(yuǎn)距離法。除了這4種常用方法以外還有重心法，中位數(shù)法，ward法.DBSCAN是一種產(chǎn)生劃分聚類的基于密度的聚類算法，簇的個(gè)數(shù)由算法自動(dòng) 地

27、確定。低密度區(qū)域中的點(diǎn)被視為噪音而忽略。因此DBSCAN不產(chǎn)生完全聚類。3數(shù)據(jù)挖掘在社會(huì)網(wǎng)絡(luò)分析中的應(yīng)用在2.2中已經(jīng)說(shuō)過(guò)，數(shù)據(jù)挖掘任務(wù)可分為描述型 (descriptive) 任務(wù)和預(yù)測(cè) 型(predictive)任務(wù)兩類：描述型數(shù)據(jù)挖掘任務(wù)試圖刻畫和歸納數(shù)據(jù)庫(kù)中數(shù)據(jù)的總體特性；而預(yù)測(cè)型數(shù)據(jù)挖掘任務(wù)則試圖根據(jù)以往數(shù)據(jù)中包含的經(jīng)驗(yàn)，預(yù)測(cè)新的條件下發(fā)生的事件。社會(huì)網(wǎng)絡(luò)分析的任務(wù)也不過(guò)這兩種，一類從社會(huì)網(wǎng)絡(luò)中發(fā)現(xiàn) 社會(huì)的特性，另一類利用已經(jīng)建好的網(wǎng)絡(luò)模型， 對(duì)某些情況進(jìn)行預(yù)測(cè)。對(duì)于這兩 類任務(wù)，傳統(tǒng)的數(shù)據(jù)挖掘算法已經(jīng)有許多方法，關(guān)系數(shù)據(jù)挖掘的方法中既有從 ILP中發(fā)展而來(lái)的算法，也有通過(guò)將原有算法

28、改進(jìn)后形成的算法。特別是關(guān)于連接挖掘(Link Mining)的算法能夠很好地解決社會(huì)網(wǎng)絡(luò)分析的任務(wù)。下面簡(jiǎn)單介紹幾類適用于社會(huì)網(wǎng)絡(luò)分析的數(shù)據(jù)挖掘算法：3.1基于相似度度量方法數(shù)據(jù)挖掘中的許多方法基于相似度度量，例如k-近鄰算法和一些聚類算法， 以及在一些排序任務(wù)之中給出一個(gè)評(píng)價(jià)準(zhǔn)則。相似度的定義是這類算法中的核心步驟。相似度的定義是和問(wèn)題相關(guān)的，同一個(gè)的數(shù)據(jù)集在不同的任務(wù)下最佳的相 似度的定義很有可能是不同的。很多的時(shí)候很難選取一個(gè)適合的相似度度量，尤 其當(dāng)屬性數(shù)目多，并且和目標(biāo)任務(wù)的關(guān)系不明確的時(shí)候。 但是，如果能夠給出合 適的相似度度量，這類算法具有很好的直觀解釋。相似性度量在聯(lián)系預(yù)測(cè)中

29、應(yīng)用聯(lián)系預(yù)測(cè)是判斷兩個(gè)行動(dòng)者之間是否存在某種聯(lián)系。在社會(huì)網(wǎng)絡(luò)G中，相似度度量函數(shù)對(duì)于每個(gè)結(jié)點(diǎn)對(duì)x, y給出一個(gè)存在聯(lián)系的可能性score(x, y)。 在有些應(yīng)用中，該函數(shù)可以看作是根據(jù)網(wǎng)絡(luò) G的拓?fù)浣Y(jié)構(gòu)，對(duì)每個(gè)結(jié)點(diǎn)x和y 計(jì)算了他們之間的相似程度。而在有些社會(huì)網(wǎng)絡(luò)分析任務(wù)中，這個(gè)權(quán)重并非是計(jì) 算結(jié)點(diǎn)間的相似程度，而是為了特別的目標(biāo)進(jìn)行適當(dāng)?shù)男薷摹?這些權(quán)重有的基于 結(jié)點(diǎn)的臨近結(jié)點(diǎn)(node neighborhoods)，有的基于所有路徑的集成(Ensemble of all paths) 。 基于臨近結(jié)點(diǎn)如果兩個(gè)作者的共事者有很大的交集，他們將來(lái)進(jìn)行合作的可能性將大于兩 個(gè)基本沒(méi)有相同共事者

30、的作者。兩個(gè)有著交疊的社交圈的人也比其他人更有可能 成為朋友。從這樣的直覺(jué)觀察出發(fā)，結(jié)點(diǎn)x和結(jié)點(diǎn)y在未來(lái)發(fā)生聯(lián)系的可能性與 他們的臨近結(jié)點(diǎn)有關(guān)。對(duì)于結(jié)點(diǎn) x，用丨(x)表示x在圖G中的近鄰。有一些方 法通過(guò)度量:(x)和:(y)的相交程度作為結(jié)點(diǎn)x和結(jié)點(diǎn)y之間出現(xiàn)聯(lián)系的可能 性。 公共近鄰(commomeighbors )用近鄰交集包含元素的數(shù)目作為衡量交疊程 度的標(biāo)準(zhǔn)是最為直接的想法，即定義：score(x, y):二-(x)廠jyI Jaccard系數(shù)(Jaccard coefficient)Jaccard系數(shù)是借鑒了信息檢索中常使用的相似性度量，(、吋吋score(x，”：(x): yI

31、 Adamic/Adar方法(Adamic/Adar Method) 以上兩種方法都是簡(jiǎn)單的計(jì)數(shù)， 將所有的近鄰?fù)葘?duì)待，而 Adamic/Adar方法則考慮了近鄰的性質(zhì)，進(jìn)行了加 權(quán)1score(x,y):=22 z印刃仃申 »)I 偏好聯(lián)結(jié)(Preferential attachment)非常適用于網(wǎng)絡(luò)的增長(zhǎng)模型。它基于 網(wǎng)絡(luò)中從結(jié)點(diǎn)x增加一條邊的概率正比于結(jié)點(diǎn)x當(dāng)前的近鄰數(shù)目。即當(dāng)前近鄰 多的結(jié)點(diǎn)，更可能產(chǎn)生新的連接。score(x, y) := F(x) F(y)該公式也同時(shí)說(shuō)明了在無(wú)尺度網(wǎng)絡(luò)中已經(jīng)獲得連接的節(jié)點(diǎn)有更大的能力去 獲取更多的連接，正是這種結(jié)構(gòu)產(chǎn)生了無(wú)尺度網(wǎng)絡(luò)中的

32、一些特殊的中心節(jié)點(diǎn)。 基于集成所有路徑在某些應(yīng)用中，兩個(gè)結(jié)點(diǎn)間最短路徑距離往往不能準(zhǔn)確地刻畫兩個(gè)結(jié)點(diǎn)的相 似度。因而，有一系列的方法考慮通過(guò)集成兩個(gè)結(jié)點(diǎn)間所有的路徑的方式來(lái)定義 它們的相似度。I Katz方法(Katz method)給短路徑更高的權(quán)重，然后將所有的路徑加起來(lái)cdscore(x, y):八 ：1 paths%：i =1其中，path&打是G中結(jié)點(diǎn)x到結(jié)點(diǎn)y所有長(zhǎng)度為l的路徑。 l 如果選 取得很小，這個(gè)度量和公共近鄰產(chǎn)生的結(jié)果比較相似，因?yàn)殚L(zhǎng)度大的路徑對(duì)于和的貢獻(xiàn)非常小。 命中時(shí)間(Hitting time )在G上隨機(jī)游動(dòng)(Randonwalk)是指從圖G中 結(jié)點(diǎn)x開(kāi)

33、始，反復(fù)地移動(dòng)到x的近鄰中均一地隨機(jī)選出的一個(gè)近鄰。 從結(jié)點(diǎn)x 到結(jié)點(diǎn)y的命中時(shí)間Hx,y就是指從結(jié)點(diǎn)x開(kāi)始通過(guò)隨機(jī)游動(dòng)到結(jié)點(diǎn)y的期望移 動(dòng)次數(shù)。 通勤時(shí)間(Commuteime )由于命中時(shí)間通常不具有對(duì)稱性，有時(shí)采用通勤 時(shí)間作為距離度量，其定義為Cx,y：=Hx,y Hy，xI SimRa nk是下面遞歸定義的不動(dòng)點(diǎn)：兩個(gè)結(jié)點(diǎn)相似的程度取決于他們聯(lián)結(jié)到相似的近鄰。數(shù)值上，定義 score ( x , x ):二1score(x, y)“ 外警仁e(a,b)其中 0,1。這里只列出上面幾種定義，其實(shí)根據(jù)不同的應(yīng)用，還有很多不同的變種。并 不存在某一種度量?jī)?yōu)于其它各種度量。必須結(jié)合不同的應(yīng)用

34、來(lái)進(jìn)行適當(dāng)?shù)倪x取， 這個(gè)是基于度量方法的一個(gè)不足。3.2基于統(tǒng)計(jì)的方法現(xiàn)階段統(tǒng)計(jì)關(guān)系學(xué)習(xí)方面的主要針對(duì)于在關(guān)系數(shù)據(jù)中的學(xué)習(xí)概率模型帶來(lái) 的挑戰(zhàn)的研究。特別地，我們經(jīng)常要進(jìn)行研究究竟關(guān)系數(shù)據(jù)特征如何影響由精確 學(xué)習(xí)所帶來(lái)的統(tǒng)計(jì)推斷，研究者們我們提出集中連接度(concentrated linkage )，程度差異(degree disparity ),關(guān)系自相關(guān)(relational autocorrelation )三方面的特征，并且從這三方面來(lái)探討他們?nèi)绾卧趯W(xué)習(xí)算法 中產(chǎn)生的病態(tài)行為1。為了更加充分解釋這一研究，關(guān)系數(shù)據(jù)特征如下：集中連接度(concentrated linkage )真正的

35、關(guān)系數(shù)據(jù)集能夠表示連接度 在不同類型的對(duì)象中的顯著非一致性。在不同的情形下在關(guān)系數(shù)據(jù)集中有著不同 的集中連接度，比如在電影中就會(huì)有許多電影連接許多的演員，如圖3.1左。但是在上市公司中每個(gè)上市公司只可能連接到極少數(shù)的會(huì)計(jì)事務(wù)所，如3.1右。低連接度高連接度圖3.1集中連接度程度差異(degree disparity )另一個(gè)關(guān)系數(shù)據(jù)集的特性便是程度差異。這一特性的產(chǎn)生往往是不同類的對(duì)象有交大的差異程度。 圖3.2直觀的顯示了程 度差異。在不同的數(shù)據(jù)集中均發(fā)現(xiàn)了相似的程度差異。例如在不同行業(yè)中貿(mào)易公 司的法人數(shù)量差異和大學(xué)網(wǎng)站中不同類型網(wǎng)頁(yè)中的超連接數(shù)量的不同。無(wú)程度差異咼程度差異圖3.2程度差

36、異關(guān)系自相關(guān)(relational autocorrelation ) 自相關(guān)是在不同關(guān)聯(lián)對(duì)象 中相同屬性的價(jià)值相關(guān)性。例如，在時(shí)間t+1的屬性值對(duì)于在時(shí)間t的該屬性值 就具有很高的相關(guān)性。類似，我們定義了關(guān)系自相關(guān)來(lái)描述在鄰近表中的變量值 的相關(guān)性。例如票房收入與導(dǎo)演關(guān)系緊密(關(guān)聯(lián)系數(shù)為0.65 )，但與演員關(guān)系較小(關(guān)聯(lián)系數(shù)為0.17)。圖3.3直觀的顯示了關(guān)系相關(guān)性。低相關(guān)性高相關(guān)性圖3.3關(guān)系相關(guān)性關(guān)系數(shù)據(jù)的這三個(gè)特征使得建立出優(yōu)秀的統(tǒng)計(jì)模型需要考慮更多的方面。統(tǒng)計(jì)關(guān)系學(xué)習(xí)(Statistical Relational Learning)是將統(tǒng)計(jì)的方法和數(shù)據(jù)的關(guān)系表示結(jié)合起來(lái)的一類算法

37、，它關(guān)注數(shù)據(jù)的聯(lián)合概率分布。統(tǒng)計(jì)關(guān)系學(xué)習(xí) 發(fā)展很快，很多模型被提出，主要有 PRM(Probabilistic Relatio nal Models), RMN(Relational Markov Networks) , SLR(Structural Logic Regression), RDM(Relatio nal Depe ndency Networks), MLN(Markov Logic Networks) 。這些 統(tǒng)計(jì)關(guān)系學(xué)習(xí)的模型就是針對(duì)關(guān)系數(shù)據(jù)建立的，因而可以很好地描述社會(huì)網(wǎng)絡(luò)， 進(jìn)而完成所需的分析任務(wù)?；诮y(tǒng)計(jì)的算法往往因?yàn)樾枰獌?yōu)化的參數(shù)較多，計(jì)算開(kāi)銷相對(duì)較大。MLN(Mar

38、kov Logic Networks)3Richardson和Domingos希望通過(guò)MLN將概率和以及邏輯整合在同一個(gè) 表示之中。因?yàn)楦怕誓Ｐ湍軌蚝芎锰幚聿淮_定性，而邏輯表示能夠簡(jiǎn)潔地表示知識(shí)。MLN將馬爾可夫網(wǎng)和一階邏輯結(jié)合起來(lái)馬爾可夫網(wǎng)描述了一組隨機(jī)變量X =(X1,X2,Xn).的聯(lián)合概率分布。通常，采用log-linear模型表示為:P(X1=x)expC Wjfj(x)Zj其中，Z是規(guī)范化項(xiàng)，fj(x)是狀態(tài)x的特征屬性，(即定義域?yàn)?的函數(shù))馬爾可夫邏輯中的一個(gè)公式由一個(gè)一階邏輯公式及相應(yīng)的權(quán)重組成。 一組馬 爾可夫邏輯公式所做成的集合就被稱為馬爾可夫邏輯網(wǎng)絡(luò)，它定義了所有可能的

39、 變?cè)≈到M合的概率分布。下面給出它的形式化定義：一個(gè)馬爾可夫邏輯網(wǎng)絡(luò)L是一組二元組(fj,wj，其中fi是一個(gè)一階邏輯公 式，Wi是一個(gè)實(shí)數(shù)值。它同一個(gè)有限的常量集合 C =g,C2,通過(guò)下面的兩 條準(zhǔn)則共同定義了一個(gè)馬爾可夫網(wǎng) M l,c :1. L中出現(xiàn)的所有謂詞的每個(gè)可能的取值對(duì)應(yīng)于 M L,c中的一個(gè)二值結(jié)點(diǎn)。 結(jié)點(diǎn)值為1表示其對(duì)應(yīng)的謂詞取真。2. L中的每一個(gè)公式 Fi的每一種取值對(duì)應(yīng)應(yīng)于M l,c中的一個(gè)特征屬性。 該特征屬性取1表示其對(duì)應(yīng)的公式值為真。該特征屬性的權(quán)重就是L中Fi所對(duì) 應(yīng)的wi。有些社會(huì)網(wǎng)絡(luò)模型可以看作是一個(gè)馬爾可夫網(wǎng)絡(luò)，而且可以簡(jiǎn)單地用類似x-y-vR(x,y)二(A(x,v)二 A(y,v)的語(yǔ)句來(lái)表示，其中x，y表示行動(dòng)者，R (x, y)表示它們之間的關(guān)系，A(x, v)表示x的一個(gè)屬性，語(yǔ)句的權(quán)重表示了結(jié)點(diǎn)間的關(guān)系和該屬性相似性之間的 關(guān)聯(lián)程度。例如，一個(gè)表達(dá)朋友之間傾向于有相同的吸煙習(xí)慣就可以簡(jiǎn)單地表達(dá) 為 x-yFrie nds(x,y)= (Smoke$x)= Smoke$y)3.3 基于