第一篇：文本挖掘算法總結(jié)

文本數(shù)據(jù)挖掘算法應(yīng)用小結(jié)

1、基于概率統(tǒng)計(jì)的貝葉斯分類

2、ID3 決策樹分類

3、基于粗糙集理論Rough Set的確定型知識(shí)挖掘

4、基于k-means聚類

5、無限細(xì)分的模糊聚類Fuzzy Clustering

6、SOM神經(jīng)元網(wǎng)絡(luò)聚類

7、基于Meaning的文本相似度計(jì)算

8、文本模糊聚類計(jì)算

9、文本k-means聚類

10、文本分類

11、關(guān)聯(lián)模式發(fā)現(xiàn)

12、序列模式發(fā)現(xiàn)

13、PCA主成分分析

1、基于概率統(tǒng)計(jì)的貝葉斯分類

算法概述：貝葉斯公式是由英國數(shù)學(xué)家(Thomas Bayes 1702-1763)創(chuàng)造，用來描述兩個(gè)條件概率之間的關(guān)系，比如 P(A|B)為當(dāng)“B”事件發(fā)生時(shí)“A”事件發(fā)生的概率，按照乘法法則：

P(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的一個(gè)劃分，將n條記錄劃分成k個(gè)記錄集合，如果以P(Di)表示事件Di發(fā)生的概率，且P(Di)> 0(i=1，2，…，k)。對(duì)于任一事件x，P(x)>0，則有：

貝葉斯分類的基本原理，就是利用貝葉斯條件概率公式，將事件X視為多個(gè)條件屬性Cj各種取值的組合，當(dāng)x事件發(fā)生時(shí)決策屬性Di發(fā)生的條件概率。貝葉斯分類是一種概率型分類知識(shí)挖掘方法，不能百分之百地確定X事件發(fā)生時(shí)Di一定發(fā)生。

解決問題：預(yù)測(cè)所屬分類的概率。通過已知n條樣本集記錄，計(jì)算各種條件屬性組發(fā)生的概率，得出“貝葉斯分類”規(guī)則，給定一個(gè)未知“標(biāo)簽”記錄，選擇最大概率為其所屬“分類”。

2、ID3 決策樹分類

算法概述：ID3算法是J.Ross Quinlan在1975提出的分類算法，當(dāng)時(shí)還沒有“數(shù)據(jù)挖掘”的概念。該算法以信息論為基礎(chǔ)，以信息熵和信息增益度來確定分枝生成決策樹D-Tree。ID3算法以決策樹D-Tree構(gòu)建分類知識(shí)模型，D-Tree中最上面的節(jié)點(diǎn)為根節(jié)點(diǎn)Root，每個(gè)分支是一個(gè)新的決策節(jié)點(diǎn)，或者是樹的葉子。每個(gè)決策節(jié)點(diǎn)代表一個(gè)問題或決策，每一個(gè)葉子節(jié)點(diǎn)代表一種可能的分類結(jié)果，沿決策樹在每個(gè)節(jié)點(diǎn)都會(huì)遇到一個(gè)測(cè)試，對(duì)每個(gè)節(jié)點(diǎn)上問題的不同取值導(dǎo)致不同的分支，最后會(huì)到達(dá)一個(gè)葉子節(jié)點(diǎn)為確定所屬分類。

解決問題：預(yù)測(cè)所屬分類。通過已知樣本集記錄，生成一顆“分類知識(shí)樹”，給定一個(gè)未知“標(biāo)簽”記錄，通過“分類知識(shí)樹”來確定其所屬分類。

3、基于粗糙集理論Rough Set的確定型知識(shí)挖掘

算法概述：1982年波蘭學(xué)者Z.Paw lak 提出了粗糙集理論Rough Sets Theory，它是一種刻劃不完整性和不確定性的數(shù)學(xué)工具，能有效分析不精確、不一致（Inconsistent)、不完整（Incomplete)等各種不完備信息，利用數(shù)據(jù)進(jìn)行分析和推理，從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。粗糙集理論是繼概率論、模糊集、證據(jù)理論之后的又一個(gè)處理不確定性事物的數(shù)學(xué)工具。粗糙集理論是建立在分類機(jī)制的基礎(chǔ)上的，它將分類理解為在特定空間上的等價(jià)關(guān)系，而等價(jià)關(guān)系構(gòu)成了對(duì)該空間的劃分。粗糙集理論將知識(shí)理解為對(duì)數(shù)據(jù)的劃分，每一被劃分的集合稱為概念。其主要思想是利用已知的知識(shí)庫，將不精確或不確定的知識(shí)用已知的知識(shí)庫中的知識(shí)來（近似）刻畫。解決問題：預(yù)測(cè)所屬分類。粗糙集分類將樣本空間S劃分為上近似集（Upper approximation)、下近似集（Lower approximation）、邊界集（Boundary region)，挖掘條件屬性C與決策屬性D集合所包含的不可分記錄（不能再細(xì)分，該集合中的所有記錄都屬于某一決策屬性Di的取值），這些記錄形成不可辨識(shí)的關(guān)系（Indiscernibility relation)，由此確定分類規(guī)則： IF <條件屬性C成立> THEN <決策屬性Di發(fā)生>

即，如果滿條件C，則其所屬分類為Di。IF中的條件C可以是單一條件，也可以是組合and（并且）組合條件。

BIC給出的是“最小分類規(guī)則”。所謂“最小分類規(guī)則”是，最少的條件組合。例如一個(gè)人屬于“高”、“富”、“帥”，條件為：“身高”、“財(cái)富”、“工資性收入”、“財(cái)產(chǎn)性收入”、“產(chǎn)業(yè)收入”、“臉型”、“眼睛大小”、“鼻梁形狀”、“英俊”等條件來判別，通過“粗糙集”分類計(jì)算，得出最小分類規(guī)則可能是

“IF 財(cái)富>=XXX1 and 身高>=185cm and 相貌=英俊” 其他條件可以忽略不計(jì)，這就是“最小分類規(guī)則”。

“粗糙集”分類規(guī)則為“百分之百確定型”分類規(guī)則，這是對(duì)樣本集的統(tǒng)計(jì)結(jié)果，如果出現(xiàn)非“樣本集”中出現(xiàn)過的條件變量屬性，將無法得出“粗糙集”，可轉(zhuǎn)而使用概率型“貝葉斯分類”進(jìn)行計(jì)算。

4、基于k-means聚類

算法概述：給定一個(gè)包括n條記錄、每條記錄有m個(gè)屬性 的樣本集，再給出分類數(shù)k，要求將樣本集中的記錄，按記錄間的相似性大?。ɑ蚓嚯x遠(yuǎn)近），將相似性最大（或距離最近）的記錄劃分到k個(gè)類中，相同分類中記錄間的距離要盡可能地小，而分類之間的距離要盡可能地大。BIC改進(jìn)了常規(guī)的k-means聚類算法，在聚類過程中，同時(shí)計(jì)算分類質(zhì)量（類內(nèi)均差、類間均距 和），并求解最優(yōu)聚類max{ }。

解決問題：將n條記錄聚成k個(gè)分類。對(duì)n個(gè)樣本集記錄，指定分類個(gè)數(shù)k，為k個(gè)分類指定初始迭代記錄為k個(gè)分類中心，通過計(jì)算其他記錄對(duì)k個(gè)分類中心的距離，對(duì)不斷變換分類、變換類中心，收斂都當(dāng)分類不再變化時(shí)，計(jì)算結(jié)束。由此，將n個(gè)樣本集記錄分配到k個(gè)分類中，得到k個(gè)分類中心指標(biāo)。

5、無限細(xì)分的模糊聚類Fuzzy Clustering 算法概述：在實(shí)際解決聚類問題時(shí)，很多數(shù)事物是“模糊”的，其特征屬性A無法確進(jìn)行量化，如：人的相貌、人與人之間的關(guān)系、人的性格、購買商品的意愿等，這就需要用模糊數(shù)學(xué)來進(jìn)行相似性計(jì)算。模糊數(shù)學(xué)是伴隨著上世紀(jì)五六十年代興起的控制論、信息論、系統(tǒng)論（俗稱“老三論”）而形成的一種決策方法，是美國加利福尼亞大學(xué)伯克利分校Lotfi Zadeh教授于1965年創(chuàng)立的。模糊聚類基本計(jì)算步驟為：

（1）將樣本集中的n條記錄變換成n x n的模糊相似矩陣；

（2）通過傳遞包卷積計(jì)算將模糊相似矩陣變換成等價(jià)相似矩陣；（3）最后通過λ截矩陣將n條記錄分成1-n個(gè)分類。

K-means聚類需事先確定聚類數(shù)k，而模糊聚類Fuzzy Clustering無需事先確定聚類數(shù)k，可以從最小的k=1（所有學(xué)習(xí)集中的n條記錄為1個(gè)分類），到k=n（所有學(xué)習(xí)集中的n條記錄各為1個(gè)分類）。

解決問題：將n條記錄聚成1-n個(gè)分類。模糊聚類Fuzzy Clustering算法完全基于數(shù)據(jù)自然狀況進(jìn)行聚類，可產(chǎn)生聚類的解集合 max{

(k=1,2，，,n)，因此，可以在解集合中求解最優(yōu)聚類 }，這對(duì)觀察分析樣本集的數(shù)據(jù)性態(tài)非常有用，可供觀察不同情況下的“聚類”狀況。

