鄭詩慧+李卓+賈蕊+王杉

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

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

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

1 概述

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

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

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

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

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

數(shù)據(jù)挖掘，通常又稱為數(shù)據(jù)庫中發(fā)現(xiàn)知識（Knowledge Discovery in Databases， KDD），就是從大量的、不完全的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的，人們事先不知道的，但是又潛在有用的信息和知識的過程[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的蘊涵式，其中X和Y分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo)和后繼，關(guān)聯(lián)規(guī)則XY存在支持度和置信度。而且，挖掘關(guān)聯(lián)規(guī)則的問題也可以歸結(jié)為挖掘頻繁項集。

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

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

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

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

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

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

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

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

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

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

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

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

在社交關(guān)系中，用戶之間除了因為相遇而有聯(lián)系以外，還會因為做了同樣的事情，有著同樣的興趣愛好，生活規(guī)律而產(chǎn)生聯(lián)系。這里主要考慮的是用戶之間因為做了同一件事情而產(chǎn)生的聯(lián)系，所以不考慮一個用戶某件事情做了多少次。

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

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

4 實例

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

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

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

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

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

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

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

5 觀點及結(jié)論

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

參考文獻(xiàn)：

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

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