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

[[182755]]

任務目標

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

寫在前面

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

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

• 搜索技術
• 數(shù)據(jù)挖掘技術
• 具體應用

搜索

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

文檔表示

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

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

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

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

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

文檔索引

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

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

文檔檢索

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

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

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

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

文檔收集

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

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

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

鏈接分析

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

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

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

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

主要任務

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

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

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

常用工具

開源的工具有：

• 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

統(tǒng)計自然語言處理

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

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

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

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

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

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

簡單的模式匹配

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

• 基于規(guī)則的方法
• 最少分詞算法
• 基于統(tǒng)計的方法

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

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

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

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

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

常見應用

接下來介紹數(shù)據(jù)挖掘的積累常見應用：

智能問答技術

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

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

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

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

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

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

情感分析與觀點挖掘

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

基本的框架如下所示：

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

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

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

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

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

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

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

情緒分析

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

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

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

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

特征情感分類(aspect sentiment classification)

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

信息摘要

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

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

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

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

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

社交網(wǎng)絡分析

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

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

比較常見的任務有：

社交網(wǎng)絡抽取(Social Network Extraction)：從數(shù)據(jù)源中抽取、構建社交網(wǎng)絡

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

輸入為一個社交網(wǎng)絡，輸出為最重要的節(jié)點列表，一般方法是為節(jié)點計算分數(shù)或排序，反映節(jié)點的重要性/專業(yè)性/影響力

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

用戶畫像：根據(jù)用戶特點給用戶群體分類

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

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

試一試

嘗試在網(wǎng)絡尋找應用了數(shù)據(jù)挖掘的產(chǎn)品，并思考不同公司是如何使用的

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

總結

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