數(shù)據(jù)挖掘技術(shù)在社交關(guān)系分析中的應(yīng)用

鄭詩(shī)慧+李卓+賈蕊+王杉

摘要：該文對(duì)社交關(guān)系和數(shù)據(jù)挖掘的方法進(jìn)行了介紹和分析，同時(shí)也結(jié)合具體實(shí)例說明了數(shù)據(jù)挖掘技術(shù)在社交關(guān)系分析中的應(yīng)用。

關(guān)鍵詞：數(shù)據(jù)挖掘、社交關(guān)系

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）04-0029-03

1 概述

我們生活在一個(gè)信息過量的數(shù)據(jù)時(shí)代。每天來自各行各業(yè)的數(shù)據(jù)都會(huì)不斷地注入到我們的計(jì)算機(jī)網(wǎng)絡(luò)或各種存儲(chǔ)設(shè)備中，而我們要做的就是從這些海量的數(shù)據(jù)里發(fā)現(xiàn)有價(jià)值的信息，并把這些信息轉(zhuǎn)換成有用的知識(shí)，從而提高信息利用率。

早期的數(shù)據(jù)收集由于受到種種方面的限制，通常收集范圍僅局限在一個(gè)很小的范圍內(nèi)，而分析時(shí)一般只會(huì)采用人工的方式僅借助一些圖和概率的知識(shí)從中分析一些很簡(jiǎn)單的信息，在數(shù)據(jù)量小的同時(shí)，信息有效性并不高。而現(xiàn)如今隨著科技的發(fā)展，數(shù)據(jù)挖掘技術(shù)自然進(jìn)化而來，它可以幫助我們更加便捷的分析更為龐大的數(shù)據(jù)。

現(xiàn)如今的社會(huì)上存在著這樣的一種現(xiàn)象，每個(gè)個(gè)體之間都存在著相互的聯(lián)系和依賴，并且這種關(guān)系對(duì)于個(gè)體有著很重要的影響。可以形象一點(diǎn)的說，社交關(guān)系中的個(gè)體就像互聯(lián)網(wǎng)中的節(jié)點(diǎn)一樣互相連接。所以，我們可以通過一種網(wǎng)絡(luò)模型來描繪當(dāng)前的社交關(guān)系，網(wǎng)絡(luò)中的節(jié)點(diǎn)表示個(gè)體，連接則表示兩個(gè)節(jié)點(diǎn)之間的關(guān)系。

本文結(jié)合具體實(shí)例，通過分析社交關(guān)系，挖掘出某個(gè)時(shí)間段內(nèi)，兩個(gè)人之間相遇、交友、興趣、生活規(guī)律等相遇的概率，將這些數(shù)據(jù)記錄下來進(jìn)行研究，從而說明數(shù)據(jù)挖掘在社交關(guān)系分析中的應(yīng)用。

2 數(shù)據(jù)挖掘方法

數(shù)據(jù)挖掘，通常又稱為數(shù)據(jù)庫(kù)中發(fā)現(xiàn)知識(shí)（Knowledge Discovery in Databases， KDD），就是從大量的、不完全的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含在其中的，人們事先不知道的，但是又潛在有用的信息和知識(shí)的過程[1]。

常用的數(shù)據(jù)挖掘方法有四種：關(guān)聯(lián)規(guī)則分析（Associations）、聚類分析（Clustering）、分類分析（Classifiers）、序列模式分析（Sequential Patterns）。這里主要介紹前兩種方法。

1） 關(guān)聯(lián)規(guī)則分析（Associations）[1]

關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)涵式，其中X和Y分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo)和后繼，關(guān)聯(lián)規(guī)則XY存在支持度和置信度。而且，挖掘關(guān)聯(lián)規(guī)則的問題也可以歸結(jié)為挖掘頻繁項(xiàng)集。

一般而言，關(guān)聯(lián)規(guī)則的挖掘分為兩步：一是找出所有的頻繁項(xiàng)集，這些項(xiàng)集的每一個(gè)頻繁出現(xiàn)的次數(shù)至少與預(yù)定義的最小支持計(jì)數(shù)一樣；二是由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小置信度。

關(guān)聯(lián)規(guī)則的主要算法是Apriori算法，通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項(xiàng)集。其利用循環(huán)漸進(jìn)的方式，找出數(shù)據(jù)庫(kù)中項(xiàng)目的關(guān)系，以形成規(guī)則。過程大致分為兩步，一為連接步（類似于矩陣運(yùn)算），二為剪枝步（去掉沒用的中間結(jié)果）。

2） 聚類分析（Clustering）[1]

