本文說的主題是關于「數據挖掘」，以下為內容大綱，讓大家對互聯網搜索與挖掘有一個宏觀的了解，即知道要做什么和怎么做。注：本文的框架來源于北京大學萬小軍開設的互聯網數據挖掘 Web Data Mining 課程，筆者對內容進行了篩選和編排，用來作為『不周山之數據挖掘』系列的導論部分。

[[182755]]

任務目標

• 了解搜索和自然語言處理的基本知識
• 熟悉數據挖掘的流程與各個步驟所用的技術
• 對數據挖掘的應用場景有基本的認識

寫在前面

隨著互聯網的日益蓬勃發展，如何從廣袤的信息海洋中提取出有價值的信息、模式和關系，逐漸成為了一門新的領域 —— 數據挖掘。作為一門交叉學科，數據挖掘融合了信息檢索、互聯網、數據庫、機器學習、自然語言處理等不同的學科，用多樣技術完成具體的數據挖掘應用。常見的應用有：垂直搜索、推薦系統、智能問答、機器翻譯、輿情監測、情報收集等等，可謂是深入到了我們日常生活的方方面面。

接下來我們會從基礎技術說起，從以下三個方面來了解數據挖掘：

• 搜索技術
• 數據挖掘技術
• 具體應用

搜索

搜索其實是一個很大的主題，但是核心問題其實并不復雜，一是如何去表示文檔，二是在這樣的基礎上如何去檢索文檔。具體的評價標準是『效果』和『效率』。效果指的是如何準確匹配查詢與文檔，一般來說會基于檢索模型進行。效率值得是如何快速返回檢索結果，一般來說是基于索引進行的。

文檔表示

文檔表示一般有兩種方法：手動或自動

手動方法，主要依靠人工標注，結果比較可靠，而且標注的詞匯是預先設定好的關鍵詞，檢索起來效率比較高。但是人工標注無論是時間成本還是人力成本都較高，一般來說難以大批量使用。這類人工標注的信息一般稱為文檔的元描述(Meta-descriptions)，除了包含域信息(author, title, date)外，還回包含關鍵詞和分類。

自動方法，最有代表性的是詞袋(Bag of Words)技術，即使用文檔中出現的詞的集合來表示一篇文檔。但是這種方法也有很多不足之處，因為是詞語的無序集合，句法信息首先已經丟失了，另外針對不同的語言會有不同的難點。

對于中文來說，如何進行分詞(即把句子分成詞)就是一個很大的難點，尤其是層出不窮的網絡熱梗，如何保證準確和實時就是非常大的挑戰。對于英文來說，雖然沒有分詞的問題，但是大小寫、單復數、時態、詞根等等同樣讓人頭疼。這也導致了大部分搜索引擎都不會考慮詞根問題，一是因為文檔太多，進行二次處理得不償失，二是因為對于搜索結果來說影響沒有那么大，自然就沒有太大的動力去做。

但是無論是中文還是英文，有一個操作是一定會做的，就是去掉停用詞(Stop Words)，也就是去掉那些不具有內容信息的詞，比如對于中文來說『的地得』，對于英文來說的『a, an, the』。但需要注意的是這樣一個簡單的操作雖然可以大幅減少索引的大小，縮短檢索時間，但實際上不能提高檢索效果，具體挺用詞表的確定也需要根據不同的文檔集合和應用具體對待，沒有一個一概而論的方案。

文檔索引

表示了文檔之后，我們需要對其進行索引，不然每次檢索如果需要用戶等太久，體驗就很糟糕了。而具體到用什么進行檢索，最終人們選擇了用詞而不是短語來作為索引，這里一個比較有代表性的工具就是 Lucene，現在互聯網上廣為應用的 Elasticsearch 和 Solr 都是基于 Lucene 的。

Lucene 最重要的技術就是倒排索引(inverted index)，可看做鏈表數組，每個鏈表的表頭包含關鍵詞，其后序單元則包括所有包括這個關鍵詞的文檔標號，以及一些其他信息，如該詞的頻率和位置等。這里關鍵詞查詢一般采用 B-Tree 或哈希表，文檔列表組織一般采用二叉搜索樹。

文檔檢索

