數據分析與決策技術叢書

R語言數據挖掘

Learning Data Mining with R

［哈薩克斯坦］貝特·麥克哈貝爾（Bater Makhabel）　著

李洪成　許金煒　段力輝　譯

圖書在版編目（CIP）數據

R語言數據挖掘 / （哈）貝特·麥克哈貝爾（Bater Makhabel）著；李洪成，許金煒，段力輝譯. —北京：機械工業出版社，2016.9

（數據分析與決策技術叢書）

書名原文：Learning Data Mining with R

ISBN 978-7-111-54769-3

I. R…　II. ①貝…　②李…　③許…　④段…　III. ①程序語言－程序設計　②數據采集　IV. ①TP312　②TP274

中國版本圖書館CIP數據核字（2016）第212252號

本書版權登記號：圖字：01-2015-2379

Bater Makhabel：Learning Data Mining with R（ISBN: 978-1-78398-210-3）.

Copyright ? 2015 Packt Publishing. First published in the English language under the title “Learning Data Mining with R”.

All rights reserved.

Chinese simplified language edition published by China Machine Press.

Copyright ? 2016 by China Machine Press.?

本書中文簡體字版由Packt Publishing授權機械工業出版社獨家出版。未經出版者書面許可，不得以任何方式復制或抄襲本書內容。

R語言數據挖掘

出版發行：機械工業出版社（北京市西城區百萬莊大街22號　郵政編碼：100037）

責任編輯：盛思源 責任校對：殷　虹

印　　刷： 版　　次：2016年11月第1版第1次印刷

開　　本：186mm×240mm　1/16 印　　張：13.75

書　　號：ISBN 978-7-111-54769-3 定　　價：49.00元

凡購本書，如有缺頁、倒頁、脫頁，由本社發行部調換

客服熱線：（010）88379426　88361066 投稿熱線：（010）88379604

購書熱線：（010）68326294　88379649　68995259 讀者信箱：hzit@hzbook.com

版權所有 ? 侵權必究

封底無防偽標均為盜版

本書法律顧問：北京大成律師事務所　韓光/鄒曉東

The Translator’s Words?譯　者　序

隨著互聯網中文檔的快速積累，在網絡中獲取一些有用的信息變得愈發困難。本書收集了數據挖掘的一些最常用算法，首先對這些算法進行簡單描述，然后給出了這些算法的常見應用背景，以方便數據挖掘用戶學習和參考。對于關聯規則、分類、聚類分析、異常值檢測、數據流挖掘、時間序列、圖形挖掘、網絡分析、文本挖掘和網絡分析等流行的數據挖掘算法，給出了較為詳盡的介紹，并且給出了這些算法的偽代碼和R語言實現。

本書提供了應用最流行的數據挖掘算法解決預測模型問題的可行策略，讀者可以從中更好地理解主流的預測模型，也可以學習數據挖掘的實際經驗。

本書第1章介紹數據挖掘、機器學習和數據預處理的基本概念；第2章介紹頻繁模式挖掘、關聯規則和相關性；第3章和第4章分別介紹分類和高級分類技術；第5章和第6章分別介紹聚類分析算法和高級聚類分析算法；第7章討論異常值檢測；第8章介紹流數據、時間序列數據及序列數據挖掘；第9章討論圖挖掘和網絡分析；第10章介紹文本和網絡數據挖掘。

讀者可以從書中給出的偽代碼出發，構建適合自己需要的算法；或者直接應用隨書提供的R語言實現的算法。本書適合對數據挖掘感興趣的各類人士，不管你是數據挖掘算法的研究人員，還是數據挖掘工程師，本書都可以提供相應的幫助。

本書的翻譯得到了廣西高校數據分析與計算重點實驗室的資助。在本書的翻譯過程中，得到了王春華編輯的大力支持和幫助。本書責任編輯盛思源老師具有豐富的經驗，為本書的出版付出了大量的勞動，這里對她們的支持和幫助表示衷心的感謝。

由于時間和水平所限，難免會有不當之處，希望同行和讀者多加指正。

譯者

作者簡介 About the Author

Bater Makhabel（LinkedIn: BATERMJ和GitHub: BATERMJ）為系統構架師，生活在中國北京、上海和烏魯木齊等地。他于1995至2002年之間在清華大學學習，并獲得計算機科學和技術的學士和博士學位。他在機器學習、數據挖掘、自然語言處理（NLP）、分布系統、嵌入系統、網絡、移動平臺、算法、應用數學和統計領域有豐富的經驗。他服務過的客戶包括CA Technologies、META4ALL和EDA（DFR的一家子公司）。同時，他也擁有在中國創辦公司的經歷。

Bater的生活開創性地在計算機科學和人文科學之間取得了平衡。在過去的12年中，他在應用多種先進計算機技術于文化創作方面獲得了經驗，其中一項是人機界面，通過哈薩克語與計算機系統進行交互。他一直和他工作領域中的其他作家有合作，但是本書是他的第一部正式作品。

About the Reviewers 審校者簡介

Jason H.D. Cho在伊利諾伊大學香檳分校獲得計算機碩士學位，現在在攻讀博士。他對應用自然語言處理和大數據解決醫學信息問題特別感興趣。尤其是，他希望能在社交媒體上找到病人關心的健康需求。他曾帶領一個學員小組在美國一項主要的保健競賽（CIMIT）中躋身前10名。Jason也為自然語言處理和大數據研究領域的文章進行審稿。

Gururaghav Gopal現在在Paterson證券公司工作，其職位是量化分析員、開發人員、交易員和分析師。以前，他是一個和電商行業相關的數據科學咨詢師。他曾經在印度韋洛爾的韋洛爾理工大學教授大學生和研究生模式識別課程。他曾經在一些研究機構做過研究助理，包括IFMR和NAL。

Gururaghav獲得了電子工程的學士學位、計算機科學和工程的碩士學位，并在IFMR輔修金融工程和風險管理方面的課程。之后，他便在金融相關領域工作。他獲得過多個獎項并以他的名字發表過多篇文章。他對編程、教學和咨詢感興趣。在閑暇時間，他會聽

音樂。

Vibhav Kamath獲得了位于孟買的印度理工學院工業工程和運籌學的碩士學位，并具有位于浦那的工學院的電子工程學士學位。大四期間，他對算法和數學模型產生了興趣，從此便進入分析領域。Vibhav現在在班加羅爾的一家IT服務公司工作，其工作的一部分內容是應用R編程語言基于優化和線性回歸技術來開發統計和數學模型。他曾經審閱過Packt出版社出版的兩本R語言圖書：R Graphs Cookbook, ?Second Edition和Social Media Mining with R，他曾經應用SAS、SQL和Excel/VBA做過數據可視化，為一家銀行開發過儀表盤程序。

過去，Vibhav從事過離散時間仿真和語言處理（均基于MATLAB）等方面的學術工作。他涉獵過機器人領域，建立了一個瀏覽魔方的機器人Micromouse。除了分析和編程之外，Vibhav喜歡閱讀小說類讀物。空閑時，他打乒乓球、板球和網球，實在無聊時就玩田字格游戲（數獨和數謎）。可以通過郵件vibhav.kamath@hotmail.com或者領英in.linkedin.com/in/vibhavkamath與他聯系。

Hasan Kurban于2012年在布盧明頓的印度大學獲得計算機碩士學位，現在在該校的信息與計算機學院攻讀博士學位，專業為計算機科學同時輔修統計學。他的研究方向為數據挖掘、機器學習和統計學。

Preface 前　　言

世界各地的統計學家和分析師正面臨著處理許多復雜統計分析項目的迫切問題。由于人們對數據分析領域的興趣日益增加，所以R語言提供了一個免費且開源的環境，非常適合學習和有效地利用現實世界中的預測建模方案。隨著R語言社區的不斷發展及其大量程序包的不斷增加，它具備了解決眾多實際問題的強大功能。

R編程語言誕生已經有數十年了，它已經變得非常知名，不但被社區的科學家而且被更廣泛的開發者社區所熟知。它已經成長為一個強大的工具，可以幫助開發者在執行數據相關任務時生成有效且一致的源代碼。由于R語言開發團隊和獨立貢獻者已經創建了良好的文檔，所以使用R語言編程并不困難。

進而，你可以使用來自R語言官方網站的程序包。如果你想不斷提高自己的專業水平，那么你可能需要閱讀在過去幾年中已經出版的書籍。你應該始終銘記：創建高水平、安全且國際兼容的代碼比初始創建的第一個應用程序更加復雜。

本書的目的是幫助你處理在復雜的統計項目中遇到的一系列可能比較困難的問題。本書的主題包括：學習在運行R語言程序時，如何使用R代碼段處理數據，挖掘頻繁模式、關聯規則和相關規則。本書還為那些具有R語言基礎的讀者提供了成功創建和自定義最常用數據挖掘算法的技能和知識。這將有助于克服困難，并確保在運用R語言公開可用的豐富程序包開發數據挖掘算法時，R編程語言能夠得到最有效的使用。

本書的每一章是獨立存在的，因此你可以自由地跳轉到任何一章，學習你覺得自己需要對某個特定的話題進行更加深入了解的章節。如果你覺得自己遺漏了一些重要的知識，你可以回顧前面的章節。本書的組織方式有助于逐步拓展你的知識框架。

你需要了解如何編寫不同的預測模型、流數據和時間序列數據的代碼，同時你還會接觸到基于MapReduce算法（一種編程模型）的解決方案。學完本書，你將會為自己所具備的能力（知道哪種數據挖掘算法應用于哪種情況）而感到自信。

我喜歡使用R編程語言進行多用途數據挖掘任務的開發與研究，我非常高興能與大家分享我的熱情和專業知識，幫助大家更有效地使用R語言，更舒適地使用數據挖掘算法的發展成果與應用。

本書主要內容

第1章闡述數據挖掘的概要知識，數據挖掘與機器學習、統計學的關系，介紹數據挖掘基本術語，如數據定義和預處理等。

第2章包含使用R語言編程時，學習挖掘頻繁模式、關聯規則和相關規則所需的高級且有趣的算法。

第3章幫助你學習使用R語言編寫經典分類算法，涵蓋了應用于不同類型數據集的多種分類算法。

第4章講述更多的分類算法，如貝葉斯信念網絡、支持向量機（SVM）和k近鄰算法。

第5章講述如何使用流行與經典的算法進行聚類，如k均值、CLARA和譜算法。

第6章介紹與當前行業熱點話題相關的高級聚類算法的實現，如EM、CLIQUE和DBSCAN等。

第7章介紹如何應用經典和流行算法來檢測現實世界案例中的異常值。

第8章運用最流行、最經典以及一流的算法來講解流數據、時間序列和序列數據挖掘這3個熱點話題。

第9章介紹圖挖掘和社交挖掘算法的概要及其他有趣的話題。

第10章介紹應用領域中最流行算法的有趣應用。

附錄包含算法和數據結構的列表以便幫助你學習數據挖掘。

學習本書的準備知識

任何一臺裝有Windows、Linux或者Mac OS系統的個人計算機都可以運行本書給出的代碼示例。本書所使用的軟件都是開源的，可以從http://www.r-project.org/上免費獲取。

讀者對象

本書適合對R語言和統計學具有基本知識的數據科學家、定量分析師和軟件工程師。本書假定讀者只熟悉非常基本的R語言知識，如主要的數據類型、簡單的函數和如何來回移動數據。不需要先前熟悉數據挖掘軟件包。但是，你應該對數據挖掘的概念和過程有基本的認知。

即使你對于數據挖掘完全是一個新人，你也能夠同時掌握基本和高級的數據挖掘算法的實現。你將學習如何從各種數據挖掘算法中選擇合適的算法，將這些算法應用于現實世界可用的大多數數據集中的某些特定數據集中。

約定

本書中，你將發現多種文字印刷格式，它們用于對不同類型的信息進行區分。下面是關于這些格式的一些例子以及它們的含義。

文本中的代碼、數據庫表名、文件夾名、文件名、文件擴展名、路徑名、虛擬URL、用戶輸入和Twitter ID如下所示：“我們可以通過使用include指令來包含其他的上下文。”

新的術語和重要詞用粗體標示。例如，在屏幕上、菜單中或者對話框中看到的詞將這樣出現在文本中：“單擊Next按鈕進入下一個界面。”

警告或者重要的說明將會出現在這樣的圖標后面。

