張海陽+齊俊傳+毛健

摘要：該文采用R語言作為研究工具以及聚類和決策樹等數(shù)據(jù)挖掘算法，研究如何針對社交網(wǎng)站中的用戶進(jìn)行分類，挖掘最終可指導(dǎo)網(wǎng)站優(yōu)化和提高服務(wù)質(zhì)量的客戶分類數(shù)據(jù)。采用網(wǎng)絡(luò)爬蟲從某社交網(wǎng)站中抓取數(shù)據(jù)，該文采用聚類算法中的DIANA算法對抽樣樣本計(jì)算并對數(shù)據(jù)進(jìn)行初步的簇類劃分；接著采用PAM算法對整體樣本進(jìn)行進(jìn)一步的計(jì)算并提取出大聚類，接著采用分別CART和C4.5等決策樹算法對決策樹規(guī)則進(jìn)行進(jìn)一步的研究，最終對研究結(jié)果進(jìn)行評估并用來指導(dǎo)實(shí)踐。

關(guān)鍵詞：R語言；數(shù)據(jù)挖掘；C4.5；Cart

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

隨著互聯(lián)網(wǎng)社交網(wǎng)站的繁榮和各種網(wǎng)絡(luò)應(yīng)用的不斷深入，社交網(wǎng)站已成為互聯(lián)網(wǎng)上的重要平臺應(yīng)用。伴隨社交網(wǎng)絡(luò)的發(fā)展，不同地域、性格和特質(zhì)的用戶群展現(xiàn)出了差異化的需求，面對這些群體和用戶需求，如何細(xì)分市場識別并提供差異化的服務(wù)，以幫助企業(yè)在激烈的競爭中保持老用戶，發(fā)展新用戶。本文圍繞社交網(wǎng)絡(luò)理論和客戶細(xì)分理論的研究，運(yùn)用數(shù)據(jù)挖掘工具中的決策樹算法，對社交網(wǎng)絡(luò)客戶細(xì)分進(jìn)行了深入的探討并最終得出可指導(dǎo)時間的社交網(wǎng)絡(luò)客戶細(xì)分規(guī)則。

1.1 R語言

R是一種在數(shù)據(jù)統(tǒng)計(jì)領(lǐng)域廣泛使用的語言，R語言是一種開源語言，該語言的前身是S語言，也可以說R語言是S語言的一種實(shí)現(xiàn)，R在語法上類似C語言。R是一個統(tǒng)計(jì)分析軟件，既可以進(jìn)行統(tǒng)計(jì)分析，又可以進(jìn)行圖形顯示。R能進(jìn)行復(fù)雜的數(shù)據(jù)存儲和數(shù)據(jù)處理，利用數(shù)據(jù)、向量、矩陣的數(shù)學(xué)方法進(jìn)行各種統(tǒng)計(jì)分析，并將統(tǒng)計(jì)分析結(jié)果以圖形方式展示出來，因此R也是一種統(tǒng)計(jì)制圖軟件。R內(nèi)嵌豐富的數(shù)學(xué)統(tǒng)計(jì)函數(shù)，從而使使用者能靈活的進(jìn)行統(tǒng)計(jì)分析。它可以運(yùn)行于UNIX，Windows和Macintosh的操作系統(tǒng)上，而且嵌入了一個非常方便實(shí)用的幫助系統(tǒng)。

R是一種功能強(qiáng)大的編程語言，就像傳統(tǒng)的編程語言C和JAVA一樣，R也可以利用條件、循環(huán)等編程方法實(shí)現(xiàn)對數(shù)據(jù)的各種處理，從而實(shí)現(xiàn)數(shù)據(jù)統(tǒng)計(jì)目的。R作為一種開源的軟件，被越來越多的用來代替SAS等軟件進(jìn)行數(shù)據(jù)統(tǒng)計(jì)分析。

R作為一個統(tǒng)計(jì)系統(tǒng)來使用，其中集成了用于經(jīng)典和現(xiàn)代統(tǒng)計(jì)分析的各種算法和函數(shù)，這些算法和函數(shù)是以包的形式提供的。R內(nèi)含了8個包，如果需要其他的包，可在官網(wǎng)上進(jìn)行下載安裝。