文檔檢索的思路也很簡單：如果一篇文檔與一個查詢相似，那么該文檔與查詢相關。相似性一般根據字符串匹配來判定，比方說相似的詞匯或相同的語義。

最初人們常用的是基于布爾代數的匹配，雖然比較簡單，但是對查詢的要求很高;并且匹配標準過于嚴格，容易導致過少或過多的檢索結果。盡管布爾模型不再用作主流文檔檢索模型，但其思想常用于實現高級(綜合)檢索功能。

現在最常用的是向量空間模型(Vector Space Model)，其思路是文檔與查詢都是高維空間中的一個向量，用戶自由輸入文本也是一個向量，利用向量空間的相似性進行查詢。具體的相似性同樣可以用兩種方法來確定：內積或者夾角。因為是空間，所以度量距離的時候會采用不同的描述距離的方式，有 Minkowski metric, Euclidian distance, Jacquard measure 和 Dice’s coefficient 等等。

同一篇文檔中不同詞語其實也會有不同的權重，這里我們比較常用的是 TF-IDF 算法，其中 TF 表示詞語出現的頻率，而 IDF 則能區別不同詞語的重要性。

文檔收集

前面介紹了文檔檢索的各種概念，但是現在問題來了，文檔從哪里來呢?這就要提到我們最常聽見的爬蟲(Web Crawler)了，它能夠快速有效地收集盡可能多的有用 Web 頁面，包括頁面之間的鏈接結構。

隨著 Web 2.0 的興起，腳本語言生成的動態內容和各類多媒體內容給爬蟲增加了許多難度，但基本的頁面爬取策略沒有太大的改變，一般以以廣度優先為主，深度優先為輔， 需要具體的特性主要有：

• 健壯 Robustness, 避免進入死循環
• 友好 Politeness, 遵守服務器的采集協議
• 分布式 Distributed, 多臺機器分布式采集
• 可擴展 Scalable, 爬蟲架構方便擴展
• 性能與效率，有效利用系統資源
• 質量 Quality, 傾向于采集有用的頁面
• 新穎 Freshness, 獲取網頁的最新版本
• 可擴充 Extensible, 能夠處理新數據類型、新的采集協議等

鏈接分析

除了頁面的內容本身，超鏈接其實也能提供非常多有價值的信息。一條從頁面 A 指向頁面 B 的鏈接表明 A 與 B 相關且 A 推薦/引用/投票/贊成 B。Google 當年最重要的 PageRank 算法，其實就是這個問題的最初且最成功的解決方案。

這里有一個很有趣的現象叫做排序沉入(Rank Sink)，頁面 A 引用了頁面 B，頁面 B 也引用了頁面 A，就形成了一個閉環，不再向外傳播分數了。這是我們在實際運用中需要避免的情況。

數據挖掘

數據挖掘根據應用的不同，分為不同的子領域，這些子領域又和機器學習、概率統計、模式識別等有著千絲萬縷的關系。接下來先介紹基本概念，然后聊聊一些常見的應用。

主要任務

數據挖掘的任務主要包括兩類，一類是基于一些變量預測其他變量的未知值或未來值，稱為預測型任務，常用的技術是分類(Classification)，回歸(Regression)和偏差分析(Deviation Detection)。另一類是發現描述數據的人們可解釋的模式，稱為描述型任務，常用的技術是聚類(Clustering)，關聯規則挖掘(Association Rule Discovery)和摘要(Summarization)。

為了完成上述任務，整個數據挖掘的流程為：獲取數據 -> 選擇數據 -> 預處理數據 -> 數據規整 -> 數據挖掘 -> 模式識別。不同階段會使用不同的技術，但一定要把整個流程走通，數據挖掘才有意義。

隨著數據量的增大，如何讓數據挖掘更加容易拓展效率更高，如何去挖掘有上下文關系的數據，如何從復雜、異構、網絡化數據中挖掘復雜知識，如何挖掘低質量數據，如何保證安全性和隱私，都是未來數據挖掘需要努力的方向。

常用工具

開源的工具有：

• Weka
• GATE
• Carrot2
• NLTK
• Orange
• RapidMiner
• KNIME

商用的應用主要有：