提示或技巧將會出現在這樣的圖標后面。

讀者反饋

讀者的反饋始終是受歡迎的。讓我們知道你如何看待本書——你喜歡哪些內容或者你可能不喜歡哪些內容。讀者的反饋對于我們制定使讀者真正獲得最大效用的主題是十分重要的。

可以通過發送電子郵件至郵箱feedback@packtpub.com，并在電子郵件的主題中提及書名來給我們提供意見。

如果你對于某個主題有專長，或者你有興趣編寫一本書或協助完成一本書，可以到網站www.packtpub.com/authors看一看我們的撰稿指南。

客戶支持

既然你現在自豪地擁有了一本Packt書，那么我們可以做很多事來幫助你充分利用你購買的書籍。

下載示例代碼

你可以從你在http://www.packtpub.com網站的賬戶上下載所有你已經購買的Packt書的示例代碼。如果你在其他地方購買本書，你可以訪問http://www.packtpub.com/support網站并注冊，我們將通過電子郵件直接給你發送文件。你也可以在網站https://github.com/batermj/learning-data-mining-with-r找到本書的代碼文件。

勘誤表

雖然我們已經盡力確保書中內容的準確性，但錯誤難免會發生。如果你在我們的某一本書中發現錯誤（可能是文本或者代碼中的錯誤）并向我們報告錯誤，我們將不勝感激。由此，你可以使其他讀者免于困惑并幫助我們改進該書的后續版本。如果你發現任何錯誤，請通過訪問http://www.packtpub.com/submit-errata網站，選擇相應圖書，單擊errata submission form（勘誤提交表單）的鏈接，并輸入錯誤的詳細信息以便報告給我們。一旦你的錯誤得到驗證，你的提交將被接受并上傳到我們的網站，或者添加到現有的勘誤表中，列于該標題下的勘誤表部分。任何現有的勘誤表均可從http://www.packtpub.com/support網站上選擇你所需要的標題進行查看。

盜版行為

因特網上版權材料的盜版行為是所有媒介一直存在的問題。在Packt，我們非常重視對版權和許可證的保護。如果你在網絡上遇到任何形式非法復制我們著作的行為，請立刻向我們提供位置地址或者網站名稱以便我們能夠尋找補救方法。

我們的聯系方式是copyright@packtpub.com，請一并附上關于涉嫌盜版材料的鏈接。

我們非常感謝你對我們的作者以及我們為你帶來有價值內容的能力的保護。

問題

如果你對本書有任何方面的問題，可以聯系我們（questions@packtpub.com），我們將竭盡所能幫助你解決。

Acknowledgements?致　　謝

感謝我的妻子Zurypa Dawletkan和兒子Bakhtiyar。他們支持我利用多個周末和夜晚使得本書得以出版。

我也要感謝Luke Presland，給予我機會來撰寫這本書。十分感謝Rebecca Pedley和Govindan K，你們對本書的貢獻是巨大的。感謝Jalasha D’costa和其他技術編輯及團隊為該書出版付出的努力，使得本書看起來還不錯。同時，感謝組稿編輯和技術審校者。

我也要謝謝我的兄弟Bolat Makhabel博士（LinkedIn: BOLATMJ），他給我提供了本書英文版封面的照片，他具有醫學背景。照片中的植物名為Echinops（植物學的拉丁名字），哈薩克語稱為Lahsa，在中國稱為藍刺頭。這種植物用于傳統的哈薩克醫藥，也是我兄弟研究的一部分。

盡管我的專業知識來源于不斷的實踐，但它也來源于我的母校（清華大學）和戴梅萼教授、趙雁南教授、王家欽教授、Ju Yuma教授以及其他眾多老師為我打下的堅實基礎。他們的精神鼓勵我在計算機科學和技術領域繼續努力。我要感謝我的岳父母Dawletkan Kobegen和Burux Takay，感謝他們照顧我的兒子。

最后，我要對我的姐姐Aynur Makhabel和姐夫Akimjan Xaymardan表達我最大的敬意。

目　　錄 Contents

譯者序

作者簡介

審校者簡介

前言

致謝

第1章　預備知識 ?1

1.1　大數據 ?2

1.2　數據源 ?3

1.3　數據挖掘 ?4

1.3.1　特征提取 ?4

1.3.2　總結 ?4

1.3.3　數據挖掘過程 ?5

1.4　社交網絡挖掘 ?7

1.5　文本挖掘 ?9

1.5.1　信息檢索和文本挖掘 ?10

1.5.2　文本挖掘預測 ?10

1.6　網絡數據挖掘 ?10

1.7　為什么選擇R ?12

1.8　統計學 ?12

1.8.1　統計學與數據挖掘 ?13

1.8.2　統計學與機器學習 ?13

1.8.3　統計學與R語言 ?13

1.8.4　數據挖掘中統計學的局限性 ?13

1.9　機器學習 ?13

1.9.1　機器學習方法 ?14

1.9.2　機器學習架構 ?14

1.10　數據屬性與描述 ?15

1.10.1　數值屬性 ?16

1.10.2　分類屬性 ?16

1.10.3　數據描述 ?16

1.10.4　數據測量 ?17

1.11　數據清洗 ?18

1.11.1　缺失值 ?18

1.11.2　垃圾數據、噪聲數據或異常值 ?19

1.12　數據集成 ?19

1.13　數據降維 ?20

1.13.1　特征值和特征向量 ?20

1.13.2　主成分分析 ?20

1.13.3　奇異值分解 ?20

1.13.4　CUR分解 ?21

1.14　數據變換與離散化 ?21

1.14.1　數據變換 ?21

1.14.2　標準化數據的變換方法 ?22

1.14.3　數據離散化 ?22

1.15　結果可視化 ?23

1.16　練習 ?24

1.17　總結 ?24

第2章　頻繁模式、關聯規則和相關規則挖掘 ?25

2.1　關聯規則和關聯模式概述 ?26

2.1.1　模式和模式發現 ?26

2.1.2　關系或規則發現 ?29

2.2　購物籃分析 ?30

2.2.1　購物籃模型 ?31

2.2.2　Apriori算法 ?31

2.2.3　Eclat算法 ?35

2.2.4　FP-growth算法 ?37

2.2.5　基于最大頻繁項集的GenMax算法 ?41

2.2.6　基于頻繁閉項集的Charm算法 ?43

2.2.7　關聯規則生成算法 ?44

2.3　混合關聯規則挖掘 ?46

2.3.1　多層次和多維度關聯規則挖掘 ?46

2.3.2　基于約束的頻繁模式挖掘 ?47

2.4　序列數據集挖掘 ?48

2.4.1　序列數據集 ?48

2.4.2　GSP算法 ?48

2.5　R語言實現 ?50

2.5.1　SPADE算法 ?51

2.5.2　從序列模式中生成規則 ?52

2.6　高性能算法 ?52

2.7　練習 ?53

2.8　總結 ?53

第3章　分類 ?54

3.1　分類 ?55

3.2　通用決策樹歸納法 ?56

3.2.1　屬性選擇度量 ?58

3.2.2　決策樹剪枝 ?59

3.2.3　決策樹生成的一般算法 ?59

3.2.4　R語言實現 ?61

3.3　使用ID3算法對高額度信用卡用戶分類 ?61

3.3.1　ID3算法 ?62

3.3.2　R語言實現 ?64

3.3.3　網絡攻擊檢測 ?64

3.3.4　高額度信用卡用戶分類 ?66

3.4　使用C4.5算法進行網絡垃圾頁面檢測 ?66

3.4.1　C4.5算法 ?67

3.4.2　R語言實現 ?68

3.4.3　基于MapReduce的并行版本 ?69

3.4.4　網絡垃圾頁面檢測 ?70

3.5　使用CART算法判斷網絡關鍵資源頁面 ?72

3.5.1　CART算法 ?73

3.5.2　R語言實現 ?74

3.5.3　網絡關鍵資源頁面判斷 ?74

3.6　木馬程序流量識別方法和貝葉斯分類 ?75

3.6.1　估計 ?75

3.6.2　貝葉斯分類 ?76

3.6.3　R語言實現 ?77

3.6.4　木馬流量識別方法 ?77

3.7　垃圾郵件識別和樸素貝葉斯分類 ?79

3.7.1　樸素貝葉斯分類 ?79

3.7.2　R語言實現 ?80

3.7.3　垃圾郵件識別 ?80

3.8　基于規則的計算機游戲玩家類型分類和基于規則的分類 ?81

3.8.1　從決策樹變換為決策規則 ?82

3.8.2　基于規則的分類 ?82

3.8.3　序列覆蓋算法 ?83

3.8.4　RIPPER算法 ?83

3.8.5　計算機游戲玩家類型的基于規則的分類 ?85

3.9　練習 ?86

3.10　總結 ?86

第4章　高級分類算法 ?87

4.1　集成方法 ?87

4.1.1　Bagging算法 ?88

4.1.2　Boosting和AdaBoost算法 ?89

4.1.3　隨機森林算法 ?91

4.1.4　R語言實現 ?91

4.1.5　基于MapReduce的并行版本 ?92

4.2　生物學特征和貝葉斯信念網絡 ?92

4.2.1　貝葉斯信念網絡算法 ?93

4.2.2　R語言實現 ?94

4.2.3　生物學特征 ?94

4.3　蛋白質分類和k近鄰算法 ?94

4.3.1　kNN算法 ?95

4.3.2　R語言實現 ?95

4.4　文檔檢索和支持向量機 ?95

4.4.1　支持向量機算法 ?97

4.4.2　R語言實現 ?99

4.4.3　基于MapReduce的并行版本 ?99

4.4.4　文檔檢索 ?100

4.5　基于頻繁模式的分類 ?100

4.5.1　關聯分類 ?100

4.5.2　基于判別頻繁模式的分類 ?101

4.5.3　R語言實現 ?101

4.5.4　基于序列頻繁項集的文本分類 ?102

4.6　基于反向傳播算法的分類 ?102

4.6.1　BP算法 ?104

4.6.2　R語言實現 ?105

4.6.3　基于MapReduce的并行版本 ?105

4.7　練習 ?106

4.8　總結 ?107

第5章　聚類分析 ?108

5.1　搜索引擎和k均值算法 ?110

5.1.1　k均值聚類算法 ?111

5.1.2　核k均值聚類算法 ?112

5.1.3　k模式聚類算法 ?112

5.1.4　R語言實現 ?113

5.1.5　基于MapReduce的并行版本 ?113

5.1.6　搜索引擎和網頁聚類 ?114

5.2　自動提取文檔文本和k中心點算法 ?116

5.2.1　PAM算法 ?117

5.2.2　R語言實現 ?117

5.2.3　自動提取和總結文檔文本 ?117

5.3　CLARA算法及實現 ?118

5.3.1　CLARA算法 ?119

5.3.2　R語言實現 ?119

5.4　CLARANS算法及實現 ?119

5.4.1　CLARANS算法 ?120

5.4.2　R語言實現 ?120

5.5　無監督的圖像分類和仿射傳播聚類 ?120

5.5.1　仿射傳播聚類 ?121

5.5.2　R語言實現 ?122

5.5.3　無監督圖像分類 ?122

5.5.4　譜聚類算法 ?123

5.5.5　R語言實現 ?123

5.6　新聞分類和層次聚類 ?123

5.6.1　凝聚層次聚類 ?123

5.6.2　BIRCH算法 ?124

5.6.3　變色龍算法 ?125

5.6.4　貝葉斯層次聚類算法 ?126

5.6.5　概率層次聚類算法 ?126

5.6.6　R語言實現 ?127

5.6.7　新聞分類 ?127

5.7　練習 ?127

5.8　總結 ?128

第6章　高級聚類分析 ?129

6.1　電子商務客戶分類分析和DBSCAN算法 ?129

6.1.1　DBSCAN算法 ?130

6.1.2　電子商務客戶分類分析 ?131

6.2　網頁聚類和OPTICS算法 ?132

6.2.1　OPTICS算法 ?132

6.2.2　R語言實現 ?134

6.2.3　網頁聚類 ?134

6.3　瀏覽器緩存中的訪客分析和DENCLUE算法 ?134

6.3.1　DENCLUE算法 ?135

6.3.2　R語言實現 ?135

6.3.3　瀏覽器緩存中的訪客分析 ?136

6.4　推薦系統和STING算法 ?137

6.4.1　STING算法 ?137

6.4.2　R語言實現 ?138

