大數(shù)據(jù)挖掘與應(yīng)用-第16章文本分析方法及其應(yīng)用

第十六章文本分析方法及應(yīng)用文本分析是指對文本的表示及其特征項的選取，文本分析是文本挖掘、信息檢索的一個基本問題，它把從文本中抽取出的特征詞進行量化來表示文本信息。文本分析的目的是將它們從一個無結(jié)構(gòu)的原始文本轉(zhuǎn)化為結(jié)構(gòu)化的計算機可以識別處理的信息，即對文本進行科學(xué)的抽象，建立它的數(shù)學(xué)模型，用以描述和代替文本，使計算機能夠通過對這種模型的計算和操作來實現(xiàn)對文本的識別。16.1文本分析簡介由于文本是非結(jié)構(gòu)化的數(shù)據(jù)，要想從大量的文本中挖掘有用的信息就必須首先將文本轉(zhuǎn)化為可處理的結(jié)構(gòu)化形式。目前通常采用向量空間模型來描述文本向量，但是如果直接用分詞算法和詞頻統(tǒng)計方法得到的特征項來表示文本向量中的各個維，那么這個向量的維度將是非常的大。這種未經(jīng)處理的文本矢量不僅給后續(xù)工作帶來巨大的計算開銷，使整個處理過程的效率非常低下，而且會損害分類、聚類算法的精確性，從而使所得到的結(jié)果很難令人滿意。因此必須對文本向量做進一步凈化處理，在保證原文含義的基礎(chǔ)上找出對文本特征類別最具代表性的文本特征，為了解決這個問題，最有效的辦法就是通過特征選擇來降維。因此，文本表示模型的選擇和特征詞選擇算法的選取是文本分析的重要研究內(nèi)容，特征選擇和特征提取的方法在第2章已經(jīng)進行了介紹，本章重點介紹一下與文本表示模型相關(guān)的方法和技術(shù)。16.2TF-IDF方法

通常取以10為底的對數(shù)，分母中的1是為了避免出現(xiàn)分母為零的情況。TFI-DF算法是建立在如下假設(shè)之上：1.對區(qū)別文件最有意義的詞語應(yīng)該是那些在文件中出現(xiàn)頻率較高，而在整個文件集的其他文件中出現(xiàn)頻率較低的詞，所以如果特征空間坐標系取TF作為測度，就可以體現(xiàn)同類文本的特點。2.考慮到單個詞區(qū)別不同文件的能力，TFI-DF算法認為一個詞出現(xiàn)在不同文件的頻數(shù)越小，它區(qū)別不同文件的能力就越大。因此引入了逆向文件頻率IDF的概念，以TF和IDF的乘積作為特征空間坐標系的取值測度，并用它完成對權(quán)值TF的調(diào)整，調(diào)整權(quán)值的目的在