• IBM InfoSphere Warehouse
• Microsoft Analysis Services
• SAS Enterprise Miner
• STATISTICA Data Miner
• Oracle Data Mining

自然語言處理

自然語言處理是人工智能和語言學領域的分支學科指的是利用計算機對人類特有的書面形式和口頭形式的自然語言進行各種類型處理和加工的技術。其中最關鍵的任務有：自動分詞、命名實體識別、詞性標注、句法分析、語義分析和篇章分析。主要應用在：機器翻譯、文本分類、情感分析、信息檢索與過濾、自動問答、信息抽取、自動文摘和人機對話等領域。

推薦教材：

• Foundations of Statistical Natrual Language Processing
• Speech and Language Processing

統計自然語言處理

這里主要以漢語為例子說說分詞。一般認為詞是最小的、能夠獨立運用的、有意義的語言單位。但是漢語分詞有許多挑戰，比如：

• 詞和詞組的邊界模糊
• 新詞(未登陸詞)
• 切分歧義

漢字串 AJB 被稱作交集型切分歧義，如果滿足 AJ, JB 同時為詞，此時漢字串 J 被稱作交集串

漢字串 AB 被稱作組合型切分歧義，如果滿足條件 A, B, AB 同時為詞

真歧義：存在兩種或兩種以上的真實存在的切分形式

具體的分詞方法目前主要有以下幾種，前兩天也有一個利用深度學習的解決方案開源了，可以關注一下：

簡單的模式匹配

正向最大匹配(FMM)、逆向最大匹配(BMM, 比正向更有效)、雙向匹配(BM, 比較兩種方法的結果，大顆粒詞越多越好，非詞典詞和單子詞越少越好，可以識別出交叉歧義)

• 基于規則的方法
• 最少分詞算法
• 基于統計的方法

統計語言模型分詞、串頻統計和詞形匹配相結合的漢語自動分詞、無詞典分詞

第一步是候選網格構造：利用詞典匹配，列舉輸入句子所有可能的切分詞語，并以詞網格形式保存

第二步計算詞網格中的每一條路徑的權值，權值通過計算圖中的每一個節點(每一個詞)的一元統計概率和節點之間的二元統計概率的相關信息

最后根據圖搜索算法在圖中找到一條權值最大的路徑，作為最后的分詞結果

優缺點：可利用不同的統計語言模型計算最優路徑，具有比較高的分詞正確率;但算法時間、空間復雜度較高

常見應用

接下來介紹數據挖掘的積累常見應用：

智能問答技術

智能問答技術起源于信息檢索社區，簡單來說就是根據用戶的提問給出簡短的答案或提供答案的證據。根據不同的劃分標準，我們可以總結出如下的幾類問題類型：

• 根據答案類型劃分
• 事實型問題(Factual questions)
• 觀點型問題(Opinions)
• 摘要型問題(Summaries)
• 根據問題言語行為(question speech act)劃分
• 是否型問題(Yes/NO questions)
• WH 問題(WH questions)
• 間接請求(Indirect Requests)
• 命令(Commands)
• 復雜/困難問題
• 為什么/怎么樣(Why, How questions)
• 什么(What questions)

遺憾的是，目前大部分理解問題的技術都是基于正則表達式的，畢竟在自然語言理解這塊，暫時還沒有突破性進展。

傳統自動問答技術主要是基于語料庫的自動問答或基于知識庫的自動問答，基本包括三個步驟：

• 問題分析(分類、模板匹配、語義分析)
• 段落檢測(段落抽取、排序)
• 答案抽取(實體識別、模板匹配、排序)

社區問答主要是應用與諸如知乎和 Quora 這類網站，目前主要的方向是問題分類、問題推薦、信譽評估和知識抽取等等。

情感分析與觀點挖掘

情感分析與觀點挖掘主要應用于產品比較與推薦、個人與機構聲譽分析、電視節目滿意度分析、互聯網輿情分析和反恐與維穩。目前很多互聯網平臺(如淘寶、大眾點評)都已經利用這種技術幫助提取用戶評價中的關鍵詞以提供更好的用戶體驗。

基本的框架如下所示：