6.4.3　推薦系統 ?138

6.5　網絡情感分析和CLIQUE算法 ?139

6.5.1　CLIQUE算法 ?139

6.5.2　R語言實現 ?140

6.5.3　網絡情感分析 ?140

6.6　觀點挖掘和WAVE聚類算法 ?140

6.6.1　WAVE聚類算法 ?141

6.6.2　R語言實現 ?141

6.6.3　觀點挖掘 ?141

6.7　用戶搜索意圖和EM算法 ?142

6.7.1　EM算法 ?143

6.7.2　R語言實現 ?143

6.7.3　用戶搜索意圖 ?143

6.8　客戶購買數據分析和高維數據聚類 ?144

6.8.1　MAFIA算法 ?144

6.8.2　SURFING算法 ?145

6.8.3　R語言實現 ?146

6.8.4　客戶購買數據分析 ?146

6.9　SNS和圖與網絡數據聚類 ?146

6.9.1　SCAN算法 ?146

6.9.2　R語言實現 ?147

6.9.3　社交網絡服務 ?147

6.10　練習 ?148

6.11　總結 ?148

第7章　異常值檢測 ?150

7.1　信用卡欺詐檢測和統計方法 ?151

7.1.1　基于似然的異常值檢測算法 ?152

7.1.2　R語言實現 ?152

7.1.3　信用卡欺詐檢測 ?153

7.2　活動監控——涉及手機的欺詐檢測和基于鄰近度的方法 ?153

7.2.1　NL算法 ?153

7.2.2　FindAllOutsM算法 ?153

7.2.3　FindAllOutsD算法 ?154

7.2.4　基于距離的算法 ?155

7.2.5　Dolphin算法 ?156

7.2.6　R語言實現 ?157

7.2.7　活動監控與手機欺詐檢測 ?157

7.3　入侵檢測和基于密度的方法 ?157

7.3.1　OPTICS-OF算法 ?159

7.3.2　高對比度子空間算法 ?159

7.3.3　R語言實現 ?160

7.3.4　入侵檢測 ?160

7.4　入侵檢測和基于聚類的方法 ?161

7.4.1　層次聚類檢測異常值 ?161

7.4.2　基于k均值的算法 ?161

7.4.3　ODIN算法 ?162

7.4.4　R語言實現 ?162

7.5　監控網絡服務器的性能和基于分類的方法 ?163

7.5.1　OCSVM算法 ?163

7.5.2　一類最近鄰算法 ?164

7.5.3　R語言實現 ?164

7.5.4　監控網絡服務器的性能 ?164

7.6　文本的新奇性檢測、話題檢測與上下文異常值挖掘 ?164

7.6.1　條件異常值檢測算法 ?165

7.6.2　R語言實現 ?166

7.6.3　文本的新奇性檢測與話題檢測 ?166

7.7　空間數據中的集體異常值 ?167

7.7.1　路徑異常值檢測算法 ?167

7.7.2　R語言實現 ?167

7.7.3　集體異常值的特征 ?168

7.8　高維數據中的異常值檢測 ?168

7.8.1　Brute-Force算法 ?168

7.8.2　HilOut算法 ?168

7.8.3　R語言實現 ?169

7.9　練習 ?169

7.10　總結 ?169

第8章　流數據、時間序列數據和序列數據挖掘 ?171

8.1　信用卡交易數據流和STREAM算法 ?171

8.1.1　STREAM算法 ?172

8.1.2　單通道法聚類算法 ?173

8.1.3　R語言實現 ?174

8.1.4　信用卡交易數據流 ?174

8.2　預測未來價格和時間序列分析 ?175

8.2.1　ARIMA算法 ?176

8.2.2　預測未來價格 ?176

8.3　股票市場數據和時間序列聚類與分類 ?176

8.3.1　hError算法 ?177

8.3.2　基于1NN分類器的時間序列分類 ?178

8.3.3　R語言實現 ?178

8.3.4　股票市場數據 ?178

8.4　網絡點擊流和挖掘符號序列 ?179

8.4.1　TECNO-STREAMS算法 ?179

8.4.2　R語言實現 ?181

8.4.3　網絡點擊流 ?181

8.5　挖掘事務數據庫中的序列模式 ?181

8.5.1　PrefixSpan算法 ?182

8.5.2　R語言實現 ?182

8.6　練習 ?182

8.7　總結 ?182

第9章　圖挖掘與網絡分析 ?183

9.1　圖挖掘 ?183

9.1.1　圖 ?183

9.1.2　圖挖掘算法 ?184

9.2　頻繁子圖模式挖掘 ?184

9.2.1　gPLS算法 ?184

9.2.2　GraphSig算法 ?184

9.2.3　gSpan算法 ?185

9.2.4　最右路徑擴展和它們的支持 ?185

9.2.5　子圖同構枚舉算法 ?186

9.2.6　典型的檢測算法 ?186

9.2.7　R語言實現 ?186

9.3　社交網絡挖掘 ?186

9.3.1　社區檢測和Shingling算法 ?187

9.3.2　節點分類和迭代分類算法 ?188

9.3.3　R語言實現 ?188

9.4　練習 ?188

9.5　總結 ?188

第10章　文本與網絡數據挖掘 ?189

10.1　文本挖掘與TM包 ?190

10.2　文本總結 ?190

10.2.1　主題表示 ?191

10.2.2　多文檔總結算法 ?192

10.2.3　最大邊緣相關算法 ?193

10.2.4　R語言實現 ?193

10.3　問答系統 ?194

10.4　網頁分類 ?194

10.5　對報刊文章和新聞主題分類 ?195

10.5.1　基于N-gram的文本分類算法 ?195

10.5.2　R語言實現 ?197

10.6　使用網絡日志的網絡使用挖掘 ?197

10.6.1　基于形式概念分析的關聯規則挖掘算法 ?198

10.6.2　R語言實現 ?198

10.7　練習 ?198

10.8　總結 ?199

附錄　算法和數據結構 ?200

第1章

預?備?知?識

本章中，你將學習基本的數據挖掘術語，比如數據定義、預處理等。

最重要的數據挖掘算法將通過R語言進行說明，以便幫助你快速掌握原理，包括但不局限于分類、聚類和異常值檢測。在深入研究數據挖掘之前，我們來看一看將要介紹的主題：

數據挖掘

社交網絡挖掘

文本挖掘

網絡數據挖掘

為什么選擇R

統計學

機器學習

數據屬性與描述

數據測量

數據清洗

數據集成

數據降維

數據變換與離散化

結果可視化

在人類歷史上，來自每個方面的數據結果都是廣泛的，例如網站、由用戶的電子郵件或姓名或賬戶構成的社交網絡、搜索詞、地圖上的位置、公司、IP地址、書籍、電影、音樂和產品。

數據挖掘技術可應用于任何類型的舊數據或者新數據，每種數據類型都可以運用特定的技術（并不需要全部技術）得到最好的處理。也就是說，數據挖掘技術受到數據類型、數據集大小以及任務應用環境等條件的限制。每一種數據集都有自己適合的數據挖掘解決方案。

一旦舊的數據挖掘技術不能應用于新的數據類型或者如果新的數據類型不能轉換成傳統的數據類型，那么總是需要研究新的數據挖掘技術。應用于Twitter龐大資源集的流數據挖掘算法的演變是一個典型的例子，針對社交網絡開發的圖挖掘算法是另一個例子。

最流行且最基本的數據形式來自數據庫、數據倉庫、有序數據或者序列數據、圖形數據以及文本數據等。換句話說，它們是聯合數據、高維數據、縱向數據、流數據、網絡數據、數值數據、分類數據或者文本數據。

1.1　大數據

大數據是數據量很大的數據，它不適合存儲在單臺機器中。也就是說，在研究大數據時，數據本身的大小成為了問題的一部分。除了容量（Volume），大數據的其他兩個主要特征就是多樣性（Variety）和速度（Velocity），這就是大數據著名的三個特征。速度指的是數據處理的速率或者數據處理有多快；多樣性指的是各種數據源類型。大數據源集合產生的噪聲更頻繁并且影響挖掘的結果，這就需要高效的數據預處理算法。

因此，分布式文件系統用來作為對大量數據成功執行并行算法的工具，可以肯定的是，每過1秒，我們將得到更多的數據。數據分析和可視化技術是與海量數據相關的數據挖掘任務的主要部分。海量數據的特性吸引了許多與平臺相關的新的數據挖掘技術，其中一個就是RHadoop。我們將在后面的內容中對它進行描述。

大數據中的一些重要數據類型如下所述：

第一種數據類型來自攝像機視頻，它包含了用于加快犯罪調查分析、增強零售分析以及軍事情報分析等更多的元數據。

第二種數據類型來自嵌入式的傳感器，如醫用傳感器，用來監測病毒的任何潛在爆發。

第三種數據類型來自娛樂，由任何人通過社交媒體自由發布的信息。

第四種數據類型來自消費者圖像，它們源自社交媒體，像這種圖像的標注是很重要的。

下面的表說明了數據大小增長的歷史。該表顯示信息每兩年翻一番多，改變著研究人員或者公司的管理方式，通過數據挖掘技術從數據中獲取價值，揭示著新的數據挖掘研究。

年份 數據大小 說　　明

N/A 1MB（Megabyte：兆字節）=220

人的大腦大約存儲200MB的信息

N/A 1PB（Petabyte：拍字節）=250

這類似于由NASA對地球3年的觀察數據的大小或者相當于美國國會圖書館書籍的70.8倍

1999 1EB 1EB（Exabyte：艾字節）=260

世界產生了1.5EB獨特的信息

2007 281EB 世界產生了大約281EB獨特的信息

2011 1.8ZB 1ZB（Zetabyte：澤字節）=270

這是人類在2011年收集的所有數據

近期 1YB（Yottabytes：堯字節）=280

可擴展性和效率

效率、可擴展性、性能、優化以及實時執行的能力對于幾乎所有的算法都是很重要的問題，它對數據挖掘也是如此。數據挖掘算法始終有一些必要的衡量指標或者基準因素。

隨著數據量的持續增長，保持數據挖掘算法的效率和可擴展性對于有效地從眾多數據存儲庫或數據流中的海量數據集里提取信息是很有必要的。

從單臺機器到廣泛分布的數據存儲、眾多數據集的龐大規模以及數據挖掘方法計算的復雜性，這些都是驅動并行和分布式數據密集型挖掘算法發展的因素。

1.2　數據源

數據充當數據挖掘系統的輸入，因此數據存儲庫是非常重要的。在企業環境中，數據庫和日志文件是常見來源；在網絡數據挖掘中，網頁是數據的來源；連續地從各種傳感器中提取數據也是典型的數據源。

這里有一些免費的在線數據源十分有助于學習數據挖掘：

頻繁項集挖掘數據存儲庫（Frequent Itemset Mining Dataset Repository）：一個帶有數據集的存儲庫，用于找到頻繁項集的方法（http://fimi.ua.ac.be/data/）。

UCI機器學習存儲庫（UCI Machine Learning Repository）：一個數據集的集合，適用于分類任務（http://archive.ics.uci.edu/ml/）。

statlib的數據及其描述庫（The Data and Story Library at statlib）：DASL是一個在線庫，它擁有說明基本統計方法用途的數據文件和故事。我們希望提供來自多主題的數據，這樣統計學教師可以找到學生感興趣的真實世界的例子。使用DASL強大的搜索引擎來查找感興趣的故事和數據文件（http://lib.stat.cmu.edu/DASL/）。

詞匯網（WordNet）：一個英語詞匯數據庫（http://wordnet.princeton.edu）。

1.3　數據挖掘

數據挖掘就是在數據中發現一個模型，它也稱為探索性數據分析，即從數據中發現有用的、有效的、意想不到的且可以理解的知識。有些目標與其他科學，如統計學、人工智能、機器學習和模式識別是相同的。在大多數情況下，數據挖掘通常被視為一個算法問題。聚類、分類、關聯規則學習、異常檢測、回歸和總結都屬于數據挖掘任務的一部分。

數據挖掘方法可以總結為兩大類數據挖掘問題：特征提取和總結。

1.3.1　特征提取

這是為了提取數據最突出的特征并忽略其他的特征。下面是一些例子：

頻繁項集（Frequent itemset）：該模型對構成小項集籃子的數據有意義。（找出一堆項目中出現最為頻繁、關系最為密切的一個子集。——譯者注）