6、SOM神經(jīng)元網(wǎng)絡(luò)聚類

算法概述：人類對(duì)事物的認(rèn)知是一個(gè)不斷積累的過程，通過對(duì)事物的觀察，不斷地認(rèn)識(shí)和修正因果關(guān)系，最后逐漸穩(wěn)定為認(rèn)知規(guī)則。醫(yī)學(xué)證明，人眼的視網(wǎng)膜、脊髓和海馬中存一種側(cè)抑制現(xiàn)象，即，當(dāng)一個(gè)神經(jīng)細(xì)胞興奮后，會(huì)對(duì)其周圍的神經(jīng)細(xì)胞產(chǎn)生抑制作用。這種側(cè)抑制使神經(jīng)細(xì)胞之間呈現(xiàn)出競(jìng)爭(zhēng)，開始時(shí)可能多個(gè)細(xì)胞同時(shí)興奮，但一個(gè)興奮程度最強(qiáng)的神經(jīng)細(xì)胞對(duì)周圍神經(jīng)細(xì)胞的抑制作用也最強(qiáng)，其結(jié)果使其周圍神經(jīng)細(xì)胞興奮程度減弱，從而該神經(jīng)細(xì)胞是這次競(jìng)爭(zhēng)的“勝者”，其它神經(jīng)細(xì)胞在競(jìng)爭(zhēng)中失敗。1981年芬蘭學(xué)者kohonen提出一個(gè)稱為自組織特征映射（Self Organization Feature Map-SOM或SOFM）網(wǎng)絡(luò)，前述大腦神經(jīng)細(xì)胞興奮規(guī)律等，在該網(wǎng)絡(luò)中都得到了反應(yīng)。在競(jìng)爭(zhēng)層神經(jīng)元之間的連線，它們是模擬生物神經(jīng)網(wǎng)絡(luò)層內(nèi)神經(jīng)元相互抑制現(xiàn)象的權(quán)值，這類抑制性權(quán)值滿足一定的分布關(guān)系，如距離近的抑制強(qiáng)，距離遠(yuǎn)的抑制弱。

通過上述可知，SOM聚類算法設(shè)計(jì)的核心思想是體現(xiàn)神經(jīng)元在認(rèn)知過程中的3個(gè)特性：（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)元最遠(yuǎn)距離，來體現(xiàn)上述特性“2”、“3”。

解決問題：將n條記錄按m個(gè)輸出神經(jīng)元聚成m個(gè)分類。模仿人類的學(xué)習(xí)方法，對(duì)事物的認(rèn)識(shí)是一個(gè)由淺入深、逐步學(xué)習(xí)、修正的過程，將對(duì)各種要素組態(tài)的認(rèn)識(shí)逐步穩(wěn)定到認(rèn)知領(lǐng)域，由此進(jìn)行“聚類”。

7、基于Meaning的文本相似度計(jì)算 算法概述：給出一組n個(gè)文檔D{具有代表性的詞組

}，BIC為每個(gè)文檔計(jì)算出一組最，同時(shí)，計(jì)算出

相互間內(nèi)容接近度及接近序列。

BIC的Meaning挖掘與自動(dòng)搜索不同于現(xiàn)有Baidu、Google人工輸入關(guān)鍵詞的搜索方式，現(xiàn)有搜索引擎不考慮語義和語境，只考慮詞W與文檔D的包含關(guān)系

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

在句子中語序關(guān)系的發(fā)生概率與馬爾科夫鏈，因此，能夠更好地確定搜索詞的語義和語境，通過對(duì)文檔間的相關(guān)性（接近度）進(jìn)行聚類計(jì)算，可按Meaning“接近度”進(jìn)行自動(dòng)搜索而無需人工干預(yù)，并隨文檔內(nèi)容的變化而自動(dòng)跟蹤Meaning變化，使搜索更加準(zhǔn)確、更加自動(dòng)化，讓搜索“隨用戶的心而動(dòng)”。

BIC可用于基于Meaning計(jì)算的搜索、輿情分析、特定情報(bào)分析、垂直搜索和相似內(nèi)容推薦等文本挖掘。

解決問題：計(jì)算兩個(gè)文本的相似度。

8、文本模糊聚類計(jì)算

算法概述：基于模糊聚類算法，BIC首先計(jì)算將n個(gè)文本組成相似矩陣檔對(duì)第j個(gè)文本文檔的相似度），然后將相似矩陣似矩陣

變成模糊相似矩陣

（第i個(gè)文本文，通過求模糊相 的等價(jià)矩陣和截矩陣，將n個(gè)文本文檔分成1-n個(gè)分類，同時(shí)，按相同分類中的}，不同文本分類間具有最大差異Max{

}，來求解文本具有最接近的內(nèi)容相似度Min{ 按文本內(nèi)容進(jìn)行最優(yōu)分類方案。

解決問題：在不確定將文本劃分成幾類的情況下，將n個(gè)文本聚成1-n個(gè)分類，以此來觀察“聚類”效果。

9、文本k-means聚類

算法概述：基于k-means聚類，在BIC平臺(tái)上，用戶上傳或輸入n個(gè)文本，確定希望分類數(shù)量k和k個(gè)分類樣本，BIC將以k個(gè)樣本作為初始迭代點(diǎn)進(jìn)行k-means聚類計(jì)算，將n個(gè)文本分成k個(gè)分類。

解決問題：在已經(jīng)確定了k個(gè)分類的情況下，將文本劃分到k個(gè)“分類”中。

10、文本分類

算法概述：通過“文本模糊聚類”或“文本k-means”聚類，BIC不僅將n個(gè)文本按內(nèi)容相似度進(jìn)行分類，同時(shí)挖掘出各個(gè)分類的“分類代表詞組”，以后，用戶任意給出一個(gè)文本，BIC將根據(jù)其對(duì)各個(gè)“分類代表詞組”的相似度，選擇最相似的分類MaxSim{i}，將該待分類文檔分配到MaxSim{i}類。

解決問題：在已經(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)系。給定一組交易記錄：

每筆交易ID包含m個(gè)商品{BIC可計(jì)算得出任意兩商品

}，n條記錄組成二維表，構(gòu)成 矩陣，組合的Confidence(A->B)=P(A | B)置信度和支持度Support(A->B)=P(A U B)，可用于分析商品之間的關(guān)聯(lián)性“購物籃”問題。

BIC的關(guān)聯(lián)模式發(fā)現(xiàn)是一個(gè)快速、交互式Apriore計(jì)算過程：從發(fā)現(xiàn)最基本的2個(gè)Item關(guān)聯(lián)高頻項(xiàng)集開始，計(jì)算支持度Support(A->B)=P(A U B)和置信度Confidence(A->B)=P(A | B)，逐步計(jì)算和發(fā)現(xiàn)2、3、4…Item關(guān)聯(lián)頻繁項(xiàng)集。因?yàn)椋海?）任何求解高頻關(guān)聯(lián)事務(wù)T中的項(xiàng)數(shù)Item必然大于等于2，如果只有1個(gè)Item不存在關(guān)聯(lián)；

（2）任何交易記錄T中無論有多少個(gè)Item組合，如果存在大于2個(gè)Item的高頻組合，都必然存在2關(guān)聯(lián)的高頻真子集。

如：交易記錄T1={Item1，Item2}，交易記錄T2={Item1，Item3，Item4，Item2}，則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就是通過最基本的2關(guān)聯(lián)高頻項(xiàng)集發(fā)現(xiàn)開始，逐步縮小記錄集合，逐步發(fā)現(xiàn)所有任意數(shù)量Item組合的高頻項(xiàng)集。因此，BIC的關(guān)聯(lián)計(jì)算是一個(gè)快速、交互式計(jì)算的Apriore算法。

解決問題：從樣本集中發(fā)現(xiàn)有較強(qiáng)“置信度”的關(guān)聯(lián)規(guī)則。

12、序列模式發(fā)現(xiàn)

算法概述：算法原理同“關(guān)聯(lián)分析”，但統(tǒng)計(jì)點(diǎn)在于事物（或商品購買）發(fā)生的先后序列。如商品購買行為預(yù)測(cè)：汽車改裝愛好者，購買某種品牌增壓器的人，很多人后來還購買了活塞環(huán)、又購買了某品牌機(jī)油…，通過序列分析，發(fā)現(xiàn)其購買序列、預(yù)測(cè)下一步購買行為； 如疾病診斷：患有某種疾病的人，先出現(xiàn)A癥狀、后出現(xiàn)B癥狀、又出現(xiàn)C癥狀…，通過出現(xiàn)癥狀的序列分析，發(fā)現(xiàn)疾病發(fā)生、發(fā)展的序列模式，對(duì)疾病進(jìn)行診斷；

如Web訪問行為模式發(fā)現(xiàn)：每個(gè)IP訪問網(wǎng)站都是一個(gè)Web會(huì)話Session，每個(gè)Session由一系列的URL序列組成，通過Session計(jì)統(tǒng)計(jì)得到高頻URL序列，預(yù)測(cè)用戶的訪問行為； 不限于上述例子，還包括生物進(jìn)化序列模式、DNA序列、地震、火災(zāi)、戰(zhàn)爭(zhēng)沖突爆發(fā)序列模式預(yù)測(cè)等，序列規(guī)律是大量存在的，只要有足夠的統(tǒng)計(jì)數(shù)據(jù)，都可以通過BIC發(fā)現(xiàn)最率并進(jìn)行預(yù)測(cè)。