1.2 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘（Data mining），顧名思義就是從海量的數(shù)據(jù)中運(yùn)用數(shù)據(jù)挖掘算法從中提取出隱含的、有用的信息。數(shù)據(jù)挖掘涉及統(tǒng)計(jì)學(xué)、人工智能和數(shù)據(jù)庫等多種學(xué)科。近年來，隨著計(jì)算機(jī)的發(fā)展，各個領(lǐng)域積累了海量的數(shù)據(jù)，這些數(shù)據(jù)如何變廢為寶，這就需要數(shù)據(jù)挖掘的幫助。因此數(shù)據(jù)挖掘在信息產(chǎn)業(yè)界廣泛應(yīng)用，比如市場決策和分析、科學(xué)研究、智能探索、商務(wù)管理等。

數(shù)據(jù)挖掘是一個多學(xué)科的交叉領(lǐng)域，統(tǒng)計(jì)學(xué)、人工智能和數(shù)據(jù)庫等多種學(xué)科為數(shù)據(jù)挖掘提供豐富的理論基礎(chǔ)。包括統(tǒng)計(jì)學(xué)的概率分析、相關(guān)性、參數(shù)估計(jì)、聚類分析和假設(shè)檢驗(yàn)等，以及機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、模式識別、信息檢索、知識庫、并行計(jì)算、圖形學(xué)、數(shù)據(jù)庫等。同時數(shù)據(jù)挖掘也為這些領(lǐng)域提供了新的挑戰(zhàn)和機(jī)遇。例如，數(shù)據(jù)挖掘提升了源于高性能（并行）計(jì)算的技術(shù)在處理海量數(shù)據(jù)集方面性能。隨著數(shù)據(jù)挖掘的蓬勃發(fā)展，近幾年分布式技術(shù)在處理海量數(shù)據(jù)方面也變得越來越重要，尤其是Hadoop的發(fā)展極大的提高了數(shù)據(jù)挖掘的并行處理效率。

數(shù)據(jù)挖掘也同時促進(jìn)了數(shù)據(jù)挖掘算法的發(fā)展，數(shù)據(jù)挖掘算法是根據(jù)數(shù)據(jù)創(chuàng)建數(shù)據(jù)挖掘模型的方法和計(jì)算方法，算法將首先分析數(shù)據(jù)源提供的數(shù)據(jù)，根據(jù)數(shù)據(jù)的特點(diǎn)和需求建立特定的數(shù)學(xué)模型。

根據(jù)數(shù)據(jù)挖掘模型的特點(diǎn)，可以選擇相應(yīng)的算法。在選擇算法是，可根據(jù)實(shí)際情況選擇劃分聚類的算法，或選擇決策樹的算法。選擇算法的不同可能對挖掘結(jié)果有一定的影響。

數(shù)據(jù)挖掘的步驟是首先確立挖掘目標(biāo)，提出一個初步計(jì)劃，估計(jì)用到的工具和技術(shù)；第二步是數(shù)據(jù)理解，即收集原始數(shù)據(jù)，并對數(shù)據(jù)進(jìn)行描述和初步探索，檢查這些數(shù)據(jù)的質(zhì)量；第三步是數(shù)據(jù)準(zhǔn)備，包括數(shù)據(jù)選擇、清洗、合并和格式化；第四步是建立數(shù)據(jù)模型，包括選擇建模技術(shù)、測試方案設(shè)計(jì)、模型訓(xùn)練；第五步是模型評估，根據(jù)評估結(jié)果得出結(jié)論，確定是否部署該模型；第六步是模型部署；第七步是選擇算法；最后是得出結(jié)論。

1.3 C4.5算法

C4.5是一種機(jī)器學(xué)習(xí)的方法，在數(shù)據(jù)挖掘分類中應(yīng)用廣泛，它的目標(biāo)是監(jiān)督學(xué)習(xí)。C4.5是在ID3的基礎(chǔ)上衍生出來的。ID3是一種決策樹算法。ID3衍生出C4.5和CART兩種算法。

