中國汽車技術(shù)研究中心 王文斌 白 辰 田 源

基于三角聚集度的社區(qū)發(fā)現(xiàn)標(biāo)準(zhǔn)在汽車消費(fèi)人群分析的適用性研究

中國汽車技術(shù)研究中心 王文斌 白 辰 田 源

為解決汽車企業(yè)對于不同類型汽車消費(fèi)人群的分析調(diào)研需求，本文研究了關(guān)系網(wǎng)絡(luò)中消費(fèi)人群的社區(qū)發(fā)現(xiàn)問題，根據(jù)圖數(shù)據(jù)挖掘中三角型的特性，提出基于三角聚集度的社區(qū)發(fā)現(xiàn)標(biāo)準(zhǔn)。研究發(fā)現(xiàn)該方法對于車企的消費(fèi)人群劃分判別具有很好的適用性。

汽車消費(fèi)人群分析；社區(qū)發(fā)現(xiàn)；三角聚集度

1 引言

近年來，隨著網(wǎng)絡(luò)和各種電子設(shè)備的日益普及，越來越多人都參與到互聯(lián)網(wǎng)的信息交流中去。在眾多的網(wǎng)站中，Twitter、Facebook、微博、人人網(wǎng)、以及微信朋友圈等一系列社交網(wǎng)絡(luò)作為近年來廣泛使用的交流平臺，如雨后春筍般紛紛涌現(xiàn)出來，面向各個領(lǐng)域拓展自己的用戶。而那些現(xiàn)實(shí)生活中的人們因?yàn)楦髯缘呐d趣愛好、地理位置、工作性質(zhì)等原因所組成不同的“真實(shí)”群體，如何在這一“虛擬”的社交網(wǎng)絡(luò)中將其群體（或稱其為“社區(qū)”）標(biāo)注提取出來，并挖掘這些群體的共同特點(diǎn)，發(fā)現(xiàn)知識、創(chuàng)造價值，已經(jīng)成為社交網(wǎng)絡(luò)數(shù)據(jù)挖掘領(lǐng)域的一項(xiàng)研究熱點(diǎn)，“社區(qū)發(fā)現(xiàn)”作為一個新興的研究領(lǐng)域，也就因此成為研究者廣泛關(guān)注的問題。

2 社區(qū)發(fā)現(xiàn)

社交網(wǎng)絡(luò)反映了現(xiàn)實(shí)生活中的這樣一個特點(diǎn)：人們都會因?yàn)楦髯缘呐d趣愛好，或所在地理位置、工作性質(zhì)等原因而形成各種各樣的群體。而在社交網(wǎng)絡(luò)中，這些群體都會因?yàn)楸舜说氖熳R或共同關(guān)注了某人或某物而有著較其他陌生人相比，更為頻繁的交流。那么利用這種關(guān)系，是否可以在社交平臺中復(fù)雜而龐大的用戶群體中找出這些現(xiàn)實(shí)的群體呢？因?yàn)槿粽页鲞@些群體，必能通過這些群體的特征，利用數(shù)據(jù)挖掘的思想，找出類似“啤酒—尿布”的規(guī)律或知識，從而產(chǎn)生價值。

面對這個問題，學(xué)者們紛紛展開研究，“社交網(wǎng)絡(luò)挖掘”便成為數(shù)據(jù)挖掘領(lǐng)域一個新的重要分支，而社區(qū)發(fā)現(xiàn)是社交網(wǎng)絡(luò)挖掘的重點(diǎn)研究問題。例如在著名社交網(wǎng)站Facebook中截取的斯坦福大學(xué)學(xué)生之間的部分好友關(guān)系圖，就可以通過這種關(guān)系劃分出他們之間的關(guān)系：或同畢業(yè)于一個高中，或一同參加了一個暑期夏令營，或?qū)儆诓煌纳鐖F(tuán)。

當(dāng)然，社交網(wǎng)絡(luò)這一概念不僅僅指互聯(lián)網(wǎng)上的交友網(wǎng)站，它可以看作是由圖表示的異構(gòu)關(guān)系數(shù)據(jù)集?，F(xiàn)實(shí)世界中，在科技、商業(yè)、經(jīng)濟(jì)和生物等方面，都有社交網(wǎng)絡(luò)的存在，比如汽車企業(yè)與客戶間的購買關(guān)系，汽車論壇中車友間信息的交流，以至萬維網(wǎng)、電力網(wǎng)格、計(jì)算機(jī)病毒傳播、電話交互圖以及科學(xué)家的合著關(guān)系、論文的引用網(wǎng)絡(luò)；生物學(xué)領(lǐng)域中的流行病學(xué)網(wǎng)絡(luò)，細(xì)胞與新陳代謝網(wǎng)絡(luò)和食物網(wǎng)絡(luò)等，都是社區(qū)發(fā)現(xiàn)的研究對象[4]。

