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

[[182755]]

任務(wù)目標(biāo)

• 了解搜索和自然語(yǔ)言處理的基本知識(shí)
• 熟悉數(shù)據(jù)挖掘的流程與各個(gè)步驟所用的技術(shù)
• 對(duì)數(shù)據(jù)挖掘的應(yīng)用場(chǎng)景有基本的認(rèn)識(shí)

寫在前面

隨著互聯(lián)網(wǎng)的日益蓬勃發(fā)展，如何從廣袤的信息海洋中提取出有價(jià)值的信息、模式和關(guān)系，逐漸成為了一門新的領(lǐng)域 —— 數(shù)據(jù)挖掘。作為一門交叉學(xué)科，數(shù)據(jù)挖掘融合了信息檢索、互聯(lián)網(wǎng)、數(shù)據(jù)庫(kù)、機(jī)器學(xué)習(xí)、自然語(yǔ)言處理等不同的學(xué)科，用多樣技術(shù)完成具體的數(shù)據(jù)挖掘應(yīng)用。常見的應(yīng)用有：垂直搜索、推薦系統(tǒng)、智能問答、機(jī)器翻譯、輿情監(jiān)測(cè)、情報(bào)收集等等，可謂是深入到了我們?nèi)粘Ｉ畹姆椒矫婷妗?/p>

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

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

搜索

搜索其實(shí)是一個(gè)很大的主題，但是核心問題其實(shí)并不復(fù)雜，一是如何去表示文檔，二是在這樣的基礎(chǔ)上如何去檢索文檔。具體的評(píng)價(jià)標(biāo)準(zhǔn)是『效果』和『效率』。效果指的是如何準(zhǔn)確匹配查詢與文檔，一般來說會(huì)基于檢索模型進(jìn)行。效率值得是如何快速返回檢索結(jié)果，一般來說是基于索引進(jìn)行的。

文檔表示

文檔表示一般有兩種方法：手動(dòng)或自動(dòng)

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

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

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

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

文檔索引

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

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

文檔檢索

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

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

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

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

文檔收集

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

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

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

鏈接分析

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

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

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

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

主要任務(wù)

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

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

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

常用工具

開源的工具有：

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

商用的應(yīng)用主要有：

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

自然語(yǔ)言處理

自然語(yǔ)言處理是人工智能和語(yǔ)言學(xué)領(lǐng)域的分支學(xué)科指的是利用計(jì)算機(jī)對(duì)人類特有的書面形式和口頭形式的自然語(yǔ)言進(jìn)行各種類型處理和加工的技術(shù)。其中最關(guān)鍵的任務(wù)有：自動(dòng)分詞、命名實(shí)體識(shí)別、詞性標(biāo)注、句法分析、語(yǔ)義分析和篇章分析。主要應(yīng)用在：機(jī)器翻譯、文本分類、情感分析、信息檢索與過濾、自動(dòng)問答、信息抽取、自動(dòng)文摘和人機(jī)對(duì)話等領(lǐng)域。

推薦教材：

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

統(tǒng)計(jì)自然語(yǔ)言處理

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

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

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

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

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

具體的分詞方法目前主要有以下幾種，前兩天也有一個(gè)利用深度學(xué)習(xí)的解決方案開源了，可以關(guān)注一下：

簡(jiǎn)單的模式匹配

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

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

統(tǒng)計(jì)語(yǔ)言模型分詞、串頻統(tǒng)計(jì)和詞形匹配相結(jié)合的漢語(yǔ)自動(dòng)分詞、無詞典分詞

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

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

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

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

常見應(yīng)用

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

智能問答技術(shù)

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

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

遺憾的是，目前大部分理解問題的技術(shù)都是基于正則表達(dá)式的，畢竟在自然語(yǔ)言理解這塊，暫時(shí)還沒有突破性進(jìn)展。

傳統(tǒng)自動(dòng)問答技術(shù)主要是基于語(yǔ)料庫(kù)的自動(dòng)問答或基于知識(shí)庫(kù)的自動(dòng)問答，基本包括三個(gè)步驟：

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

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

情感分析與觀點(diǎn)挖掘

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

基本的框架如下所示：

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

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

主客觀分析/觀點(diǎn)文本識(shí)別

• 客觀：反映關(guān)于世界的事實(shí)信息
• 主觀：反映個(gè)人情感、信念等

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

對(duì)包含觀點(diǎn)的文本進(jìn)行傾向性判斷

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

情緒分析

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

而對(duì)于觀點(diǎn)挖掘來說，一個(gè)觀點(diǎn)表示為一個(gè)五元組：目標(biāo)對(duì)象, 目標(biāo)對(duì)象特征, 觀點(diǎn)的情感值, 觀點(diǎn)持有者, 觀點(diǎn)表達(dá)時(shí)間。實(shí)際上，觀點(diǎn)抽取任務(wù)是很困難的，我們重點(diǎn)關(guān)注兩個(gè)子任務(wù)：

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

抽取對(duì)象的所有特征表達(dá)，并將同義特征表達(dá)聚類。每個(gè)特征類表示了關(guān)于該對(duì)象的獨(dú)一無二的某個(gè)特征

特征情感分類(aspect sentiment classification)

確定觀點(diǎn)針對(duì)每個(gè)特征的情感傾向：正面、負(fù)面、中性

信息摘要

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

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

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

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

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

社交網(wǎng)絡(luò)分析

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

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

比較常見的任務(wù)有：

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

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

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

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

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

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

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

試一試

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

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

總結(jié)

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