聚類分析簡(jiǎn)稱聚類，是一個(gè)把數(shù)據(jù)對(duì)象（或觀測(cè)）劃分成子集的過程。每個(gè)子集是一個(gè)簇（cluster），使得簇中的對(duì)象彼此相似，但與其他簇中的對(duì)象不相似。由聚類分析產(chǎn)生的簇的集合稱作一個(gè)聚類。此種語境下，相同的數(shù)據(jù)集上，不同的聚類方法可能產(chǎn)生不同的聚類。

聚類的方法通常有K均值算法、凝聚層次聚類、DBSCAN。K均值算法是基于原型的，劃分的聚類技術(shù)，它試圖發(fā)現(xiàn)用戶指定個(gè)數(shù)（K）的簇。凝聚層次聚類，首先將每一個(gè)點(diǎn)作為單點(diǎn)簇，然后重復(fù)的合并兩個(gè)最近的簇，直到產(chǎn)生單個(gè)的，包含所有點(diǎn)的簇。DBSCAN是一種產(chǎn)生劃分聚類的基于密度的聚類算法，簇的個(gè)數(shù)由算法自動(dòng)地確定。低密度區(qū)域中的點(diǎn)被視為噪音而忽略，因此，DBSCAN不產(chǎn)生完全聚類。

3 社交關(guān)系分析

1）用戶和用戶之間的關(guān)系

在社交關(guān)系中，可以把每個(gè)用戶看作一個(gè)節(jié)點(diǎn)，用戶之間在某種條件下只要相遇過就算作有聯(lián)系，這種聯(lián)系作為節(jié)點(diǎn)之間的連線。用戶之間的聯(lián)系可以是多次的，也可以是零次的，并且一個(gè)用戶可以與多個(gè)用戶進(jìn)行聯(lián)系。

圖1是由5個(gè)用戶構(gòu)成的一個(gè)簡(jiǎn)單示意圖，由圖中可以看出，結(jié)點(diǎn)v1到v2有一條單向弧，值為3，說明v1用戶與v2用戶有3次聯(lián)系。結(jié)點(diǎn)v2到v3是一條雙向弧，值為1和2，說明v2用戶和v3用戶有1次聯(lián)系，v3用戶和v2用戶有2次聯(lián)系，等等。

入度是指所有指向該結(jié)點(diǎn)的弧上的值的和。而在一個(gè)有向帶值的聯(lián)系圖中，一個(gè)結(jié)點(diǎn)的入度與所有結(jié)點(diǎn)的入度和的比值α越高，就說明該用戶與其他用戶的聯(lián)系越密切，該用戶所處的地位就越重要。如圖1中，結(jié)點(diǎn)v1的入度為0，則α為0/12=0；結(jié)點(diǎn)v4的入度為1，則α為1/12=0.083；結(jié)點(diǎn)v2的入度為7，則α為7/12=0.583，等等。

出度是指所有該結(jié)點(diǎn)指向其他結(jié)點(diǎn)的所有弧上的值的和。同理，在一個(gè)有向帶值的聯(lián)系圖中，一個(gè)結(jié)點(diǎn)的出度與所有結(jié)點(diǎn)的出度和的比值β越高，就說明該用戶在聯(lián)系中越活躍。如圖1中，結(jié)點(diǎn)v1的出度為5，則β為5/14=0.357，結(jié)點(diǎn)v5的出度為2，則β為2/14=0.143，等等。

2）用戶和事件之間的關(guān)系

在社交關(guān)系中，用戶之間除了因?yàn)橄嘤龆新?lián)系以外，還會(huì)因?yàn)樽隽送瑯拥氖虑椋兄瑯拥呐d趣愛好，生活規(guī)律而產(chǎn)生聯(lián)系。這里主要考慮的是用戶之間因?yàn)樽隽送患虑槎a(chǎn)生的聯(lián)系，所以不考慮一個(gè)用戶某件事情做了多少次。

圖2是由5個(gè)用戶和3個(gè)事情構(gòu)成的一個(gè)簡(jiǎn)單示意圖，圖中的線連接用戶與事情，由圖中可以看出，v1用戶分別到e1和e2事情上有連線，說明用戶v1參與了事情e1和e2，等等。

通過圖2中，每個(gè)事情的用戶參與人數(shù)和總?cè)藬?shù)個(gè)數(shù)相比較，我們不難發(fā)現(xiàn)，在e3事情上有v2，v3，v4，v5用戶參與，且是3個(gè)事情當(dāng)中，參與的人數(shù)最多的一個(gè)事情，這就說明了這四位用戶之間因?yàn)樽隽送瑯拥氖虑?，有著相同的興趣愛好而產(chǎn)生了聯(lián)系。

4 實(shí)例

