基于R語言的數(shù)據(jù)挖掘算法研究

1、 基于R語言的數(shù)據(jù)挖掘算法研究 張海陽+齊俊傳+毛健Summary：該文采用R語言作為研究工具以及聚類和決策樹等數(shù)據(jù)挖掘算法，研究如何針對社交網(wǎng)站中的用戶進行分類，挖掘最終可指導網(wǎng)站優(yōu)化和提高服務質(zhì)量的客戶分類數(shù)據(jù)。采用網(wǎng)絡爬蟲從某社交網(wǎng)站中抓取數(shù)據(jù)，該文采用聚類算法中的DIANA算法對抽樣樣本計算并對數(shù)據(jù)進行初步的簇類劃分；接著采用PAM算法對整體樣本進行進一步的計算并提取出大聚類，接著采用分別CART和C4.5等決策樹算法對決策樹規(guī)則進行進一步的研究，最終對研究結(jié)果進行評估并用來指導實踐。Key：R語言；數(shù)據(jù)挖掘；C4.5；Cart：TP393 ：A ：1009-3044（2016）28-

2、0016-03隨著互聯(lián)網(wǎng)社交網(wǎng)站的繁榮和各種網(wǎng)絡應用的不斷深入，社交網(wǎng)站已成為互聯(lián)網(wǎng)上的重要平臺應用。伴隨社交網(wǎng)絡的發(fā)展，不同地域、性格和特質(zhì)的用戶群展現(xiàn)出了差異化的需求，面對這些群體和用戶需求，如何細分市場識別并提供差異化的服務，以幫助企業(yè)在激烈的競爭中保持老用戶，發(fā)展新用戶。本文圍繞社交網(wǎng)絡理論和客戶細分理論的研究，運用數(shù)據(jù)挖掘工具中的決策樹算法，對社交網(wǎng)絡客戶細分進行了深入的探討并最終得出可指導時間的社交網(wǎng)絡客戶細分規(guī)則。1.1 R語言R是一種在數(shù)據(jù)統(tǒng)計領域廣泛使用的語言，R語言是一種開源語言，該語言的前身是S語言，也可以說R語言是S語言的一種實現(xiàn)，R在語法上類似C語言。R是一個統(tǒng)計分析

3、軟件，既可以進行統(tǒng)計分析，又可以進行圖形顯示。R能進行復雜的數(shù)據(jù)存儲和數(shù)據(jù)處理，利用數(shù)據(jù)、向量、矩陣的數(shù)學方法進行各種統(tǒng)計分析，并將統(tǒng)計分析結(jié)果以圖形方式展示出來，因此R也是一種統(tǒng)計制圖軟件。R內(nèi)嵌豐富的數(shù)學統(tǒng)計函數(shù)，從而使使用者能靈活的進行統(tǒng)計分析。它可以運行于UNIX，Windows和Macintosh的操作系統(tǒng)上，而且嵌入了一個非常方便實用的幫助系統(tǒng)。R是一種功能強大的編程語言，就像傳統(tǒng)的編程語言C和JAVA一樣，R也可以利用條件、循環(huán)等編程方法實現(xiàn)對數(shù)據(jù)的各種處理，從而實現(xiàn)數(shù)據(jù)統(tǒng)計目的。R作為一種開源的軟件，被越來越多的用來代替SAS等軟件進行數(shù)據(jù)統(tǒng)計分析。R作為一個統(tǒng)計系統(tǒng)來使用，其

4、中集成了用于經(jīng)典和現(xiàn)代統(tǒng)計分析的各種算法和函數(shù)，這些算法和函數(shù)是以包的形式提供的。R內(nèi)含了8個包，如果需要其他的包，可在官網(wǎng)上進行下載安裝。1.2 數(shù)據(jù)挖掘數(shù)據(jù)挖掘（Data mining），顧名思義就是從海量的數(shù)據(jù)中運用數(shù)據(jù)挖掘算法從中提取出隱含的、有用的信息。數(shù)據(jù)挖掘涉及統(tǒng)計學、人工智能和數(shù)據(jù)庫等多種學科。近年來，隨著計算機的發(fā)展，各個領域積累了海量的數(shù)據(jù)，這些數(shù)據(jù)如何變廢為寶，這就需要數(shù)據(jù)挖掘的幫助。因此數(shù)據(jù)挖掘在信息產(chǎn)業(yè)界廣泛應用，比如市場決策和分析、科學研究、智能探索、商務管理等。數(shù)據(jù)挖掘是一個多學科的交叉領域，統(tǒng)計學、人工智能和數(shù)據(jù)庫等多種學科為數(shù)據(jù)挖掘提供豐富的理論基礎。包括統(tǒng)計

