文本挖掘算法總結(jié)

1、文本數(shù)據(jù)挖掘算法應(yīng)用小結(jié)1基于概率統(tǒng)計的貝葉斯分類2、ID3決策樹分類3、基于粗糙集理論 Rough Set的確定型知識挖掘4、基于k-means聚類5、無限細(xì)分的模糊聚類 Fuzzy Clusteri ng6、SOM神經(jīng)元網(wǎng)絡(luò)聚類7、基于Meaning的文本相似度計算8、文本模糊聚類計算9、文本k-means聚類10、文本分類11、關(guān)聯(lián)模式發(fā)現(xiàn)12、序列模式發(fā)現(xiàn)13、PCA主成分分析1基于概率統(tǒng)計的貝葉斯分類算法概述：貝葉斯公式是由英國數(shù)學(xué)家(Thomas Bayes 1702-1763 )創(chuàng)造，用來描述兩個條件概率之間的關(guān)系，比如 P(A|B)為當(dāng)“ B”事件發(fā)生時“ A”事件發(fā)生的概率，

2、按照乘法法 則：P(A A B)=P(A)*P(B|A)=P(B)*P(A|B)，可導(dǎo)出貝葉斯公式：P(A|B)=P(B|A)*P(A)/P(B)貝葉斯分類基本思想為：設(shè)決策變量為D , D1, D2 , Di，Dk為n條記錄組成的樣本空間S的一個劃分，將n條記錄劃分成k個記錄集合，如果以 P(Di)表示事件Di發(fā)生的概率, 且 P(Di) > 0 ( i=1 , 2,，k)。對于任一事件 x, P(x)>0，則有：貝葉斯分類的基本原理，就是利用貝葉斯條件概率公式，將事件X視為多個條件屬性 Cj各種取值的組合，當(dāng)x事件發(fā)生時決策屬性 Di發(fā)生的條件概率。貝葉斯分類是一種概率型分 類

3、知識挖掘方法，不能百分之百地確定X事件發(fā)生時Di 一定發(fā)生。解決問題：預(yù)測所屬分類的概率。通過已知n條樣本集記錄，計算各種條件屬性組發(fā)生的概 率，得出“貝葉斯分類”規(guī)則，給定一個未知“標(biāo)簽”記錄，選擇最大概率為其所屬“分類”。2、ID3決策樹分類算法概述：ID3算法是J. Ross Quinlan在1975提出的分類算法，當(dāng)時還沒有“數(shù)據(jù)挖掘” 的概念。該算法以信息論為基礎(chǔ)，以信息熵和信息增益度來確定分枝生成決策樹D-Tree。ID3算法以決策樹D-Tree構(gòu)建分類知識模型，D-Tree中最上面的節(jié)點為根節(jié)點Root，每個分支是一個新的決策節(jié)點，或者是樹的葉子。每個決策節(jié)點代表一個問題或決策，

4、每一個葉子節(jié)點代表一種可能的分類結(jié)果，沿決策樹在每個節(jié)點都會遇到一個測試，對每個節(jié)點上問題的不同取值導(dǎo)致不同的分支，最后會到達(dá)一個葉子節(jié)點為確定所屬分類。3YE$離中強關(guān)解決問題：預(yù)測所屬分類。通過已知樣本集記錄，生成一顆“分類知識樹”，給定一個未知“標(biāo)簽”記錄，通過“分類知識樹”來確定其所屬分類。3、基于粗糙集理論 Rough Set的確定型知識挖掘算法概述：1982年波蘭學(xué)者 乙Paw lak提出了粗糙集理論 Rough Sets Theory，它是一種刻 劃不完整性和不確定性的數(shù)學(xué)工具，能有效分析不精確、不一致(Inconsistent)、不完整(Incomplete)等各種不完備信息，