序列模式發(fā)現(xiàn)與關(guān)聯(lián)模式發(fā)現(xiàn)在算法上很相似，但序列模式強(qiáng)調(diào)Item的先后順序，而關(guān)聯(lián)模式發(fā)現(xiàn)不關(guān)心順序，只看是否在一個(gè)事物T中2個(gè)Item（或多個(gè)）是否同時(shí)出現(xiàn)。

BIC的序列模式發(fā)現(xiàn)是一個(gè)快速、交互式Apriore計(jì)算過程：從發(fā)現(xiàn)2個(gè)Item序列高頻序列開始，計(jì)置信度Confidence(A->B)=P(A | B)，逐步計(jì)算和發(fā)現(xiàn)2、3、4…Item序列頻繁序列。因?yàn)椋海?）任何求解高頻序列事務(wù)T中的項(xiàng)數(shù)Item必然大于等于2，如果只有1個(gè)Item不存在關(guān)聯(lián)；

（2）任何事務(wù)記錄T中無論有多少個(gè)Item序列組合，如果存在大于2個(gè)Item的高頻序列組合，都必然存在2序列的高頻序列真子集。

如：事務(wù)序列記錄T1={Item1，Item2}，事務(wù)序列記錄T2={Item1，Item3，Item4，Item2}，則T1為T2的非空真子集T1?T2。

所以，如果存在3個(gè)Item序列的高頻Item組合，必然存在2序列的高頻序列組合，如果存在4個(gè)Item的高頻序列組合，必然存在3高頻序列組合…。BIC就是通過最基本的2序列高頻序列發(fā)現(xiàn)開始，逐步縮小記錄集合，逐步發(fā)現(xiàn)所有任意數(shù)量Item組合的高頻序列組合。因此，BIC的序列計(jì)算是一個(gè)*快速、交互式計(jì)算的Apriore算法。

解決問題：序列模式發(fā)現(xiàn)的目的是挖掘事務(wù)發(fā)生、發(fā)展的序列(Sequencing)模式，從樣本集發(fā)現(xiàn)有較強(qiáng)“置信度”的序列規(guī)則。

13、PCA主成分分析

算法概述：假設(shè)一個(gè)事物由多種因素構(gòu)成，設(shè)有n個(gè)樣本，每個(gè)樣本共有m個(gè)屬性（指標(biāo)、構(gòu)成要素），構(gòu)成一個(gè)n×m階的成分?jǐn)?shù)據(jù)矩陣，PCA算法的目的是：（1）降低維度

當(dāng)矩陣X的維數(shù)m較大時(shí)，在m維空間中考察問題比較麻煩，需要降低維度，在不影響對(duì)事物評(píng)價(jià)的基礎(chǔ)上，選擇較少的幾個(gè)主要指標(biāo)P（p < m）來代替原來較多的變量指標(biāo)m。（2）消除變量間的相關(guān)性

（3）分析指標(biāo)體系中各個(gè)指標(biāo)的對(duì)事物的區(qū)分性。衡量一個(gè)事物好壞由多個(gè)指標(biāo)所決定，但指標(biāo)對(duì)事物的區(qū)分性有強(qiáng)弱之分，通過PCA計(jì)算，可以分析哪些指標(biāo)有更好的區(qū)分性，哪些指標(biāo)的區(qū)分性較弱。PCA解決算法原理： PCA算法的核心是，將非實(shí)對(duì)稱矩陣X變成實(shí)對(duì)稱矩陣A，求矩陣A的特征值和特征向量，特征值為P個(gè)指標(biāo)，特征向量為P個(gè)指標(biāo)對(duì)原來m個(gè)指標(biāo)的荷載參數(shù)。BIC采用Jacobi（雅可比）方法來求特征值和特征向量。

Jacobi方法的基本理論是，對(duì)于一實(shí)對(duì)稱矩陣A，必有一正交矩陣U，使得 可以證明，如果

，則矩陣D為矩陣A的相似矩陣，相似矩陣具有相同的特征

，變換過程中，讓值和特征向量。Jacobi方法通過平一系列的面旋轉(zhuǎn)變換來求非對(duì)角線上的元素逐步變小，對(duì)角線上的元素逐漸變大，最后將矩陣D中非對(duì)角線上的元素變成0（或趨近于0），對(duì)角線上的元素 li 是矩陣 A 的特征值，正交陣 U 的第 j 列是 A 的屬于 li 的特征向量，以此求解矩陣A的特征值和特征向量。解決問題：

PCA可廣泛用于事物要素（指標(biāo)）分析。任何一個(gè)事物都是由多個(gè)指標(biāo)組成，包括商業(yè)行為、醫(yī)學(xué)診斷、藥理分析、生產(chǎn)質(zhì)量控制、生產(chǎn)工藝設(shè)計(jì)、經(jīng)濟(jì)分析，甚至是軍事、外交事物等。人們需要掌握，構(gòu)成事物的要素（指標(biāo)）與事物的結(jié)果是什么關(guān)系？哪些是主要指標(biāo)？哪些是次要指標(biāo)？指標(biāo)和指標(biāo)之間存在什么關(guān)系？PCA通過一組樣本集的計(jì)算分析，就可以精確回答這些問題。

第二篇：文本挖掘算法總結(jié)

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

P(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的一個(gè)劃分，將n條記錄劃分成k個(gè)記錄集合，如果以P(Di)表示事件Di發(fā)生的概率，且P(Di)> 0(i=1，2，…，k)。對(duì)于任一事件x，P(x)>0，則有：

貝葉斯分類的基本原理，就是利用貝葉斯條件概率公式，將事件X視為多個(gè)條件屬性Cj各種取值的組合，當(dāng)x事件發(fā)生時(shí)決策屬性Di發(fā)生的條件概率。貝葉斯分類是一種概率型分類知識(shí)挖掘方法，不能百分之百地確定X事件發(fā)生時(shí)Di一定發(fā)生。

解決問題：預(yù)測(cè)所屬分類的概率。通過已知n條樣本集記錄，計(jì)算各種條件屬性組發(fā)生的概率，得出“貝葉斯分類”規(guī)則，給定一個(gè)未知“標(biāo)簽”記錄，選擇最大概率為其所屬“分類”。

2、ID3 決策樹分類 算法概述：ID3算法是J.Ross Quinlan在1975提出的分類算法，當(dāng)時(shí)還沒有“數(shù)據(jù)挖掘”的概念。該算法以信息論為基礎(chǔ)，以信息熵和信息增益度來確定分枝生成決策樹D-Tree。ID3算法以決策樹D-Tree構(gòu)建分類知識(shí)模型，D-Tree中最上面的節(jié)點(diǎn)為根節(jié)點(diǎn)Root，每個(gè)分支是一個(gè)新的決策節(jié)點(diǎn)，或者是樹的葉子。每個(gè)決策節(jié)點(diǎn)代表一個(gè)問題或決策，每一個(gè)葉子節(jié)點(diǎn)代表一種可能的分類結(jié)果，沿決策樹在每個(gè)節(jié)點(diǎn)都會(huì)遇到一個(gè)測(cè)試，對(duì)每個(gè)節(jié)點(diǎn)上問題的不同取值導(dǎo)致不同的分支，最后會(huì)到達(dá)一個(gè)葉子節(jié)點(diǎn)為確定所屬分類。

解決問題：預(yù)測(cè)所屬分類。通過已知樣本集記錄，生成一顆“分類知識(shí)樹”，給定一個(gè)未知“標(biāo)簽”記錄，通過“分類知識(shí)樹”來確定其所屬分類。

3、基于粗糙集理論Rough Set的確定型知識(shí)挖掘 算法概述：1982年波蘭學(xué)者Z.Paw lak 提出了粗糙集理論Rough Sets Theory，它是一種刻劃不完整性和不確定性的數(shù)學(xué)工具，能有效分析不精確、不一致（Inconsistent)、不完整（Incomplete)等各種不完備信息，利用數(shù)據(jù)進(jìn)行分析和推理，從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。粗糙集理論是繼概率論、模糊集、證據(jù)理論之后的又一個(gè)處理不確定性事物的數(shù)學(xué)工具。粗糙集理論是建立在分類機(jī)制的基礎(chǔ)上的，它將分類理解為在特定空間上的等價(jià)關(guān)系，而等價(jià)關(guān)系構(gòu)成了對(duì)該空間的劃分。粗糙集理論將知識(shí)理解為對(duì)數(shù)據(jù)的劃分，每一被劃分的集合稱為概念。其主要思想是利用已知的知識(shí)庫，將不精確或不確定的知識(shí)用已知的知識(shí)庫中的知識(shí)來（近似）刻畫。

解決問題：預(yù)測(cè)所屬分類。粗糙集分類將樣本空間S劃分為上近似集（Upper approximation)、下近似集（Lower approximation）、邊界集（Boundary region)，挖掘條件屬性C與決策屬性D集合所包含的不可分記錄（不能再細(xì)分，該集合中的所有記錄都屬于某一決策屬性Di的取值），這些記錄形成不可辨識(shí)的關(guān)系（Indiscernibility relation)，由此確定分類規(guī)則：