相似項（Similar item）：有時你的數據看起來像數據集的集合，而目標是找到一對數據集，它們擁有較大比例的共同元素。這是數據挖掘的一個基本問題。

1.3.2　總結

目標是簡明且近似地對數據集進行總結（或者說摘要），比如聚類，它是這樣一個過程：檢查數據的集合并根據某些度量將數據點分類到相應的類中。目標就是使相同類中的點彼此之間的距離較小，而不同類中的點彼此之間的距離較大。

1.3.3　數據挖掘過程

從不同的角度定義數據挖掘過程有兩種比較流行的過程，其中更廣泛采用的一種是CRISP-DM：

跨行業數據挖掘標準過程（Cross-Industry Standard Process for Data Mining，CRISP-DM）。

采樣、探索、修正、建模、評估（Sample, Explore, Modify, Model, Assess，縮寫為SEMMA），這是由美國SAS研究所制定的。

1.3.3.1　CRISP-DM

這個過程共分6個階段，如下圖所示。它不是一成不變的，但通常會有大量的回溯。

讓我們詳細地看一看每個階段：

業務理解（business understanding）：這項任務包括確定業務目標、評估當前形勢、建立數據挖掘目標并制訂計劃。

數據理解（data understanding）：這項任務評估數據需求，包括原始數據收集、數據描述、數據探索和數據質量的驗證。

數據準備（data preparation）：一旦獲得數據，在上一步中確定數據源。然后需要對數據進行選擇、清洗，并形成期望的形式和格式。

建模（modeling）：可視化和聚類分析對于初步分析是有用的。可以應用像廣義規則歸納（generalized rule induction）這樣的工具開發初始關聯規則。這是一個發現規則的數據挖掘技術，從條件因素與給定的決策或者結果之間的因果關系來對數據進行說明。也可以應用其他適用于數據的模型。

評估（evaluation）：結果應該在第一階段中的業務目標指定的環境下對模型結果進行評估。在大多數情況下，這會導致新需求的確定，轉而返回到前一個階段。

部署（deployment）：可以使用數據挖掘來驗證之前的假設或者知識。

1.3.3.2　SEMMA

下圖是SEMMA過程的概覽。

讓我們詳細地看一看這些過程：

采樣（sample）：在該步中，提取一個大數據集的一部分。

探索（explore）：為了更好地理解數據集，在此步中搜索未預料的趨勢和異常。

修正（modify）：創建、選擇和轉換變量，以便專注于模型構建過程。

建模（model）：搜索多種模型的組合，以便預測一個滿意的結果。

評估（assess）：根據實用性和可靠性對數據挖掘過程的結果進行評估。

1.4　社交網絡挖掘

正如我們前面提到的，數據挖掘是從數據中發現一個模型，社交網絡挖掘就是從表示社交網絡的圖形數據中發現模型。

社交網絡挖掘是網絡數據挖掘的一個應用，比較流行的應用有社會科學和文獻計量學、PageRank和HITS算法、粗粒度圖模型的不足、增強模型和技術、主題提取的評估以及網絡的評估與建模。

社交網絡

當涉及社交網絡的討論時，你會想到Facebook、Google+和LinkedIn等。社交網絡的基本特征如下：

存在一個參與網絡的實體集合。通常情況下，這些實體是人，但它們也完全可能是其他實體。

網絡的實體之間至少存在一種關系。在Facebook上，這種關系被稱為朋友，有時，這種關系要么存在要么不存在，兩個人要么是朋友要么不是朋友。然而，在社交網絡的其他例子中，關系有一個度。這個度可以是離散的，比如在Google+上，朋友、家人、相識或者不相識；這個度也可能是一個實際的數字，比如平均一天內兩個人相互交談所花費的時間。

社交網絡有一個非隨機性或者忠誠性的假設。這個條件最難形式化，但直觀解釋是關系趨于集中；也就是說，如果實體A與B和C都相關，那么B與C相關的概率就高于平均水平。

下面是社交網絡的一些種類：

電話網絡（telephone network）：該網絡的節點是電話號碼，代表個體。

電子郵件網絡（E-mail network）：該網絡的節點是電子郵件地址，也代表個體。

合作網絡（collaboration network）：該網絡的節點代表發表了研究論文的個體，連接兩個節點的邊表示聯合發表一篇或者多篇論文的兩個個體。

社交網絡以無向圖建模。實體是節點，如果兩個節點根據刻畫網絡的關系相互關聯，那么就有一條邊連接兩個節點。如果相關聯的關系有一個度，那么這個度就通過標記邊來表示。

下載代碼示例

你可以從http://www.packtpub.com的賬戶中下載所有你購買的Packt出版社出版的書籍的示例代碼文件。如果你在其他地方購買了這本書，你可以訪問http://www.packtpub.com/support網站并注冊，我們將通過電子郵件直接給你發送文件。

這里有一個例子，它是用R語言的sna程序包中的科爾曼高中朋友數據（Coleman’s High School Friendship Data）進行分析。數據來源于對某個學年同一高中的73個男孩之間的友好關系的研究，所有被調查對象提供了兩個時間點（春季和秋季）來報告其關系。數據集的名稱是coleman，它是R語言中的數組類型。節點代表一個具體的學生，線代表兩個學生之間的關系。

1.5　文本挖掘

文本挖掘基于文本數據，關注從大型自然語言文本中提取相關信息，并搜尋有意義的關系、語法關系以及提取實體或各項之間的語義關聯。它也被定義為自動或半自動的文本處理。相關的算法包括文本聚類、文本分類、自然語言處理和網絡挖掘。

文本挖掘的特征之一是數字與文本混合，或者用其他的觀點來說，就是源數據集中包含了混合數據類型。文本通常是非結構化文件的集合，這將被預處理并變換成數值或者結構化的表示。在變換之后，大部分的數據挖掘算法都可以應用，并具有不錯的效果。

文本挖掘的過程描述如下：

第一步準備文本語料庫，包括報告、信函等。

第二步基于文本語料庫建立一個半結構化的文本數據庫。

第三步建立一個詞語文檔矩陣，包含詞語的頻率。

第四步進行進一步的分析，比如文本分析、語義分析、信息檢索和信息總結。

1.5.1　信息檢索和文本挖掘

信息檢索幫助用戶查找信息，經常與在線文檔相關聯，它著重于信息的獲取、組織、存儲、檢索和分布。信息檢索（Information Retrieval，IR）的任務是根據查詢檢索有關的文檔。信息檢索的基本技術是測量相似性。其基本步驟如下所述：

指定一個查詢。下面是一些查詢類型：

關鍵詞查詢（keyword query）：由一個關鍵詞列表表示，用來查找包含至少一個關鍵詞的文檔。

布爾查詢（boolean query）：由布爾運算符和關鍵詞構建的查詢。

短語查詢（phrase query）：由組成短語的一系列詞語所構成的查詢。

近鄰查詢（proximity query）：短語查詢的降級版本，它可以是關鍵詞和短語的組合。

全文檔查詢（full document query）：一個完整文檔的查詢，用于尋找類似于查詢文檔的其他文檔。

自然語言問題（natural language questions）：該查詢有助于將用戶的需求表示成一個自然語言問題。

搜索文檔集。

返回相關文檔的子集。

1.5.2　文本挖掘預測

預測文本的結果與預測數值數據挖掘一樣耗力，并且有與數值分類相關聯的相似問題。文本挖掘預測通常是一個分類問題。

文本預測需要先驗知識，通過樣本了解如何對新文檔做出預測。一旦文本變換成數值數據，就可以應用預測方法。

1.6　網絡數據挖掘

網絡挖掘的目的是從網絡超鏈接結構、網頁和使用數據來發現有用的信息或知識。網絡是作為數據挖掘應用輸入的最大數據源之一。

網絡數據挖掘基于信息檢索、機器學習（Machine Learning，ML）、統計學、模式識別和數據挖掘。盡管很多數據挖掘方法可以應用于網絡挖掘，但是由于異構的、半結構化的和非結構化的網絡數據，所以網絡挖掘不單純是一個數據挖掘問題。

網絡挖掘任務至少可以定義為3種類型：

網絡結構挖掘（web structure mining）：這有助于從超鏈接中尋找有關網址和頁面的有用信息或者有價值的結構總結。

網絡內容挖掘（web content mining）：這有助于從網頁內容中挖掘有用的信息。

網絡用法挖掘（web usage mining）：這有助于從網絡日志中發現用戶訪問模式，以便檢測入侵、欺詐和試圖闖入的情況。

應用于網絡數據挖掘的算法源自經典的數據挖掘算法。它們有很多相似之處，比如挖掘過程，但也存在差異。網絡數據挖掘的特征使其不同于數據挖掘的原因如下：

數據是非結構化的。

網絡信息不斷變化和數據量不斷增長。

任何數據類型都可以在網絡上得到，如結構化和非結構化數據。

網絡上存在異構信息，冗余頁面也存在。

網絡上鏈接著海量信息。

數據是噪聲數據。

網絡數據挖掘不同于一般數據挖掘是由于源數據集的巨大動態容量、極其多樣化的數據格式等。與網絡相關的最流行的數據挖掘任務如下：

信息提取（Information Extraction，IE）：信息提取的任務包含以下步驟：詞匯標記、句子分割、詞性分配、命名實體識別、短語解析、句子解析、語義解釋、話語解釋、模板填充以及合并。

自然語言處理（Natural Language Processing，NLP）：它研究人與人和人與機器互動的語言特征、語言能力和行為模型、用這樣的模型實現過程的框架、過程/模型的迭代優化以及對結果系統的評估技術。與網絡數據挖掘相關的經典自然語言處理任務包括標注、知識表示、本體論模型等。

問題回答（question answering）：目標就是以自然語言形式從文本集中尋找問題的答案。它可以歸類為槽填充、有限域以及具有更高難度的開放域。一個簡單的例子就是基于預先定義的常見問題解答（FAQ）來回答客戶的詢問。

資源發現（resource discovery）：比較流行的應用是優先收集重要的頁面；使用鏈路拓撲結構、主題局部性和主題爬行進行相似性搜索；社區發現。

1.7　為什么選擇R

R是一種高質量、跨平臺、靈活且廣泛使用的開源免費語言，可用于統計學、圖形學、數學和數據科學。它由統計學家創建，并為統計學家服務。

R語言包含了5?000多種算法以及全球范圍內具備專業知識的數百萬用戶，并得到了充滿活力且富有才華的社區貢獻者的支持。它不僅可以使用完善的統計技術，也允許使用試驗性的統計技術。

R是一個用于統計計算與圖形學的免費開源軟件，其環境由R-projects維護，根據自由軟件基金會（Free Software Foundation）的GNU通用公共授權（General Public License）的條款，R語言的源代碼是可以獲得的。由于存在各種平臺，如Unix、Linux、Windows以及Mac OS，所以R語言也編譯和開發了用于不同平臺的版本。

R的缺點有哪些

R存在以下3個缺點：

一個缺點就是內存約束，因此它需要將整個數據集存儲在內存（RAM）中以便實現高性能，這也稱為內存分析。

類似于其他開源系統，任何人都可以創建和貢獻經過嚴格測試或者未經過嚴格測試的程序包。換言之，貢獻給R社區的程序包是容易出錯的，需要更多的測試以確保代碼的質量。

R語言似乎比某些其他商業語言慢。

幸運的是，存在可用于解決這些問題的程序包。有些方法可以歸為并行解決方案，本質就是將程序的運行分散到多個CPU上，從而克服上面所列R語言的缺陷。有不少好的例子，比如RHadoop，但并不局限于RHadoop。你很快就會在下面的章節中看到更多關于這個話題的內容。你可以從綜合R典藏網（Comprehensive R Archive Network，CRAN）下載SNOW添加包和Parallel添加包。

1.8　統計學

統計學研究數據收集、數據分析、數據解釋或說明，以及數據表示。作為數據挖掘的基礎，它們的關系將在下面章節中說明。

1.8.1　統計學與數據挖掘

第一次使用數據挖掘這個術語的人是統計學家。最初，數據挖掘是一個貶義詞，指的是企圖提取得不到數據支持的信息。在一定程度上，數據挖掘構建統計模型，這是一個基礎分布，用于可視化數據。

數據挖掘與統計學有著內在的聯系，數據挖掘的數學基礎之一就是統計學，而且很多統計模型都應用于數據挖掘中。