5、利用數(shù)據(jù)進(jìn)行分析和推理，從中發(fā)現(xiàn)隱含的知識，揭示 潛在的規(guī)律。粗糙集理論是繼概率論、模糊集、證據(jù)理論之后的又一個處理不確定性事物的數(shù)學(xué)工具。粗糙集理論是建立在分類機制的基礎(chǔ)上的，它將分類理解為在特定空間上的等價關(guān)系，而等價關(guān)系構(gòu)成了對該空間的劃分。粗糙集理論將知識理解為對數(shù)據(jù)的劃分，每一被劃分的集合稱為概念。其主要思想是利用已知的知識庫，將不精確或不確定的知識用已知的 知識庫中的知識來(近似)刻畫。解決問題：預(yù)測所屬分類。粗糙集分類將樣本空間 S劃分為上近似集(Upper approximation)、 下近似集(Lower approximation )、邊界集(Boundary regio

6、n)，挖掘條件屬性 C與決策屬性 D集合所包含的不可分記錄(不能再細(xì)分，該集合中的所有記錄都屬于某一決策屬性Di的取值)，這些記錄形成不可辨識的關(guān)系(Indiscernibility relation)，由此確定分類規(guī)則：IF 條件屬性C成立 THEN 決策屬性Di發(fā)生即，如果滿條件C,則其所屬分類為 Di。IF中的條件C可以是單一條件，也可以是組合and (并且)組合條件。BIC給出的是“最小分類規(guī)則”。所謂“最小分類規(guī)則”是，最少的條件組合。例如一個人 屬于“高”、“富”、“帥”，條件為：“身高”、“財富”、“工資性收入”、“財產(chǎn)性收入”、“產(chǎn)業(yè) 收入”、“臉型”、“眼睛大小”、“鼻梁形狀

7、”、“英俊”等條件來判別，通過“粗糙集”分類計 算，得出最小分類規(guī)則可能是“ IF財富=XXX1 and 身高=185cm and相貌=英俊”其他條件可以忽略不計，這就是“最小分類規(guī)則”?！按植诩狈诸愐?guī)則為“百分之百確定型”分類規(guī)則，這是對樣本集的統(tǒng)計結(jié)果，如果出現(xiàn) 非“樣本集”中出現(xiàn)過的條件變量屬性，將無法得出“粗糙集”，可轉(zhuǎn)而使用概率型“貝葉斯分類”進(jìn)行計算。4、基于k-means聚類算法概述：給定一個包括n條記錄、每條記錄有 m個屬性 的樣本集，再給出分類數(shù) k,要 求將樣本集中的記錄，按記錄間的相似性大小(或距離遠(yuǎn)近)，將相似性最大(或距離最近)的記錄劃分到k個類中，相同分類中記錄間

8、的距離要盡可能地小，而分類之間的距離要盡可能地大。BIC改進(jìn)了常規(guī)的k-means聚類算法，在聚類過程中，同時計算分類質(zhì)量（類內(nèi)均差、類|魚|空間均距亡片和無），并求解最優(yōu)聚類 max元。解決問題：將n條記錄聚成k個分類。對n個樣本集記錄，指定分類個數(shù)k，為k個分類指定初始迭代記錄為 k個分類中心，通過計算其他記錄對 k個分類中心的距離，對不斷變換分 類、變換類中心，收斂都當(dāng)分類不再變化時，計算結(jié)束。由此，將n個樣本集記錄分配到 k個分類中，得到k個分類中心指標(biāo)。5、 無限細(xì)分的模糊聚類Fuzzy Clusteri ng算法概述：在實際解決聚類問題時，很多數(shù)事物是“模糊”的，其特征屬性A無法確

9、進(jìn)行量化，如：人的相貌、人與人之間的關(guān)系、人的性格、購買商品的意愿等，這就需要用模糊數(shù)學(xué)來進(jìn)行相似性計算。模糊數(shù)學(xué)是伴隨著上世紀(jì)五六十年代興起的控制論、信息論、系統(tǒng)論（俗稱“老三論”）而形成的一種決策方法， 是美國加利福尼亞大學(xué)伯克利分校 Lotfi Zadeh 教授于1965年創(chuàng)立的。模糊聚類基本計算步驟為：（1）將樣本集中的n條記錄變換成n x n的模糊相似矩陣；（2）通過傳遞包卷積計算將模糊相似矩陣變換成等價相似矩陣；（3） 最后通過入截矩陣將 n條記錄分成1-n個分類。K-means聚類需事先確定聚類數(shù) k，而模糊聚類Fuzzy Clustering無需事先確定聚類數(shù) k,可 以從最小

10、的k=1 （所有學(xué)習(xí)集中的 n條記錄為1個分類），到k=n （所有學(xué)習(xí)集中的 n條記 錄各為1個分類）。解決問題：將n條記錄聚成1-n個分類。模糊聚類 Fuzzy Clustering算法完全基于數(shù)據(jù)自然狀況進(jìn)行聚類，可產(chǎn)生聚類的解集合'（k=1,2,n），因此，可以在解集合中求解最優(yōu)聚類max '，這對觀察分析樣本集的數(shù)據(jù)性態(tài)非常有用，可供觀察不同情況下的“聚類”狀況。6、SOM神經(jīng)元網(wǎng)絡(luò)聚類算法概述：人類對事物的認(rèn)知是一個不斷積累的過程，通過對事物的觀察，不斷地認(rèn)識和修正因果關(guān)系，最后逐漸穩(wěn)定為認(rèn)知規(guī)則。醫(yī)學(xué)證明，人眼的視網(wǎng)膜、脊髓和海馬中存一種側(cè)抑制現(xiàn)象，即,當(dāng)一個神經(jīng)細(xì)