IF <條件屬性C成立> THEN <決策屬性Di發(fā)生> 即，如果滿條件C，則其所屬分類為Di。IF中的條件C可以是單一條件，也可以是組合and（并且）組合條件。

BIC給出的是“最小分類規(guī)則”。所謂“最小分類規(guī)則”是，最少的條件組合。例如一個(gè)人屬于“高”、“富”、“帥”，條件為：“身高”、“財(cái)富”、“工資性收入”、“財(cái)產(chǎn)性收入”、“產(chǎn)業(yè)收入”、“臉型”、“眼睛大小”、“鼻梁形狀”、“英俊”等條件來判別，通過“粗糙集”分類計(jì)算，得出最小分類規(guī)則可能是 “IF 財(cái)富>=XXX1 and 身高>=185cm and 相貌=英俊” 其他條件可以忽略不計(jì)，這就是“最小分類規(guī)則”。

“粗糙集”分類規(guī)則為“百分之百確定型”分類規(guī)則，這是對(duì)樣本集的統(tǒng)計(jì)結(jié)果，如果出現(xiàn)非“樣本集”中出現(xiàn)過的條件變量屬性，將無法得出“粗糙集”，可轉(zhuǎn)而使用概率型“貝葉斯分類”進(jìn)行計(jì)算。

4、基于k-means聚類 算法概述：給定一個(gè)包括n條記錄、每條記錄有m個(gè)屬性 的樣本集，再給出分類數(shù)k，要求將樣本集中的記錄，按記錄間的相似性大小（或距離遠(yuǎn)近），將相似性最大（或距離最近）的記錄劃分到k個(gè)類中，相同分類中記錄間的距離要盡可能地小，而分類之間的距離要盡可能地大。

BIC改進(jìn)了常規(guī)的k-means聚類算法，在聚類過程中，同時(shí)計(jì)算分類質(zhì)量（類內(nèi)均差、類間均距?和），并求解最優(yōu)聚類max{?}。

解決問題：將n條記錄聚成k個(gè)分類。對(duì)n個(gè)樣本集記錄，指定分類個(gè)數(shù)k，為k個(gè)分類指定初始迭代記錄為k個(gè)分類中心，通過計(jì)算其他記錄對(duì)k個(gè)分類中心的距離，對(duì)不斷變換分類、變換類中心，收斂都當(dāng)分類不再變化時(shí)，計(jì)算結(jié)束。由此，將n個(gè)樣本集記錄分配到k個(gè)分類中，得到k個(gè)分類中心指標(biāo)。

5、無限細(xì)分的模糊聚類Fuzzy Clustering 算法概述：在實(shí)際解決聚類問題時(shí)，很多數(shù)事物是“模糊”的，其特征屬性A無法確進(jìn)行量化，如：人的相貌、人與人之間的關(guān)系、人的性格、購買商品的意愿等，這就需要用模糊數(shù)學(xué)來進(jìn)行相似性計(jì)算。模糊數(shù)學(xué)是伴隨著上世紀(jì)五六十年代興起的控制論、信息論、系統(tǒng)論（俗稱“老三論”）而形成的一種決策方法，是美國加利福尼亞大學(xué)伯克利分校Lotfi Zadeh教授于1965年創(chuàng)立的。

模糊聚類基本計(jì)算步驟為：

（1）將樣本集中的n條記錄變換成n x n的模糊相似矩陣；

（2）通過傳遞包卷積計(jì)算將模糊相似矩陣變換成等價(jià)相似矩陣；

（3）最后通過λ截矩陣將n條記錄分成1-n個(gè)分類。

K-means聚類需事先確定聚類數(shù)k，而模糊聚類Fuzzy Clustering無需事先確定聚類數(shù)k，可以從最小的k=1（所有學(xué)習(xí)集中的n條記錄為1個(gè)分類），到k=n（所有學(xué)習(xí)集中的n條記錄各為1個(gè)分類）。

解決問題：將n條記錄聚成1-n個(gè)分類。模糊聚類Fuzzy Clustering算法完全基于數(shù)據(jù)自然狀況進(jìn)行聚類，可產(chǎn)生聚類的解集合(k=1,2，，,n)，因此，可以在解集合中求解最優(yōu)聚類max{??}，這對(duì)觀察分析樣本集的數(shù)據(jù)性態(tài)非常有用，可供觀察不同情況下的“聚類”狀況。

6、SOM神經(jīng)元網(wǎng)絡(luò)聚類 算法概述：人類對(duì)事物的認(rèn)知是一個(gè)不斷積累的過程，通過對(duì)事物的觀察，不斷地認(rèn)識(shí)和修正因果關(guān)系，最后逐漸穩(wěn)定為認(rèn)知規(guī)則。醫(yī)學(xué)證明，人眼的視網(wǎng)膜、脊髓和海馬中存一種側(cè)抑制現(xiàn)象，即，當(dāng)一個(gè)神經(jīng)細(xì)胞興奮后，會(huì)對(duì)其周圍的神經(jīng)細(xì)胞產(chǎn)生抑制作用。這種側(cè)抑制使神經(jīng)細(xì)胞之間呈現(xiàn)出競(jìng)爭(zhēng)，開始時(shí)可能多個(gè)細(xì)胞同時(shí)興奮，但一個(gè)興奮程度最強(qiáng)的神經(jīng)細(xì)胞對(duì)周圍神經(jīng)細(xì)胞的抑制作用也最強(qiáng)，其結(jié)果使其周圍神經(jīng)細(xì)胞興奮程度減弱，從而該神經(jīng)細(xì)胞是這次競(jìng)爭(zhēng)的“勝者”，其它神經(jīng)細(xì)胞在競(jìng)爭(zhēng)中失敗。

1981年芬蘭學(xué)者kohonen提出一個(gè)稱為自組織特征映射（Self Organization Feature Map-SOM或SOFM）網(wǎng)絡(luò)，前述大腦神經(jīng)細(xì)胞興奮規(guī)律等，在該網(wǎng)絡(luò)中都得到了反應(yīng)。在競(jìng)爭(zhēng)層神經(jīng)元之間的連線，它們是模擬生物神經(jīng)網(wǎng)絡(luò)層內(nèi)神經(jīng)元相互抑制現(xiàn)象的權(quán)值，這類抑制性權(quán)值滿足一定的分布關(guān)系，如距離近的抑制強(qiáng)，距離遠(yuǎn)的抑制弱。

通過上述可知，SOM聚類算法設(shè)計(jì)的核心思想是體現(xiàn)神經(jīng)元在認(rèn)知過程中的3個(gè)特性：

（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)元最遠(yuǎn)距離，來體現(xiàn)上述特性“2”、“3”。

解決問題：將n條記錄按m個(gè)輸出神經(jīng)元聚成m個(gè)分類。模仿人類的學(xué)習(xí)方法，對(duì)事物的認(rèn)識(shí)是一個(gè)由淺入深、逐步學(xué)習(xí)、修正的過程，將對(duì)各種要素組態(tài)的認(rèn)識(shí)逐步穩(wěn)定到認(rèn)知領(lǐng)域，由此進(jìn)行“聚類”。

7、基于Meaning的文本相似度計(jì)算 算法概述：給出一組n個(gè)文檔D{?}，BIC為每個(gè)文檔計(jì)算出一組最具有代表性的詞組，同時(shí)，計(jì)算出相互間內(nèi)容接近度及接近序列。

BIC的Meaning挖掘與自動(dòng)搜索不同于現(xiàn)有Baidu、Google人工輸入關(guān)鍵詞的搜索方式，現(xiàn)有搜索引擎不考慮語義和語境，只考慮詞W與文檔D的包含關(guān)系?和詞在文檔內(nèi)的頻數(shù)TF，因此，關(guān)鍵詞的搜索與文檔內(nèi)容無關(guān)。

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

BIC通過計(jì)算得出文檔代表詞組，相當(dāng)于人工輸入 {“姚明”、“得分”、“籃板”}，同時(shí)計(jì)算詞?在句子中語序關(guān)系的發(fā)生概率與馬爾科夫鏈，因此，能夠更好地確定搜索詞的語義和語境，通過對(duì)文檔間的相關(guān)性（接近度）進(jìn)行聚類計(jì)算，可按Meaning“接近度”進(jìn)行自動(dòng)搜索而無需人工干預(yù)，并隨文檔內(nèi)容的變化而自動(dòng)跟蹤Meaning變化，使搜索更加準(zhǔn)確、更加自動(dòng)化，讓搜索“隨用戶的心而動(dòng)”。

BIC可用于基于Meaning計(jì)算的搜索、輿情分析、特定情報(bào)分析、垂直搜索和相似內(nèi)容推薦等文本挖掘。

解決問題：計(jì)算兩個(gè)文本的相似度。

8、文本模糊聚類計(jì)算 算法概述：基于模糊聚類算法，BIC首先計(jì)算將n個(gè)文本組成相似矩陣（第i個(gè)文本文檔對(duì)第j個(gè)文本文檔的相似度），然后將相似矩陣?變成模糊相似矩陣，通過求模糊相似矩陣?的等價(jià)矩陣和截矩陣，將n個(gè)文本文檔分成1-n個(gè)分類，同時(shí)，按相同分類中的文本具有最接近的內(nèi)容相似度Min{?}，不同文本分類間具有最大差異Max{?}，來求解按文本內(nèi)容進(jìn)行最優(yōu)分類方案。