統計模型可以用來總結數據集合，也可以用于驗證數據挖掘結果。

1.8.2　統計學與機器學習

隨著統計學和機器學習的發展，這兩個學科成為一個統一體。統計檢驗被用來驗證機器學習模型和評估機器學習算法，機器學習技術與標準統計技術可以有機結合。

1.8.3　統計學與R語言

R是一種統計編程語言，它提供大量基于統計知識的統計函數。許多R語言添加包的貢獻者來自統計學領域，并在他們的研究中使用R語言。

1.8.4　數據挖掘中統計學的局限性

在數據挖掘技術的演變過程中，由于數據挖掘中統計的局限性，人們在試圖提取并不真正存在于數據中的信息時可能會犯錯誤。

Bonferroni原則（Bonferroni’s Principle）是一個統計定理，也被稱為Bonferroni校正（Bonferroni correction）。你可以假設你找到的大部分結果都是事實上不存在的，即算法返回的結果大大超過了所假設的范圍。

1.9　機器學習

應用于機器學習算法的數據集稱為訓練集，它由一組成對的數據(x, y)構成，稱為訓練樣本。成對的數據解釋如下：

x：這是一個值向量，通常稱為特征向量。每個值或者特征，要么是分類變量（這些值來自一組離散值，比如{S, M, L}），要么是數值型。

y：這是一個標簽，表示x的分類或者回歸值。

機器學習過程的目的就是發現一個函數y=f(x)，它能最好地預測與每一個x值相關聯的y值。原則上y的類型是任意的，但有一些常見的和重要的類型：

y：這是一個實數，機器學習問題稱為回歸。

y：這是一個布爾值，真或者假，通常分別寫為+1和-1。在這種情況下，機器學習問題稱為二元分類。

y：這是某些有限集合的成員。這個集合的成員可以認為是類，并且每個成員代表一類。此機器學習問題稱為多級分類。

y：這是某些潛在無限集合的成員，例如，x的一個解析樹，它被解析為一個句子。

到現在為止，在我們可以更直接地描述挖掘目標的情況下，還沒有證明機器學習是成功的。機器學習和數據挖掘是兩個不同的主題，盡管它們共享一些算法——特別是目標為提取信息時。在某些情況下，機器學習是有意義的，一個典型的情形就是當我們試圖從數據集中尋找某些信息。

1.9.1　機器學習方法

算法的主要類型均列于下方，每個算法由函數f區分。

決策樹（decision tree）：這種形式的f呈樹形，樹的每個節點都有一個關于x的函數，用來確定必須搜索哪個子節點或者哪些子節點。

感知器（perceptron）：這些是應用于向量x={x1, x2, …, xn}的分量的閾值函數。對每個i=1, 2, …, n，權重wi與第i個分量相關聯，且有一個閾值wixi≥θ。如果閾值滿足條件，輸出為+1，否則為-1。

神經網絡（neural net）：這些是有感知器的非循環網絡，某些感知器的輸出用作其他感知器的輸入。

基于實例的學習（instance-based learning）：此方法使用整個訓練集來表示函數f。

支持向量機（support-vector machine）：該類的結果是一個分類器，它對未知數據更準確。分類的目標是尋找最優超平面，通過最大化兩個類的最近點之間的間隔將它們分隔。

1.9.2　機器學習架構

這里，機器學習的數據方面指的是處理數據的方式以及使用數據構建模型的方式。

訓練和測試（training and testing）：假定所有數據都適用于訓練，分離出一小部分可用的數據作為測試集，使用余下的數據建立一個合適的模型或者分類器。

批處理與在線學習（batch versus online learning）：對于批處理方式，在其進程的開始，整個訓練集都是可得到的；對于在線學習，其訓練集以數據流的形式獲得，且對它進行處理后不能被再次訪問。

特征選擇（feature selection）：這有助于找出那些用作學習算法輸入的特征。

創建訓練集（creating a training set）：通過手動創建標簽信息，從而把數據變為訓練集。

1.10　數據屬性與描述

屬性（attribute）是代表數據對象的某些特征、特性或者維度的字段。

在大多數情況下，數據可以用矩陣建模或者以矩陣形式表示，其中列表示數據屬性，行表示數據集中的某些數據記錄。對于其他情況，數據不能用矩陣表示，比如文本、時間序列、圖像、音頻以及視頻等。數據可以通過適當的方法，如特征提取，變換成矩陣。

數據屬性的類型來自它的語境、域或者語義，有數值、非數值、分類數據類型以及文本數據。有兩種適用于數據屬性與描述的視角，它們在數據挖掘與R語言中被廣泛使用，如下所述：

基于代數或者幾何視角的數據（data in algebraic or geometric view）：整個數據集可以建模為一個矩陣。線性代數和抽象代數在這里起著很重要的作用。

基于概率視角的數據（data in probability view）：將觀測數據視為多維隨機變量。每一個數值屬性就是一個隨機變量，維度就是數據的維度。不論數值是離散的還是連續的，這里都可以運用概率論。

為了幫助讀者更自然地學習R語言，我們將采用幾何、代數以及概率視角的數據。

這里有一個矩陣的例子。列數由m確定，m就是數據的維度；行數由n確定，n就是數據集的大小。

其中，xi表示第i行，表示一個m元組，如下所示：

Xj表示第j列，表示一個n元組，如下所示：

1.10.1　數值屬性

因為數值數據是定量的且允許任意計算，所以它易于處理。數值數據與整數或者浮點數的性質是一樣的。

來自有限集或者可數無限集的數值屬性稱為是離散的（discrete），例如一個人的年齡，它是從1150開始的整數值。來自任何實數值的其他屬性稱為是連續的（continuous）。主要有兩種數值類型：

定距尺度（interval-scaled）：這是以相同單位尺度測量的定量值，例如某些特定魚類的重量，以國際度量標準，如克或者千克。

定比尺度（ratio-scaled）：除了值之間的差值之外，該值可以通過值之間的比率進行計算。這是一個具有固定零點的數值屬性，因此可以說一個值是另一個值的多少倍。

1.10.2　分類屬性

分類屬性的值來自一組符號構成的集域（集合），例如人類服裝的大小被分類為{S, M, L}。分類屬性可以劃分為兩種類型：

名義（nominal）：該集合中的值是無序的且不是定量的，這里只有相等運算是有意義的。

定序（ordinal）：與定類類型相反，這里的數據是有序的。這里除了相等運算外，也可以進行不相等運算。

1.10.3　數據描述

基本描述可以用來識別數據的特征，區分噪聲或者異常值。兩種基本的統計描述如下所示：

集中趨勢的度量（measures of central tendency）：它測量數據分布的中間或中心位置：均值、中位數、眾數、值域中點等。

數據的離散程度的度量（measures of dispersion of the data）：它包括全距、四分位數、四分位數間距等。

1.10.4　數據測量

數據測量用于聚類、異常值檢測和分類。它指的是近似性、相似性和差異性的度量。兩個元組或數據記錄之間的相似值的取值范圍是0～1的一個實數值，數值越大，元組之間的相似度就越高。差異性的原理相反，差異性值越大，兩個元組就越不相似。

對于一個數據集，數據矩陣在n×m階矩陣（n個元組和m個屬性）中存儲了n個數據元組：

相異度矩陣存儲了數據集中的所有n個元組的近似度集合，通常為一個n×n階的矩陣。在下面的矩陣中，d(i,?j)是兩個元組之間的差異性。0表示彼此之間高度相似或者高度接近，同樣，1表示完全不相同。數值越大，相異度就越高。

大多數時候，相異度和相似度是相關的概念。相似性度量通常可以使用一個函數來定義，可以用相異性的度量來構建相似性，反之亦然。

這里有一張表，它列出了不同類型屬性值常用的度量方法。

屬性值類型 相異度

定類屬性 兩個元組之間的相異度可由下式計算：d(i,?j)=(p-m)/p。其中，p表示數據的維度，m表示在相同狀態下匹配的數目

定序屬性 定類屬性的處理與數值屬性的處理類似，但在使用相應的方法之前，它首先需要進行變換

定距尺度 歐幾里得（Euclidean）、曼哈頓（Manhattan）、閔可夫斯基（Minkowski）距離用于計算數據元組的相異度

1.11　數據清洗

數據清洗是數據質量的一部分，數據質量（Data Quality，DQ）的目標如下：

準確性（數據被正確記錄）。

完整性（所有相關數據都被記錄）。

唯一性（沒有重復的數據記錄）。

時效性（數據不過時）。

一致性（數據是一致的）。

數據清洗試圖填補缺失值、發現異常值同時平滑噪聲、修正數據中的不一致性。數據清洗通常是一個兩步迭代的過程，由差異檢測和數據變換構成。

在大多數情況下，數據挖掘的過程都包含如下兩個步驟：

第一步對源數據集進行測試以便發現差異。

第二步是選擇變換方法來修正數據（基于要修正屬性的準確性以及新值與原始值的接近程度）。然后應用變換來修正差異。

1.11.1　缺失值

在從各類數據源獲取數據的過程中，當某些字段為空或者包含空值時會存在許多情況。好的數據錄入程序應該盡量避免或者最小化缺失值或錯誤的數目。缺失值與默認值是無法區分的。

如果某些字段存在缺失值，那么有一些解決方案——每種解決方案都有不同的考慮與缺陷，并且每種方案在特定情況下都是可用的。

忽略元組：由于忽略元組，除了那個缺失值以外，你也不能使用剩余的值。這種方法只適用于當元組包含的一些屬性有缺失值或者每個屬性缺失值的百分比變化不大時。

人工填補缺失值：對于大型數據集，該方法并不適用。

使用全局常量填補缺失值（use a global constant to fill the value）：使用該常量填補缺失值可能會誤導挖掘過程，并不十分安全。

使用屬性集中趨勢的度量來填補缺失值：集中趨勢的度量可用于對稱數據分布。

使用屬性均值或者中位數：當給定元組時，對于屬于同一類的所有樣本使用屬性均值或者中位數。

使用最可能的值來填補缺失值：缺失值可以用回歸或者基于推理的工具，比如貝葉斯形式或者決策樹歸納所確定的數據進行填補。

最流行的方法是最后一種方案，它基于當前值以及源于其他屬性的值。

1.11.2　垃圾數據、噪聲數據或異常值

正如在物理測試或者統計測試中，噪聲是發生在獲取測量數據的測試過程中的一個隨機誤差。對于數據收集的過程，不管你使用什么方法，噪聲都不可避免地存在。

用于數據平滑的方法如下所述。隨著數據挖掘研究的發展，新的方法也不斷出現。

分箱：這是一個局部范圍平滑的方法，在該方法中，使用近鄰值計算特定箱子的終值。已排序的數據分布到多個箱子中，箱子中的每個值將被基于近鄰值來計算出的值所取代。計算可以是箱子的中位數、箱子的邊界，即箱子的邊界數據。

回歸：回歸的目標是找到最佳曲線或者多維空間中某個類似于曲線的東西（函數）。因此，其他值可以用于預測目標屬性或者變量的值。在其他方面，這是一種比較流行的平滑方法。

分類或者異常檢測：分類器是發現噪聲或者異常的另一種固有方法。在分類過程中，除了異常值外，大部分源數據將被分組到幾個類中。

1.12　數據集成

數據集成將多個數據源中的數據合并，形成一個一致的數據存儲。其常見的問題如下：

異構數據：這沒有普遍的解決方案。

不同的定義（different definition）：這是內在的，即相同的數據具有不同的定義，如不同的數據庫模式。

時間一致性：這可以檢查數據是否在相同的時間段收集。

舊數據：這指的是從舊系統留下的數據。

社會學因素：這限制了數據的收集。

處理上述問題也有一些方法：

實體識別問題：模式整合和目標匹配是棘手的，這稱為實體識別問題。

冗余與相關性分析：有些冗余可以通關相關性分析來檢測。給定兩個屬性，基于可用的數據，這樣的分析可以測量一個屬性影響另一個屬性的強度。

元組重復：在元組級可以檢測重復，從而可以檢測屬性之間的冗余。

數據值沖突的檢測和分辨率：在不同的抽象級，屬性可能不同，其中一個系統中的一個屬性可能在不同的抽象級被記錄。

1.13　數據降維

在分析復雜的多變量數據集時，降低維度往往是必要的，因為這樣的數據集總是以高維形式呈現。因此，舉例來說，從大量變量來建模的問題和基于定性數據多維分析的數據挖掘任務。同樣，有很多方法可以用來對定性數據進行數據降維。