11、胞興奮后，會對其周圍的神經(jīng)細(xì)胞產(chǎn)生抑制作用。這種側(cè)抑制使神經(jīng)細(xì)胞之間呈現(xiàn)出競爭，開始時可能多個細(xì)胞同時興奮，但一個興奮程度最強的神經(jīng)細(xì)胞對周圍神經(jīng)細(xì)胞的抑制作用也最強，其結(jié)果使其周圍神經(jīng)細(xì)胞興奮程度減弱，從而該神經(jīng)細(xì)胞是這次競爭的“勝者”，其它神經(jīng)細(xì)胞在競爭中失敗。1981年芬蘭學(xué)者 kohonen提出一個稱為自組織特征映射（Self Organization Feature Map-SOM或SOFM ）網(wǎng)絡(luò)，前述大腦神經(jīng)細(xì)胞興奮規(guī)律等，在該網(wǎng)絡(luò)中都得到了反應(yīng)。在競爭層神經(jīng) 元之間的連線，它們是模擬生物神經(jīng)網(wǎng)絡(luò)層內(nèi)神經(jīng)元相互抑制現(xiàn)象的權(quán)值，這類抑制性權(quán)值滿足一定的分布關(guān)系，如距離近的抑制強，距

12、離遠(yuǎn)的抑制弱。輻入模式通過上述可知，SOM聚類算法設(shè)計的核心思想是體現(xiàn)神經(jīng)元在認(rèn)知過程中的3個特性：（1）根據(jù)樣本比較，逐步積累、不斷修正、漸近穩(wěn)定特性？（2）神經(jīng)元之間的側(cè)抑由近到遠(yuǎn)、逐步衰弱制特性？（3）神經(jīng)元興奮區(qū)域隨認(rèn)知次數(shù)逐步縮小范圍特性？BIC采用歐氏距離作為輸入模式Xi與各輸出神經(jīng)元 Wj之間的相似度，選擇具有最小距離的神經(jīng)元為興奮神經(jīng)元；采用（1-ti/tm ）作為學(xué)習(xí)衰減函數(shù)，其中 ti為當(dāng)前學(xué)習(xí)次數(shù)（第幾 次樣本訓(xùn)練），tm為總的學(xué)習(xí)數(shù)，以此來體現(xiàn)上述特性“1”；采用（1-ti/T ）、C/Wij作為神經(jīng)元側(cè)抑制函數(shù)，其中 C為設(shè)定的常數(shù)、 Wij為被選中的神經(jīng)元與其他神經(jīng)

13、元最遠(yuǎn)距離，來 體現(xiàn)上述特性“ 2”、“3”。解決問題：將n條記錄按m個輸出神經(jīng)元聚成 m個分類。模仿人類的學(xué)習(xí)方法，對事物的 認(rèn)識是一個由淺入深、 逐步學(xué)習(xí)、修正的過程，將對各種要素組態(tài)的認(rèn)識逐步穩(wěn)定到認(rèn)知領(lǐng) 域，由此進(jìn)行“聚類”。7、基于Meaning的文本相似度計算算法概述：給出一組n個文檔Di”心二- - - b , BIC為每個文檔計算出一組最- - -具有代表性的詞組-，同時，計算出相互間內(nèi)容接近度及接近序列。BIC的Meaning挖掘與自動搜索不同于現(xiàn)有Baidu、Google人工輸入關(guān)鍵詞的搜索方式，現(xiàn)有搜索引擎不考慮語義和語境，只考慮詞W與文檔D的包含關(guān)系'和詞在文檔

14、內(nèi)的頻數(shù)TF，因此，關(guān)鍵詞的搜索與文檔內(nèi)容無關(guān)。例如：“姚明”是中國籃球的驕傲，但“姚明”還投身于公益事業(yè)，如果在搜索引擎中輸入“姚明”，不見得搜索的文檔內(nèi)容只包含與籃球相關(guān)的內(nèi)容，還可能包括公益及其他包含 “姚明”的文檔，可見，關(guān)鍵詞搜索具有不確定性。如果在搜索引擎輸入一組詞 “姚明”、“得分”、“籃板” ，搜出文檔是籃球比賽內(nèi)容的概率更大，顯然，叫形成的交集縮小了搜索范圍，但組詞 “姚明”、“得分”、“籃板” 是經(jīng)過人思考給出的。BIC通過計算得出文檔代表詞組 ' '' ' 1 ' 'i，相當(dāng)于人工輸入 “姚i明”、“得分”、“籃板” ，同時