• 應用層：情感檢索，情感摘要，情感問答
• 核心層：情感要素抽取，情感傾向性分析，主客觀分析/觀點文本識別
• 基礎層：NLP 基本模塊，情感資源收集與標注
• 來源：產品評論，電影評論，新聞評論，博客，微博

而具體應用中，會將文本按照所表達的總體情感進行分類，可能的分類主要有如下三種，一般會從詞、句子、文檔三中粒度來進行分析：

主客觀分析/觀點文本識別

• 客觀：反映關于世界的事實信息
• 主觀：反映個人情感、信念等

傾向性分析(可看作主客觀分析的細粒度處理)

對包含觀點的文本進行傾向性判斷

一般分為三類：褒義、貶義、中性(在一些問題不考慮中性)

情緒分析

憤怒、高興、喜好、悲哀、吃驚等等

而對于觀點挖掘來說，一個觀點表示為一個五元組：目標對象, 目標對象特征, 觀點的情感值, 觀點持有者, 觀點表達時間。實際上，觀點抽取任務是很困難的，我們重點關注兩個子任務：

特征抽取與聚類(aspect extraction and grouping)

抽取對象的所有特征表達，并將同義特征表達聚類。每個特征類表示了關于該對象的獨一無二的某個特征

特征情感分類(aspect sentiment classification)

確定觀點針對每個特征的情感傾向：正面、負面、中性

信息摘要

信息摘要指的是對海量數據內容進行提煉與總結，以簡潔、直觀的摘要來概括用戶所關注的主要內容，方便用戶快速了解與瀏覽海量內容。遺憾的是，研究 50 多年，有一定進展，但仍不能令人滿意。一般來說實現思路有兩種：

抽取式：從文檔中抽取已有句子形成摘要。這種方法實現簡單，能保證句子的可讀性

生成式/混合式：生成新的句子，或者對已有句子進行壓縮、重構與融合。這種方法難度更大，但更接近摘要的本質

抽取式文檔摘要的典型工作流程是：文檔集 -> 文檔理解 -> 句子重要性計算與排名(利用詞語句子的各類特征，基于機器學習) -> 句子選擇 -> 摘要句子排序 -> 摘要

目前摘要總體性能不高，需要方法上的突破。

社交網絡分析

社交網絡作為 Web 2.0 的典型代表，用戶生成的內容相當多，可以看作是某種程度上的群體智慧和在強交互性基礎上構造的異構網絡。

社交網絡分析主要是基于社交關系、結構進行挖掘，比如社區檢測、連接預測、影響力分析。而社交內容挖掘則是基于文本等內容數據進行挖掘，比如摘要、關鍵詞、情感分析。因為每個人在社交網絡上可以抽象為一個元素，于是他們之間的關系可以用矩陣表示。另一種表示的方式是使用圖，其中節點 = 成員，邊 = 關系。

比較常見的任務有：

社交網絡抽取(Social Network Extraction)：從數據源中抽取、構建社交網絡

網絡中心性分析(Network Centrality Analysis)：識別社交網絡上最重要的節點(重要性的定義由目的、環境所定)

輸入為一個社交網絡，輸出為最重要的節點列表，一般方法是為節點計算分數或排序，反映節點的重要性/專業性/影響力

對于點重要性的評估可以采用網絡中心性測度(Centrality measures)方法，具體中心性的定義可能是度數中心性(朋友最多)、中介中心性(處在信息流動關鍵節點)或親近中心性(離所有節點平均距離最短)

用戶畫像：根據用戶特點給用戶群體分類

鏈接預測(Link Prediction)：給定一個社交網絡，預測哪些節點相互連接。例如: facebook 中的好友推薦

病毒式營銷(Viral Marketing)：找出若干用戶，為其提供優惠或折扣，從而影響網絡上的其他用戶，使得收益最大化

試一試

嘗試在網絡尋找應用了數據挖掘的產品，并思考不同公司是如何使用的

對于大數據時代的個人隱私問題，你怎么看?

總結

這一講，我們簡單了解了數據挖掘及應用的方方面面，當然，如果有很多不明白的概念，建議簡單看看維基百科了解一下，不過實在不明白也沒關系，隨著之后的實踐，應該會有恍然大悟的一天。