5、學的概率分析、相關(guān)性、參數(shù)估計、聚類分析和假設檢驗等，以及機器學習、神經(jīng)網(wǎng)絡、模式識別、信息檢索、知識庫、并行計算、圖形學、數(shù)據(jù)庫等。同時數(shù)據(jù)挖掘也為這些領域提供了新的挑戰(zhàn)和機遇。例如，數(shù)據(jù)挖掘提升了源于高性能（并行）計算的技術(shù)在處理海量數(shù)據(jù)集方面性能。隨著數(shù)據(jù)挖掘的蓬勃發(fā)展，近幾年分布式技術(shù)在處理海量數(shù)據(jù)方面也變得越來越重要，尤其是Hadoop的發(fā)展極大的提高了數(shù)據(jù)挖掘的并行處理效率。數(shù)據(jù)挖掘也同時促進了數(shù)據(jù)挖掘算法的發(fā)展，數(shù)據(jù)挖掘算法是根據(jù)數(shù)據(jù)創(chuàng)建數(shù)據(jù)挖掘模型的方法和計算方法，算法將首先分析數(shù)據(jù)源提供的數(shù)據(jù)，根據(jù)數(shù)據(jù)的特點和需求建立特定的數(shù)學模型。根據(jù)數(shù)據(jù)挖掘模型的特點，可以選擇相應的算法

6、。在選擇算法是，可根據(jù)實際情況選擇劃分聚類的算法，或選擇決策樹的算法。選擇算法的不同可能對挖掘結(jié)果有一定的影響。數(shù)據(jù)挖掘的步驟是首先確立挖掘目標，提出一個初步計劃，估計用到的工具和技術(shù)；第二步是數(shù)據(jù)理解，即收集原始數(shù)據(jù)，并對數(shù)據(jù)進行描述和初步探索，檢查這些數(shù)據(jù)的質(zhì)量；第三步是數(shù)據(jù)準備，包括數(shù)據(jù)選擇、清洗、合并和格式化；第四步是建立數(shù)據(jù)模型，包括選擇建模技術(shù)、測試方案設計、模型訓練；第五步是模型評估，根據(jù)評估結(jié)果得出結(jié)論，確定是否部署該模型；第六步是模型部署；第七步是選擇算法；最后是得出結(jié)論。1.3 C4.5算法C4.5是一種機器學習的方法，在數(shù)據(jù)挖掘分類中應用廣泛，它的目標是監(jiān)督學習。C4.5

7、是在ID3的基礎上衍生出來的。ID3是一種決策樹算法。ID3衍生出C4.5和CART兩種算法。C4.5的算法思路是，在給定的數(shù)據(jù)集中，每一個元祖都是互斥的，每一個元組都能用一組屬性值來描述，每一個元組都屬于某一類別。C4.5的目標是通過學習，建立一個從屬性值到類別的映射關(guān)系，并且這個映射能夠指導對新的類別進行分類。C4.5是一種決策樹算法，決策樹是一種樹結(jié)構(gòu)，其中每個非葉節(jié)點表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個葉節(jié)點給定一個類標記。決策樹建立起來之后，對于一個未給定類標記的元組，學習一條有根節(jié)點到葉節(jié)點的路徑，該葉節(jié)點的標記就是該元組的預測。決策樹的優(yōu)勢在于適合于探測性的知

8、識發(fā)現(xiàn)。圖1就是一棵典型的C4.5算法對數(shù)據(jù)集產(chǎn)生的決策樹。表1所示，它表示的是天氣情況與去不去打高爾夫球之間的關(guān)系。1.4 Cart算法CART（Classification And Regression Tree），即分類回歸樹算法，該算法是一種決策樹算法，并且生成的是一棵二叉樹。Cart有兩種關(guān)鍵思想，一種是將訓練樣本進行二分遞歸分割建樹，即給定一個訓練集，用二分算法將該訓練集分成兩個子訓練集，不斷遞歸鄉(xiāng)下分割，這樣每個非葉子節(jié)點都有兩個分支，所以對于第一棵子樹的葉子節(jié)點數(shù)比非葉子節(jié)點數(shù)多1，最終形成一顆二叉樹；另一種是用驗證數(shù)據(jù)進行剪枝。 遞歸劃分法，用類別集Y表示因變量，用X1，X2