15、計算詞"】在句子中語序關(guān)系的發(fā)生概率與馬爾科夫鏈，因此，能夠更好地確定搜索詞的語義和語境，通過對文檔間的相關(guān)性 （接近度）進(jìn)行聚類計算，可按Meaning “接近度”進(jìn)行自動搜索而無需人工干預(yù)，并隨文檔內(nèi)容的變化而自動跟蹤 Meaning變化，使搜索更加準(zhǔn)確、更加自動化，讓搜索“隨用戶的心而動”。BIC可用于基于Meaning計算的搜索、輿情分析、特定情報分析、垂直搜索和相似內(nèi)容推薦等文本挖掘。解決問題：計算兩個文本的相似度。8、文本模糊聚類計算算法概述：基于模糊聚類算法，BIC首先計算將n個文本組成相似矩陣(第i個文本文檔對第j個文本文檔的相似度)，然后將相似矩陣變成模糊相似矩陣悶

16、，通過求模糊相似矩陣的等價矩陣和截矩陣，將n個文本文檔分成1-n個分類，同時，按相同分類中的文本具有最接近的內(nèi)容相似度Min也，不同文本分類間具有最大差異Max - ，來求解按文本內(nèi)容進(jìn)行最優(yōu)分類方案。解決問題：在不確定將文本劃分成幾類的情況下，將n個文本聚成1-n個分類，以此來觀察“聚類”效果。9、文本k-means聚類算法概述：基于k-means聚類，在BIC平臺上，用戶上傳或輸入 n個文本，確定希望分類 數(shù)量k和k個分類樣本，BIC將以k個樣本作為初始迭代點進(jìn)行k-means聚類計算，將n個文本分成k個分類。解決問題：在已經(jīng)確定了 k個分類的情況下，將文本劃分到k個“分類”中。10、文本

17、分類算法概述：通過“文本模糊聚類”或“文本k-means”聚類，BIC不僅將n個文本按內(nèi)容相似度進(jìn)行分類，同時挖掘出各個分類的“分類代表詞組”，以后，用戶任意給出一個文本，BIC將根據(jù)其對各個“分類代表詞組”的相似度，選擇最相似的分類MaxSimi,將該待分類文檔分配到MaxSimi類。解決問題：在已經(jīng)完成文本聚類的情況下，將不確定的文本劃分到“分類”中。11、關(guān)聯(lián)模式發(fā)現(xiàn)算法概述：關(guān)聯(lián)分析的目的是挖掘隱藏的關(guān)聯(lián)(Association)模型，最著名的關(guān)聯(lián)模式應(yīng)用是挖掘“購物籃”問題，是從發(fā)現(xiàn)購買行中，發(fā)現(xiàn)商品之間的關(guān)聯(lián)關(guān)系。給定一組交易記錄：交易12商品;商品商口口打'2商品橘子Q香

18、蕉Q1- EQ平果心香水皮包* 皮輕帽子*心護P+>p2aWQ+J沖每筆交易ID包含m個商品 ' ，n條記錄組成二維表，構(gòu)成矩陣,BIC可計算得出任意兩商品 組合的Con fide nce(A->B)=P(A | B)置信度和支持度Support(A->B)=P(A U B)，可用于分析商品之間的關(guān)聯(lián)性“購物籃”問題。BIC的關(guān)聯(lián)模式發(fā)現(xiàn)是一個快速、 交互式Apriore計算過程：從發(fā)現(xiàn)最基本的2個Item關(guān)聯(lián) 高頻項集開始，計算支持度 Support(A->B)=P(A U B)和置信度 Confidence(A->B)=P(A | B)， 逐步計算和發(fā)

19、現(xiàn) 2、3、4Item關(guān)聯(lián)頻繁項集。因為：(1 )任何求解高頻關(guān)聯(lián)事務(wù)T中的項數(shù)Item必然大于等于2,如果只有1個Item不存在關(guān)聯(lián)；(2)任何交易記錄 T 中無論有多少個 Item 組合,如果存在大于 2 個 Item 的高頻組合,都 必然存在 2 關(guān)聯(lián)的高頻真子集。如：交易記錄 T1=Item1 ， Item2，交易記錄 T2=Item1 ， Item3， Item4， Item2，貝U T1 為 T2 的非空真子集 T1? T2。所以,如果存在 3 關(guān)聯(lián)的高頻 Item 組合,必然存在 2 關(guān)聯(lián)的高頻組合；如果存在 4關(guān)聯(lián)的 Item高頻組合，必然存在3關(guān)聯(lián)高頻組合。BIC就是通過最基