16.3中文分詞方法詞是最小的能夠獨立活動的有意義的語言成分，英文單詞之間是以空格作為自然分界符的，而漢語是以字為基本的書寫單位，詞語之間沒有明顯的區(qū)分標記，因此，中文分詞是中文信息處理的基礎(chǔ)與關(guān)鍵。分詞技術(shù)針對用戶提交查詢的關(guān)鍵詞串進行的查詢處理后，根據(jù)用戶的關(guān)鍵詞串用各種匹配方法進行分詞的一種技術(shù)。常見的分詞方法分為三類：基于字典或詞庫匹配的分詞方法、基于詞頻度統(tǒng)計的分詞方法以及基于知識理解的分詞方法等?；谧值浠蛟~庫匹配的分詞方法又叫機械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功(識別出一個詞)。按照掃描方向的不同，字符串匹配分詞方法可以分為正向匹配和逆向匹配；按照不同長度優(yōu)先匹配的情況，可以分為最大(最長)匹配和最小(最短)匹配；按照是否與詞性標注過程相結(jié)合，又可以分為單純分詞方法和分詞與詞性標注相結(jié)合的一體化方法。16.3中文分詞方法16.3.1基于字典或詞庫匹配的分詞方法1.正向最大匹配法最大正向匹配法的基本思想為：假定分詞詞典中的最長詞有i個漢字字符，則用被處理文檔的當前字串中的前i個字作為匹配字段，查找字典。若字典中存在這樣的一個i字詞，則匹配成功，匹配字段被作為一個詞切分出來。如果詞典中找不到這樣的一個i字詞，則匹配失敗，將匹配字段中的最后一個字去掉，對剩下的字串重新進行匹配處理，如此進行下去直到匹配成功，即切分出一個詞或剩余字串的長度為零為止。這樣就完成了一輪匹配，然后取下一個i字字串進行匹配處理，直到文檔被掃描完為止。簡單而言，正向最大匹配法就是把一個詞從左至右來分詞，例如“不知道你在說什么”這句話采用正向最大匹配法的結(jié)果是：“不知道”、“你”、“在”和“說什么”。2.反向最大匹配法反向最大匹配法的基本原理與正向最大匹配法相同，不同的是分詞切分的方向與正向最大匹配法相反，而且使用的分詞辭典也不同。反向最大匹配法從被處理文檔的末端開始匹配掃描，每次取最末端的2i個字符（i字字串）作為匹配字段，若匹配失敗，則去掉匹配字段最前面的一個字，繼續(xù)匹配。相應(yīng)地，它使用的分詞詞典是逆序詞典，其中的每個詞條都將按逆序方式存放。在實際處理時，先將文檔進行倒排處理，生成逆序文檔。然后，根據(jù)逆序詞典，對逆序文檔用正向最大匹配法處理即可。簡單地說，反向最大匹配法就是把一個詞從左至右來分詞，例如“不知道你在說什么”這句話采用反向最大匹配法的結(jié)果是：“不”、知道”、“你在”、“說”和“什么”。由于漢語中偏正結(jié)構(gòu)較多，若從后向前匹配可以適當提高精確度。所以反向最大匹配法比正向最大匹配法的誤差要小。例如切分字段“碩士研究生產(chǎn)”，正向最大匹配法的結(jié)果會是“碩士研究生/產(chǎn)”，而反向最大匹配法利用逆向掃描，可得到正確的分詞結(jié)果“碩士/研究/生產(chǎn)”。當然，最大匹配算法是一種基于分詞詞典的機械分詞法，不能根據(jù)文檔上下文的語義特征來切分詞語，對詞典的依賴性較大，所以在實際使用時難免會造成一些分詞錯誤。為了提高系統(tǒng)分詞的準確度，可以采用正向最大匹配法和反向最大匹配法相結(jié)合的分詞方案。3.雙向匹配分詞法雙向匹配法將正向最大匹配法與反向最大匹配法組合，先根據(jù)標點對文檔進行粗切分，把文檔分解成若干個句子，然后再對這些句子用正向最大匹配法和反向最大匹配法進行掃描切分，如果兩種分詞方法得到的匹配結(jié)果相同，則認為分詞正確，否則按最小集處理。4.最短路徑分詞法就是說一段話里面要求分出的詞數(shù)是最少的?！安恢滥阍谡f什么”最短路徑分詞法的結(jié)果是“不知道”、“你在”和“說什么”，這就是最短路徑分詞法，分出來就只有3個詞?；谠~的頻度統(tǒng)計的分詞方法是一種全切分方法，在討論這個方法之前先要明白什么叫全切分方法。全切分要求獲得輸入序列的所有可接受的切分形式，而部分切分只取得一種或幾種可接受的切分形式，由于部分切分忽略了可能的其他切分形式，所以建立在部分切分基礎(chǔ)上的分詞方法不管采取何種歧義糾正策略，都可能會遺漏正確的切分，造成分詞錯誤或失??；而建立在全切分基礎(chǔ)上的分詞方法，由于全切分取得了所有可能的切分形式，因而從根本上避免了可能切分形式的遺漏，克服了部分切分方法的缺陷。16.3中文分詞方法16.3.2基于詞的頻度統(tǒng)計的分詞方法全切分算法能取得所有可能的切分形式，它的句子覆蓋率和分詞覆蓋率均為100%，但全切分分詞并沒有在文本處理中廣泛地采用，原因有以下幾點：1.全切分算法只是能獲得正確分詞的前提，因為全切分不具有歧義檢測功能，最終分詞結(jié)果的正確性和完全性依賴于獨立的歧義處理方法，如果評測有誤，也會造成錯誤的結(jié)果。2.全切分的切分結(jié)果個數(shù)隨句子長度的增長呈指數(shù)增長，一方面將導(dǎo)致龐大的無用數(shù)據(jù)充斥于存儲數(shù)據(jù)庫；另一方面，當句長達到一定長度后，由于切分形式過多，造成分詞效率嚴重下降。