9、，XP表示自變量，通過遞歸分割的方式把關(guān)于X的P維空間分割成不重疊的矩形。CART算法是怎樣進行樣本劃分的呢？首先，一個自變量被選擇，例如Xi的一個值Si，若選擇Si把P維空間分為兩個部分，一部分包含的元素都滿足XiSi。其次把上述分割的兩部分遞歸分割，直到把X空間劃分的每個小矩形都盡可能的是同構(gòu)的。CART過程中第二個關(guān)鍵的思想是用獨立的驗證數(shù)據(jù)集對根據(jù)訓練集生長的樹進行剪枝。CART剪枝的目的是生成一個具有最小錯誤的樹，因為一方面在樹生成過程中可能存在不能提高分類純度劃分節(jié)點，如果使用這些異常數(shù)據(jù)進行分類，分類的準確性就會受到很大的影響。剪去這些異常數(shù)據(jù)的過程，被稱為樹剪枝。通過剪枝，可以

10、去除這些孤立點和雜音，提高樹獨立于訓練數(shù)據(jù)正確分類的能力。另一方面分類回歸樹的遞歸建樹過程存在過擬合訓練數(shù)據(jù)。CART用成本復雜性標準來剪枝。CART用的成本復雜性標準是分類樹的簡單誤分（基于驗證數(shù)據(jù)的）加上一個對樹的大小的懲罰因素。成本復雜性標準對于一個數(shù)來說是Err（T）+a|L（T）|，其中a表示每個節(jié)點的懲罰，Err（T）是驗證數(shù)據(jù)被樹誤分部分，L（T）是樹T的葉節(jié)點樹，其中a是一個變動的數(shù)字。從這個序列的樹中選擇一個在驗證數(shù)據(jù)集上具有最小誤分的樹稱為最小錯誤樹。2 基于R語言數(shù)據(jù)挖掘算法的客戶分類2.1 數(shù)據(jù)準備本研究采用的社交網(wǎng)絡數(shù)據(jù)均來自于某論壇，本文采用LoalaSam爬蟲程序

11、，LoalaSam是一個由c/c+開發(fā)，運行在Windows平臺上的一個多線程的網(wǎng)絡爬蟲程序，它甚至每一個工作線程可以遍歷一個域名。LoalaSam能快速的獲取信息，圖片，音頻，視頻等資源。通過LoalaSam對某論壇進行爬去，采用LoalaSam模仿用戶登錄，跳過驗證碼，不斷地向服務器發(fā)出請求，進入用戶界面后，并通過網(wǎng)頁中的超鏈接，以該用戶為根節(jié)點抓取和此用戶相關(guān)聯(lián)的所有用戶，并遞歸的不斷縱深抓取，最終形成實驗用的數(shù)據(jù)源。并將這些數(shù)據(jù)保存到Oracle數(shù)據(jù)庫中。通過Oracle數(shù)據(jù)庫存取采集到的數(shù)據(jù)，數(shù)據(jù)庫一共使用兩張表，一張關(guān)系表friend，一個實體表user，每次抓取到的客戶信息全部存

12、入user表中，并同時為所有好友關(guān)系在user表中進行關(guān)聯(lián)。本文采用基于R語言的數(shù)據(jù)挖掘技術(shù)實現(xiàn)社交網(wǎng)絡的客戶細分。本文在聚類算法實現(xiàn)的時候創(chuàng)新性的提出一種新的聚類策略即首先通過分層聚類算法計算樣本抽樣并得出可聚類的簇數(shù)。然后將簇數(shù)傳遞給劃分聚類算法，在所有實驗樣本上進行更為精確和高效的重定位?；诖司垲惤Y(jié)果，我們將同時采用Cart算法和C4.5算法來進行決策樹規(guī)則探索。2.2 數(shù)據(jù)預處理本文研究數(shù)據(jù)的預處理，從數(shù)據(jù)的抓取結(jié)果來看很多屬性類型為字符型，無論是采用數(shù)據(jù)庫系統(tǒng)還是轉(zhuǎn)換為其他形式的文件形式來存儲，挖掘算法處理起來其速度、資源消耗都不是樂觀的。因此對部分屬性就行了數(shù)字離散化處理。2.3