降低維度的目標就是通過兩個或者多個比原先矩陣小很多的矩陣來取代大型矩陣，但原始矩陣可以被近似重構。通常是選取這些小矩陣的乘積來重構原始的矩陣，這一般會損失一些次要信息。

1.13.1　特征值和特征向量

一個矩陣的特征向量是指該矩陣（下述方程中的A）乘以該特征向量（下述方程中的v）的結果為一個常數乘以該特征向量。這個常數就是關于該特征向量的特征值。一個矩陣可能有好幾個特征向量。

Av=λv

一個特征對就是特征向量及其特征值，也就是上式中的(v, λ)。

1.13.2　主成分分析

用于降維的主成分分析（Principal Component Analysis，PCA）技術將多維空間中的點集所構成的數據視為一個矩陣，其中行對應于點，列對應于維度。

該矩陣與其轉置的乘積具有特征向量和特征值，其主特征向量可以看作空間中的方向，且沿著該方向，點排成最佳的直線。第二特征向量表示的方向使得源于主特征向量的偏差在該方向上是最大的。

主成分分析降維是通過最小化表示矩陣中給定列數的均方根誤差來近似數據，用其少數的特征向量來表示矩陣中的點。

1.13.3　奇異值分解

一個矩陣的奇異值分解（Singular Value Decomposition，SVD）由以下3個矩陣構成：

U

Σ

V

U和V是列正交的，其列向量是正交的且它們的長度為1。Σ是一個對角矩陣，其對角線上的值稱為奇異值。原始矩陣等于U、Σ和V的轉置的乘積。

當連接原始矩陣的行和列的概念較少時，奇異值分解是有用的。

當矩陣U和V通常與原始矩陣一樣大時，采用奇異值分解降維。為了使用較少列的U和V，刪除U、V和Σ中與最小奇異值對應的列。這樣根據修正后的U、Σ和V重構原始矩陣時就最小化了誤差。

1.13.4　CUR分解

CUR分解旨在將一個稀疏矩陣分解成更小的稀疏矩陣，這些小矩陣的乘積近似于原始矩陣。

CUR從一個給定的稀疏矩陣中選擇一組列構成矩陣C和一組行構成矩陣R，C和R的作用就相當于奇異值分解中的U和V?T。行與列是根據一個分布隨機選擇的，該分布取決于元素平方和的平方根。在矩陣C和R之間有一個方陣稱為U，它是由所選擇的行與列的交集的偽逆（pseudo-inverse）所構造出來的。

根據CUR解決方案，3個分量矩陣C、U和R將被檢索。這3個矩陣的乘積將近似于原始矩陣M。在R社區中，有一個R添加包rCUR用于CUR矩陣分解。

1.14　數據變換與離散化

根據前面的內容，我們可以知道總有一些數據格式最適合特定的數據挖掘算法。數據變換是一種將原始數據變換成較好數據格式的方法，以便作為數據處理前特定數據挖掘算法的輸入。

1.14.1　數據變換

數據變換程序將數據變換成可用于挖掘的恰當形式。它們如下所述：

平滑：使用分箱、回歸和聚類去除數據中的噪聲。

屬性構造：根據給定的屬性集，構造和添加新的屬性。

聚合：在匯總或者聚合中，對數據執行操作。

標準化：這里，對屬性數據進行縮放以便落入一個較小的范圍。

離散化：數值屬性的原始值被區間標簽或者概念標簽所取代。

對名義數據進行概念分層：這里，屬性可以被推廣到更高層次的概念中。

1.14.2　標準化數據的變換方法

為了避免依賴數據屬性的測量單位的選擇，數據需要標準化。這意味著將數據變換或者映射到一個較小的或者共同的范圍內。在這個過程后，所有的屬性獲得相同的權重。有許多標準化的方法，我們看看其中的一些辦法。

最小-最大標準化：該方法保留了原始數據值之間的關系，對原始數據進行線性變換。當一個屬性的實際最大值和最小值可用時，該屬性將被標準化。

z分數標準化：這里，屬性值的標準化是基于屬性的均值和標準差。當對一個屬性進行標準化時，如果其實際最大值和最小值是未知的，則該方法仍然是有效的。

十進制標準化：該方法通過移動屬性值的小數點將其標準化。

1.14.3　數據離散化

數據離散化通過值映射將數值數據變換成區間標簽或者概念標簽。離散化技術包括：

通過分箱將數據離散化：這是一個根據指定數目的、分段的、自上而下的無監督分割技術。

根據直方圖分析將數據離散化：在該技術中，直方圖將屬性值分割在不相交的范圍內，稱為桶或者箱，同樣為無監督的方法。

通過聚類分析將數據離散化：在該技術中，應用聚類算法離散化數值屬性，它通過將該屬性的值分割到不同的類或者組中。

通過決策樹分析將數據離散化：這里，決策樹采用自上而下的分割方法，它是一個有監督的方法。為了離散化數值屬性，該方法選擇具有最小熵的屬性值作為分割點，并遞歸地劃分所得的區間以實現分層離散化。

通過相關分析將數據離散化：該技術采用自下而上的方法，通過發現最佳近鄰區間，然后遞歸地將它們合并成更大的區間，這是一個有監督的方法。

1.15　結果可視化

可視化是數據描述的圖形表示，以便一目了然地揭示復雜的信息，包括所有類型的結構化信息表示。它包括圖形、圖表、圖解、地圖、故事板以及其他結構化的圖示。

好的可視化結果使你有機會通過專家的眼光來查看數據。可視化結果很美，不僅因為它們的美學設計，而且因為它們有效地生成見解和新理解的優雅的細節層。

數據挖掘的每個結果都可以通過使用算法進行可視化說明。可視化在數據挖掘過程中起著重要的作用。

創建最佳的可視化有4個主要特征：

新穎的：可視化不能只作為一個信息渠道，而且還要提供一些新意，以新的風格呈現信息。

信息化的：對這些因素和數據本身的注意將形成一個有效的、成功的且漂亮的可視化結果。

有效的：好的可視化結果有明確的目標、清晰定義的信息或者用于表達信息的特殊視角。它必須盡可能簡單明了，但不應該丟失必要的、相關的復雜性。這里無關的數據可以看作噪聲。可視化應該反映它們所代表的數據的質量，揭示數據源中內在的和隱含的性質與關系，以便給最終使用者帶來新的知識、見解和樂趣。

美感：圖形必須為呈現信息的主要目標服務，不僅僅是坐標軸、布局、形狀、線條和排版，而且還要恰當使用這些工具。

可視化與R語言

R語言提供了具有出版質量的圖表和圖形的制作。R語言中包含圖形設備，還有一些設備不屬于標準R語言安裝的一部分，可以通過命令行使用R語言中的圖形。

R語言圖形設置的最重要特征就是在R中存在兩種截然不同的圖形系統。

傳統的圖形系統

網格圖形系統

將對最合適的設施進行評估并將它們應用于本書列出的所有算法的每一個結果的可視化中。

R圖形系統和添加包中的函數可以分為如下幾種類型：

生成完整圖形的高級函數

給現有圖形添加進一步輸出的低級函數

與圖形輸出交互運行的函數

可以以多種圖形格式產生R的圖形輸出，比如PNG、JPEG、BMP、TIFF、SVG、PDF和PS。

為了加強你對本章知識的理解，這里有一些練習用于你檢查相關的概念。

1.16　練習

現在，讓我們來檢測到目前為止我們所學習的知識：

數據挖掘和機器學習有什么區別？

什么是數據預處理？什么是數據質量？

在你的計算機上下載R并安裝R。

比較數據挖掘和機器學習。

1.17　總結

本章討論了以下主題：

數據挖掘和可用的數據源。

R語言的簡要概述以及使用R語言的必要性。

統計學和機器學習，以及它們與數據挖掘關系的描述。

兩個標準的行業數據挖掘過程。

數據屬性類型和數據測量方法。

數據預處理的3個重要步驟。

數據挖掘算法的可擴展性和效率，以及數據可視化的方法與必要性。

社交網絡挖掘、文本挖掘和網絡數據挖掘。

關于RHadoop和Map Reduce的簡短介紹。

在下面的章節中，我們將學習如何使用R語言來處理數據并實現不同的數據挖掘算法。

第2章

頻繁模式、關聯規則和相關規則挖掘

本章中，我們將首先學習如何用R語言挖掘頻繁模式、關聯規則及相關規則。然后，我們將使用基準數據評估所有這些方法以便確定頻繁模式和規則的興趣度。本章內容主要涵蓋以下幾個主題：

關聯規則和關聯模式概述

購物籃分析

混合關聯規則挖掘

序列數據挖掘

高性能算法

關聯規則挖掘算法可以從多種數據類型中發現頻繁項集，包括數值數據和分類數據。根據不同的適用環境，關聯規則挖掘算法會略有差異，但大多算法都基于同一個基礎算法，即Apriori算法。另一個基礎算法稱為FP-Growth算法，與Apriori算法類似。大多數的與模式相關的挖掘算法都是來自這些基礎算法。

將找到的頻繁模式作為一個輸入，許多算法用來發現關聯規則或相關規則。每個算法僅僅是基礎算法一個變體。

隨著不同領域中的數據集大小和數據類型的增長，提出了一些新的算法，如多階段算法、多重散列算法及有限掃描算法。

2.1　關聯規則和關聯模式概述

數據挖掘的一個最受歡迎的任務就是發現源數據集之間的關系，它從不同的數據源（如購物籃數據、圖數據或流數據）中發現頻繁模式。

為了充分理解關聯規則分析的目的，本章中所有算法均用R語言編寫，這些代碼使用算法的標準R添加包（如arules添加包）進行說明。

2.1.1　模式和模式發現

在眾多的領域應用中，頻繁模式挖掘經常用于解決各種問題，比如大型購物中心的市場調查可以通過分析購物交易數據來完成。

頻繁模式是經常出現在數據集中的模式。頻繁模式挖掘的數據類型可以是項集、子序列或子結構。因此，頻繁模式也可稱為：

頻繁項集

頻繁子序列

頻繁子結構

接下來的章節將詳細介紹這3種頻繁模式。

當從給定的數據集中發現重復出現的有意義的規則或關系時，這些新發現頻繁模式將作為一個重要的平臺。

為了提高挖掘數據集的效率，提出了不同的模式。本章列舉了以下幾種模式，后面將給出它們詳細的定義。

封閉模式

最大模式

近似模式

緊湊模式

判別式頻繁模式

2.1.1.1　頻繁項集

頻繁項集的概念來源于真實的購物籃分析。在諸如亞馬遜等商店中，存在很多的訂單或交易數據。當客戶進行交易時，亞馬遜的購物車中就會包含一些項。商店店主可以通過分析這些大量的購物事務數據，發現顧客經常購買的商品組合。據此，可以簡單地定義零個或多個項的組合為項集。

我們把一項交易稱為一個購物籃，任何購物籃都有組元素。將變量s設置為支持閾值，我們可以將它和一組元素在所有的購物籃中出現的次數做比較，如果這組元素在所有購物籃中出現的次數不低于s，我們就將這組元素稱為一個頻繁項集。

若一個項集包含有k個項，則該項集稱為k項集，其中k是非零整數。項集X的支持計數記為support_count(X)，表示給定數據集中包含項集X的計數。

給定一個預先定義的最小支持度閾值s，如果support_count(X)≥s，則稱項集X為頻繁項集。最小支持度閾值s是一個可以自定義的參數，可以根據領域專家或經驗進行調整。

頻繁項集也經常應用于許多領域，如下表所示。

項 籃子 說明

相關概念 詞 文檔

剽竊 文檔 句子

生物標記物 生物標記物和疾病 病人的數據集

如果某個項集是頻繁的，那么該項集的任何一個子集也一定是頻繁的。這稱為Apriori原理，它是Apriori算法的基礎。Apriori原理的直接應用就是用來對大量的頻繁項集進行剪枝。

影響頻繁項集數目的一個重要因素是最小支持計數：最小支持計數越小，頻繁項集的數目也越多。

為了優化頻繁項集生成算法，人們提出一些其他概念：

閉項集：給定數據集S，如果Y∈S, X ?Y，則support_count (X) ≠ support_count (Y)，那么X稱作閉項集。換言之，如果X是頻繁的，則X是頻繁閉項集。