20、本的 2關(guān)聯(lián)高頻項集發(fā)現(xiàn)開 始,逐步縮小記錄集合,逐步發(fā)現(xiàn)所有任意數(shù)量 Item 組合的高頻項集。因此, BIC 的關(guān)聯(lián) 計算是一個快速、交互式計算的 Apriore 算法。解決問題： 從樣本集中發(fā)現(xiàn)有較強“置信度”的關(guān)聯(lián)規(guī)貝。12、序列模式發(fā)現(xiàn)算法概述： 算法原理同“關(guān)聯(lián)分析” ,但統(tǒng)計點在于事物(或商品購買)發(fā)生的先后序列。 如商品購買行為預(yù)測： 汽車改裝愛好者, 購買某種品牌增壓器的人, 很多人后來還購買了活 塞環(huán)、又購買了某品牌機油，通過序列分析，發(fā)現(xiàn)其購買序列、預(yù)測下一步購買行為；如疾病診斷：患有某種疾病的人，先出現(xiàn) A癥狀、后出現(xiàn) B癥狀、又出現(xiàn) C癥狀，通過 出現(xiàn)癥狀的序列分析,

21、發(fā)現(xiàn)疾病發(fā)生、發(fā)展的序列模式,對疾病進(jìn)行診斷；如Web訪問行為模式發(fā)現(xiàn)： 每個IP訪問網(wǎng)站都是一個 Web會話Session,每個Session由一 系列的URL序列組成，通過 Session計統(tǒng)計得到高頻 URL序列，預(yù)測用戶的訪問行為； 不限于上述例子,還包括生物進(jìn)化序列模式、 DNA 序列、地震、火災(zāi)、戰(zhàn)爭沖突爆發(fā)序列 模式預(yù)測等,序列規(guī)律是大量存在的,只要有足夠的統(tǒng)計數(shù)據(jù),都可以通過BIC 發(fā)現(xiàn)最率并進(jìn)行預(yù)測。序列模式發(fā)現(xiàn)與關(guān)聯(lián)模式發(fā)現(xiàn)在算法上很相似,但序列模式強調(diào)Item 的先后順序,而關(guān)聯(lián)模式發(fā)現(xiàn)不關(guān)心順序，只看是否在一個事物T中2個Item (或多個)是否同時出現(xiàn)。BIC 的序列

22、模式發(fā)現(xiàn)是一個快速、 交互式 Apriore 計算過程： 從發(fā)現(xiàn) 2 個 Item 序列高頻序列 開始，計置信度 Confidence(A->B)=P(A | B)，逐步計算和發(fā)現(xiàn) 2、3、4Item序列頻繁序列。 因為：(1) 任何求解高頻序列事務(wù)T 中的項數(shù) Item 必然大于等于 2,如果只有 1 個 Item 不存在關(guān) 聯(lián)；(2) 任何事務(wù)記錄 T 中無論有多少個 Item 序列組合,如果存在大于 2 個 Item 的高頻序列 組合,都必然存在 2 序列的高頻序列真子集。如：事務(wù)序列記錄 T1=Item1 , Item2 ,事務(wù)序列記錄 T2=Item1 , Item3, Ite

23、m4, Item2 , 貝 T1 為 T2 的非空真子集 T1? T2。所以,如果存在 3個 Item 序列的高頻 Item 組合,必然存在 2序列的高頻序列組合,如果存 在 4個 Item 的高頻序列組合,必然存在 3 高頻序列組合。 BIC 就是通過最基本的 2 序列 高頻序列發(fā)現(xiàn)開始, 逐步縮小記錄集合, 逐步發(fā)現(xiàn)所有任意數(shù)量 Item 組合的高頻序列組合。 因此, BIC 的序列計算是一個 * 快速、交互式計算的 Apriore 算法。解決問題：序列模式發(fā)現(xiàn)的目的是挖掘事務(wù)發(fā)生、發(fā)展的序列(Seque ncing)模式，從樣本集發(fā)現(xiàn)有較強“置信度”的序列規(guī)貝。13、PCA 主成分分析算法概述：假設(shè)一個事物由多種因素構(gòu)成，設(shè)有n個樣本，每個樣本共有 m個屬性