解決問題：在不確定將文本劃分成幾類的情況下，將n個(gè)文本聚成1-n個(gè)分類，以此來觀察“聚類”效果。

9、文本k-means聚類 算法概述：基于k-means聚類，在BIC平臺(tái)上，用戶上傳或輸入n個(gè)文本，確定希望分類數(shù)量k和k個(gè)分類樣本，BIC將以k個(gè)樣本作為初始迭代點(diǎn)進(jìn)行k-means聚類計(jì)算，將n個(gè)文本分成k個(gè)分類。

解決問題：在已經(jīng)確定了k個(gè)分類的情況下，將文本劃分到k個(gè)“分類”中。

10、文本分類 算法概述：通過“文本模糊聚類”或“文本k-means”聚類，BIC不僅將n個(gè)文本按內(nèi)容相似度進(jìn)行分類，同時(shí)挖掘出各個(gè)分類的“分類代表詞組”，以后，用戶任意給出一個(gè)文本，BIC將根據(jù)其對(duì)各個(gè)“分類代表詞組”的相似度，選擇最相似的分類MaxSim{i}，將該待分類文檔分配到MaxSim{i}類。

解決問題：在已經(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)系。

給定一組交易記錄：

每筆交易ID包含m個(gè)商品{}，n條記錄組成二維表，構(gòu)成 矩陣，BIC可計(jì)算得出任意兩商品?組合的Confidence(A->B)=P(A | B)置信度和支持度Support(A->B)=P(A U B)，可用于分析商品之間的關(guān)聯(lián)性“購物籃”問題。

BIC的關(guān)聯(lián)模式發(fā)現(xiàn)是一個(gè)快速、交互式Apriore計(jì)算過程：從發(fā)現(xiàn)最基本的2個(gè)Item關(guān)聯(lián)高頻項(xiàng)集開始，計(jì)算支持度Support(A->B)=P(A U B)和置信度Confidence(A->B)=P(A | B)，逐步計(jì)算和發(fā)現(xiàn)2、3、4 …Item關(guān)聯(lián)頻繁項(xiàng)集。

因?yàn)椋?/p>

（1）任何求解高頻關(guān)聯(lián)事務(wù)T中的項(xiàng)數(shù)Item必然大于等于2，如果只有1個(gè)Item不存在關(guān)聯(lián)；

（2）任何交易記錄T中無論有多少個(gè)Item組合，如果存在大于2個(gè)Item的高頻組合，都必然存在2關(guān)聯(lián)的高頻真子集。

如：交易記錄T1={Item1，Item2}，交易記錄T2={Item1，Item3，Item4，Item2}，則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就是通過最基本的2關(guān)聯(lián)高頻項(xiàng)集發(fā)現(xiàn)開始，逐步縮小記錄集合，逐步發(fā)現(xiàn)所有任意數(shù)量Item組合的高頻項(xiàng)集。因此，BIC的關(guān)聯(lián)計(jì)算是一個(gè)快速、交互式計(jì)算的Apriore算法。

解決問題：從樣本集中發(fā)現(xiàn)有較強(qiáng)“置信度”的關(guān)聯(lián)規(guī)則。

12、序列模式發(fā)現(xiàn) 算法概述：算法原理同“關(guān)聯(lián)分析”，但統(tǒng)計(jì)點(diǎn)在于事物（或商品購買）發(fā)生的先后序列。

如商品購買行為預(yù)測(cè)：汽車改裝愛好者，購買某種品牌增壓器的人，很多人后來還購買了活塞環(huán)、又購買了某品牌機(jī)油…，通過序列分析，發(fā)現(xiàn)其購買序列、預(yù)測(cè)下一步購買行為；

如疾病診斷：患有某種疾病的人，先出現(xiàn)A癥狀、后出現(xiàn)B癥狀、又出現(xiàn)C癥狀…，通過出現(xiàn)癥狀的序列分析，發(fā)現(xiàn)疾病發(fā)生、發(fā)展的序列模式，對(duì)疾病進(jìn)行診斷；

如Web訪問行為模式發(fā)現(xiàn)：每個(gè)IP訪問網(wǎng)站都是一個(gè)Web會(huì)話Session，每個(gè)Session由一系列的URL序列組成，通過Session計(jì)統(tǒng)計(jì)得到高頻URL序列，預(yù)測(cè)用戶的訪問行為；

不限于上述例子，還包括生物進(jìn)化序列模式、DNA序列、地震、火災(zāi)、戰(zhàn)爭(zhēng)沖突爆發(fā)序列模式預(yù)測(cè)等，序列規(guī)律是大量存在的，只要有足夠的統(tǒng)計(jì)數(shù)據(jù)，都可以通過BIC發(fā)現(xiàn)最率并進(jìn)行預(yù)測(cè)。

序列模式發(fā)現(xiàn)與關(guān)聯(lián)模式發(fā)現(xiàn)在算法上很相似，但序列模式強(qiáng)調(diào)Item的先后順序，而關(guān)聯(lián)模式發(fā)現(xiàn)不關(guān)心順序，只看是否在一個(gè)事物T中2個(gè)Item（或多個(gè)）是否同時(shí)出現(xiàn)。

BIC的序列模式發(fā)現(xiàn)是一個(gè)快速、交互式Apriore計(jì)算過程：從發(fā)現(xiàn)2個(gè)Item序列高頻序列開始，計(jì)置信度Confidence(A->B)=P(A | B)，逐步計(jì)算和發(fā)現(xiàn)2、3、4…Item序列頻繁序列。

因?yàn)椋?/p>

（1）任何求解高頻序列事務(wù)T中的項(xiàng)數(shù)Item必然大于等于2，如果只有1個(gè)Item不存在關(guān)聯(lián)；

（2）任何事務(wù)記錄T中無論有多少個(gè)Item序列組合，如果存在大于2個(gè)Item的高頻序列組合，都必然存在2序列的高頻序列真子集。

如：事務(wù)序列記錄T1={Item1，Item2}，事務(wù)序列記錄T2={Item1，Item3，Item4，Item2}，則T1為T2的非空真子集T1?T2。

所以，如果存在3個(gè)Item序列的高頻Item組合，必然存在2序列的高頻序列組合，如果存在4個(gè)Item的高頻序列組合，必然存在3高頻序列組合…。BIC就是通過最基本的2序列高頻序列發(fā)現(xiàn)開始，逐步縮小記錄集合，逐步發(fā)現(xiàn)所有任意數(shù)量Item組合的高頻序列組合。因此，BIC的序列計(jì)算是一個(gè)*快速、交互式計(jì)算的Apriore算法。

解決問題：序列模式發(fā)現(xiàn)的目的是挖掘事務(wù)發(fā)生、發(fā)展的序列(Sequencing)模式，從樣本集發(fā)現(xiàn)有較強(qiáng)“置信度”的序列規(guī)則。

13、PCA主成分分析 算法概述：假設(shè)一個(gè)事物由多種因素構(gòu)成，設(shè)有n個(gè)樣本，每個(gè)樣本共有m個(gè)屬性（指標(biāo)、構(gòu)成要素），構(gòu)成一個(gè)n×m階的成分?jǐn)?shù)據(jù)矩陣，PCA算法的目的是：

（1）降低維度 當(dāng)矩陣X的維數(shù)m較大時(shí)，在m維空間中考察問題比較麻煩，需要降低維度，在不影響對(duì)事物評(píng)價(jià)的基礎(chǔ)上，選擇較少的幾個(gè)主要指標(biāo)P（p < m）來代替原來較多的變量指標(biāo)m。

（2）消除變量間的相關(guān)性（3）分析指標(biāo)體系中各個(gè)指標(biāo)的對(duì)事物的區(qū)分性。衡量一個(gè)事物好壞由多個(gè)指標(biāo)所決定，但指標(biāo)對(duì)事物的區(qū)分性有強(qiáng)弱之分，通過PCA計(jì)算，可以分析哪些指標(biāo)有更好的區(qū)分性，哪些指標(biāo)的區(qū)分性較弱。

PCA解決算法原理：

PCA算法的核心是，將非實(shí)對(duì)稱矩陣X變成實(shí)對(duì)稱矩陣A，求矩陣A的特征值和特征向量，特征值為P個(gè)指標(biāo)，特征向量為P個(gè)指標(biāo)對(duì)原來m個(gè)指標(biāo)的荷載參數(shù)。BIC采用Jacobi（雅可比）方法來求特征值和特征向量。

Jacobi方法的基本理論是，對(duì)于一實(shí)對(duì)稱矩陣A，必有一正交矩陣U，使得，可以證明，如果，則矩陣D為矩陣A的相似矩陣，相似矩陣具有相同的特征值和特征向量。Jacobi方法通過平一系列的面旋轉(zhuǎn)變換來求，變換過程中，讓非對(duì)角線上的元素逐步變小，對(duì)角線上的元素逐漸變大，最后將矩陣D中非對(duì)角線上的元素變成0（或趨近于0），對(duì)角線上的元素 li 是矩陣 A 的特征值，正交陣 U 的第 j 列是 A 的屬于 li 的特征向量，以此求解矩陣A的特征值和特征向量。