其中P(X,Y)是漢字X,Y的相鄰共現(xiàn)概率，P(X)，P(Y)分別是X,Y在語料中出現(xiàn)的概率?；バ畔Ⅲw現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。在緊密程度高于某一個閾值時，便可認為此字組可能構(gòu)成了一個詞。實際應(yīng)用的統(tǒng)計分詞系統(tǒng)都要使用一部基本的分詞詞典進行串匹配分詞，與字符串匹配分詞方法不同的是，統(tǒng)計分詞方法分出來的詞都是帶有概率信息的，最后通過在所有可能的切分結(jié)果中選出一種概率最大的分詞結(jié)果，這種方法具有自動消除歧義的優(yōu)點。目前，這種方法是分詞的主流方法。1.基于知識理解的分詞方法通常的分詞系統(tǒng)，都力圖在分詞階段消除所有歧義切分現(xiàn)象。而有些系統(tǒng)則在后續(xù)過程中來處理歧義切分問題，其分詞過程只是整個語言理解過程的一小部分。其基本思想就是在分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧義現(xiàn)象。它通常包括三個部分:分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。在總控部分的協(xié)調(diào)下，分詞子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對分詞歧義進行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗階段。16.3中文分詞方法16.3.3其他中文分詞方法2.并行分詞方法并行分詞方法借助于一個含有分詞詞庫的管道進行，比較匹配過程是分步進行的，每一步可以對進入管道中的詞同時與詞庫中相應(yīng)的詞進行比較，由于同時有多個詞進行比較匹配，因而分詞速度可以大幅度提高。這種方法涉及到多級內(nèi)碼理論和管道的詞典數(shù)據(jù)結(jié)構(gòu)。具體內(nèi)容可參考文獻[1]。總之，基于字典或詞庫匹配的分詞方法應(yīng)用詞典匹配、漢語詞法或其它漢語語言知識進行分詞，這類方法簡單、分詞效率較高，但漢語語言現(xiàn)象復(fù)雜豐富，詞典的完備性、規(guī)則的一致性等問題使其難以適應(yīng)開放的大規(guī)模文本的分詞處理?；谠~頻度統(tǒng)計的分詞方法基于字和詞的統(tǒng)計信息，如把相鄰字間的信息、詞頻及相應(yīng)的共現(xiàn)信息等應(yīng)用于分詞，由于這些信息是通過調(diào)查真實語料而取得的，因而基于統(tǒng)計的分詞方法具有較好的實用性，而基于知識理解的分詞方法試圖讓機器具有人類的理解能力，需要使用大量的語言知識和信息。由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機器可直接讀取的形式。因此目前基于知識的分詞系統(tǒng)還處在試驗階段。對中文分詞技術(shù)而言，出現(xiàn)了基于各種編程語言開發(fā)的分詞軟件包。如庖丁解牛分詞包[2]、LingPipe[3]、LibMMSeg[3]、IKAnalyzer[4]、PHPCWS[5]以及KTDictSeg[6]等。定義1主題（Topic）就是一個概念或方面。它表現(xiàn)為一系列相關(guān)的詞語（word），能夠代表某個主題，從數(shù)學(xué)角度來看就是詞匯表上詞語的條件概率分布。在文本挖掘時，計算文檔相似性是非常基礎(chǔ)的操作，通常對文本進行分詞、構(gòu)建向量空間模型（VectorSpaceModel,VSM），通過Jaccard系數(shù)或者余弦相似性（CosineSimilarity）計算距離或者相似度。上述方法是基于corpus庫的思路，即僅僅考慮詞組并未考慮文本的語義信息。針對下面情況，基于corpus庫將很難處理：16.4PLDA方法16.4.1主題模型“如果時間回到2006年，馬云和楊致遠的手還會握在一起嗎？”“阿里巴巴集團和雅虎就股權(quán)回購一事簽署了最終協(xié)議?！比绻捎没赾orpus庫的Jaccard距離等算法，那么這兩個文本的完全不相關(guān)，但是事實上，“馬云”和“阿里巴巴集團”，“楊致遠”和“雅虎”有著密切的聯(lián)系，從語義上看，兩者都和“阿里巴巴”有關(guān)系。再例如：“富士蘋果真好?！薄疤O果四代真好?！睆腸orpus庫上來看兩者非常相似，但是事實上，這兩個句子從語義上來講沒有任何關(guān)系，一個是“水果”而另一個是“手機”?；谝陨侠?，可以通過“主題”去解決這一問題。主題就像一個桶，裝了出現(xiàn)頻率很高的詞語，這些詞語和主題有很強的相關(guān)性，或者說這些詞語定義了這個主題。比如以“阿里巴巴”為主題，那么“馬云”，“電子商務(wù)”等詞會以很高的頻率出現(xiàn)，而如果涉及到以“騰訊”為主題，那么“馬化騰”、“微信”、“QQ”會以較高的頻率出現(xiàn)；同時，一個詞語可能來自于不同的桶，比如“電子商務(wù)”可以來自“阿里巴巴”主題，也可以來自“京東”主題，所以一段文字往往包含多個主題，一個主題也可以對應(yīng)多段文字。