13、 PAM分類算法實證本文在進行聚類研究的時候，采取了折中的辦法。首先利用分層方法對樣本進行聚類，得出可劃分的簇數(shù)目；進而將分層所得的簇數(shù)目以參數(shù)形式回傳劃分算法，進行迭代和重新定位。即采用DIANA算法劃分抽樣樣本，得出可劃分的簇數(shù)目K，進而將K交予PAM，以對樣本進行重新劃分定位。兩種方法協(xié)同作用，共同確立最后的劃分。PAM算法將整個樣本劃分為4部分，在excel里利用透視表對相應type進行匯總，分別計算各個類別的平均來訪輸（Account），平均分享相冊數(shù)（Album），平均貢獻日志數(shù)（Diary），平均擁有的好友數(shù)（Frinum）；Count列代表每種類別的客戶數(shù)。PAM算法產(chǎn)生的四種

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

15、，但是實際影響類別的分屬，如果研究具體挖掘各個因素對于客戶細分類別的影響，還應該通過決策樹和相應的決策規(guī)則方法。2.4 CART策樹算法實證CART算法采用二分遞歸分割的技術(shù)，利用GINI系數(shù)為屬性找到最佳劃分，能夠考慮每個節(jié)點都成為葉子的可能，對每個節(jié)點都分配類別。CART可以生成結(jié)構(gòu)簡潔的二叉樹，但精度和效率較C$.5差。首先進行CART算法分析，需要下載tree程序包。R語言的實現(xiàn)過程如下：library（tree） #加載程序包newint=read.csv（“interval.csv”） #interval為合并過類別的新表nt=tree（type，new int） #調(diào)用算法對原始

16、數(shù)據(jù)進行建樹summary（nt） #輸出Cart決策樹的概要Classification tree：Tree（formula = type ，data = int）我們發(fā)現(xiàn)Cart算法能清晰地描述出規(guī)則，并輸出一顆簡潔明了的二叉樹。上述決策樹規(guī)則中，行末標注“*”號的為最終輸出的決策樹規(guī)則?？梢园l(fā)現(xiàn)，此模型中葉節(jié)點為每一分支中y值概率最高的類別決定，最終生成了深度為5，葉節(jié)點數(shù)為15的一顆二叉樹。 第一分支是以來訪人數(shù)Account作為測試屬性的，分成Account=2.5兩枝：在Account=2.5這一枝則判斷好友數(shù)Frinum的數(shù)量。依此類推，最終得到15個葉節(jié)點和規(guī)則，節(jié)點的樣本量分

17、布依次為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ù)進行這樣或那樣的分類，所以當分析商業(yè)問題時，這種方法會給決策者提供簡潔的if-then規(guī)則，遠比一些復雜的方程更讓決策者接受。2.5 C4.5決策樹算法實證接著我們嘗試用C4.5算法得到一顆完備的決策樹。在R語言中實現(xiàn)C4.5算法需要用到RWeKa數(shù)據(jù)包。

18、WeKa全名為懷卡托智能分析環(huán)境（Waikato Environment for knowledge Analisys），是一個基于Java，用于數(shù)據(jù)挖掘用于數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的開源項目。其開發(fā)者是來自新西蘭懷卡托大學的兩名學者lanH.Witten和Eibe Frank。經(jīng)過十多年年的發(fā)展歷程，WeKa是現(xiàn)今最完備的數(shù)據(jù)挖掘工具之一，而且被公認為是數(shù)據(jù)挖掘開源項目中最著名的一個。RWeKa為Weka的R語言擴展包，成功加載RWe卡包后就可以在R語言環(huán)境中實現(xiàn)Weka的數(shù)據(jù)挖掘功能。RWeka的數(shù)據(jù)挖掘功能。RWeka的安裝同樣需要一定的數(shù)據(jù)包支持，都成功導入后，程序才能正常調(diào)用。WeKa里的

19、J48決策樹模型是對Quinlan的C4.5決策樹算法的實現(xiàn)，并加入了合理的剪枝過程，有非常好的精度。以下為算法的R語言實現(xiàn)過程：library（RWeka） #加載RWeka程序包library（party） #加載party程序包injsummary（inj） #輸出C4.5決策樹的概要對結(jié)果觀察發(fā)現(xiàn)，C4.5的決策樹效果相當好，正確分類的樣本數(shù)為10231個，準確率達到98%。聚類結(jié)果中Diamond中只有26個被錯誤預測為Gold，1個被錯誤預測為Silver，還有1個被錯誤預測為Copper。但是由于決策樹過于完備，節(jié)點和葉子都較多。實際操作的時候可視具體情況需要結(jié)合Cart和C4.5的特點進行取舍。3 結(jié)論隨著社交網(wǎng)絡的蓬勃發(fā)展，本文圍繞社交網(wǎng)絡理論和客戶細分理論研究，運用數(shù)據(jù)挖掘工具