C4.5的算法思路是，在給定的數(shù)據(jù)集中，每一個元祖都是互斥的，每一個元組都能用一組屬性值來描述，每一個元組都屬于某一類別。C4.5的目標(biāo)是通過學(xué)習(xí)，建立一個從屬性值到類別的映射關(guān)系，并且這個映射能夠指導(dǎo)對新的類別進(jìn)行分類。

C4.5是一種決策樹算法，決策樹是一種樹結(jié)構(gòu)，其中每個非葉節(jié)點(diǎn)表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個葉節(jié)點(diǎn)給定一個類標(biāo)記。決策樹建立起來之后，對于一個未給定類標(biāo)記的元組，學(xué)習(xí)一條有根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑，該葉節(jié)點(diǎn)的標(biāo)記就是該元組的預(yù)測。決策樹的優(yōu)勢在于適合于探測性的知識發(fā)現(xiàn)。

圖1就是一棵典型的C4.5算法對數(shù)據(jù)集產(chǎn)生的決策樹。

表1所示，它表示的是天氣情況與去不去打高爾夫球之間的關(guān)系。

1.4 Cart算法

CART（Classification And Regression Tree），即分類回歸樹算法，該算法是一種決策樹算法，并且生成的是一棵二叉樹。Cart有兩種關(guān)鍵思想，一種是將訓(xùn)練樣本進(jìn)行二分遞歸分割建樹，即給定一個訓(xùn)練集，用二分算法將該訓(xùn)練集分成兩個子訓(xùn)練集，不斷遞歸鄉(xiāng)下分割，這樣每個非葉子節(jié)點(diǎn)都有兩個分支，所以對于第一棵子樹的葉子節(jié)點(diǎn)數(shù)比非葉子節(jié)點(diǎn)數(shù)多1，最終形成一顆二叉樹；另一種是用驗(yàn)證數(shù)據(jù)進(jìn)行剪枝。

遞歸劃分法，用類別集Y表示因變量，用X1，X2，…，XP表示自變量，通過遞歸分割的方式把關(guān)于X的P維空間分割成不重疊的矩形。

CART算法是怎樣進(jìn)行樣本劃分的呢？首先，一個自變量被選擇，例如Xi的一個值Si，若選擇Si把P維空間分為兩個部分，一部分包含的元素都滿足Xi<=Si；另一部分包含的元素都滿足Xi>Si。其次把上述分割的兩部分遞歸分割，直到把X空間劃分的每個小矩形都盡可能的是同構(gòu)的。

CART過程中第二個關(guān)鍵的思想是用獨(dú)立的驗(yàn)證數(shù)據(jù)集對根據(jù)訓(xùn)練集生長的樹進(jìn)行剪枝。CART剪枝的目的是生成一個具有最小錯誤的樹，因?yàn)橐环矫嬖跇渖蛇^程中可能存在不能提高分類純度劃分節(jié)點(diǎn)，如果使用這些異常數(shù)據(jù)進(jìn)行分類，分類的準(zhǔn)確性就會受到很大的影響。剪去這些異常數(shù)據(jù)的過程，被稱為樹剪枝。通過剪枝，可以去除這些孤立點(diǎn)和雜音，提高樹獨(dú)立于訓(xùn)練數(shù)據(jù)正確分類的能力。另一方面分類回歸樹的遞歸建樹過程存在過擬合訓(xùn)練數(shù)據(jù)。

CART用成本復(fù)雜性標(biāo)準(zhǔn)來剪枝。CART用的成本復(fù)雜性標(biāo)準(zhǔn)是分類樹的簡單誤分（基于驗(yàn)證數(shù)據(jù)的）加上一個對樹的大小的懲罰因素。成本復(fù)雜性標(biāo)準(zhǔn)對于一個數(shù)來說是Err（T）+a|L（T）|，其中a表示每個節(jié)點(diǎn)的懲罰，Err（T）是驗(yàn)證數(shù)據(jù)被樹誤分部分，L（T）是樹T的葉節(jié)點(diǎn)樹，其中a是一個變動的數(shù)字。從這個序列的樹中選擇一個在驗(yàn)證數(shù)據(jù)集上具有最小誤分的樹稱為最小錯誤樹。