主題模型的訓(xùn)練方法有很多，目前主要訓(xùn)練方法有PLSA(ProbabilisticLatentSemanticAnalysis)和LDA(LatentDirichletAllocation)。PLSA主要采用EM(期望最大化)算法，通過不斷進行E過程（求期望）與M過程（最大化）這兩種迭代過程去生成模型，同時EM算法保證上述迭代的收斂；LDA通過Gibbssampling方法去實現(xiàn)。主題模型具有如下特點：1.它可以衡量文檔之間的語義相似性。對于一篇文檔，我們求出來的主題分布可以看作是對它的一個抽象表示。對于概率分布，我們可以通過一些距離公式來計算出兩篇文檔的語義距離，從而得到它們之間的相似度。

2.它可以解決多義詞的問題。上述例子中，“蘋果”可能是水果，也可能指蘋果公司。通過我們求出來的分布，我們就可以知道“蘋果”都屬于哪些主題，就可以通過主題的匹配來計算它與其他文字之間的相似度。3.它可以排除文檔中噪音的影響。一般來說，文檔中的噪音往往處于次要主題中，我們可以把它們忽略掉，只保持文檔中最主要的主題。4.它是無監(jiān)督的，完全自動化的。我們只需要提供訓(xùn)練文檔，它就可以自動訓(xùn)練出各種概率，無需任何人工標注過程。5.它是跟語言無關(guān)的。任何語言只要能夠?qū)λM行分詞，就可以進行訓(xùn)練，得到它的主題分布。1