解決問題：

PCA可廣泛用于事物要素（指標(biāo)）分析。任何一個(gè)事物都是由多個(gè)指標(biāo)組成，包括商業(yè)行為、醫(yī)學(xué)診斷、藥理分析、生產(chǎn)質(zhì)量控制、生產(chǎn)工藝設(shè)計(jì)、經(jīng)濟(jì)分析，甚至是軍事、外交事物等。人們需要掌握，構(gòu)成事物的要素（指標(biāo)）與事物的結(jié)果是什么關(guān)系？哪些是主要指標(biāo)？哪些是次要指標(biāo)？指標(biāo)和指標(biāo)之間存在什么關(guān)系？PCA通過一組樣本集的計(jì)算分析，就可以精確回答這些問題。

第三篇：18大經(jīng)典數(shù)據(jù)挖掘算法小結(jié)

18大經(jīng)典數(shù)據(jù)挖掘算法小結(jié)

2015-03-05 CSDN大數(shù)據(jù) CSDN大數(shù)據(jù)

csdnbigdataCSDN分享Hadoop、Spark、NoSQL/NewSQL、HBase、Impala、內(nèi)存計(jì)算、流計(jì)算、機(jī)器學(xué)習(xí)和智能算法等相關(guān)大數(shù)據(jù)觀點(diǎn)，提供云計(jì)算和大數(shù)據(jù)技術(shù)、平臺(tái)、實(shí)踐和產(chǎn)業(yè)信息等服務(wù)。本文所有涉及到的數(shù)據(jù)挖掘代碼的都放在了github上了。

地址鏈接: https://github.com/linyiqun/DataMiningAlgorithm 大概花了將近2個(gè)月的時(shí)間，自己把18大數(shù)據(jù)挖掘的經(jīng)典算法進(jìn)行了學(xué)習(xí)并且進(jìn)行了代碼實(shí)現(xiàn)，涉及到了決策分類，聚類，鏈接挖掘，關(guān)聯(lián)挖掘，模式挖掘等等方面。也算是對(duì)數(shù)據(jù)挖掘領(lǐng)域的小小入門了吧。下面就做個(gè)小小的總結(jié)，后面都是我自己相應(yīng)算法的博文鏈接，希望能夠幫助大家學(xué)習(xí)。

1.C4.5算法。C4.5算法與ID3算法一樣，都是數(shù)學(xué)分類算法，C4.5算法是ID3算法的一個(gè)改進(jìn)。ID3算法采用信息增益進(jìn)行決策判斷，而C4.5采用的是增益率。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42395865 2.CART算法。CART算法的全稱是分類回歸樹算法，他是一個(gè)二元分類，采用的是類似于熵的基尼指數(shù)作為分類決策，形成決策樹后之后還要進(jìn)行剪枝，我自己在實(shí)現(xiàn)整個(gè)算法的時(shí)候采用的是代價(jià)復(fù)雜度算法，詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42558235 3.KNN(K最近鄰)算法。給定一些已經(jīng)訓(xùn)練好的數(shù)據(jù)，輸入一個(gè)新的測(cè)試數(shù)據(jù)點(diǎn)，計(jì)算包含于此測(cè)試數(shù)據(jù)點(diǎn)的最近的點(diǎn)的分類情況，哪個(gè)分類的類型占多數(shù)，則此測(cè)試點(diǎn)的分類與此相同，所以在這里,有的時(shí)候可以復(fù)制不同的分類點(diǎn)不同的權(quán)重。近的點(diǎn)的權(quán)重大點(diǎn)，遠(yuǎn)的點(diǎn)自然就小點(diǎn)。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42613011 4.Naive Bayes(樸素貝葉斯)算法。樸素貝葉斯算法是貝葉斯算法里面一種比較簡(jiǎn)單的分類算法，用到了一個(gè)比較重要的貝葉斯定理，用一句簡(jiǎn)單的話概括就是條件概率的相互轉(zhuǎn)換推導(dǎo)。詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42680161 5.SVM(支持向量機(jī))算法。支持向量機(jī)算法是一種對(duì)線性和非線性數(shù)據(jù)進(jìn)行分類的方法，非線性數(shù)據(jù)進(jìn)行分類的時(shí)候可以通過核函數(shù)轉(zhuǎn)為線性的情況再處理。其中的一個(gè)關(guān)鍵的步驟是搜索最大邊緣超平面。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42780439 6.EM(期望最大化)算法。期望最大化算法，可以拆分為2個(gè)算法，1個(gè)E-Step期望化步驟,和1個(gè)M-Step最大化步驟。他是一種算法框架，在每次計(jì)算結(jié)果之后，逼近統(tǒng)計(jì)模型參數(shù)的最大似然或最大后驗(yàn)估計(jì)。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42921789 7.Apriori算法。Apriori算法是關(guān)聯(lián)規(guī)則挖掘算法，通過連接和剪枝運(yùn)算挖掘出頻繁項(xiàng)集，然后根據(jù)頻繁項(xiàng)集得到關(guān)聯(lián)規(guī)則，關(guān)聯(lián)規(guī)則的導(dǎo)出需要滿足最小置信度的要求。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43059211 8.FP-Tree(頻繁模式樹)算法。這個(gè)算法也有被稱為FP-growth算法，這個(gè)算法克服了Apriori算法的產(chǎn)生過多侯選集的缺點(diǎn)，通過遞歸的產(chǎn)生頻度模式樹，然后對(duì)樹進(jìn)行挖掘，后面的過程與Apriori算法一致。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43234309 9.PageRank(網(wǎng)頁重要性/排名)算法。PageRank算法最早產(chǎn)生于Google,核心思想是通過網(wǎng)頁的入鏈數(shù)作為一個(gè)網(wǎng)頁好快的判定標(biāo)準(zhǔn)，如果1個(gè)網(wǎng)頁內(nèi)部包含了多個(gè)指向外部的鏈接，則PR值將會(huì)被均分，PageRank算法也會(huì)遭到Link Span攻擊。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43311943 10.HITS算法。HITS算法是另外一個(gè)鏈接算法，部分原理與PageRank算法是比較相似的，HITS算法引入了權(quán)威值和中心值的概念，HITS算法是受用戶查詢條件影響的，他一般用于小規(guī)模的數(shù)據(jù)鏈接分析，也更容易遭受到攻擊。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43311943 11.K-Means(K均值)算法。K-Means算法是聚類算法，k在在這里指的是分類的類型數(shù)，所以在開始設(shè)定的時(shí)候非常關(guān)鍵，算法的原理是首先假定k個(gè)分類點(diǎn)，然后根據(jù)歐式距離計(jì)算分類，然后去同分類的均值作為新的聚簇中心，循環(huán)操作直到收斂。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43373159 12.BIRCH算法。BIRCH算法利用構(gòu)建CF聚類特征樹作為算法的核心，通過樹的形式，BIRCH算法掃描數(shù)據(jù)庫，在內(nèi)存中建立一棵初始的CF-樹，可以看做數(shù)據(jù)的多層壓縮。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43532111 13.AdaBoost算法。AdaBoost算法是一種提升算法，通過對(duì)數(shù)據(jù)的多次訓(xùn)練得到多個(gè)互補(bǔ)的分類器，然后組合多個(gè)分類器，構(gòu)成一個(gè)更加準(zhǔn)確的分類器。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43635115 14.GSP算法。GSP算法是序列模式挖掘算法。GSP算法也是Apriori類算法，在算法的過程中也會(huì)進(jìn)行連接和剪枝操作，不過在剪枝判斷的時(shí)候還加上了一些時(shí)間上的約束等條件。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43699083 15.PreFixSpan算法。PreFixSpan算法是另一個(gè)序列模式挖掘算法，在算法的過程中不會(huì)產(chǎn)生候選集，給定初始前綴模式，不斷的通過后綴模式中的元素轉(zhuǎn)到前綴模式中，而不斷的遞歸挖掘下去。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43766253 16.CBA(基于關(guān)聯(lián)規(guī)則分類)算法。CBA算法是一種集成挖掘算法，因?yàn)樗墙⒃陉P(guān)聯(lián)規(guī)則挖掘算法之上的，在已有的關(guān)聯(lián)規(guī)則理論前提下，做分類判斷，只是在算法的開始時(shí)對(duì)數(shù)據(jù)做處理，變成類似于事務(wù)的形式。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43818787 17.RoughSets(粗糙集)算法。粗糙集理論是一個(gè)比較新穎的數(shù)據(jù)挖掘思想。這里使用的是用粗糙集進(jìn)行屬性約簡(jiǎn)的算法，通過上下近似集的判斷刪除無效的屬性，進(jìn)行規(guī)制的輸出。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43876001 18.gSpan算法。gSpan算法屬于圖挖掘算法領(lǐng)域。，主要用于頻繁子圖的挖掘，相較于其他的圖算法，子圖挖掘算法是他們的一個(gè)前提或基礎(chǔ)算法。gSpan算法用到了DFS編碼，和Edge五元組，最右路徑子圖擴(kuò)展等概念，算法比較的抽象和復(fù)雜。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43924273

第四篇：算法總結(jié)