2 基于R語言數(shù)據(jù)挖掘算法的客戶分類

2.1 數(shù)據(jù)準(zhǔn)備

本研究采用的社交網(wǎng)絡(luò)數(shù)據(jù)均來自于某論壇，本文采用LoalaSam爬蟲程序，LoalaSam是一個由c/c++開發(fā)，運(yùn)行在Windows平臺上的一個多線程的網(wǎng)絡(luò)爬蟲程序，它甚至每一個工作線程可以遍歷一個域名。LoalaSam能快速的獲取信息，圖片，音頻，視頻等資源。

通過LoalaSam對某論壇進(jìn)行爬去，采用LoalaSam模仿用戶登錄，跳過驗(yàn)證碼，不斷地向服務(wù)器發(fā)出請求，進(jìn)入用戶界面后，并通過網(wǎng)頁中的超鏈接，以該用戶為根節(jié)點(diǎn)抓取和此用戶相關(guān)聯(lián)的所有用戶，并遞歸的不斷縱深抓取，最終形成實(shí)驗(yàn)用的數(shù)據(jù)源。并將這些數(shù)據(jù)保存到Oracle數(shù)據(jù)庫中。

通過Oracle數(shù)據(jù)庫存取采集到的數(shù)據(jù)，數(shù)據(jù)庫一共使用兩張表，一張關(guān)系表friend，一個實(shí)體表user，每次抓取到的客戶信息全部存入user表中，并同時為所有好友關(guān)系在user表中進(jìn)行關(guān)聯(lián)。

本文采用基于R語言的數(shù)據(jù)挖掘技術(shù)實(shí)現(xiàn)社交網(wǎng)絡(luò)的客戶細(xì)分。本文在聚類算法實(shí)現(xiàn)的時候創(chuàng)新性的提出一種新的聚類策略即首先通過分層聚類算法計(jì)算樣本抽樣并得出可聚類的簇?cái)?shù)。然后將簇?cái)?shù)傳遞給劃分聚類算法，在所有實(shí)驗(yàn)樣本上進(jìn)行更為精確和高效的重定位?；诖司垲惤Y(jié)果，我們將同時采用Cart算法和C4.5算法來進(jìn)行決策樹規(guī)則探索。

2.2 數(shù)據(jù)預(yù)處理

本文研究數(shù)據(jù)的預(yù)處理，從數(shù)據(jù)的抓取結(jié)果來看很多屬性類型為字符型，無論是采用數(shù)據(jù)庫系統(tǒng)還是轉(zhuǎn)換為其他形式的文件形式來存儲，挖掘算法處理起來其速度、資源消耗都不是樂觀的。因此對部分屬性就行了數(shù)字離散化處理。

2.3 PAM分類算法實(shí)證

本文在進(jìn)行聚類研究的時候，采取了折中的辦法。首先利用分層方法對樣本進(jìn)行聚類，得出可劃分的簇?cái)?shù)目；進(jìn)而將分層所得的簇?cái)?shù)目以參數(shù)形式回傳劃分算法，進(jìn)行迭代和重新定位。即采用DIANA算法劃分抽樣樣本，得出可劃分的簇?cái)?shù)目K，進(jìn)而將K交予PAM，以對樣本進(jìn)行重新劃分定位。兩種方法協(xié)同作用，共同確立最后的劃分。

PAM算法將整個樣本劃分為4部分，在excel里利用透視表對相應(yīng)type進(jìn)行匯總，分別計(jì)算各個類別的平均來訪輸（Account），平均分享相冊數(shù)（Album），平均貢獻(xiàn)日志數(shù)（Diary），平均擁有的好友數(shù)（Frinum）；Count列代表每種類別的客戶數(shù)。

PAM算法產(chǎn)生的四種類別：

