重磅干貨丨互聯(lián)網(wǎng)數(shù)據(jù)挖掘?qū)д?/h1>

來源：wdxtub 時間：2017-02-06 11:48:35 作者：小土刀

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

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

　　了解搜索和自然語言處理的基本知識

　　熟悉數(shù)據(jù)挖掘的流程與各個步驟所用的技術(shù)

　　對數(shù)據(jù)挖掘的應(yīng)用場景有基本的認(rèn)識

　　?寫在前面

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

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

　　搜索技術(shù)

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

　　具體應(yīng)用

　　?搜索

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

　　文檔表示

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

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

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

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

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

　　文檔索引

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

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

　　文檔檢索

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

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

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

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

　　文檔收集

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

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

　　健壯 Robustness, 避免進(jìn)入死循環(huán)

　　友好 Politeness, 遵守服務(wù)器的采集協(xié)議

　　分布式 Distributed, 多臺機器分布式采集

　　可擴展 Scalable, 爬蟲架構(gòu)方便擴展

　　性能與效率，有效利用系統(tǒng)資源

　　質(zhì)量 Quality, 傾向于采集有用的頁面

　　新穎 Freshness, 獲取網(wǎng)頁的最新版本

　　可擴充 Extensible, 能夠處理新數(shù)據(jù)類型、新的采集協(xié)議等

　　鏈接分析

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

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

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

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

　　主要任務(wù)

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

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

　　隨著數(shù)據(jù)量的增大，如何讓數(shù)據(jù)挖掘更加容易拓展效率更高，如何去挖掘有上下文關(guān)系的數(shù)據(jù)，如何從復(fù)雜、異構(gòu)、網(wǎng)絡(luò)化數(shù)據(jù)中挖掘復(fù)雜知識，如何挖掘低質(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

　　自然語言處理

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

　　▊推薦教材：

　　Foundations of Statistical Natrual Language Processing

　　Speech and Language Processing

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

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

　　詞和詞組的邊界模糊

　　新詞(未登陸詞)

　　切分歧義

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

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

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

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

　　簡單的模式匹配

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

　　基于規(guī)則的方法

　　最少分詞算法

　　基于統(tǒng)計的方法

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

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

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

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

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

　　常見應(yīng)用

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

　　▊智能問答技術(shù)

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

　　根據(jù)答案類型劃分

　　事實型問題(Factual questions)

　　觀點型問題(Opinions)

　　摘要型問題(Summaries)

　　根據(jù)問題言語行為(question speech act)劃分

　　是否型問題(Yes/NO questions)

　　WH 問題(WH questions)

　　間接請求(Indirect Requests)

　　命令(Commands)

　　復(fù)雜/困難問題

　　為什么/怎么樣(Why, How questions)

　　什么(What questions)

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

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

　　問題分析(分類、模板匹配、語義分析)

　　段落檢測(段落抽取、排序)

　　答案抽取(實體識別、模板匹配、排序)

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

　　情感分析與觀點挖掘

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

　　▊基本的框架如下所示：

　　應(yīng)用層：情感檢索，情感摘要，情感問答

　　核心層：情感要素抽取，情感傾向性分析，主客觀分析/觀點文本識別

　　基礎(chǔ)層：NLP 基本模塊，情感資源收集與標(biāo)注

　　來源：產(chǎn)品評論，電影評論，新聞評論，博客，微博

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

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

　　客觀：反映關(guān)于世界的事實信息

　　主觀：反映個人情感、信念等

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

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

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

　　情緒分析

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

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

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

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

　　特征情感分類(aspect sentiment classification)

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

　　信息摘要

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　?試一試

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

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

　　?總結(jié)

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

　　注：本文來源wdxtub.com/2016/11/27/bzs-dm-internet/ 作者：小土刀，版權(quán)著作權(quán)屬原創(chuàng)者所有。編輯：Fynlch（王培），數(shù)據(jù)觀微信公眾號（ID:cbdioreview），欲了解更多大數(shù)據(jù)行業(yè)相關(guān)資訊，可搜索數(shù)據(jù)觀（中國大數(shù)據(jù)產(chǎn)業(yè)觀察網(wǎng)www.21jieyan.cn）進(jìn)入查看。

責(zé)任編輯：王培