最大頻繁項集：如果Y∈S, X ?Y，X是最大頻繁項集，則Y是非頻繁的。換言之，Y沒有頻繁超集。

約束頻繁項集：若頻繁項集X滿足用戶指定的約束，則X稱為約束頻繁項集。

近似頻繁項集：若項集X只給出待挖掘數據近似的支持計數，則稱為近似頻繁項集。

top-k頻繁項集：給定數據集S和用戶指定的整數k，若X是前k個頻繁項集，則X稱為top-k頻繁項集。

下面給出一個事務數據集的例子。所有項集僅包含集合D = {Ik |{k∈[1,7]}中的項。假定最小支持度計數為3。

tid（交易號） 項集或交易中的項列表

T001 I1, I2, I4, I7

T002 I2, I3, I6

T003 I1, I4, I6

T004 I1, I2, I5

T005 I2, I3, I4

T006 I2, I5, I6

T007 I2, I4, I7

T008 I1, I7

T009 I1, I2, I3

T010 I1, I2, I4

那么，可以得到頻繁項集L1 = {Ik | k∈{1, 2, 4, 6, 7}}和L2 = {{I1, I2}，{I1, I4}，{I2, I4}}。

2.1.1.2　頻繁子序列

頻繁子序列是元素的一個有序列表，其中每個元素包含至少一個事件。一個例子是某網站頁面訪問序列，具體而言，它是某個用戶訪問不同網頁的順序。下面給出了頻繁子序列的兩個例子。

消費者數據：某些客戶在購物商城連續的購物記錄可作為序列，購買的每個商品作為事件項，用戶一次購買的所有項作為元素或事務。

網頁使用數據：訪問WWW歷史記錄的用戶可作為一個序列，每個UI/頁面作為一個事件或項目，元素或事務定義為用戶通過一次鼠標的單擊訪問的頁面。

序列中包含的項數定義為序列的長度。長度為k的序列定義為k序列。序列的大小定義為序列中項集的數目。當滿足1≤j1≤j2≤…≤jr-1≤jr≤v，且a1bj1, a2bj2, …, arbjr，則稱序列s1=<a1a2…ar>為序列s2=<b1b…br>的子序列或s2為s1的超序列。

2.1.1.3　頻繁子結構

在某些領域中，研究任務可借助圖論來進行建模。因此，需要挖掘其中常見的子圖（子樹或子格）。例如：

網絡挖掘：網頁視為圖的頂點，網頁之間的鏈接視為圖的邊，用戶的頁面訪問記錄用來構造圖。

網絡計算：網絡上具有計算能力的任何設備作為頂點，這些設備之間的相互連接作為邊。由這些設備和設備之間的相互連接組成的整個網絡視為圖。

語義網絡：XML元素視為頂點，元素之間的父/子關系視為邊。所有的XML文件可視為圖。

圖G表示為：G = (V, E)，其中V表示頂點的集合，E表示邊的集合。當V′V且E′E，圖G′= (V′, E′)稱為G=(V, E)的子圖。下圖給出一個子圖的例子。圖中，左邊是原始圖及其包含的頂點和邊，右邊是刪除多條邊（或刪除多個頂點）后的子圖。

2.1.2　關系或規則發現

基于已發現的頻繁模式，可以挖掘關聯規則。根據關系的興趣度的不同側重點，可以進一步研究以下兩種類型的關系：關聯規則和相關規則。

2.1.2.1　關聯規則

關聯分析可以從海量數據集中發現有意義的關系，這種關系可以表示成關聯規則的形式或頻繁項集的形式。具體的關聯分析算法將在后面一個章節中給出。

關聯規則挖掘旨在發現給定數據集（事務數據集或其他序列-模式-類型數據集）中的結果規則集合。給定預先定義的最小支持度計數s和置信度c，給定已發現的規則X→Y support_count (X→Y)≥s且confidence (X→Y)≥c。

當X∩Y=（X、Y不相交），則X→Y是關聯規則。規則的興趣度通過支持度（support）和置信度（confidence）來測量。支持度表示數據集中規則出現的頻率，而置信度測量在X出現的前提下，Y出現的可能性。

對于關聯規則，衡量規則可用性的核心度量是規則的支持度和置信度。兩者之間的關系是：

support_count(X)是數據集中包含X的項集數。

通常，在support_count(X)中，支持度和置信度的值表示為0～100的百分數。

給定最小支持度閾值s和最小置信度閾值c。如果support_count (X→Y) > s且confidence (X→Y)≥c，則關聯規則X→Y稱為強規則。

對于關聯規則含義的解釋應當慎重，尤其是當不能確定地判斷規則是否意味著因果關系時。它只說明規則的前件和后件同時發生。以下是可能遇到不同種類的規則：

布爾關聯規則：若規則包含項出現的關聯關系，則稱為布爾關聯規則。

單維關聯規則：若規則最多包含一個維度，則為單維關聯規則。

多維關聯規則：若規則至少涉及兩個維度，則為多維關聯規則。

相關關聯規則：若關系或規則是通過統計相關進行測量的，滿足給定的相關性規則，則稱為相關關聯規則。

定量關聯規則：若規則中至少一個項或屬性是定量的，則稱為定量關聯規則。

2.1.2.2　相關規則

在某些情況下，僅僅憑借支持度和置信度不足以過濾掉那些無意義的關聯規則。此時，需要利用支持計數、置信度和相關性對關聯規則進行篩選。

計算關聯規則的相關性有很多方法，如卡方分析、全置信度分析、余弦分析等。對于k項集X={i1, i2 …, ik}，X的全置信度值定義為：

2.2　購物籃分析

購物籃分析（Market basket analysis）是用來挖掘消費者已購買的或保存在購物車中物品組合規律的方法。這個概念適用于不同的應用，特別是商店運營。源數據集是一個巨大的數據記錄，購物籃分析的目的發現源數據集中不同項之間的關聯關系。

2.2.1　購物籃模型

購物籃模型是說明購物籃和其關聯的商品之間的關系的模型。來自其他研究領域的許多任務與該模型有共同點。總言之，購物籃模型可作為研究的一個最典型的例子。

購物籃也稱為事務數據集，它包含屬于同一個項集的項集合。

Apriori算法是逐層挖掘項集的算法。與Apriori算法不同，Eclat算法是基于事務標識項集合交集的TID集合交集項集的挖掘算法，而FP-Growth算法是基于頻繁模式樹的算法。TID集合表示交易記錄標識號的集合。

2.2.2　Apriori算法

作為常見的算法設計策略，Apriori算法挖掘關聯規則可以分解為以下兩個子問題：

頻繁項集生成

關聯規則生成

該分解策略大大降低了關聯規則挖掘算法的搜索空間。

2.2.2.1　輸入數據特征和數據結構

作為Apriori算法的輸入，首先需要將原始輸入項集進行二值化，也就是說，1代表項集中包含有某項，0代表不包含某項。默認假設下，項集的平均大小是比較小的。流行的處理方法是將輸入數據集中的每個唯一的可用項映射為唯一的整數ID。

項集通常存儲在數據庫或文件中并需要多次掃描。為控制算法的效率，需要控制掃描的次數。在此過程中，當項集掃描其他項集時，需要對感興趣的每個項集的表示形式計數并存儲，以便算法后面使用。

在研究中，發現項集中有一個單調性特征。這說明每個頻繁項集的子集也是頻繁的。利用該性質，可以對Apriori算法過程中的頻繁項集的搜索空間進行剪枝。該性質也可以用于壓縮與頻繁項集相關的信息。這個性質使頻繁項集內的小頻繁項集一目了然。例如，從頻繁3項集中可以輕松地找出包含的3個頻繁2項集。

當我們談論k項集時，我們指的是包含k個項的項集。

購物籃模型表采用水平格式，它包含一個事務ID和多個項，它是Apriori算法的基本輸入格式。相反，還有另一種格式稱為垂直格式，它使用項ID和一系列事務ID的集合。垂直格式數據的挖掘算法留作練習。

2.2.2.2　Apriori算法

在Apriori算法頻繁項集產生過程中，主要包含以下兩種操作：連接和剪枝。

一個主要的假定是：任何項集中的項是按字母序排列的。

連接：給定頻繁k-1項集Lk-1，為發現頻繁k項集Lk，需要首先產生候選k項集（記為Ck）。

剪枝：候選項集Ck通常包含頻繁項集LkCk，為減少計算開銷。這里利用單調性質對Ck進行剪枝。

以下是頻繁項集產生的偽代碼：

2.2.2.3　R語言實現

這里給出Apriori頻繁項生成集算法的R語言代碼。記事務數據集為D，最小支持計數閾值為MIN_SUP，算法的輸出為L，它是數據集D中的頻繁項集。

Apriori函數的輸出可以用R添加包arules來驗證，該包可以實現包含Apriori算法和Eclat算法的模式挖掘和關聯規則挖掘。Apriori算法的R代碼如下：

為了檢驗上面的R代碼，可以應用arules添加包對算法輸出進行驗證。

Arules添加包（Hahsler et al.，2011）提供了挖掘頻繁項集、最大頻繁項集、封閉頻繁項集以及關聯規則等功能。可用的算法包含Apriori算法和Eclat算法。此外，arulesSequence添加包（基于arules添加包）中還包含cSPADE算法。

給定項集：

首先，利用預先定義的排序算法將D中的項組織為有序列表，這里，簡單地根據字母順序將各項進行排序，可得到：

假定最小支持計數為5，輸入數據如下表所示：

tid（事務id） 項集或事務中的項目列表

T001 I1, I2, I4, I7

T002 I2, I3, I6

T003 I1, I4, I6

T004 I1, I2, I5

T005 I2, I3, I4

T006 I2, I5, I6

T007 I2, I4, I7

T008 I1, I7

T009 I1, I2, I3

T010 I1, I2, I4

在對數據集D的第一次掃描中，可以得到每個候選1項集C1的支持計數。候選項集及其支持計數為：

項集 支持計數

{I1} 6

{I2} 8

{I3} 2

{I4} 5

{I5} 2

{I6} 3

{I7} 3

在將支持計數與最小支持計數比較后，可以得到頻繁1項集L1：

項集 支持計數

{I1} 6

{I2} 8

{I4} 5

通過L1，產生候選項集C2，C2={{I1, I2}, {I1, I4}, {I2, I4}}。

項集 支持計數

{I1, I2} 4

{I1, I4} 3

{I2, I4} 4

將支持計數與最小支持數比較后，可以得到L2=?。然后，算法終止。

2.2.2.4　Apriori算法的變體

為提升Apriori算法的效率和可擴展性，人們提出了Apriori算法的一些變體。下面介紹幾種比較代表性的Apriori改進算法。

2.2.3　Eclat算法

Apriori算法循環的次數與模式的最大長度是一樣的。Eclat（Equivalence CLASS Transformation）算法是為了減少循環次數而設計的算法。在Eclat算法中，數據格式不再是<tid, item id set>（<事務編號，項ID集合>），而是<item id, tid set>（<項ID，事務編號集合>）。Eclat算法的數據輸入格式是樣本購物籃文件中的垂直格式，或者從事務數據集中發現頻繁項集。在該算法中，還使用Apriori性質從k項集生成頻繁k+1項集。

通過求集合的交集來生成候選項集。正如前文所述，垂直格式結構稱為事務編號集合（tidset）。如果與某個項目I相關的所有事務編號都存儲在一個垂直格式事務集合中，那么該項集就是特定項的事務編號集合。

通過求事務編號集合的交集來計算支持計數。給定兩個tidset X和Y，X∩Y交集的支持計數是X∩Y的基數。偽代碼是F←, P←{<i,t(i)>|i∈I, |t(i)|≥MIN_SUP}。

R語言實現

下面給出Eclat算法挖掘頻繁模式的R語言代碼。在調用該函數前，需要將f設為空，而p是頻繁1項集。

這里給出一個例子的運行結果。其中，I={beer,chips,pizza,wine}。與之對應的水平和垂直格式的事務數據集如下表所示。

tid X

1 {beer, chips, wine}

2 {beer, chips}

3 {pizza, wine}

4 {chips, pizza}

x tidset

beer {1,2}

chips {1,2,4}

pizza {3,4}

wine {1,3}

該信息的二進制格式為：

tid beer chips pizza wine

1 1 1 0 1

2 1 1 0 0

3 0 0 1 1

4 0 1 1 0

在調用Eclat算法之前，設置最小支持度MIN_SUP=2, F={}，則有：

算法運行過程如下圖所示。經過兩次迭代后，可以得到所有的頻繁事物編號集合，{<beer,1 2>,<chips,1 2 4>,<pizza, 3 4>,<wine, 1 3>,<{beer, chips}, 1 2>}。

可以使用R添加包arules對Eclat函數的結果進行驗證。

2.2.4　FP-growth算法

FP-growth算法是在大數據集中挖掘頻繁項集的高效算法。FP-growth算法與Apriori算法的最大區別在于，該算法不需要生成候選項集，而是使用模式增長策略。頻繁模式（FP）樹是一種數據結構。

2.2.4.1　輸入數據特征和數據結構

算法采用一種垂直和水平數據集混合的數據結構，所有的事務項集存儲在樹結構中。該算法使用的樹結構稱為頻繁模式樹。這里，給出了該結構生成的一個例子。其中，I={A,B,C,D,E,F}，事務數據集D如下表所示。FP樹的構建過程如下表所示。FP樹中的每個節點表示一個項目以及從根節點到該節點的路徑，即節點列表表示一個項集。這個項集以及項集的支持信息包含在每個節點中。

tid X

1 {A, B, C, D, E}

2 {A, B, C, E}

3 {A, D, E}

4 {B, E, D}

5 {B, E, C}

6 {E, C, D}

7 {E, D}

排序的項目順序如下表所示。

項目 E D C B A

支持計數 7 5 4 4 3

根據這個新的降序順序，對事務數據集進行重新記錄，生成新的有序事務數據集，如下表所示：

tid X

1 {E, D, C, B, A}

2 {E, C, B, A}

3 {E, D, A}

4 {E, D, B}

5 {E, C, B}

6 {E, D, C}

7 {E, D}

隨著將每個項集添加到FP樹中，可生成最終的FP樹，FP樹的生成過程如下圖所示。在頻繁模式（FP）樹生成過程中，同時計算各項的支持信息，即隨著節點添加到頻繁模式樹的同時，到節點路徑上的項目的支持計數也隨之增加。

將最頻繁項放置在樹的頂部，這樣可以使樹盡可能緊湊。為了開始創建頻繁模式樹，首先按照支持計數降序的方式對項進行排序。其次，得到項的有序列表并刪除不頻繁項。然后，根據這個順序對原始事務數據集中的每個項重新排序。

給定最小支持度MIN_SUP=3，根據這個邏輯可以對下面的項集進行處理。

下面是執行步驟4和步驟7后的結果，算法的過程非常簡單和直接。

頭表通常與頻繁模式樹結合在一起。頭指針表的每個記錄存儲指向特定節點或項目的鏈接。

作為FP-growth算法的輸入，頻繁模式樹用來發現頻繁模式或頻繁項集。這里的例子是以逆序或從葉子節點刪除FP樹的項目，因此，順序是A, B, C, D, E。按照這種順序，可以為每個項目創建投影頻繁模式樹。

2.2.4.2　FP-growth算法

這里是遞歸定義的偽代碼，其輸入值為：R←GenerateFPTree(D), P← , F←?

2.2.4.3　R語言實現

FP-growth算法的主要部分的R語言實現代碼如下所示。

2.2.5　基于最大頻繁項集的GenMax算法

GenMax算法用來挖掘最大頻繁項集（Maximal Frequent Itemset，MFI）。算法應用了最大性特性，即增加多步來檢查最大頻繁項集而不只是頻繁項集。這部分基于Eclat算法的事物編號集合交集運算。差集用于快速頻繁檢驗。它是兩個對應項目的事物編號集合的差。

可以通過候選最大頻繁項集的定義來確定它。假定最大頻繁項集記為M，若X屬于M，且X是新得到頻繁項集Y的超集，則Y被丟棄；然而，若X是Y的子集，則將X從集合M中移除。

下面是調用GenMax算法前的偽代碼，

M← ，且P←{<Xi, t(Xi)>|Xi∈D, support_count(Xi)≥MIN_SUP}

其中，D是輸入事務數據集。

R語言實現

GenMax算法的主要部分的R語言代碼如下所示：

2.2.6　基于頻繁閉項集的Charm算法

在挖掘頻繁閉項集過程中，需要對項集進行封閉檢查。通過頻繁閉項集，可以得到具有相同支持度的最大頻繁模式。這樣可以對冗余的頻繁模式進行剪枝。Charm算法還利用垂直事物編號集合的交集運算來進行快速的封閉檢查。

下面是調用Charm算法前的偽代碼，

C← ，且P←{<Xi, t(Xi)>|Xi∈D, support_count(Xi)≥MIN_SUP}

其中，D是輸入事務數據集。

R語言實現

Charm算法的主要部分的R語言實現代碼如下：

2.2.7　關聯規則生成算法

在根據Apriori算法生成頻繁項集的過程中，計算并保存每個頻繁項集的支持計數以便用于后面的關聯規則挖掘過程，即關聯規則挖掘。

為生成關聯規則X→Y，l=X∪Y，l為某個頻繁項集，需要以下兩個步驟：

首先，得到l的所有非空子集。

然后，對于l的子集X，Y=l-X，規則X→Y為強關聯規則，當且僅當confidence（X→Y）≥minimumconfidence。一個頻繁項集的任何規則的支持計數不能小于最小支持計數。

關聯規則生成算法的偽代碼如下所示。

R語言實現

生成Apriori關聯規則的算法的R語言代碼如下所示：

為了驗證上述R語言代碼，可以使用Arules和Rattle添加包驗證它的輸出。

Arules（Hahsler et al., 2011）和Rattle添加包提供了對關聯規則分析的支持。對于輸出規則的可視化，可利用AruleViz。

2.3　混合關聯規則挖掘

關聯規則挖掘有兩個有意義的應用：一是多層次和多維度關聯規則挖掘；二是基于約束的關聯規則挖掘。

2.3.1　多層次和多維度關聯規則挖掘

對于給定的事務數據集，若數據集的某些維度存在概念層次關系，則需要對該數據集進行多層次關聯規則挖掘。對事物數據集可用的任何關聯規則挖掘算法都可以用于該任務。下表給出亞馬遜商店的一個例子。

TID 購買的項

1 Dell Venue 7 16 GB Tablet, HP Pavilion 17-e140us 17.3-Inch Laptop...

2 Samsung Galaxy Tab 3 Lite, Razer Edge Pro 256GB Tablet…

2 Acer C720P-2666 Chromebook, Logitech Wireless Combo MK270 with Keyboard and Mouse...

2 Toshiba CB35-A3120 13.3-Inch Chromebook, Samsung Galaxy Tab 3 (7-Inch, White)...

下面是多層次模式挖掘的流程圖。

基于概念層次，低層次概念可以投影到高層次概念，具有高層次概念的新數據集可以代替原始的低層次概念。

可以在每個概念層次計算支持計數。許多類Apriori算法在計算支持計數時稍微有些不同。下面是幾種不同的方法：

對所有的層次使用統一的最小支持度閾值。

對較低的層次使用較小的支持度閾值。

基于組的最小支持度閾值。

有時，Apriori性質并不總成立。這里有一些例外。

多層次關聯規則是從概念層次的多層次中挖掘出來的。

2.3.2　基于約束的頻繁模式挖掘

基于約束的頻繁模式挖掘是使用用戶設定的約束對搜索空間進行剪枝的啟發式算法。

常見的約束有（但不局限于）以下幾種情況：

知識類型的約束（指定我們想要挖掘什么）

數據約束（對初始數據集的限制）

維度層次約束

興趣度約束

規則約束

2.4　序列數據集挖掘

序列數據集挖掘的一個重要任務是序列模式挖掘。A-Priori-life算法被用來進行序列模式挖掘，這里使用的A-Priori-life算法，它是采用廣度優先策略。然而，FP-growth算法，采用深度優先策略。出于不同的原因，算法有時還需要綜合考慮一些約束。

從序列模式中，可以發現商店消費者的常見購買模式。在其他方面，特別是廣告或市場營銷，序列模式挖掘發揮重要作用。可以從網絡日志挖掘、網頁推薦系統、生物信息學分析、病歷跟蹤分析、災害預防與安全管理等領域中預測個人消費者行為。

本章中的規則都是從序列模式中挖掘出來的，它們具有多種。其中一些類型序列模式如下所示：

序列規則：X→Y，其中XY。

標簽序列規則（Label Sequential Rule，LSR）：形如X→Y，其中Y是一個序列，X是將序列Y中的若干項用通配符替換后而產生的序列。

類序列規則（Class Sequential Rule，CSR）：定義為X，若：

X→y，假設S為序列數據集，I是序列數據集S中所有項的集合，Y是類標簽的集合，I∩Y=，X是一個序列且y∈Y。

2.4.1　序列數據集

序列數據集S定義為元組（sid, s）的集合，其中sid為序列ID，s為序列。

在序列數據集S中，序列X的支持度定義為S中包含X的元組數，即

supportS(X)={(sid, s)∨(sid, s)∈S←Xs}

這是序列模式的一個內在性質，它應用于相關的算法，如Apriori算法的Apriori性質。對于序列X及其子序列Y，support（X）≤support(Y)。

2.4.2　GSP算法

廣義序列模式（Generalized Sequential Pattern，GSP）算法是一個類似Apriori的算法，但它應用于序列模式。該算法是逐層算法，采取寬度優先策略。它具有如下的特征：

GSP算法是Apriori算法的擴展。它利用Apriori性質（向下封閉），即，給定最小支持計數，若不接受某個序列，則其超序列也將丟棄。

需要對初始事務數據集進行多次掃描。

采用水平數據格式。

每次掃描中，通過將前一次掃描中發現的模式進行自連接來產生候選項集。

在第k次掃描中，僅當在第（k-1）次掃描中接受所有的（k-1）子模式，才接收該序列模式。

GSP算法為：

偽代碼為：

2.5　R語言實現

算法主要部分的R語言實現為：

2.5.1　SPADE算法

使用等價類的序列模式發現（Sequential Pattern Discovery using Equivalent class，SPADE）算法是應用于序列模式的垂直序列挖掘算法，它采用深度優先策略。算法的特征是：

SPADE算法是Apriori算法的擴展。

算法采用Apriori性質。

需要對初始事務數據集進行多次掃描。

采用垂直數據格式。

算法采用簡單的連接運算。

所有序列的發現都需要對數據進行3次掃描。

下面是調用SPADE算法之前的偽代碼

F←, ∧k←0, P←{<s, L(s)s>∈∑, support_count(s)≥MIN_SUP}

R語言實現

算法主要部分的R語言代碼實現是：

2.5.2　從序列模式中生成規則

序列規則、標簽序列規則和類序列規則都可以從序列模式中生成，這些可以從前面的序列模式發現算法中得到。

2.6　高性能算法

伴隨著數據集規模的增長，對高性能關聯/模式挖掘算法的要求也隨之增加。

隨著Hadoop和其他類MapReduce平臺的提出，滿足這些需求成為可能。相關內容將于后續章節中進行介紹。根據數據集的大小，可以對某些算法進行調整以防止算法循環調用導致的棧空間不足問題，這也給我們將這些算法轉化到MapReduce平臺時帶來了挑戰。

2.7　練習

為加強對本章內容的掌握，這里給出一些有助于更好理解相關概念的實踐問題。

編寫R程序，尋找給定的樣本購物籃事務文件中包含了多少唯一的項名。將每個項的名字映射為一個整數ID。找出所有的頻繁閉項集。找出所有最大頻繁項集和它們的支持計數。你自己將支持計數閾值設置為一個變量值。

用R語言編碼，實現AprioriTid 算法。

2.8　總結

本章主要學習了以下內容：

購物籃分析。

作為關聯規則挖掘的第一步，頻繁項集是一個主要因素。除算法設計外，定義了閉項集、最大頻繁項集。

作為關聯規則挖掘的目標，通過支持計數、置信度等度量來挖掘關聯規則。除支持計數外，使用相關公式挖掘相關規則。

頻繁項集的單調性，即，若某個項集是頻繁的，則其所有子集也是頻繁的。

Apriori算法是挖掘頻繁模式的第一個高效算法，其他諸多算法均為Apriori的變體。

序列中的序列模式。

下一章將介紹基本分類算法，包括ID3、C4.5和CART等算法，這部分內容也是數據挖掘的重要應用。