基于R語言的數據挖掘算法研究

張海陽+齊俊傳+毛健

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

關鍵詞：R語言；數據挖掘；C4.5；Cart

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2016）28-0016-03

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

1.1 R語言

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

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

R作為一個統計系統來使用，其中集成了用于經典和現代統計分析的各種算法和函數，這些算法和函數是以包的形式提供的。R內含了8個包，如果需要其他的包，可在官網上進行下載安裝。

1.2 數據挖掘

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

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

數據挖掘也同時促進了數據挖掘算法的發展，數據挖掘算法是根據數據創建數據挖掘模型的方法和計算方法，算法將首先分析數據源提供的數據，根據數據的特點和需求建立特定的數學模型。

根據數據挖掘模型的特點，可以選擇相應的算法。在選擇算法是，可根據實際情況選擇劃分聚類的算法，或選擇決策樹的算法。選擇算法的不同可能對挖掘結果有一定的影響。

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

1.3 C4.5算法

C4.5是一種機器學習的方法，在數據挖掘分類中應用廣泛，它的目標是監督學習。C4.5是在ID3的基礎上衍生出來的。ID3是一種決策樹算法。ID3衍生出C4.5和CART兩種算法。

C4.5的算法思路是，在給定的數據集中，每一個元祖都是互斥的，每一個元組都能用一組屬性值來描述，每一個元組都屬于某一類別。C4.5的目標是通過學習，建立一個從屬性值到類別的映射關系，并且這個映射能夠指導對新的類別進行分類。

C4.5是一種決策樹算法，決策樹是一種樹結構，其中每個非葉節點表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個葉節點給定一個類標記。決策樹建立起來之后，對于一個未給定類標記的元組，學習一條有根節點到葉節點的路徑，該葉節點的標記就是該元組的預測。決策樹的優勢在于適合于探測性的知識發現。

圖1就是一棵典型的C4.5算法對數據集產生的決策樹。

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

1.4 Cart算法

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

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

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

CART過程中第二個關鍵的思想是用獨立的驗證數據集對根據訓練集生長的樹進行剪枝。CART剪枝的目的是生成一個具有最小錯誤的樹，因為一方面在樹生成過程中可能存在不能提高分類純度劃分節點，如果使用這些異常數據進行分類，分類的準確性就會受到很大的影響。剪去這些異常數據的過程，被稱為樹剪枝。通過剪枝，可以去除這些孤立點和雜音，提高樹獨立于訓練數據正確分類的能力。另一方面分類回歸樹的遞歸建樹過程存在過擬合訓練數據。

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

2 基于R語言數據挖掘算法的客戶分類

2.1 數據準備

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

通過LoalaSam對某論壇進行爬去，采用LoalaSam模仿用戶登錄，跳過驗證碼，不斷地向服務器發出請求，進入用戶界面后，并通過網頁中的超鏈接，以該用戶為根節點抓取和此用戶相關聯的所有用戶，并遞歸的不斷縱深抓取，最終形成實驗用的數據源。并將這些數據保存到Oracle數據庫中。

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

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

2.2 數據預處理

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

2.3 PAM分類算法實證

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

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

PAM算法產生的四種類別：

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

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

2.4 CART策樹算法實證

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

首先進行CART算法分析，需要下載tree程序包。R語言的實現過程如下：

>library（tree） #加載程序包

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

>nt=tree（type～，new int） #調用算法對原始數據進行建樹

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

Classification tree：

Tree（formula = type ～，data = int）

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

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

用CART算法建立的模型結果簡單易懂，很容易被人理解，它以一種簡潔的方式解釋了為什么數據進行這樣或那樣的分類，所以當分析商業問題時，這種方法會給決策者提供簡潔的if-then規則，遠比一些復雜的方程更讓決策者接受。

2.5 C4.5決策樹算法實證

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

以下為算法的R語言實現過程：

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

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

>inj<-J48（type-，data=int）， #調用C4.5算法進行決策樹建樹

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

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

3 結論

隨著社交網絡的蓬勃發展，本文圍繞社交網絡理論和客戶細分理論研究，運用數據挖掘工具中的PAM聚類算法和Cart和C4.5決策樹算法，對社交網絡的客戶細分進行了深入的探討并最終得出可指導實踐的社交網絡客戶細分規則。

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

C4.5和Cart是決策樹中比較常見的算法，C4.5具有思想簡單，構造的樹深度小、分類速度快、學習能力強、構造結果可靠等優點，但當節點數較多時，其在決策樹規則的可視化和可理解程度方面較差。

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

參考文獻：

[1] 薛薇，陳立萍.統計建模與R軟件[M].北京：清華大學出版社，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軟件的包的分類與回歸樹應用[J].統計與信息論壇，2007（5）.