算法分析與設(shè)計(jì)總結(jié)報(bào)告

71110415 錢玉明

在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學(xué)生，學(xué)習(xí)算法無疑會(huì)增強(qiáng)自己的競(jìng)爭(zhēng)力，修煉自己的“內(nèi)功”。

下面我將談?wù)勎覍?duì)這門課程的心得與體會(huì)。

一、數(shù)學(xué)是算法的基礎(chǔ)

經(jīng)過這門課的學(xué)習(xí)，我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。

①主定理

本門課中它主要應(yīng)用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個(gè)大問題分解為a個(gè)子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級(jí)高于nlogba時(shí)，我們可以設(shè)法降低子問題組合時(shí)的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴(kuò)大問題的規(guī)?；蛘邷p小子問題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。

②隨機(jī)算法中的許多定理的運(yùn)用

在這門課中，我學(xué)到了以前從未遇見過的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過多次的嘗試來降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素?cái)?shù)判定的定理。尤其是對(duì)尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯(cuò)率的計(jì)算，算法性能的評(píng)價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。

這些算法都給予了我很大啟發(fā)，要想學(xué)好算法，學(xué)好數(shù)學(xué)是必不可少的。沒有深厚的數(shù)學(xué)功力作為地基，即使再漂亮的算法框架，代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。

二、算法的核心是思想

我們學(xué)習(xí)這門課不是僅僅掌握那幾個(gè)經(jīng)典算法例子，更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢？舉個(gè)例子。有同學(xué)曾問我這樣一個(gè)問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個(gè)星期?，F(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個(gè)瓶子的水，每個(gè)瓶子可以只喝一點(diǎn)。問如何解決？其實(shí)一開始我也一頭霧水，但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān)，我就立馬有了思路，運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說，我們不僅要學(xué)習(xí)算法，更得學(xué)習(xí)思想方法。

①算法最基本的設(shè)計(jì)方法包括分治法，動(dòng)態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個(gè)元素中最大元和最小元的量級(jí)，降低n位二進(jìn)制x和y相乘的量級(jí)，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨(dú)立的子問題，關(guān)鍵是子問題要與原問題同類，可以采取平衡法來提高性能。

動(dòng)態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復(fù)的，后面的問題可以利用前面解決過的問題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹，解決矩陣連乘時(shí)最小計(jì)算次數(shù)問題，尋找最長公共子序列等等。

貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。

周游法就是簡(jiǎn)單理解就是采取一定的策略遍歷圖中所有的點(diǎn)，典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。

回溯法就是就是在滿足一定的條件后就往前走，當(dāng)走到某步時(shí)，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問題，平面點(diǎn)集的凸包問題和0-1背包問題。

分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問題。

②評(píng)價(jià)算法性能的方法如平攤分析中的聚集法，會(huì)計(jì)法和勢(shì)能法。聚集法就是把指令分為幾類，計(jì)算每一類的消耗，再全部疊加起來。會(huì)計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去，以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢(shì)能法計(jì)算每一步的勢(shì)的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計(jì)。

這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間，盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會(huì)計(jì)法中用什么指令提前計(jì)算什么指令的消耗，勢(shì)能法中如何選取勢(shì)能。因此掌握這些方法原理還不夠，還要學(xué)會(huì)去應(yīng)用，在具體的問題中去判斷分析。

三、算法與應(yīng)用緊密相關(guān)

我認(rèn)為學(xué)習(xí)算法不能局限于書本上的理論運(yùn)算，局限于如何提高性能以降低復(fù)雜度，我們要將它與實(shí)際生活聯(lián)系起來。其實(shí)算法問題的產(chǎn)生就來自于生活，設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長公共子序列算法可以應(yīng)用在生物信息學(xué)中通過檢測(cè)相似DNA片段的相似成分來檢測(cè)生物特性的相似性，也可以用來判斷兩個(gè)字符串的相近性，這可應(yīng)用在數(shù)據(jù)挖掘中。快速傅立葉變換（FFT）可應(yīng)用在計(jì)算多項(xiàng)式相乘上來降低復(fù)雜度，脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法，它對(duì)于解決網(wǎng)絡(luò)流量分配問題起了很大的幫助，等等。

這些應(yīng)用給了我很大的啟發(fā)：因?yàn)閱渭冎v一個(gè)Union-Find算法，即使了解了它的實(shí)現(xiàn)原理，遇到具體的實(shí)際問題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問題結(jié)合起來，不能停留在思想方法階段，要學(xué)以致用，做到具體問題具體分析。

四、對(duì)計(jì)算模型和NP問題的理解

由于對(duì)這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。

首先談到計(jì)算模型，就不得不提到圖靈計(jì)算，他將基本的計(jì)算抽象化，造出一個(gè)圖靈機(jī)，得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問題都是可以計(jì)算的，否則就是不可計(jì)算的。由此引申出一個(gè)著名論題：任何合理的計(jì)算模型都是相互等價(jià)的。它說明了可計(jì)算性本身不依賴于任何具體的模型而客觀存在。

NP問題比較復(fù)雜，我認(rèn)為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個(gè)特殊的性質(zhì)，如果存在一個(gè)NP-C問題找到一個(gè)多項(xiàng)式時(shí)間的解法，則所有的NP-C問題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時(shí)可以找出精確解，但是規(guī)模大時(shí)，就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會(huì)采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法，如漢諾塔問題。

最后談?wù)剬?duì)這門課程的建議

①對(duì)于這門算法課，我認(rèn)為應(yīng)該加強(qiáng)對(duì)算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會(huì)兒，或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制，誰能解決這個(gè)問題，平時(shí)成績加分。這在一定程度上會(huì)將強(qiáng)我們思考分析問題的能力。因?yàn)槲腋杏X到，一個(gè)問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對(duì)問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點(diǎn)名回答問題可以一定程度上有效的防止不認(rèn)真聽課的現(xiàn)象。

②作業(yè)安排的不是很恰當(dāng)。本門課主要安排了三次作業(yè)，個(gè)人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼，沒有太多的技術(shù)含量。而且對(duì)于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因?yàn)檫@間接成為了程序設(shè)計(jì)題，不是算法設(shè)計(jì)題。

③本門課的時(shí)間安排的不太恰當(dāng)，因?yàn)楸緦W(xué)期的課程太多，壓力太大。沒有太多的時(shí)間去學(xué)習(xí)這門課程。因?yàn)槲蚁嘈糯蠹叶紝?duì)它感興趣，比較重視，想花功夫，但苦于沒時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期，那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過，且課程的壓力也不是很大。錯(cuò)開時(shí)間的話，我覺得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。

第五篇：算法總結(jié)

算法分塊總結(jié)

為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過的題目按算法分塊做一個(gè)全面詳細(xì)的總結(jié)，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設(shè)計(jì)中，時(shí)刻都要牢記要減少冗余，要以簡(jiǎn)潔高效為追求目標(biāo)。另外當(dāng)遇到陌生的問題時(shí)，要想方設(shè)法進(jìn)行模型簡(jiǎn)化，轉(zhuǎn)化，轉(zhuǎn)化成我們熟悉的東西。

圖論模型的應(yīng)用

分層圖思想的應(yīng)用：

用此思想可以建立起更簡(jiǎn)潔、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型，進(jìn)而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質(zhì)： 由于層是由復(fù)制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進(jìn)行新層的存儲(chǔ)，甚至幾乎不需要花時(shí)間去處理。由于層之間的相似性，很多計(jì)算結(jié)果都是相同的。所以我們只需對(duì)這些計(jì)算進(jìn)行一次，把結(jié)果存起來，而不需要反復(fù)計(jì)算。如此看來，雖然看起來圖變大了，但實(shí)際上問題的規(guī)模并沒有變大。層之間是拓?fù)溆行虻?。這也就意味著在層之間可以很容易實(shí)現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。

這些特點(diǎn)說明這個(gè)分層圖思想還是很有潛力的，尤其是各層有很多公共計(jì)算結(jié)果這一點(diǎn)，有可能大大消除冗余計(jì)算，進(jìn)而降低算法時(shí)間復(fù)雜度。二分圖最大及完備匹配的應(yīng)用： ZOJ place the robots: 二分圖最優(yōu)匹配的應(yīng)用：

最大網(wǎng)絡(luò)流算法的應(yīng)用：典型應(yīng)用就求圖的最小割。最小費(fèi)用最大流的應(yīng)用：

容量有上下界的最大流的應(yīng)用：

歐拉路以及歐拉回路的應(yīng)用：主要利用求歐拉路的套圈算法。最小生成樹：

求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復(fù)雜度降為O(Vlog2V+E)，后者一般應(yīng)用于稀疏圖，其時(shí)間復(fù)雜度為O(Elog2V)。最小K度限制生成樹：

抽象成數(shù)學(xué)模型就是：

設(shè)G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個(gè)頂點(diǎn),k為給定的一個(gè)正整數(shù)。首先考慮邊界情況。先求出問題有解時(shí)k 的最小值：把v0點(diǎn)從圖中刪去后，圖中可能會(huì)出 現(xiàn)m 個(gè)連通分量，而這m 個(gè)連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當(dāng)k