觀察可知，絕大部分客戶集中在群組1，這個群組來訪人數(shù)和好友數(shù)較多，相冊數(shù)和日志數(shù)也處于中上游水平，在擁有相當(dāng)社會資本的同時具備一定的成長潛力，是論壇的中間力量，為Diamond用戶。群組2位居第二，這群組各項(xiàng)指標(biāo)均位于末端，也是所謂的消極客戶，稱之為Copper。群組4除日志數(shù)和好友數(shù)率高于Copper組外，其余觀察均墊底，表明這部分客戶的成長潛力和積極性都未表現(xiàn)出來，有可能是新加入客戶，稱之為Silver。群組3客戶人數(shù)位居最末，其余各項(xiàng)指標(biāo)均位居第一，表明這個群組在社交網(wǎng)中最受歡迎，稱之為Gold。

由于只將客戶的社會屬性提取作為類別命名的依據(jù)，四個類別背后隱含其他信息均未在上述討論中，但是實(shí)際影響類別的分屬，如果研究具體挖掘各個因素對于客戶細(xì)分類別的影響，還應(yīng)該通過決策樹和相應(yīng)的決策規(guī)則方法。

2.4 CART策樹算法實(shí)證

CART算法采用二分遞歸分割的技術(shù)，利用GINI系數(shù)為屬性找到最佳劃分，能夠考慮每個節(jié)點(diǎn)都成為葉子的可能，對每個節(jié)點(diǎn)都分配類別。CART可以生成結(jié)構(gòu)簡潔的二叉樹，但精度和效率較C$.5差。

首先進(jìn)行CART算法分析，需要下載tree程序包。R語言的實(shí)現(xiàn)過程如下：

>library（tree） #加載程序包

>newint=read.csv（“interval.csv”） #interval為合并過類別的新表

>nt=tree（type～，new int） #調(diào)用算法對原始數(shù)據(jù)進(jìn)行建樹

>summary（nt） #輸出Cart決策樹的概要

Classification tree：

Tree（formula = type ～，data = int）

我們發(fā)現(xiàn)Cart算法能清晰地描述出規(guī)則，并輸出一顆簡潔明了的二叉樹。上述決策樹規(guī)則中，行末標(biāo)注“*”號的為最終輸出的決策樹規(guī)則?？梢园l(fā)現(xiàn)，此模型中葉節(jié)點(diǎn)為每一分支中y值概率最高的類別決定，最終生成了深度為5，葉節(jié)點(diǎn)數(shù)為15的一顆二叉樹。

第一分支是以來訪人數(shù)Account作為測試屬性的，分成Account<2.5以及Account>=2.5兩枝：在Account<2.5這一支上又判斷相冊數(shù)（Album）的數(shù)量，在Account>=2.5這一枝則判斷好友數(shù)Frinum的數(shù)量。依此類推，最終得到15個葉節(jié)點(diǎn)和規(guī)則，節(jié)點(diǎn)的樣本量分布依次為1056，117，883，1107，396，845，353， 650，462，591，919，1046，451，264，370。從分類結(jié)果看，最終的錯分率（Misclassification error rate）為24%，，劃分效果上表現(xiàn)中規(guī)中矩。

用CART算法建立的模型結(jié)果簡單易懂，很容易被人理解，它以一種簡潔的方式解釋了為什么數(shù)據(jù)進(jìn)行這樣或那樣的分類，所以當(dāng)分析商業(yè)問題時，這種方法會給決策者提供簡潔的if-then規(guī)則，遠(yuǎn)比一些復(fù)雜的方程更讓決策者接受。

2.5 C4.5決策樹算法實(shí)證