但在這一社區(qū)發(fā)現(xiàn)這一新興領(lǐng)域進(jìn)行算法的提出、對比和研究前，首先要確定一種合適的判別標(biāo)準(zhǔn)來確定這種劃分方法的好壞?，F(xiàn)在使用最多的方法是2004年由M. Newman[1]提出的計(jì)算劃分社區(qū)的modularity （模塊性），但這一劃分標(biāo)準(zhǔn)的缺點(diǎn)也很明顯，它對于小型的社區(qū)并不適用。其他標(biāo)準(zhǔn)比如R. Kannan[2]提出的連通度（conductance），也存在對于一些聚集度極佳的特殊圖形，不能準(zhǔn)確體現(xiàn)其聚集性質(zhì)的缺點(diǎn)。

3 三角聚集度

3.1 圖數(shù)據(jù)中的三角形

圖中三角形的查找和統(tǒng)計(jì)在圖數(shù)據(jù)領(lǐng)域有著廣泛的研究意義和價值。因?yàn)槿切未嬖趦蓚€重要特性——同質(zhì)和傳遞，這兩個性質(zhì)在社交網(wǎng)絡(luò)的圖數(shù)據(jù)挖掘中就起到了跟重要的作用：社交網(wǎng)絡(luò)的用戶傾向于與有用相似愛好和興趣的人建立朋友關(guān)系（在數(shù)據(jù)的角度，用戶之間擁有相似的三角形模式），這種傾向性在社交網(wǎng)絡(luò)中，主要表現(xiàn)在用戶更愿意與擁有相同朋友圈子的人成為朋友。同時，統(tǒng)計(jì)三角形也被應(yīng)用于挖掘隱藏的網(wǎng)頁主題、彭谷聚類參數(shù),以及檢測垃圾郵件。

3.2 聚集系數(shù)

其實(shí)最早在1949年R. D. Luce和A. D. Perry的一篇論文[3]中，圖中三角形的聚集度已經(jīng)在圖論中被提出并定義這一系數(shù)為圖的聚集系數(shù)，描述的是圖中的若干點(diǎn)傾向于集聚在一起的程度的一種度量。

而圖中的某一個節(jié)點(diǎn)，聚集系數(shù)表示了它相連的點(diǎn)抱成團(tuán)（完全子圖）的程度。為方便說明，這里定義在G = (V, E)中包含一系列節(jié)點(diǎn)V和連接它們的邊E。表示的第i個相鄰節(jié)點(diǎn)。表示的相鄰節(jié)點(diǎn)的數(shù)量。一個頂點(diǎn)的聚集系數(shù)等于所有與它相連的頂點(diǎn)之間所連的邊的數(shù)量，除以這些頂點(diǎn)之間可以連出的最大邊數(shù)。在無向圖中的最大邊數(shù)為，所以某一點(diǎn)的聚集系數(shù)公式表示為：

那么整個網(wǎng)絡(luò)的所有點(diǎn)聚集系數(shù)就可以定義為所有節(jié)點(diǎn)n的局部聚集系數(shù)的均值：

那么若一個圖的平均聚集系數(shù)比相同節(jié)點(diǎn)集生成的隨機(jī)圖有顯著提高，但平均最短距離卻與相應(yīng)隨機(jī)生成的隨機(jī)圖十分相近，那么這個圖被認(rèn)為是小世界的社交網(wǎng)絡(luò)圖。有著更高平均聚集系數(shù)的社交網(wǎng)絡(luò)被發(fā)現(xiàn)有著模塊結(jié)構(gòu)，同時在不同節(jié)點(diǎn)中還有更小的平均距離。

3.3 三角聚集度

根據(jù)三角形在圖數(shù)據(jù)中的性質(zhì)以及聚集系數(shù)這一指標(biāo)，提出一種新的社區(qū)發(fā)現(xiàn)的度量標(biāo)準(zhǔn)——三角聚集度（Triangular-Clustering Coeffcient）

其公式定義如下：

在定義了節(jié)點(diǎn)對于社區(qū)的歸屬度的計(jì)算方法后，根據(jù)式（3.1）的思路，將這個社區(qū)內(nèi)所有點(diǎn)的歸屬度取其平均值，得到計(jì)算這個社區(qū)C的整體的凝聚程度的表達(dá)式：

而后便可通過式（3.2）的思路確定該劃分對于整張圖來說劃分優(yōu)劣的的一個指標(biāo)即將各個社區(qū)根據(jù)其大小加權(quán)后平均即可：

3.4 度量標(biāo)準(zhǔn)分析

一個好的社區(qū)發(fā)現(xiàn)度量標(biāo)準(zhǔn)需要能很好的反映出根據(jù)此標(biāo)準(zhǔn)評判出的優(yōu)秀社區(qū)的一些特點(diǎn)和屬性，這些屬性可以保證所劃分出的社區(qū)內(nèi)節(jié)點(diǎn)的稠密性和結(jié)構(gòu)特點(diǎn)。下面簡單對一個優(yōu)秀社區(qū)的四個屬性進(jìn)行簡單說明及分析：