首先，將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去，此時(shí)的圖可能不再連通，對(duì)各個(gè)連通分量，分別求最小生成樹。接著，對(duì)于每個(gè)連通分量V’，求一點(diǎn)v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個(gè)m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時(shí)間復(fù)雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡(jiǎn)便，把該樹轉(zhuǎn)化成以v0為根的有根樹。

假設(shè)已經(jīng)得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關(guān)聯(lián)的邊后，必定形成一個(gè)環(huán)。若想得到一棵p+1 度限制生成樹，需刪去一條在環(huán)上的且與v0無關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大，則所得到的生成樹的權(quán)值和就越小。動(dòng)態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點(diǎn)，動(dòng)態(tài)轉(zhuǎn)移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

狀態(tài)共|V|個(gè)，狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度O(1)，所以總的時(shí)間復(fù)雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時(shí)間復(fù)雜度為O(V)。1 先求出最小m度限制生成樹；

2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當(dāng)dT(v0)=k時(shí)停止。

加邊和去邊過程，利用動(dòng)態(tài)規(guī)劃優(yōu)化特別值得注意。

次小生成樹：

加邊和去邊很值得注意。

每加入一條不在樹上的邊，總能形成一個(gè)環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權(quán)值越大，新得到的生成樹的權(quán)值和越小。具體做法：

首先做一步預(yù)處理，求出樹上每兩個(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預(yù)處理，我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。如何預(yù)處理呢？因?yàn)檫@是一棵樹，所以并不需要什么高深的算法，只要簡(jiǎn)單的BFS 即可。

最短路徑的應(yīng)用：

Dijkstra 算法應(yīng)用： Folyed 算法應(yīng)用：

Bellman-Ford 算法的應(yīng)用：

差分約束系統(tǒng)的應(yīng)用：

搜索算法

搜索對(duì)象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個(gè)較優(yōu)的搜索出發(fā)點(diǎn)，凡是能用高效算法的地方盡量爭(zhēng)取用高效算法。基本的遞歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應(yīng)用： 枚舉思想的應(yīng)用： ZOJ 1252 island of logic A*算法的應(yīng)用：

IDA*算法的應(yīng)用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，動(dòng)態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索：

可行性剪枝，最優(yōu)性剪枝，調(diào)整搜索順序是常用的優(yōu)化手段。

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉(zhuǎn)移方程，另外還要考慮高效的預(yù)處理（以便更好更快的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移）。最常用的思想就是用枚舉最后一次操作。

狀態(tài)壓縮DP，又叫帶集合的動(dòng)態(tài)規(guī)劃：題目特點(diǎn)是有一維的維數(shù)特別小。類似TSP問題的DP：

狀態(tài)劃分比較困難的題目： 樹形DP：

四邊形不等式的應(yīng)用探索：四邊形不等式通常應(yīng)用是把O(n^3)復(fù)雜度O(n^2)

高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

并查集的應(yīng)用：

巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應(yīng)用：

總結(jié)用線段樹解題的方法

根據(jù)題目要求將一個(gè)區(qū)間建成線段樹，一般的題目都需要對(duì)坐標(biāo)離散。建樹時(shí)，不要拘泥于線段樹這個(gè)名字而只將線段建樹，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個(gè)點(diǎn)、線段、或數(shù)組中一個(gè)值)組成的，都可以建線段樹；不要拘泥于一維，根據(jù)題目要求可以建立面積樹、體積樹等等

樹的每個(gè)節(jié)點(diǎn)根據(jù)題目所需，設(shè)置變量記錄要求的值

用樹形結(jié)構(gòu)來維護(hù)這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點(diǎn)的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時(shí)，都只對(duì)O(logL)個(gè)節(jié)點(diǎn)修改這個(gè)特點(diǎn)，在O(logL)的時(shí)間內(nèi)維護(hù)修改后相關(guān)節(jié)點(diǎn)的變量。

在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運(yùn)用子樹的收縮與葉子節(jié)點(diǎn)的釋放，避免重復(fù)操作。

Trie的應(yīng)用：；

Trie圖的應(yīng)用探索： 后綴數(shù)組的應(yīng)用研究：

在字符串處理當(dāng)中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹了解得比較多，關(guān)于后綴數(shù)組則很少見于國內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹的一個(gè)非常精巧的替代品，它比后綴樹容易編程實(shí)現(xiàn)，能夠?qū)崿F(xiàn)后綴樹的很多功能而時(shí)間復(fù)雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。

樹狀數(shù)組的應(yīng)用探索：；

計(jì)算幾何

掌握基本算法的實(shí)現(xiàn)。凸包的應(yīng)用：；

半平面交算法的應(yīng)用：；

幾何+模擬類題目：幾何設(shè)計(jì)好算法，模擬控制好精度。掃描法：；

轉(zhuǎn)化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應(yīng)用：；

經(jīng)典算法：找平面上的最近點(diǎn)對(duì)。

貪心

矩形切割

二分思想應(yīng)用

活用經(jīng)典算法

利用歸并排序算法思想求數(shù)列的逆序?qū)?shù)：

利用快速排序算法思想，查詢N個(gè)數(shù)中的第K小數(shù)：

博弈問題

博弈類題目通常用三類解法：第一類推結(jié)論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應(yīng)用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。

第一類：推結(jié)論。典型題目： 第二類：遞推。典型題目：

比如有向無環(huán)圖類型的博弈。在一個(gè)有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應(yīng)該具有如下性質(zhì)：

1． 所有的結(jié)束位置都是P位置。

2． 對(duì)于每一個(gè)N位置，至少存在一種移動(dòng)可以將棋子移動(dòng)到一個(gè)P位置。3． 對(duì)于每一個(gè)P位置，它的每一種移動(dòng)都會(huì)將棋子移到一個(gè)N位置。

這樣，獲勝的策略就是每次都把棋子移動(dòng)到一個(gè)P位置，因?yàn)樵谝粋€(gè)P位置，你的對(duì)手只能將棋子移動(dòng)到一個(gè)N位置，然后你總有一種方法再把棋子移動(dòng)到一個(gè)P位置。一直這樣移動(dòng)，最后你一定會(huì)將棋子移動(dòng)到一個(gè)結(jié)束位置（結(jié)束位置是P位置），這時(shí)你的對(duì)手將無法在移動(dòng)棋子，你便贏得了勝利。

與此同時(shí)，得到了這些性質(zhì)，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為：

1． 將所有的結(jié)束位置標(biāo)為P位置。

2． 將所有能一步到達(dá)P位置的點(diǎn)標(biāo)為N位置。

3． 找出所有只能到達(dá)N位置的點(diǎn)，將它們標(biāo)為P位置。

4． 如果在第三步中沒有找到新的被標(biāo)為P位置的點(diǎn)，則算法結(jié)束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對(duì)于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應(yīng)用。

關(guān)于SG函數(shù)的基本知識(shí)：對(duì)于一個(gè)有向圖(X, F)來說，SG函數(shù)g是一個(gè)在X上的函數(shù)，并且它返回一個(gè)非負(fù)整數(shù)值，具體定義為

g(x)?min{n?0,n?g(y)對(duì)于所有y?F(x)}

1． 對(duì)于所有的結(jié)束位置x，g(x)= 0。

2． 對(duì)于每一個(gè)g(x)≠ 0的位置x，在它可以一步到達(dá)的位置中至少存在一個(gè)位置y使得g(y)= 0。

3．對(duì)于每一個(gè)g(x)＝ 0的位置x，所有可以由它一步到達(dá)的位置y都有g(shù)(y)≠ 0。

定理 如果g(xi)是第i個(gè)有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個(gè)有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四類：極大極小法。

典型題目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩陣妙用

矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關(guān)系（最基本的就是求Fibonacci數(shù)列的某項(xiàng)）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目：

數(shù)學(xué)模型舉例

向量思想的應(yīng)用：

UVA 10089：注意降維和向量的規(guī)范化 ；

利用復(fù)數(shù)思想進(jìn)行向量旋轉(zhuǎn)。

UVA 10253：

遞推

數(shù)代集合

數(shù)代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個(gè)數(shù)不會(huì)超過100，因此可以考慮用一個(gè)數(shù)代替一個(gè)集合，首先把所有的運(yùn)算結(jié)果都用預(yù)處理算出來，到計(jì)算的時(shí)候只要用O(1)的復(fù)雜度就可以完成一次運(yùn)算。

組合數(shù)學(xué)

Polya定理則是解決同構(gòu)染色計(jì)數(shù)問題的有力工具。

補(bǔ)集轉(zhuǎn)化思想

ZOJ 單色三角形：

字符串相關(guān)

擴(kuò)展的KMP算法應(yīng)用：；最長回文串； 最長公共子串； 最長公共前綴；

填充問題

高精度運(yùn)算

三維空間問題專題

無論什么問題，一旦擴(kuò)展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實(shí)現(xiàn)能力。

其它問題的心得

解決一些判斷同構(gòu)問題的方法：同構(gòu)的關(guān)鍵在于一一對(duì)應(yīng)，而如果枚舉一一對(duì)應(yīng)的關(guān)系，時(shí)間復(fù)雜度相當(dāng)?shù)母撸米钚”硎?，就能把一個(gè)事物的本質(zhì)表示出來。求最小表示時(shí)，我們一定要仔細(xì)分析，將一切能區(qū)分兩個(gè)元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當(dāng)?shù)?、高效的匹配算法（例如KMP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進(jìn)行推廣