PLDA模型的產(chǎn)生設(shè)PLDA模型中總共定義了K個主題，V個詞語。任何一篇文檔是由K個主題中多個主題混合而成，換句話說每篇文檔都是主題上的一個概率分布doc(topic)。每個主題都是詞語上的一個概率分布〖topic〗_k(word)，下標k表示為第k個主題，換句話說，文檔中的每個詞語都是由某一個的主題隨機生成的。因此一篇文檔的生成過程如下：16.4PLDA方法16.4.2PLDA方法原理（1）依據(jù)doc(topic)概率分布，生成一個主題；（2）依據(jù)該主題的概率分布topic(word)，生成了一個word；（3）回到第（1）步，重復(fù)N次，則生成了這篇文章的N個word。因此，doc(topic)是總和為N的K多項分布，〖topic〗_k(word)是總和為N的V多項分布。如果選擇多項分布的先驗分布為Dirichlet分布，該模型則成了PLDA模型。

自然語言處理（NaturalLanguageProcessing，NLP）相關(guān)任務(wù)中，要將自然語言交給機器學(xué)習(xí)中的算法來處理，通常需要首先將語言數(shù)學(xué)化，而向量是人把自然界的東西抽象出來交給機器處理的有效形式，是人對機器輸入的主要方式之一。16.5Word2Vec基本原理詞向量就是用來將語言中的詞進行數(shù)學(xué)化的一種方式，顧名思義，詞向量就是把一個詞表示成一個向量，主要有兩種表示方式[7]。1. One-HotRepresentation該方法是用一個很長的向量來表示一個詞，向量的長度為詞典的大小，向量的分量只有一個1，其他全為0，1的位置對應(yīng)該詞在詞典中的位置。例如，“話筒”和“電視”可能會表示為：“話筒”表示為[0001000000…]16.5Word2Vec基本原理16.5.1詞向量的表示方式“電視”表示為[0000000100…]One-HotRepresentation方式非常適合用稀疏矩陣表示，但這種方法有兩個缺點：（1）容易受維數(shù)災(zāi)難的困擾；（2）不能很好地刻畫詞與詞之間的相似性。2.DistributedRepresentation這種方法最早是Hinton于1986年提出的，可以克服One-HotRepresentation的缺點。其基本想法是直接用一個普通的向量表示一個詞，這種向量一般是這種樣子：[0.792,?0.177,?0.107,0.109,?0.542,...]，也就是普通的向量表示形式。一個詞如何表示成如上所示的向量形式，是需要經(jīng)過一番訓(xùn)練的，訓(xùn)練方法較多，word2vec是其中一種。另外，每個詞在不同的語料庫和不同的訓(xùn)練方法下，得到的詞向量可能是不一樣的。用這種方法訓(xùn)練的詞向量維數(shù)一般不高，所以出現(xiàn)維數(shù)災(zāi)難的機會比One-HotRepresentation方法要小得多。用效果較好的訓(xùn)練算法得到的詞向量一般是有空間上的意義的，即將所有這些向量放在一起形成一個詞向量空間，而每一向量則為該空間中的一個點，在這個空間上的詞向量之間的距離度量也可以表示對應(yīng)的兩個詞之間的“距離”。所謂兩個詞之間的“距離”，就是這兩個詞之間的語法或語義之間的相似性，可以采用歐幾里得距離或余弦相似度等方法計算兩個詞向量之間的距離。16.5Word2Vec基本原理16.5.2統(tǒng)計語言模型（一）統(tǒng)計語言模型統(tǒng)計語言模型（StatisticalLanguageModel，SLM）是NLP的基礎(chǔ)，它被廣泛地應(yīng)用于語音識別、機器翻譯、分詞、詞性標注和信息檢索等任務(wù)。簡單來說，SLM是用來計算一個句子概率的概率模型，它通?；谝粋€語料庫來構(gòu)建[10]。什么叫做一個句子的概率呢？假設(shè)表示由T個詞按順序構(gòu)成的一個句子，則的聯(lián)合概率就是這個句子的概率。下面考慮一下模型參數(shù)的個數(shù)問題。剛才考慮的是一個給定長度為T的句子，需要計算T個參數(shù)。設(shè)語料庫對應(yīng)詞典D的大小（即詞匯量）為N，則如果考慮長度為T的任意句子，理論上就有NT種可能，而每種可能都要計算T個參數(shù)，總共就需要計算TNT個參數(shù)（這是大概的估算，沒有考慮重復(fù)參數(shù)的情況）。這個數(shù)量級是很大的，而且由于在計算過程中需要保存，其內(nèi)存開銷也很大。計算這些參數(shù)常見的方法有：N-Gram模型、決策樹、最大熵模型、最大熵馬爾科夫模型、條件隨機場以及神經(jīng)網(wǎng)絡(luò)等。下面討論一下N-Gram模型。通過這種簡化處理，不僅使得單個參數(shù)的統(tǒng)計變得更加容易（統(tǒng)計時需要匹配的詞串更短），也使得參數(shù)的總數(shù)變少了。那么N-Gram模型中的參數(shù)n取多大合適呢？一般來說，n的選取u需要同時考慮計算復(fù)雜度和模型效果兩個因素，具體取值如表16-1所示。表16-1N-Gram模型參數(shù)數(shù)量與n的關(guān)系表n模型參數(shù)數(shù)量1（unigram）2*1052（bigram）4*10103（trigram）8*10154（4-gram）16*1020在計算復(fù)雜度方面，表16-1給出了N-Gram模型中模型參數(shù)數(shù)量隨著n的逐漸增大而變化的情況。其中假定詞典大小N=200000（漢語的詞匯量大致是這個量級）。事實上，模型參數(shù)的量級是N的指數(shù)函數(shù)（O（Nn）），顯然n不能取值太大，實際應(yīng)用中最多是采用n=3的三元模型。在模型效果方面，理論上是n越大效果越好。但當n大道一定程度時，模型效果的提升幅度會變小。例如，當n從1到2，再從2到3時，模型的效果上升顯著，而從3到4時，效果的提升就不顯著了[8]。很顯然上面兩個問題的答案都是否定的。但這個問題無法回避，不管語料庫有多大。平滑技術(shù)就是用來處理這個問題的，這里不展開討論。總的來說，N-Gram模型的主要工作就是在語料中統(tǒng)計各種詞串出現(xiàn)的次數(shù)以及平滑處理，概率值計算好之后就存儲起來，下次需要計算一個句子的概率時，只需找到相關(guān)的概率參數(shù)，將它們連乘起來即可。如何利用模型進行預(yù)測呢？一種通用的思路就是對所考慮的問題建模后先為其構(gòu)造一個目標函數(shù)，然后對這個目標函數(shù)進行優(yōu)化，從而求得一組最優(yōu)的參數(shù)，最后利用這組最優(yōu)參數(shù)對應(yīng)的模型進行預(yù)測。（三）神經(jīng)概率語言模型這里以文獻[9]中提到的模型為例，說明神經(jīng)概率語言模型的基本原理。圖16-1給出了神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)示意圖，它包含四層：輸入層、投影層、隱藏層和輸出層。其中W、U分別為投影層與隱藏層以及隱藏層和輸出層之間的權(quán)值矩陣，p、q分別為隱藏層和輸出層上的偏置向量。圖16-1神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)示意圖對于語料C中的任意一個詞w，將Context(w)取為其前面的n-1個詞（與N-Gram模型類似）,二元組（Context(w),w）就是一個訓(xùn)練樣本了，接下來討論樣本（Context(w),w）經(jīng)過圖16-1所示的神經(jīng)網(wǎng)絡(luò)是如何計算的。需要說明的是，一旦語料C和詞向量長度m給定后，投影層和輸出層的規(guī)模就確定了，前者為(n-1)m，后者為N=|D|，即語料C的詞匯量大小，而隱藏層的規(guī)模n?h由用戶指定，是參數(shù)可調(diào)的。上述參數(shù)均通過訓(xùn)練算法得到。需要說明的是，在機器學(xué)習(xí)算法中輸入都是已知的，而在圖16-1所示的神經(jīng)概率語言模型中，輸入也需要通過訓(xùn)練才能得到。在圖16-1所示的神經(jīng)網(wǎng)絡(luò)中，投影層、隱藏層和輸出層的規(guī)模分別為（n-1）m、nh和N。整個模型的大部分計算集中在隱藏層和輸出層之間的矩陣向量計算以及輸出層上的softmax歸一化運算，很多工作都是對這一部分內(nèi)容進行優(yōu)化，包括Word2Vec的工作。與N-Gram模型相比，神經(jīng)概率語言模型具有如下優(yōu)勢。1.詞語之間的相似性可以通過詞向量來體現(xiàn)。2.基于詞向量的模型自帶平滑功能，不需要額外的處理。16.5Word2Vec基本原理16.5.3霍夫曼編碼1. 霍夫曼樹為了介紹霍夫曼編碼，需要介紹霍夫曼樹等基本概念。樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，它是數(shù)據(jù)元素（樹結(jié)點）按照分支關(guān)系組織起來的結(jié)構(gòu)。若干棵互不相交的樹所構(gòu)成的集合稱為森林。下面先給出幾個常用概念。（1） 路徑和路徑長度在一棵樹種，從一個結(jié)點往下可以到達的孩子或?qū)O子結(jié)點之間的通路稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層號為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。（2） 結(jié)點的權(quán)和帶權(quán)路徑長度若為樹種結(jié)點賦予一個具有某種含義的非負數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度是指，從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。（3） 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和。例16.1】假設(shè)從新浪微博中抓取的若干微博中，“我”、“喜歡”、“觀看”、“巴西”、“足球”、“世界杯”這六個詞出現(xiàn)的次數(shù)分別為15、8、6、5、3、1。請以這6個詞為葉子結(jié)點，以相應(yīng)詞頻為權(quán)值，構(gòu)造一棵哈夫曼樹。圖16-1哈夫曼樹構(gòu)造過程2. 霍夫曼編碼在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進制的字符串，用0、1碼的不同排列來表示字符。例如，假設(shè)要傳送報文“AFTERDATAEARAREARTAREA”，它包含字符集為“A,E,R,T,F,D”，這些字母各自出現(xiàn)的次數(shù)為8，4，5，3，1，1，現(xiàn)在要求為這些字母設(shè)計編碼。最簡單的區(qū)分上述6種字母的二進制編碼方法即為等長編碼，也就是為每個字母分配一個二進制序列。如可以用000，001,010,011,100,101對“A,E,R,T,F,D”進行編碼。顯然這種編碼的長度取決于報文中不同字符的個數(shù)，字符個數(shù)越多，編碼長度越大。但在報文傳送過程中總是希望總長度越短越好。另外，在實際應(yīng)用中，每個字符穿線的頻度是不同的，在設(shè)計編碼的時候總是希望讓使用頻率高的編碼短一些，以優(yōu)化整個報文編碼長度。為使不等長編碼為前綴編碼（即要求一個字符的編碼不能是另一個字符編碼的前綴），可以用字符集中的每個字符作為葉子結(jié)點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字符的出現(xiàn)頻率作為字符結(jié)點的權(quán)值賦予該結(jié)點。顯然，使用頻率越小的權(quán)值越小，權(quán)值越小葉子就越靠下。于是就實現(xiàn)了使用頻率小的編碼長，使用頻率高的編碼短。這樣就保證了此樹的最小帶權(quán)路徑長度，效果上就是傳送報文的最短路徑。因此求傳送報文最短路徑問題轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點，由字符出現(xiàn)頻率作為其權(quán)值所生成的哈夫曼樹的問題。利用哈夫曼樹設(shè)計的二進制前綴編碼稱為哈夫曼編碼，它既能滿足前綴編碼的條件，又能保證報文編碼總長最短。下一節(jié)要介紹的Word2Vec工具中也將用到哈夫曼編碼，它把訓(xùn)練語料中的詞當成葉子結(jié)點，其在語料中出現(xiàn)的次數(shù)當做權(quán)值，通過構(gòu)造相應(yīng)的哈夫曼樹來對每一個詞進行哈夫曼編碼?！纠?6.2】對于例16.1中6個詞的哈夫曼編碼，約定（詞頻較大者）左孩子結(jié)點編碼為1，（詞頻較小者）右孩子編碼為0.這樣，“我”、“喜歡”、“觀看”、“巴西”、“足球”、“世界杯”這六個詞的哈夫曼編碼分別為0、111、110、101、1001和1000。編碼過程如圖16-2所示。圖16-2哈夫曼編碼示意圖16.5Word2Vec基本原理16.5.4Word2vec原理簡介解釋完16.5.1節(jié)至16.5.3節(jié)的基本概念之后，我們來解釋一下Word2vec的基本原理。Word2vec是Google在2013年年中開源的一款將詞表征為實數(shù)值向量的高效工具，其利用深度學(xué)習(xí)的思想，可以通過訓(xùn)練，把對文本內(nèi)容的處理簡化為K維向量空間中的向量運算，而向量空間上的相似度可以用來表示文本語義上的相似度。Word2vec輸出的詞向量可以被用來做很多NLP相關(guān)的工作，比如聚類、找同義詞、詞性分析等等。如果換個思路，把詞當作特征，那么Word2vec就可以把特征映射到K維向量空間，可以為文本數(shù)據(jù)尋求更加深層次的特征表示。Word2vec使用的是Distributedrepresentation的詞向量表示方式。Distributedrepresentation最早由Hinton在1986年提出。其基本思想是通過訓(xùn)練將每個詞映射成K維實數(shù)向量（K一般為模型中的超參數(shù)），通過詞之間的距離（比如cosine相似度、歐氏距離等）來判斷它們之間的語義相似度。其采用一個三層的神經(jīng)網(wǎng)絡(luò)，輸入層-隱層-輸出層。核心技術(shù)是根據(jù)詞頻用Huffman編碼，使得所有詞頻相似的詞隱藏層激活的內(nèi)容基本一致，出現(xiàn)頻率越高的詞語，他們激活的隱藏層數(shù)目越少，這樣有效的降低了計算的復(fù)雜度。這個三層神經(jīng)網(wǎng)絡(luò)本身是對語言模型進行建模，但也同時獲得一種單詞在向量空間上的表示，而這個副作用才是Word2vec的真正目標。16.6基于阿里云數(shù)加平臺的文本分析實例我們對高爾基的作品《海燕》進行文本分析，數(shù)據(jù)信息如圖16-1所示。圖16-1數(shù)據(jù)信息16.6基于阿里云數(shù)加平臺的文本分析實例SplitWord是一種分詞方法，對于一篇文章做數(shù)據(jù)處理時，只能先將其分詞，然后對單個的詞做統(tǒng)計以及其他處理，因此，我們得到下面的操作流程圖。圖16-2阿里云平臺操作流程圖SplitWord，基于AliWS(AlibabaWordSegmenter的簡稱)詞法分析系統(tǒng)，對指定列對應(yīng)的文章內(nèi)容進行分詞，分詞后的各個詞語間以空格作為分隔符，若用戶指定了詞性標注或語義標注相關(guān)參數(shù)，則會將分詞結(jié)果、詞性標注結(jié)果和語義標注結(jié)果一同輸出，其中詞性標注分隔符為”/“，語義標注分隔符為”|”。目前僅支持中文淘寶分詞和互聯(lián)網(wǎng)分詞。其字段設(shè)置與參數(shù)設(shè)置如下圖所示，其中字段選擇的是‘id’和‘content’。圖16-3SplitWord算法設(shè)置界面16.6基于阿里云數(shù)加平臺的文本分析實例得到的結(jié)果如圖16-4所示。圖16-4Split算法實驗結(jié)果詞頻統(tǒng)計，