1）數(shù)據(jù)說明

本文在研究時(shí)選取的數(shù)據(jù)集[2]來自美國(guó)麻省理工學(xué)院的一個(gè)實(shí)驗(yàn)室。該份數(shù)據(jù)在進(jìn)行挖掘時(shí)，隨機(jī)選取了94個(gè)人，包括教師和學(xué)生，包括男性和女性。然后通過使用手機(jī)安裝軟件來記錄并發(fā)送一些相關(guān)的需要收集的數(shù)據(jù)內(nèi)容。整個(gè)收集過程持續(xù)了大概九個(gè)月，所收集的數(shù)據(jù)包括位置、手機(jī)的活動(dòng)（通話、短信、游戲、充電狀態(tài)等）以及每個(gè)人的自我報(bào)告等等。

2）基于相似度度量方法進(jìn)行數(shù)據(jù)挖掘

K鄰近算法，某些聚類算法都是基于相似度度量的。同一數(shù)據(jù)集，不同任務(wù)，最佳相似度往往也不同，一個(gè)合適的相似度度量會(huì)因?yàn)閷傩远?，目?biāo)任務(wù)不明確而很難選取[1]。但是，當(dāng)找到合適的相似度度量之后，這類方法便很好解釋了。

如果通過數(shù)據(jù)分析發(fā)現(xiàn)某兩個(gè)用戶在一些事情上有很大的交集，那么他們將來成為朋友的可能性會(huì)遠(yuǎn)遠(yuǎn)大于兩個(gè)沒有事情交集的用戶。同理，有著同樣交友圈的兩個(gè)人也會(huì)比其他人有更大的機(jī)會(huì)成為好朋友。再或者，兩個(gè)本身沒有交集的人，因?yàn)楣餐J(rèn)識(shí)一個(gè)好友，或者有著相同的興趣愛好，而在將來的某一天產(chǎn)生交集也成為好朋友。

圖3和圖4就是本文所研究的數(shù)據(jù)集中，關(guān)于用戶通信次數(shù)與相遇次數(shù)之間的一個(gè)關(guān)系。圖3中，坐標(biāo)橫軸是通信次數(shù)，范圍是0到300次，縱軸是相遇次數(shù)，范圍是0到4000次。從圖中不難發(fā)現(xiàn)，大部分的點(diǎn)都落到了橫軸0到50，縱軸0到500這個(gè)區(qū)間內(nèi)，不利于查看。因此，為了更加直觀方便地看到通信次數(shù)與相遇次數(shù)之間的關(guān)系，圖4是圖3中的點(diǎn)的密集范圍的一個(gè)放大，橫軸通信次數(shù)的范圍是0到150次，縱軸相遇次數(shù)的范圍是0到1000次。

通過研究數(shù)據(jù)所得到圖3和圖4中不難發(fā)現(xiàn)一個(gè)趨勢(shì)，當(dāng)兩個(gè)用戶之間交流溝通的次數(shù)越少，兩個(gè)人的相遇碰見次數(shù)也就越低。這樣的兩個(gè)人很難成為好朋友，因?yàn)樗麄冊(cè)陉P(guān)于某一個(gè)事情上并沒有多大的交集，導(dǎo)致之間并沒有多少溝通。反之，當(dāng)兩個(gè)用戶交流溝通的次數(shù)越多時(shí)，兩個(gè)人的相遇碰見次數(shù)也就越高。這樣的兩個(gè)人成為好朋友的可能性非常高，因?yàn)樗麄冎g會(huì)經(jīng)常為了共同的一個(gè)事情而進(jìn)行交流溝通以及見面。當(dāng)然，也會(huì)有一些比較例外的時(shí)候，比如兩個(gè)幾乎沒聯(lián)系的人，但是相遇次數(shù)卻非常高，這可能是因?yàn)樗麄兠刻熳谕婚g教室里上課，或者同一輛公交車回家等等。

5 觀點(diǎn)及結(jié)論

數(shù)據(jù)挖掘技術(shù)是現(xiàn)如今我們?cè)诜治龃罅繑?shù)據(jù)時(shí)不可或缺的，也是在分析社交關(guān)系這個(gè)龐大的數(shù)據(jù)集時(shí)不可或缺的。利用挖掘技術(shù)在分析數(shù)據(jù)時(shí)，可以有效地提高信息利用率，也有助于我們今后在做一些社交分享類系統(tǒng)時(shí)，提供一些非常有用的信息，提高效率。

參考文獻(xiàn)：

[1] 韓家煒，裴健. 數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2012.

[2] Nathan Eagle，PhD. The Reality Mining Data README[EB/OL].http：//realitycommons.media.mit.edu.