屬性1：有良好的內(nèi)部結(jié)構(gòu)

在M. Newman等人之前的研究中已經(jīng)表明，一個優(yōu)秀社區(qū)的一個最主要的特征就是有一個數(shù)值非常大的聚集系數(shù)。社交網(wǎng)絡(luò)構(gòu)成的圖數(shù)據(jù)與普通的隨機(jī)生成的圖的一個最大的不同也就是擁有非常多的三角形結(jié)構(gòu)。因此，三角聚集度將計(jì)算三角形的個數(shù)作為計(jì)算一個社區(qū)聚集程度的一個最重要的評判標(biāo)準(zhǔn)。

屬性2：社區(qū)的凝聚力應(yīng)隨節(jié)點(diǎn)增多而增長

在一個優(yōu)秀的度量標(biāo)準(zhǔn)中，當(dāng)一個新的節(jié)點(diǎn)被計(jì)算應(yīng)當(dāng)加入這個社區(qū)時，這個社區(qū)整體的凝聚程度應(yīng)該是能夠得到增強(qiáng)的。放到實(shí)際情景中，若想加入一個社區(qū)，這個節(jié)點(diǎn)需要與這個社區(qū)內(nèi)部很多的節(jié)點(diǎn)有聯(lián)系，這個社區(qū)越大，需要聯(lián)系的節(jié)點(diǎn)也就越多，它與這個社區(qū)的聯(lián)系才能體現(xiàn)出越強(qiáng)，越應(yīng)該屬于這個社區(qū)，否則，這個社區(qū)整體的凝聚力將會因?yàn)樗档?。用函?shù)形式表示，若節(jié)點(diǎn)x應(yīng)屬于社區(qū)C，則。

屬性3：社區(qū)中不存在橋結(jié)構(gòu)

在一個社區(qū)中若存在橋結(jié)構(gòu)，則該社區(qū)的凝聚程度將會非常弱，因?yàn)槌诉@條邊之外，兩個節(jié)點(diǎn)集之間沒有任何的聯(lián)系。因此，一個優(yōu)秀的社區(qū)中不應(yīng)存在橋結(jié)構(gòu)。

屬性4：社區(qū)中不存在割點(diǎn)

與橋結(jié)構(gòu)類似，當(dāng)在一個社區(qū)中存在若干個割點(diǎn)的話，若將此割點(diǎn)以及與之相連的邊刪除，則該社區(qū)立刻回分解成兩個互不關(guān)聯(lián)的子圖。所以割點(diǎn)也是一個社區(qū)中弱連接的體現(xiàn)，一個優(yōu)秀的社區(qū)中，是不應(yīng)該存在割點(diǎn)這一結(jié)構(gòu)的。

可見，三角聚集度滿足以上的四種性質(zhì)，同時用虛擬的小型社區(qū)數(shù)據(jù)計(jì)算其三角聚集度。如圖2所示，構(gòu)建了從簡單稀疏的社區(qū)到復(fù)雜稠密的不同8個社區(qū)（從a到h），其三角聚集度的值由低至高，體現(xiàn)了這一度量標(biāo)準(zhǔn)能很好的體現(xiàn)社區(qū)的稠密程度。

4 總結(jié)

通過建立汽車消費(fèi)人群的圖數(shù)據(jù)關(guān)系模型，研究了關(guān)系網(wǎng)絡(luò)中消費(fèi)人群的社區(qū)發(fā)現(xiàn)問題以及圖數(shù)據(jù)挖掘中三角型的特性，并通過三角形的聚集系數(shù)的定義，提出基于三角聚集度的社區(qū)發(fā)現(xiàn)標(biāo)準(zhǔn)，并驗(yàn)證了該標(biāo)準(zhǔn)對于車企的消費(fèi)人群劃分判別的適用性。

本文中提出的標(biāo)準(zhǔn)對于大數(shù)據(jù)下的汽車社區(qū)網(wǎng)絡(luò)還沒有針對性其的成型算法實(shí)現(xiàn)，設(shè)計(jì)構(gòu)思一種高效的使用三角聚集度計(jì)算的算法是今后的研究方向。

[1]M．Newman and M．Girvan．Finding and evaluating community structure in networks． Phy． Rev． E, 69(2):026113, 2004．

[2]R．Kannan et al．On clusterings:Good,bad and spectral．JACM, 51(3):497{515,2004．

[3]李曉佳,張鵬,狄增如等．復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[J]．復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2008,5(3):19-42

[4]谷峪,于戈,鮑玉斌．大規(guī)模圖數(shù)據(jù)的分布式處理2015,ISBN-9787302420729．