接著我們嘗試用C4.5算法得到一顆完備的決策樹。在R語言中實(shí)現(xiàn)C4.5算法需要用到RWeKa數(shù)據(jù)包。WeKa全名為懷卡托智能分析環(huán)境（Waikato Environment for knowledge Analisys），是一個基于Java，用于數(shù)據(jù)挖掘用于數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的開源項(xiàng)目。其開發(fā)者是來自新西蘭懷卡托大學(xué)的兩名學(xué)者lanH.Witten和Eibe Frank。經(jīng)過十多年年的發(fā)展歷程，WeKa是現(xiàn)今最完備的數(shù)據(jù)挖掘工具之一，而且被公認(rèn)為是數(shù)據(jù)挖掘開源項(xiàng)目中最著名的一個。RWeKa為Weka的R語言擴(kuò)展包，成功加載RWe卡包后就可以在R語言環(huán)境中實(shí)現(xiàn)Weka的數(shù)據(jù)挖掘功能。RWeka的數(shù)據(jù)挖掘功能。RWeka的安裝同樣需要一定的數(shù)據(jù)包支持，都成功導(dǎo)入后，程序才能正常調(diào)用。WeKa里的J48決策樹模型是對Quinlan的C4.5決策樹算法的實(shí)現(xiàn)，并加入了合理的剪枝過程，有非常好的精度。

以下為算法的R語言實(shí)現(xiàn)過程：

>library（RWeka） #加載RWeka程序包

>library（party） #加載party程序包

>inj<-J48（type-，data=int）， #調(diào)用C4.5算法進(jìn)行決策樹建樹

>summary（inj） #輸出C4.5決策樹的概要

對結(jié)果觀察發(fā)現(xiàn)，C4.5的決策樹效果相當(dāng)好，正確分類的樣本數(shù)為10231個，準(zhǔn)確率達(dá)到98%。聚類結(jié)果中Diamond中只有26個被錯誤預(yù)測為Gold，1個被錯誤預(yù)測為Silver，還有1個被錯誤預(yù)測為Copper。但是由于決策樹過于完備，節(jié)點(diǎn)和葉子都較多。實(shí)際操作的時候可視具體情況需要結(jié)合Cart和C4.5的特點(diǎn)進(jìn)行取舍。

3 結(jié)論

隨著社交網(wǎng)絡(luò)的蓬勃發(fā)展，本文圍繞社交網(wǎng)絡(luò)理論和客戶細(xì)分理論研究，運(yùn)用數(shù)據(jù)挖掘工具中的PAM聚類算法和Cart和C4.5決策樹算法，對社交網(wǎng)絡(luò)的客戶細(xì)分進(jìn)行了深入的探討并最終得出可指導(dǎo)實(shí)踐的社交網(wǎng)絡(luò)客戶細(xì)分規(guī)則。

本文分析決策樹的過程將同時采用兩種決策樹算法，利用CART算法提供可視化的二叉樹，利用C4.5提供完備的決策樹規(guī)則。

C4.5和Cart是決策樹中比較常見的算法，C4.5具有思想簡單，構(gòu)造的樹深度小、分類速度快、學(xué)習(xí)能力強(qiáng)、構(gòu)造結(jié)果可靠等優(yōu)點(diǎn)，但當(dāng)節(jié)點(diǎn)數(shù)較多時，其在決策樹規(guī)則的可視化和可理解程度方面較差。

Cart算法采用二分遞歸分割的技術(shù)，利用Gini系數(shù)為屬性找到最佳劃分，能夠考慮每個節(jié)點(diǎn)都成為葉子的可能，對每個節(jié)點(diǎn)都分配類別。Cart可以生成結(jié)構(gòu)簡潔的二叉樹，但精度和效率較差。前者生成可理解的簡單的樹圖，但在劃分精度還有所欠缺；后者在劃分上產(chǎn)生的葉節(jié)點(diǎn)和規(guī)則較多，但錯分率低至2%。在實(shí)際的操作過程中，需視實(shí)際需要進(jìn)行取舍。

參考文獻(xiàn)：

[1] 薛薇，陳立萍.統(tǒng)計(jì)建模與R軟件[M].北京：清華大學(xué)出版社，2007.

[2] Heather Green， Making Social Networks Profitable.BussinessWeek， Sep 2008

[3] Anu Vajdyanathan， Malcolm Shore and Mark Billinghurst，Data in Social Network Analysis.2008.

[4] 謝益輝.基于R軟件的包的分類與回歸樹應(yīng)用[J].統(tǒng)計(jì)與信息論壇，2007（5）.