數(shù)據(jù)挖掘技術(shù)第1頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1分類(lèi)3.1.1概述3.1.2常見(jiàn)的分類(lèi)算法

3.1.2.1決策樹(shù)算法

3.1.2.2CLS算法

3.1.2.3ID3算法

3.1.2.4C4.5算法

3.1.2.5Autoclass算法3.1.3算法實(shí)現(xiàn)第2頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.1分類(lèi)概述分類(lèi)是數(shù)據(jù)挖掘中的一個(gè)重要課題。分類(lèi)的目的是獲得一個(gè)分類(lèi)函數(shù)或分類(lèi)模型（也常常稱(chēng)作分類(lèi)器），該模型能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)映射到某一個(gè)給定類(lèi)別。分類(lèi)可用于提取描述重要數(shù)據(jù)類(lèi)的模型或預(yù)測(cè)未來(lái)的數(shù)據(jù)趨勢(shì)。

第3頁(yè)，共176頁(yè)，2023年，2月20日，星期五分類(lèi)的實(shí)現(xiàn)構(gòu)建模型：預(yù)設(shè)分類(lèi)類(lèi)別對(duì)每個(gè)樣本進(jìn)行類(lèi)別標(biāo)記訓(xùn)練集構(gòu)成分類(lèi)模型分類(lèi)模型可表示為：分類(lèi)規(guī)則、決策樹(shù)或數(shù)學(xué)公式使用模型：識(shí)別未知對(duì)象的所屬類(lèi)別模型正確性的評(píng)價(jià)已標(biāo)記分類(lèi)的測(cè)試樣本與模型的實(shí)際分類(lèi)結(jié)果進(jìn)行比較模型的正確率是指測(cè)試集中被正確分類(lèi)的樣本數(shù)與樣本總數(shù)的百分比。測(cè)試集與訓(xùn)練集相分離，否則將出現(xiàn)過(guò)擬合（over-fitting）現(xiàn)象。第4頁(yè)，共176頁(yè)，2023年，2月20日，星期五分類(lèi)的實(shí)現(xiàn)—模型構(gòu)建TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model)第5頁(yè)，共176頁(yè)，2023年，2月20日，星期五分類(lèi)的實(shí)現(xiàn)—利用模型預(yù)測(cè)ClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?第6頁(yè)，共176頁(yè)，2023年，2月20日，星期五分類(lèi)方法的評(píng)價(jià)標(biāo)準(zhǔn)預(yù)測(cè)的正確性時(shí)間構(gòu)建模型的時(shí)間使用模型所需的時(shí)間健壯性處理噪聲及缺失值的能力可擴(kuò)展性可操作性規(guī)則的優(yōu)化決策樹(shù)的大小分類(lèi)規(guī)則的簡(jiǎn)潔性第7頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.1分類(lèi)概述常見(jiàn)的分類(lèi)方法決策樹(shù)分類(lèi)決策樹(shù)歸納是一種經(jīng)典的分類(lèi)算法。它采用自頂向下、遞歸的、各個(gè)擊破的方式構(gòu)造決策樹(shù)。樹(shù)的每一個(gè)結(jié)點(diǎn)上使用信息增益度量選擇屬性，可以從所生成的決策樹(shù)中提取出分類(lèi)規(guī)則。

第8頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.1概述KNN分類(lèi)即K最近鄰法，最初由Cover和Hart于1968年提出的，是一個(gè)理論上比較成熟的方法。該方法的思路非常簡(jiǎn)單直觀：如果一個(gè)樣本在特征空間中的k個(gè)最相似（即特征空間中最鄰近）樣本中的大多數(shù)屬于某一個(gè)類(lèi)別，則該樣本也屬于這個(gè)類(lèi)別。該方法在分類(lèi)決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類(lèi)別來(lái)決定待分類(lèi)樣本所屬的類(lèi)別。該算法較適用于樣本容量比較大的類(lèi)域的自動(dòng)分類(lèi)，而那些樣本容量較小的類(lèi)域采用這種算法比較容易產(chǎn)生誤分。

第9頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.1概述SVM分類(lèi)方法即支持向量機(jī)（SupportVectorMachine）法，由Vapnik等人于1995年提出，具有相對(duì)優(yōu)良的性能指標(biāo)。該方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上的機(jī)器學(xué)習(xí)方法。通過(guò)學(xué)習(xí)，SVM可以自動(dòng)尋找出那些對(duì)分類(lèi)有較好區(qū)分能力的支持向量，由此構(gòu)造出的分類(lèi)器可以最大化類(lèi)與類(lèi)的間隔，因而有較好的適應(yīng)能力和較高的分準(zhǔn)率。該方法只需要由各類(lèi)域的邊界樣本的類(lèi)別來(lái)決定最后的分類(lèi)結(jié)果。SVM法對(duì)小樣本情況下的自動(dòng)分類(lèi)有著較好的分類(lèi)結(jié)果。第10頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.1分類(lèi)概述VSM分類(lèi)方法即向量空間模型（VectorSpaceModel）法，由Salton等人于60年代末提出。這是最早也是最著名的信息檢索方面的數(shù)學(xué)模型。其基本思想是將文檔表示為加權(quán)的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通過(guò)計(jì)算文本相似度的方法來(lái)確定待分類(lèi)樣本的類(lèi)別。當(dāng)文本被表示為空間向量模型的時(shí)候，文本的相似度就可以借助特征向量之間的內(nèi)積來(lái)表示。VSM法相對(duì)其他分類(lèi)方法而言，更適合于專(zhuān)業(yè)文獻(xiàn)的分類(lèi)。第11頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法決策樹(shù)分類(lèi)是用屬性值對(duì)樣本集逐級(jí)劃分，直到一個(gè)節(jié)點(diǎn)僅含有同一類(lèi)的樣本為止。決策樹(shù)首先起源于Hunt等人提出的概念學(xué)習(xí)系統(tǒng)（ConceptLearningSystem,CLS），然后發(fā)展到Quinlan的ID3算法，最后演化為能處理連續(xù)屬性值的C4.5算法。

第12頁(yè)，共176頁(yè)，2023年，2月20日，星期五決策樹(shù)表示與例子決策樹(shù)（DecisionTree）的每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分枝代表一個(gè)測(cè)試輸出，而每個(gè)樹(shù)葉結(jié)點(diǎn)代表類(lèi)或類(lèi)分布。樹(shù)的最頂層結(jié)點(diǎn)是根結(jié)點(diǎn)。

buys_computer的決策樹(shù)示意第13頁(yè)，共176頁(yè)，2023年，2月20日，星期五決策樹(shù)表示與例子公司職員年齡收入信譽(yù)度買(mǎi)保險(xiǎn)否≤40高良c2否≤40高優(yōu)c2否41~50高良c1否>50中良c1是>50低良c1是>50低優(yōu)c2是41~50低優(yōu)c1否≤40中良c2是≤40低良c1是>50中良c1是≤40中優(yōu)c1否41~50中優(yōu)c1是41~50高良c1否>50中優(yōu)c2描述屬性類(lèi)別屬性第14頁(yè)，共176頁(yè)，2023年，2月20日，星期五決策樹(shù)表示與例子年齡公司職員信譽(yù)度c1c2c1c2c1≤4041~50>50是否良優(yōu)第15頁(yè)，共176頁(yè)，2023年，2月20日，星期五決策樹(shù)分類(lèi)的特點(diǎn)決策樹(shù)分類(lèi)方法采用自頂向下的遞歸方式，在決策樹(shù)的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分枝，在決策樹(shù)的葉結(jié)點(diǎn)得到結(jié)論。所以從決策樹(shù)的根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)則，整棵決策樹(shù)就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則?；跊Q策樹(shù)的分類(lèi)算法的一個(gè)最大的優(yōu)點(diǎn)就是它在學(xué)習(xí)過(guò)程中不需要使用者了解很多背景知識(shí)（這同時(shí)也是它的最大的缺點(diǎn)），只要訓(xùn)練例子能夠用屬性-結(jié)論式表示出來(lái)，就能使用該算法來(lái)學(xué)習(xí)。決策樹(shù)分類(lèi)模型的建立通常分為兩個(gè)步驟：決策樹(shù)生成決策樹(shù)修剪。第16頁(yè)，共176頁(yè)，2023年，2月20日，星期五決策樹(shù)生成算法描述構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的屬性進(jìn)行樹(shù)的拓展。研究結(jié)果表明，一般情況下,樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。由于構(gòu)造最小的樹(shù)是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略來(lái)進(jìn)行。屬性選擇依賴(lài)于各種對(duì)例子子集的不純度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距離度量（DistanceMeasure）、J-measure、G統(tǒng)計(jì)、χ2統(tǒng)計(jì)、證據(jù)權(quán)重（WeightofEvidence）、最小描述長(zhǎng)度（MLP）、正交法（OrtogonalityMeasure）、相關(guān)度（Relevance）和Relief等。算法Generate_decision_tree(samples,attribute_list)/*決策樹(shù)生成算法*/輸入：訓(xùn)練樣本samples，由離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹(shù)。1)創(chuàng)建結(jié)點(diǎn)N；2)IFsamples都在同一個(gè)類(lèi)CTHEN返回N作為葉結(jié)點(diǎn)，以類(lèi)C標(biāo)記；3)IFattribute_list為空THEN返回N作為葉結(jié)點(diǎn)，標(biāo)記為samples中最普通的類(lèi)；//多數(shù)表決4)選擇attribute_list中具有最高信息增益的屬性test_attribute；5)標(biāo)記結(jié)點(diǎn)N為test_attribute；6)FOReachtest_attribute中的已知值ai由結(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為test_attribute=ai的分枝；7)設(shè)si是samples中test_attribute=ai的樣本的集合；//一個(gè)劃分8)IFsi為空THEN加上一個(gè)樹(shù)葉，標(biāo)記為samples中最普通的類(lèi)；9)ELSE加上一個(gè)由Generate_decision_tree(si，attribute_list-test_attribute)返回的結(jié)點(diǎn)；第17頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法決策樹(shù)的輸入一組帶有類(lèi)別標(biāo)記的樣本決策樹(shù)的輸出一棵二叉或多叉樹(shù)。二叉樹(shù)的內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）一般表示為一個(gè)邏輯判斷，如形式為(ai=vi)的邏輯判斷，其中ai是屬性，vi是該屬性的某個(gè)屬性值；樹(shù)的邊是邏輯判斷的分支結(jié)果。多叉樹(shù)（ID3）的內(nèi)部節(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。樹(shù)的葉子節(jié)點(diǎn)則是類(lèi)別標(biāo)記。第18頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法決策樹(shù)的構(gòu)造采用自上而下的遞歸構(gòu)造。以多叉樹(shù)為例，其構(gòu)造思路是：如果訓(xùn)練樣本集中所有樣本是同類(lèi)的，則將它作為葉子節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)容即是該類(lèi)別標(biāo)記；否則，根據(jù)某種策略選擇一個(gè)屬性，按照屬性的不同取值，將樣本集劃分為若干子集，使得每個(gè)子集上的所有樣本在該屬性上具有同樣的屬性值。然后再依次處理各個(gè)子集。實(shí)際上就是“分而治之”（divide-and-conquer）的策略。二叉樹(shù)同理，差別僅在于要選擇一個(gè)好的邏輯判斷。第19頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法決策樹(shù)構(gòu)造的條件構(gòu)造好的決策樹(shù)的關(guān)鍵是：如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣一組樣本，可以有很多決策樹(shù)能符合這組樣本。研究表明，一般情況下，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩?。由于?gòu)造最小的樹(shù)是NP問(wèn)題，因此只能采用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩浴?/p>

第20頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法實(shí)際中，用于模型學(xué)習(xí)的訓(xùn)練數(shù)據(jù)往往不是完美的，原因是：①某些屬性字段上缺值（missingvalues）；②缺少必需的數(shù)據(jù)而造成數(shù)據(jù)不完整；③數(shù)據(jù)不準(zhǔn)確含有噪聲甚至是錯(cuò)誤的。此時(shí)，需要克服噪聲和決策樹(shù)剪枝。第21頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法基本的決策樹(shù)構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹(shù)完全與訓(xùn)練樣本擬合。在有噪聲的情況下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合（overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能。第22頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法剪枝技術(shù)是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理解。剪枝的類(lèi)型向前剪枝（forwardpruning）在生成樹(shù)的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)。

向后剪枝（backwardpruning）是一種兩階段法：擬合－化簡(jiǎn)（fitting-and-simplifying），首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹(shù)，然后從樹(shù)的葉子開(kāi)始剪枝，逐步向根的方向剪。第23頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法剪枝的局限性剪枝并不是對(duì)所有的數(shù)據(jù)集都好，就象最小樹(shù)并不是最好（具有最大的預(yù)測(cè)率）的樹(shù)。當(dāng)數(shù)據(jù)稀疏時(shí)，要防止過(guò)分剪枝（over-pruning）。從某種意義上而言，剪枝也是一種偏向（bias），對(duì)有些數(shù)據(jù)效果好而有些數(shù)據(jù)則效果差。

第24頁(yè)，共176頁(yè)，2023年，2月20日，星期五Attributes={Outlook,Temperature,Humidity,Wind}OutlookHumidityWindsunnyrainovercastyesnoyeshighnormalnostrongweakyesPlayTennis={yes,no}打高爾夫球的決策樹(shù)實(shí)例（自頂向下）第25頁(yè)，共176頁(yè)，2023年，2月20日，星期五根據(jù)加薪百分比、工作時(shí)長(zhǎng)、法定節(jié)假日、及醫(yī)療保險(xiǎn)三個(gè)屬性來(lái)判斷一個(gè)企業(yè)的福利狀況(good或bad)。第26頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.1決策樹(shù)算法CLS(ConceptLearningSystem)系統(tǒng)以一棵空決策樹(shù)開(kāi)始，并通過(guò)增加結(jié)點(diǎn)逐步求精，直到產(chǎn)生一棵能正確分類(lèi)訓(xùn)練樣本的決策樹(shù)為止，是一個(gè)循環(huán)遞歸過(guò)程。設(shè)PN為已知訓(xùn)練子集，則：（1）如果PN中的所有樣本均為正例，則生成一個(gè)YES結(jié)點(diǎn)并終止；如果PN中的所有樣本均為反例，則生成一個(gè)NO結(jié)點(diǎn)并終止；否則，根據(jù)某種啟發(fā)策略選擇一個(gè)屬性A，設(shè)A取值為υ1，υ2…υr，并生成新結(jié)點(diǎn)。（2）將PN中的樣本根據(jù)其屬性A的取值加以劃分，生成r個(gè)子集記為PN1,PN2…PNr。（3）遞歸地應(yīng)用該算法到每個(gè)子集PNi。第27頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.2CLS算法CLS算法的局限性分類(lèi)屬性的選擇決定了算法的效率與所生成的決策樹(shù)的繁簡(jiǎn)程度、預(yù)測(cè)效果。選擇屬性是決策樹(shù)歸納算法的關(guān)鍵。CLS算法可以產(chǎn)生所有可能的決策樹(shù)，正確分類(lèi)訓(xùn)練樣本，并能選擇最簡(jiǎn)單的決策樹(shù)。但是屬性選擇的不確定性，在實(shí)際應(yīng)用中往往受問(wèn)題大小的限制。

第28頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.3ID3算法Quinlan提出的ID3算法，對(duì)CLS算法做出了改進(jìn)。它的基本算法仍然來(lái)自于CLS，但使用熵來(lái)選擇屬性，效果非常理想。ID3只能處理離散型描述屬性；在選擇根節(jié)點(diǎn)和各個(gè)內(nèi)部節(jié)點(diǎn)上的分枝屬性時(shí)，采用信息增益作為度量標(biāo)準(zhǔn)，選擇具有最高信息增益的描述屬性作為分枝屬性假設(shè)nj是數(shù)據(jù)集X中屬于類(lèi)別cj的樣本數(shù)量，則各類(lèi)別的先驗(yàn)概率為P(cj)=nj/total，j=1,2,…,m。第29頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.3ID3算法對(duì)于數(shù)據(jù)集X，計(jì)算期望信息計(jì)算描述屬性Af劃分?jǐn)?shù)據(jù)集X所得的熵假設(shè)Af有q個(gè)不同取值，將X劃分為q個(gè)子集{X1,X2,…,Xs,…Xq}假設(shè)ns表示Xs中的樣本數(shù)量，njs表示Xs中屬于類(lèi)別cj的樣本數(shù)量第30頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.3ID3算法由描述屬性Af劃分?jǐn)?shù)據(jù)集X所得的熵為其中計(jì)算Af劃分?jǐn)?shù)據(jù)集時(shí)的信息增益Gain(Af)=I(n1,n2,…,nm)-E(Af)第31頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.3ID3算法舉例：根據(jù)天氣狀況決定某天早上是否合適打高爾夫球，合適的屬于正例記為P，不合適的屬于反例記為N。天氣由四個(gè)屬性描述，即

outlook(天氣形勢(shì))取值分別為sunny,overcast和rain；

temperature(溫度)取值分別為cool,mild和hot；

humidity（濕度）取值為normal和high；

windy(風(fēng))取值為false和true第32頁(yè)，共176頁(yè)，2023年，2月20日，星期五

outlooktemperaturehumiditywindyclass

1sunnyhothighfalseN2sunnyhothightrueN3overcasthothighfalseP4rainhothighfalseP5raincoolnormalfalseP6raincoolnormaltrueN7overcastcoolnormaltrueP8sunnymildhighfalseN9sunnycoolnormalfalseP10rainmildnormalfalseP11sunnymildnormaltrueP12overcastmildhightrueP13overcasthotnormalfalseP14rainmildhightrueN

表打高爾夫球天氣情況的樣本集（14個(gè)）

第33頁(yè)，共176頁(yè)，2023年，2月20日，星期五ID3算法舉例其中p=9，n=5。gain(outlook)=I(p,n)-E(outlook)=0.940-0.694=0.246

第34頁(yè)，共176頁(yè)，2023年，2月20日，星期五ID3算法舉例類(lèi)似地，可得：

gain(temperature)=0.029gain(humidity)=0.151gain(windy)=0.048因此，outlook具有最大的信息增益，因此outlook被選為根結(jié)點(diǎn)并向下擴(kuò)展，通過(guò)類(lèi)似的方法，得到相應(yīng)的ID3決策樹(shù)。

第35頁(yè)，共176頁(yè)，2023年，2月20日，星期五第36頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.3ID3算法優(yōu)勢(shì)算法理論清晰方法簡(jiǎn)單學(xué)習(xí)能力較強(qiáng)不足之處對(duì)較小的數(shù)據(jù)集有效對(duì)噪聲比較敏感當(dāng)數(shù)據(jù)集增大時(shí)，決策樹(shù)可能會(huì)改變。第37頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.4C4.5算法C4.5算法ID3有很多改進(jìn)算法，其中Quinlan在1994年開(kāi)發(fā)出的C4.5算法流行最廣。

C4.5的改進(jìn)主要體現(xiàn)在兩方面：（1）解決了連續(xù)數(shù)據(jù)值的學(xué)習(xí)問(wèn)題；（2）提供了將學(xué)習(xí)結(jié)果決策樹(shù)到等價(jià)規(guī)則集的轉(zhuǎn)換功能。第38頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.4C4.5算法C4.5算法C4.5屬于一種歸納學(xué)習(xí)算法。歸納學(xué)習(xí)（InductiveLearning）旨在從大量經(jīng)驗(yàn)數(shù)據(jù)中歸納抽取一般的判定規(guī)則和模式，它是機(jī)器學(xué)習(xí)（MachineLearning）中最核心、最成熟的一個(gè)分支。根據(jù)有無(wú)導(dǎo)師指導(dǎo)，歸納學(xué)習(xí)又分為有導(dǎo)師學(xué)習(xí)（SupervisedLearning，又稱(chēng)為示例學(xué)習(xí)）和無(wú)導(dǎo)師學(xué)習(xí)(UnsupervisedLearning)。C4.5屬于有導(dǎo)師的學(xué)習(xí)算法。第39頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.4C4.5算法示例學(xué)習(xí)算法分為兩大類(lèi)：覆蓋算法（coveringalgorithms）分治算法（divide-and-conqueralgorithms）前者歸納生成規(guī)則，后者歸納生成決策樹(shù)。第40頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.5Autoclass算法Autoclass算法

是一個(gè)基于Bayesian網(wǎng)絡(luò)的無(wú)監(jiān)督的分類(lèi)算法，該算法可以處理連續(xù)和離散的屬性。對(duì)于連續(xù)屬性值，用戶應(yīng)先驗(yàn)說(shuō)明屬性的概率分布類(lèi)別（比如正態(tài)分布）；而對(duì)于離散屬性，用戶可以說(shuō)明屬性可能的所有取值。Autoclass算法可以把屬性單獨(dú)考慮，也可以先驗(yàn)說(shuō)明某些屬性的聯(lián)合分布。該算法根據(jù)先驗(yàn)的概率分布類(lèi)別，探索性地將數(shù)據(jù)集多次分成不同個(gè)數(shù)的類(lèi)，然后比較這些分類(lèi)，給出較優(yōu)的幾個(gè)結(jié)果。

第41頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.6神經(jīng)網(wǎng)絡(luò)算法人工神經(jīng)網(wǎng)（ArtificialNeuralNetwork，ANN）是20世紀(jì)80年代后期迅速發(fā)展起來(lái)的人工智能技術(shù)，它對(duì)噪聲數(shù)據(jù)具有很高的承受能力，對(duì)未經(jīng)訓(xùn)練的數(shù)據(jù)具有分類(lèi)模擬的能力，因此在網(wǎng)站信息、生物信息和基因以及文本的數(shù)據(jù)挖掘等領(lǐng)域得到了越來(lái)越廣泛的應(yīng)用。在多種ANN模型中，反向傳播（BackPropagation，BP）網(wǎng)絡(luò)是應(yīng)用最廣的一種。

第42頁(yè)，共176頁(yè)，2023年，2月20日，星期五神經(jīng)元通過(guò)非線性函數(shù)n維的輸入向量

x

被映射為變量ymk-fweightedsumInputvectorxoutputyActivationfunctionweightvectorw?w0w1wnx0x1xn第43頁(yè)，共176頁(yè)，2023年，2月20日，星期五神經(jīng)網(wǎng)絡(luò)的組成輸出節(jié)點(diǎn)輸入節(jié)點(diǎn)隱層節(jié)點(diǎn)輸入矢量輸入矢量:xiwij基本的BP網(wǎng)絡(luò)由輸入層、輸出層和隱層組成。第44頁(yè)，共176頁(yè)，2023年，2月20日，星期五第45頁(yè)，共176頁(yè)，2023年，2月20日，星期五神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)神經(jīng)網(wǎng)絡(luò)訓(xùn)練之前，需要設(shè)計(jì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。設(shè)計(jì)網(wǎng)絡(luò)拓?fù)涞年P(guān)鍵是，確定隱層的神經(jīng)元個(gè)數(shù)及各神經(jīng)元初始權(quán)值和閾值（偏差）。理論上講，隱層的神經(jīng)元數(shù)越多，逼近越精確。但實(shí)際上，隱層神經(jīng)元數(shù)不宜過(guò)多；否則會(huì)極大加長(zhǎng)訓(xùn)練時(shí)間，并造成網(wǎng)絡(luò)容錯(cuò)能力下降。經(jīng)訓(xùn)練后的神經(jīng)網(wǎng)絡(luò)若其準(zhǔn)確性不能被接受，則必須重新進(jìn)行拓?fù)湓O(shè)計(jì)或改用不同的初始權(quán)值和閾值（偏差）。

第46頁(yè)，共176頁(yè)，2023年，2月20日，星期五神經(jīng)網(wǎng)絡(luò)的訓(xùn)練訓(xùn)練的終止條件獲得一組權(quán)重值，使得訓(xùn)練集中幾乎所有樣本都分類(lèi)正確訓(xùn)練步驟利用隨機(jī)值對(duì)權(quán)值進(jìn)行初始化將訓(xùn)練樣本逐一地輸入給神經(jīng)網(wǎng)絡(luò)，進(jìn)行訓(xùn)練對(duì)于每個(gè)神經(jīng)元將其所有的輸入值進(jìn)行線性求和計(jì)算得到總的輸入利用激勵(lì)函數(shù)計(jì)算其輸出值計(jì)算誤差修正網(wǎng)絡(luò)權(quán)值和閾值（偏差）第47頁(yè)，共176頁(yè)，2023年，2月20日，星期五BP神經(jīng)網(wǎng)絡(luò)BP神經(jīng)網(wǎng)絡(luò)通過(guò)迭代處理一組訓(xùn)練樣本，將各樣本的網(wǎng)絡(luò)預(yù)測(cè)與實(shí)際已知類(lèi)標(biāo)號(hào)進(jìn)行比較實(shí)現(xiàn)學(xué)習(xí)訓(xùn)練，反向修改網(wǎng)絡(luò)的權(quán)值，使得網(wǎng)絡(luò)預(yù)測(cè)與實(shí)際類(lèi)之間的誤差平方最小。BP神經(jīng)網(wǎng)絡(luò)按照最優(yōu)訓(xùn)練準(zhǔn)則反復(fù)迭代，確定并不斷調(diào)整神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，通過(guò)迭代修改，當(dāng)誤差收斂時(shí)學(xué)習(xí)過(guò)程終止。因此，具有分類(lèi)準(zhǔn)確、收斂性好、動(dòng)態(tài)性好和魯棒性強(qiáng)等優(yōu)點(diǎn)。第48頁(yè)，共176頁(yè)，2023年，2月20日，星期五BP神經(jīng)網(wǎng)絡(luò)存在的問(wèn)題收斂速度問(wèn)題

BP分類(lèi)器最大的弱點(diǎn)是其訓(xùn)練速度非常緩慢，難以收斂。尤其是當(dāng)網(wǎng)絡(luò)的訓(xùn)練達(dá)到一定程度后，收斂更為緩慢。局部極小點(diǎn)問(wèn)題

BP算法采用的是梯度下降法，對(duì)一個(gè)復(fù)雜的網(wǎng)絡(luò)而言，其誤差曲面是一個(gè)高維空間中的曲面，其中分布著許多局部極小點(diǎn)，一旦陷入了局部極小點(diǎn)則算法很難逃離出來(lái)。第49頁(yè)，共176頁(yè)，2023年，2月20日，星期五BP神經(jīng)網(wǎng)絡(luò)存在的問(wèn)題網(wǎng)絡(luò)癱瘓問(wèn)題

在訓(xùn)練過(guò)程中，權(quán)值可能變得很大，這會(huì)使神經(jīng)元的網(wǎng)絡(luò)輸入變得更大，從而使得其激勵(lì)函數(shù)的一階導(dǎo)函數(shù)在此點(diǎn)上的取值很小。此時(shí)的訓(xùn)練步長(zhǎng)會(huì)變得非常小，最終導(dǎo)致網(wǎng)絡(luò)停止收斂，這種現(xiàn)象即是所謂的網(wǎng)絡(luò)癱瘓現(xiàn)象。第50頁(yè)，共176頁(yè)，2023年，2月20日，星期五其它的分類(lèi)算法基于案例推理的分類(lèi)基于遺傳算法的分類(lèi)基于粗糙集的分類(lèi)基于模糊集的分類(lèi)第51頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.7粗糙集粗糙集理論是建立在分類(lèi)機(jī)制的基礎(chǔ)上的，它將分類(lèi)理解成在特定空間上的等價(jià)關(guān)系，從而構(gòu)成了對(duì)該空間的劃分。其關(guān)鍵思想是將不確定的或不精確的知識(shí)用已知的知識(shí)庫(kù)中的知識(shí)來(lái)近似地刻畫(huà)，是目前被使用較多的一種歸納學(xué)習(xí)方法。該理論的特點(diǎn)是：它不需要提供除問(wèn)題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息，所以對(duì)問(wèn)題的不確定性的描述和處理相對(duì)客觀。第52頁(yè)，共176頁(yè)，2023年，2月20日，星期五粗糙集基本理論(P182)1．知識(shí)與分類(lèi)積木顏色形狀體積x1紅圓小x2藍(lán)方大x3紅三角小x4藍(lán)三角小x5黃圓小x6黃方小x7紅三角大x8藍(lán)三角大第53頁(yè)，共176頁(yè)，2023年，2月20日，星期五粗糙集基本理論(P182)2．不可分辨關(guān)系（不分明關(guān)系）3．上近似集和下近似集4．知識(shí)依賴(lài)度URX1C/2B+3A+4D/5A+6C+第54頁(yè)，共176頁(yè)，2023年，2月20日，星期五粗糙集概念的物理意義第55頁(yè)，共176頁(yè)，2023年，2月20日，星期五粗糙集理論的特點(diǎn)1．粗糙集理論的內(nèi)涵知識(shí)是主體對(duì)論域中的客體進(jìn)行分類(lèi)的能力，分類(lèi)能力越強(qiáng)，主體所具備知識(shí)的可靠性越高分類(lèi)能力受主體分辨能力的影響，因此分類(lèi)具有近似性影響分類(lèi)能力的因素很多，不同的因素重要性不同，其中某些因素起著決定性作用具有相同屬性的實(shí)體，屬性取值的不同對(duì)分類(lèi)能力也產(chǎn)生影響，屬性之間存在著某種依賴(lài)關(guān)系第56頁(yè)，共176頁(yè)，2023年，2月20日，星期五粗糙集理論的特點(diǎn)2．與其它不確定理論的關(guān)系知識(shí)系統(tǒng)中的不確定性主要來(lái)自于3個(gè)方面：（1）認(rèn)知對(duì)象間缺乏足夠的區(qū)分度。（2）對(duì)象集合存在不確定性，這里集合的不確定性有兩種解釋。（3）不合適的知識(shí)表達(dá)粒度第57頁(yè)，共176頁(yè)，2023年，2月20日，星期五決策表達(dá)邏輯知識(shí)的簡(jiǎn)化（P189）簡(jiǎn)化核決策表（P190）當(dāng)且僅當(dāng)C→D，決策表T＝(U，A，C，D)是協(xié)調(diào)的。每個(gè)決策表T=(U,A,C,D)都可以唯一地分解成兩個(gè)決策表一個(gè)是協(xié)調(diào)的T1=(U1,A,C,D)和另一個(gè)完全不協(xié)調(diào)的T2=(U2,A,C,D)Uacdeox101111x211010x310011x410010x510000x611011第58頁(yè)，共176頁(yè)，2023年，2月20日，星期五粗糙集的研究進(jìn)展(P192)1．理論研究2．應(yīng)用研究3．粒度研究具體地講，凡是在分析問(wèn)題和求解問(wèn)題中,應(yīng)用了分組、分類(lèi)和聚類(lèi)手段的一切理論與方法均屬于粒度計(jì)算(GranularComputing,GrC)的范疇粒計(jì)算作為信息處理的一種新的概念和計(jì)算范式，覆蓋了所有有關(guān)粒度的理論、方法、技術(shù)和工具的研究；這些理論都是從集會(huì)出發(fā)，采用不同的機(jī)制研究知識(shí)粒度的變換，它們之間并不是互相競(jìng)爭(zhēng)的理論，而是互補(bǔ)的第59頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.8基于案例推理（P220）基于案例推理（Casw-BasedReasoning，CBR）是通過(guò)檢查出案例庫(kù)中過(guò)去同類(lèi)的相似問(wèn)題從而獲得當(dāng)前問(wèn)題的解決方案?；舅枷耄夯谌藗?cè)趩?wèn)題求解中習(xí)慣于過(guò)去處理類(lèi)似問(wèn)題的經(jīng)驗(yàn)和獲取的知識(shí)，再針對(duì)新舊情況的差異做相應(yīng)的調(diào)整，從而得到新問(wèn)題的解并形成新的案例。適用于沒(méi)有很強(qiáng)的理論模型和領(lǐng)域知識(shí)不完全、難以定義、不良定義或定義不一致而經(jīng)驗(yàn)豐富的決策環(huán)境中。第60頁(yè)，共176頁(yè)，2023年，2月20日，星期五CBR的邏輯學(xué)基礎(chǔ)1．類(lèi)比推理在人工智能中，如機(jī)器定理證明的歸結(jié)原理，使用的是演繹推理，是從一般到特殊的推理過(guò)程，并未發(fā)現(xiàn)新的知識(shí)；反之，歸納推理則是從特殊到一般的推理過(guò)程，屬于非標(biāo)準(zhǔn)邏輯，能根據(jù)某些已知的特殊性知識(shí)，歸納出未知的一般性知識(shí)。如果這些特殊性知識(shí)已經(jīng)直接或間接包含了未知的一般性知識(shí)的所有可能情況，則歸納推理的結(jié)論完全有效，是完全歸納推理，仍然屬于形式邏輯；否則結(jié)論可能有效，也可能無(wú)效，是不完全歸納推理。第61頁(yè)，共176頁(yè)，2023年，2月20日，星期五類(lèi)比推理的基本結(jié)構(gòu)就是： 物體A有屬性a、b、c、d， 物體B有屬性a、b、c； 所以類(lèi)似地，B亦有屬性d。類(lèi)比有多種形式，如方法類(lèi)比、概念類(lèi)比、圖形類(lèi)比、聯(lián)想類(lèi)比等，都是人類(lèi)思維的體現(xiàn)。類(lèi)比推理給出的前提雖然指明了事物各種屬性的共存，但是并沒(méi)有確證這些屬性之間有必然聯(lián)系。CBR的邏輯學(xué)基礎(chǔ)第62頁(yè)，共176頁(yè)，2023年，2月20日，星期五CBR的邏輯學(xué)基礎(chǔ)2．非單調(diào)邏輯常識(shí)是人工智能研究的主要內(nèi)容，因?yàn)闄C(jī)器智能必須處理常識(shí)和實(shí)現(xiàn)常識(shí)推理。然而常識(shí)并無(wú)明確的定義，而且有眾多的例外。常識(shí)推理的基本特征是在知識(shí)不完全情況下進(jìn)行的，要作出各種假設(shè)，具有非單調(diào)性。人類(lèi)知識(shí)的增長(zhǎng)實(shí)際上是非單調(diào)的發(fā)展過(guò)程，原因是人們推理時(shí)所依據(jù)的知識(shí)具有不完全性。假如把人們?cè)诓煌J(rèn)識(shí)階段的知識(shí)用集合F表示，則是時(shí)間t的函數(shù)，F(xiàn)(t)表示人們?cè)贂r(shí)刻t的知識(shí)總和，卻不具備當(dāng)t2>t1時(shí)F(t2)>F(t1)。然而，經(jīng)典邏輯如形式邏輯、演繹邏輯等，對(duì)人類(lèi)認(rèn)知世界的處理卻是單調(diào)的。第63頁(yè)，共176頁(yè)，2023年，2月20日，星期五1、CBR的工作過(guò)程CBR智能技術(shù)（P222）第64頁(yè)，共176頁(yè)，2023年，2月20日，星期五檢索（Retrieve）：根據(jù)輸入待解決的問(wèn)題的有關(guān)信息，從案例庫(kù)中檢索相似的案例集；重用（Reuse）：從檢索到的一組案例中獲得求解方案，判別是否符合需求，若符合，則重用這些方案（或多個(gè)方案的合并解），否則需要修正；修正案例（Revise）：從相似案例中修正求解方案，使之適合于求解當(dāng)前問(wèn)題，得到當(dāng)前問(wèn)題的新求解方案；保存案例（Retain）：將新案例及其解根據(jù)一定的策略存入案例庫(kù)中，此乃CBR的學(xué)習(xí)方式。CBR智能技術(shù)第65頁(yè)，共176頁(yè)，2023年，2月20日，星期五二、案例表示案例由諸多的屬性組成，案例間相似性就是根據(jù)屬性之間的相似度來(lái)定義的，目標(biāo)案例和源案例的本質(zhì)特征具有相似性關(guān)系使得類(lèi)比有了基礎(chǔ)。案例表示的研究，是整個(gè)CBR研究的基礎(chǔ)和核心；案例的表示涉及到這樣幾個(gè)問(wèn)題：選擇什么信息存放在一個(gè)案例中、如何選擇合適的案例內(nèi)容描述結(jié)構(gòu)、案例庫(kù)如何組織和索引等1．案例表示的要求2．案例表示方法CBR智能技術(shù)第66頁(yè)，共176頁(yè)，2023年，2月20日，星期五三、CBR技術(shù)特點(diǎn)（P224）1．CBR的心理學(xué)模型：記憶推理2．CBR與思維模擬：直覺(jué)、邏輯、創(chuàng)造性思維的綜合3．知識(shí)復(fù)用：結(jié)果的復(fù)用、方法的復(fù)用4．研究CBR技術(shù)的動(dòng)機(jī)主要是克服在知識(shí)系統(tǒng)中的出現(xiàn)關(guān)鍵問(wèn)題，如問(wèn)題(1)克服理論不完善或信息缺失，(2)及時(shí)獲取與更新知識(shí)，(3)對(duì)付計(jì)算復(fù)雜性問(wèn)題，(4)輔助決策。5．增量式學(xué)習(xí)：增加知識(shí)庫(kù)案例CBR智能技術(shù)第67頁(yè)，共176頁(yè)，2023年，2月20日，星期五1．案例相似性理論

(1)語(yǔ)義相似

(2)結(jié)構(gòu)相似性

(3)目標(biāo)特征

(4)個(gè)體相似性

2．相似性計(jì)算

(1)Tversky對(duì)比匹配函數(shù)

(2)改進(jìn)的Tversky匹配法

(3)距離度量法或最近鄰算法

(4)多參數(shù)的相似性計(jì)算

(5)Weber計(jì)算法相似性研究（P226）第68頁(yè)，共176頁(yè)，2023年，2月20日，星期五案例修正技術(shù)1．案例修正方法（P228）2．修正知識(shí)獲取(1)利用領(lǐng)域知識(shí)來(lái)學(xué)習(xí)修正規(guī)則(2)交互式修正規(guī)則的學(xué)習(xí)，一般是從專(zhuān)家用戶處學(xué)習(xí)修正知識(shí)(3)從案例庫(kù)中學(xué)習(xí)修正規(guī)則，即利用機(jī)器學(xué)習(xí)技術(shù)從案例庫(kù)中獲取修正知識(shí)(4)從數(shù)據(jù)庫(kù)中直接地發(fā)現(xiàn)修正知識(shí)(5)案例推理中基于案例庫(kù)的修正學(xué)習(xí)技術(shù)(6)遞歸修正技術(shù)：它是根據(jù)案例之間的規(guī)律來(lái)遞歸求解的,根據(jù)用戶需求來(lái)引導(dǎo)并發(fā)現(xiàn)出修正知識(shí)第69頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.9遺傳算法遺傳算法（GeneticAlgorithms，GA）是一類(lèi)借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法，大多數(shù)系統(tǒng)都遵循“適者生存”的仿自然法則。經(jīng)過(guò)多年的發(fā)展，遺傳算法取得了豐碩的應(yīng)用成果和理論研究進(jìn)展。第70頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.9遺傳算法求解此類(lèi)問(wèn)題的算法應(yīng)該注意以下幾點(diǎn)：不能簡(jiǎn)單地認(rèn)為只要能產(chǎn)生適應(yīng)環(huán)境的結(jié)構(gòu)就好，還要保證求解問(wèn)題的時(shí)間處于合理的范圍；應(yīng)該在保持窮舉法的通用性的基礎(chǔ)上提高效率；由于不了解環(huán)境，在算法中要有存儲(chǔ)和利用實(shí)驗(yàn)結(jié)果，從中獲取信息的手段。因而，Holland提出了模仿自然界的進(jìn)化機(jī)制來(lái)解決適應(yīng)性問(wèn)題的優(yōu)化算法——遺傳算法。由于他提出的遺傳算法簡(jiǎn)單實(shí)用，因而已普遍被接受采納。第71頁(yè)，共176頁(yè)，2023年，2月20日，星期五遺傳算法的主要特征（P230）圖7-18是SGA（標(biāo)準(zhǔn)遺傳算法）一種模式的工作流程圖。由圖可見(jiàn)，遺傳算法是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì)象。遺傳算法的遺傳操作（GeneticOperation）包括：選擇（Selection）、交叉（Crossover）和變異（Mutation）三個(gè)主要的遺傳算子，它們使得遺傳算法具有了其它傳統(tǒng)方法所沒(méi)有的特性。遺傳算法的核心內(nèi)容是它的五個(gè)基本要素，它們是：參數(shù)編碼；初始群體的設(shè)定；適應(yīng)度函數(shù)的設(shè)計(jì)；遺傳操作設(shè)計(jì)；控制參數(shù)設(shè)定。第72頁(yè)，共176頁(yè)，2023年，2月20日，星期五遺傳算法求函數(shù)f(x)=x2+2的極值的計(jì)算過(guò)程第73頁(yè)，共176頁(yè)，2023年，2月20日，星期五遺傳算法的基本原理（P234）1、模式定理(Schematatheorem)2、積木塊假設(shè)3、欺騙問(wèn)題4、隱并行性第74頁(yè)，共176頁(yè)，2023年，2月20日，星期五遺傳算法的關(guān)鍵問(wèn)題及方法一、編碼（1）二進(jìn)制編碼（2）多字符及實(shí)數(shù)編碼（3）樹(shù)編碼（4）自適應(yīng)編碼二、適應(yīng)度函數(shù)1.適應(yīng)度函數(shù)的設(shè)定2.適應(yīng)度函數(shù)定標(biāo)三、遺傳操作1.選擇算子2.交叉算子3.變異算子四、未成熟收斂問(wèn)題第75頁(yè)，共176頁(yè)，2023年，2月20日，星期五挖掘關(guān)聯(lián)規(guī)則的遺傳算法（P241）（1）編碼（2）適應(yīng)度函數(shù)定義（3）選擇操作（4）交叉操作（5）變異操作（6）規(guī)則評(píng)價(jià)和提取編號(hào)支持度可信度規(guī)

則

前

提規(guī)

則

結(jié)

果R10.2120.876日照量介于55到75小時(shí)降雨量介于0到30毫米R(shí)20.1540.857平均氣溫介于2.0到8.0攝氏度降雨量介于0到30毫米R(shí)30.1210.904日照量介于62到82小時(shí)降雨量介于0到30毫米第76頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.10模糊技術(shù)（P242）一、模糊知識(shí)模糊集理論用來(lái)最大限度地模擬人的思維及其推理功能，來(lái)研究描述一類(lèi)信息不精確系統(tǒng)的知識(shí)模型。美國(guó)自動(dòng)控制專(zhuān)業(yè)Zadeh提出模糊理論的出發(fā)點(diǎn)之一就是描述不確定性，如模糊性、隨機(jī)性等。如果一個(gè)概念的外延邊界是不清楚的，那么這個(gè)概念的外延邊界是個(gè)模糊集合。如“青年”、“中年”，“老年”由于概念的外延的模糊而贊成的不確定性稱(chēng)為模糊型(Fuzziness)，在[0,1]上取值隸屬函數(shù)就描述了這種模糊性。Zadeh認(rèn)為：指明各個(gè)元素的隸屬集合，就等于指定了一個(gè)集合；當(dāng)屬于0和1之間時(shí)值時(shí)，就是模糊集合。第77頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.1.2.10模糊技術(shù)二、模糊集合論（一）隸屬度（P243）（二）模糊集合的表示（P244）第78頁(yè)，共176頁(yè)，2023年，2月20日，星期五模糊度及模糊關(guān)系一、模糊度（P247）是[0,1]空間上的隸屬函數(shù)，表達(dá)模糊性的大小。取值0.5時(shí)模糊性最大。海明模糊度歐幾里得模糊度明可夫斯基模糊度第79頁(yè)，共176頁(yè)，2023年，2月20日，星期五模糊度及模糊關(guān)系二、模糊關(guān)系（P247）模糊矩陣模糊關(guān)系三、模糊邏輯與模糊推理模糊命題模糊邏輯模糊推理第80頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2關(guān)聯(lián)3.2.1基本概念3.2.2典型算法3.2.3算法實(shí)現(xiàn)

第81頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.1基本概念關(guān)聯(lián)自然界中某種事物發(fā)生時(shí)其他事物也會(huì)發(fā)生，則這種聯(lián)系稱(chēng)之為關(guān)聯(lián)。反映事件之間依賴(lài)或關(guān)聯(lián)的知識(shí)稱(chēng)為關(guān)聯(lián)型知識(shí)（又稱(chēng)依賴(lài)關(guān)系）。關(guān)聯(lián)的類(lèi)型分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)。第82頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.1基本概念關(guān)聯(lián)規(guī)則關(guān)聯(lián)是兩個(gè)或多個(gè)變量取值之間存在的一類(lèi)重要的可被發(fā)現(xiàn)的某種規(guī)律性。第83頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.1基本概念關(guān)聯(lián)規(guī)則的數(shù)學(xué)定義

先設(shè)I={i1,i2,...,im}是一個(gè)以m個(gè)不同項(xiàng)為元素的集合，T是針對(duì)I的交易的集合，每一筆交易包含若干個(gè)屬于I的項(xiàng)。關(guān)聯(lián)規(guī)則可表示為X=>Y，其中X,YI且XY=X稱(chēng)為規(guī)則的前提或前項(xiàng)，Y稱(chēng)為結(jié)果或后項(xiàng)。每一規(guī)則有兩個(gè)度量標(biāo)準(zhǔn)，即支持度(Support)和可信度(Confidence)

規(guī)則的支持度定義為:support(X=>Y)=support(XUY)

規(guī)則的可信度定義為:confidence(X=>Y)=support(XUY)/support(X)第84頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.1基本概念關(guān)聯(lián)規(guī)則的形式

R:X=>Y

其中，X及Y是兩個(gè)不相交的集合，即X,YI且XY=

關(guān)聯(lián)規(guī)則可以理解為一個(gè)命題，即如果一個(gè)交易支持項(xiàng)集X，則它也以一定的可能性支持項(xiàng)集Y，這一可能性稱(chēng)之為規(guī)則的可信度，記為conf(R)或C(R)第85頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.1基本概念舉例規(guī)則形式:Body?Head[support,confidence]buys(x,“diapers”)?buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)?grade(x,“A”)[1%,75%]第86頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.1基本概念關(guān)聯(lián)規(guī)則的性質(zhì)規(guī)則的非結(jié)合性規(guī)則的不可分解性規(guī)則的不可傳遞性規(guī)則的可擴(kuò)展性第87頁(yè)，共176頁(yè)，2023年，2月20日，星期五關(guān)聯(lián)規(guī)則挖掘?qū)嵗?/p>

通過(guò)發(fā)現(xiàn)顧客放入其購(gòu)物籃中不同商品之間的聯(lián)系，分析顧客的購(gòu)買(mǎi)習(xí)慣。通過(guò)了解哪些商品頻繁地被顧客同時(shí)購(gòu)買(mǎi)，這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營(yíng)銷(xiāo)策略。例如，在同一次購(gòu)物中，如果顧客購(gòu)買(mǎi)牛奶的同時(shí)，也購(gòu)買(mǎi)面包（和什么類(lèi)型的面包）的可能性有多大？這種信息可以引導(dǎo)銷(xiāo)售，可以幫助零售商有選擇地經(jīng)銷(xiāo)和安排貨架。例如，將牛奶和面包盡可能放近一些，可以進(jìn)一步刺激一次去商店同時(shí)購(gòu)買(mǎi)這些商品。第88頁(yè)，共176頁(yè)，2023年，2月20日，星期五關(guān)聯(lián)規(guī)則挖掘?qū)嵗?gòu)物籃關(guān)聯(lián)分析實(shí)例圖第89頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.1基本概念CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer“啤酒與尿布”的關(guān)聯(lián)規(guī)則第90頁(yè)，共176頁(yè)，2023年，2月20日，星期五ForruleA

Csupport=support({A

C})=50%confidence=support({A

C})/support({A})=66.6%ForCA(50%,100%)TheAprioriprinciple:AnysubsetofafrequentitemsetmustbefrequentMin.support50%Min.confidence50%關(guān)聯(lián)挖掘?qū)嵗?1頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法典型算法

AIS算法（R.Agrawal等提出）

Apriori算法（及變種AprioriTid和AprioriHybrid)）

SETM算法（M.Houtsma等提出）

DHP算法（J.Park等提出）

PARTITION算法（A.Savasere等提出）

Sampling算法（H.Toivonen提出）

FP-growth算法（JiaweiHan提出）第92頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法AIS算法的主要思想其主要思想是一邊掃描數(shù)據(jù)庫(kù)，一邊產(chǎn)生候選項(xiàng)集并累計(jì)支持度。具體地說(shuō)，在對(duì)數(shù)據(jù)庫(kù)進(jìn)行第k次掃描時(shí)，候選項(xiàng)集是由第k-1次掃描所產(chǎn)生的邊界集(frontierset)通過(guò)增加當(dāng)前事務(wù)中的項(xiàng)得到，同時(shí)計(jì)算候選項(xiàng)集中元素的支持?jǐn)?shù)，直到某次掃描所產(chǎn)生的邊界集為空。缺點(diǎn)：生成的候選項(xiàng)集太大。第93頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法Apriori算法的主要思想該算法利用了頻繁項(xiàng)集所具有的任意頻繁項(xiàng)集的子集都是頻繁項(xiàng)集的這一性質(zhì)對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描:第一次掃描得到頻繁項(xiàng)集的集合L0

，第k趟掃描前先利用上次掃描的結(jié)果項(xiàng)目集Lk-1,產(chǎn)生候選k項(xiàng)集的集合Ck

，然后再通過(guò)掃描數(shù)據(jù)庫(kù)確定C中每一候選k項(xiàng)集的支持?jǐn)?shù)，最后在該次掃描結(jié)束時(shí)求出頻繁k項(xiàng)集的集合Lk

，算法的終止條件是Ck或Lk為空。

優(yōu)點(diǎn)：所產(chǎn)生的候選項(xiàng)集比AIS算法少得多，效率較高。事實(shí)上，它被視為關(guān)聯(lián)規(guī)則挖掘最經(jīng)典的算法，其他很多算法都是其變種或改進(jìn)。

第94頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法SETM算法的主要思想該算法實(shí)際也是AIS算法的變形。SETM把候選集的產(chǎn)生和累計(jì)分開(kāi)，在一個(gè)線性存儲(chǔ)結(jié)構(gòu)里存儲(chǔ)了所有候選集和相應(yīng)的交易的標(biāo)識(shí)符（TID）。每次掃描結(jié)束后，不再讀取數(shù)據(jù)庫(kù)，而是對(duì)TID進(jìn)行排序并累計(jì)各個(gè)候選集的支持度。其思想是掃描候選集的編碼（TID）來(lái)代替掃描數(shù)據(jù)庫(kù)，實(shí)質(zhì)上是把數(shù)據(jù)庫(kù)中與支持有關(guān)的信息單獨(dú)提取出來(lái)，構(gòu)成一個(gè)較小但充分的TID庫(kù)。這種做法大大減少了數(shù)據(jù)庫(kù)訪問(wèn)的時(shí)間。缺點(diǎn)：候選項(xiàng)集過(guò)大。

第95頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法DHP算法的主要思想該算法利用散列表(hashtable)產(chǎn)生候選集，是對(duì)Apriori算法的直接改進(jìn)。在遍歷一次數(shù)據(jù)庫(kù)得到候選k--項(xiàng)集的支持度，得到頻繁k一項(xiàng)集后，DHP算法將每一個(gè)事務(wù)的可能的(k+1)--項(xiàng)集通過(guò)哈希規(guī)則形成散列表。散列表的每一欄包括所有通過(guò)散列規(guī)則映射到該欄中的項(xiàng)集的數(shù)目。根據(jù)結(jié)果的散列表，可以生成一個(gè)位向量，當(dāng)散列表中對(duì)應(yīng)的該欄中的數(shù)值大于或者等于最小支持時(shí)，對(duì)應(yīng)的位置為1,否則為0。用該向量可以過(guò)濾掉下一次生成候選時(shí)所不必要的項(xiàng)集:如某候選項(xiàng)在向量中對(duì)應(yīng)位的值為0，則舍棄。這對(duì)候選2--項(xiàng)集的產(chǎn)生尤為有效，可以在第二次就大大減小候選集的規(guī)模。第96頁(yè)，共176頁(yè)，2023年，2月20日，星期五DHP算法優(yōu)點(diǎn)在某些場(chǎng)合，DHP算法的效率比Apriori算法明顯提高。第97頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法PARTITION算法的主要思想該算法主要針對(duì)大型數(shù)據(jù)庫(kù)，包括兩部分：

(1)將目標(biāo)數(shù)據(jù)庫(kù)分為n個(gè)互不相交的子數(shù)據(jù)庫(kù)D1，…，Dn，每個(gè)Di(i=1,2,?,n)的大小都要能容納在內(nèi)存中。然后把每個(gè)Di，讀入內(nèi)存并按一般算法發(fā)現(xiàn)頻繁項(xiàng)集Li。再把所有的Li合并為數(shù)據(jù)庫(kù)D的潛在頻繁項(xiàng)集PL=UiLi;(2)計(jì)算潛在頻繁項(xiàng)集PL在D中的支持度，得出頻繁項(xiàng)集L。

第98頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法Sampling算法的主要思想對(duì)數(shù)據(jù)庫(kù)D進(jìn)行隨機(jī)抽樣得到抽樣事務(wù)數(shù)據(jù)庫(kù)D’，先以小于指定的支持度（minsup）挖掘D’中的頻繁項(xiàng)集L’，再在剩余的數(shù)據(jù)集D-D’中繼續(xù)計(jì)算L’中各元素的支持?jǐn)?shù)，最后再以minsup求出L。這在大多數(shù)情況下就可以求得所有的頻繁項(xiàng)集，但是有時(shí)會(huì)漏掉一些。這時(shí)可以對(duì)D進(jìn)行二次掃描以發(fā)現(xiàn)漏掉的頻繁項(xiàng)集。優(yōu)點(diǎn)：多數(shù)情況下只需對(duì)數(shù)據(jù)庫(kù)掃描一次，最壞情況下也只需掃描兩次。

第99頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.3算法實(shí)現(xiàn)Apriori算法的實(shí)現(xiàn)（1）由候選項(xiàng)集(candidateitemset)產(chǎn)生頻繁項(xiàng)集(frequentitemset)；（2）由頻繁項(xiàng)集(frequentitemset)產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則(strongassociationrule)。第100頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.3算法實(shí)現(xiàn)Apriori算法的基本流程

使用逐層搜索的迭代方法，通過(guò)對(duì)數(shù)據(jù)庫(kù)的多次掃描發(fā)現(xiàn)所有的頻繁項(xiàng)集。在每一趟掃描中只考慮具有同一長(zhǎng)度k(即為項(xiàng)集中所含項(xiàng)目的個(gè)數(shù))的所有項(xiàng)集。算法的第一次掃描僅僅計(jì)算每個(gè)項(xiàng)目的具體支持度，以確定長(zhǎng)度為1的頻繁項(xiàng)集。在后繼的每一次掃描中，首先使用在前一次獲得的頻繁項(xiàng)集Lk-1和Apriori-gen函數(shù)產(chǎn)生的候選項(xiàng)集q，接著掃描數(shù)據(jù)庫(kù)，計(jì)算Ck中候選項(xiàng)的支持度，最后確定候選項(xiàng)集中哪些真正成為頻繁項(xiàng)集。重復(fù)上述過(guò)程直到再也發(fā)現(xiàn)不了新的頻繁項(xiàng)集為止。第101頁(yè)，共176頁(yè)，2023年，2月20日，星期五DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanDApriori算法實(shí)例設(shè)定最小支持度閾值為2

第102頁(yè)，共176頁(yè)，2023年，2月20日，星期五交易號(hào)項(xiàng)集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3設(shè)定最小支持度閾值為2

第103頁(yè)，共176頁(yè)，2023年，2月20日，星期五掃描D，對(duì)每個(gè)候選項(xiàng)計(jì)數(shù)，生成C1：項(xiàng)集支持度計(jì)數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2第104頁(yè)，共176頁(yè)，2023年，2月20日，星期五比較候選項(xiàng)支持度計(jì)數(shù)與最小支持度計(jì)數(shù)，生成L1：項(xiàng)集支持度計(jì)數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2第105頁(yè)，共176頁(yè)，2023年，2月20日，星期五由L1產(chǎn)生候選集C2：

項(xiàng)集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝第106頁(yè)，共176頁(yè)，2023年，2月20日，星期五再次掃描D，對(duì)每個(gè)候選項(xiàng)計(jì)數(shù)，產(chǎn)生L2：項(xiàng)集支持度計(jì)數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2第107頁(yè)，共176頁(yè)，2023年，2月20日，星期五對(duì)L2進(jìn)行連接&剪枝，產(chǎn)生C3，即最終結(jié)果。項(xiàng)集｛I1，I2，I3｝｛I1，I2，I5｝第108頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法Apriori算法的局限性由于依賴(lài)于候選項(xiàng)集產(chǎn)生頻繁項(xiàng)集的理論（Apriori類(lèi)算法）所開(kāi)發(fā)的算法具有先天的弱點(diǎn)，使得在基于Apriori算法開(kāi)發(fā)的應(yīng)用沒(méi)有實(shí)質(zhì)性突破。Han等提出的一種新的算法理論，用一種壓縮的數(shù)據(jù)結(jié)構(gòu)(FP-tree)存儲(chǔ)關(guān)聯(lián)規(guī)則挖掘所需的全部數(shù)據(jù)信息，通過(guò)對(duì)源數(shù)據(jù)的兩次掃描，將數(shù)據(jù)信息存到這種結(jié)構(gòu)里，避開(kāi)了產(chǎn)生候選項(xiàng)集的步驟，極大地減少了數(shù)據(jù)交換和頻繁匹配的開(kāi)銷(xiāo)。這就是所謂無(wú)候選項(xiàng)集產(chǎn)生的算法(FrequentPatternsGrowth,FP-Growth)。第109頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.3算法實(shí)現(xiàn)改進(jìn)的算法——FP-growth(1)它構(gòu)造了一種新穎的、緊湊的數(shù)據(jù)結(jié)構(gòu)FP-tree。它是一種擴(kuò)展的前綴樹(shù)結(jié)構(gòu)，存儲(chǔ)了關(guān)于頻繁模式數(shù)量的重要信息。(2)開(kāi)發(fā)了基于FP-tree的模式片斷成長(zhǎng)算法，它從長(zhǎng)度為1的頻繁模式開(kāi)始，只檢查它的條件模式構(gòu)建它的條件模式樹(shù)，并且在這個(gè)樹(shù)上遞歸地進(jìn)行挖掘。模式的成長(zhǎng)通過(guò)聯(lián)合條件模式樹(shù)新產(chǎn)生的后綴模式實(shí)現(xiàn)。(3)挖掘過(guò)程中采用的搜索技術(shù)是基于分區(qū)的，通過(guò)分割再解決的方法，而不是Apriori類(lèi)算法的自下向上產(chǎn)生頻繁模式的集合。第110頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.2.2典型算法FP-growth算法的主要思想(P198)

該算法主要是為了克服類(lèi)Apriori算法的產(chǎn)生候選項(xiàng)集的缺點(diǎn)，通過(guò)采用一種新的數(shù)據(jù)結(jié)構(gòu)FP-tree來(lái)達(dá)到目的。優(yōu)點(diǎn)：只掃描數(shù)據(jù)庫(kù)二次，并且不用產(chǎn)生候選項(xiàng)集，提高了效率。第111頁(yè)，共176頁(yè)，2023年，2月20日，星期五FP-growth算法實(shí)現(xiàn)交易編號(hào)所有購(gòu)物項(xiàng)（排序后的）頻繁項(xiàng)100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p其中，最小支持度閾值為3第112頁(yè)，共176頁(yè)，2023年，2月20日，星期五FP-growth算法實(shí)現(xiàn)null{}b:1f:3c:1b:1p:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:23.f,b4.c,b,pf:1c:1m:1p:1a:11.f,c,a,m,p2.f,c,a,b,m5.f,c,a,m,pFP-growth算法樹(shù)的構(gòu)造

第113頁(yè)，共176頁(yè)，2023年，2月20日，星期五FP-growth算法實(shí)例生成的FP樹(shù)

節(jié)點(diǎn)鏈性質(zhì)對(duì)任意頻繁項(xiàng)ai，順著ai的節(jié)點(diǎn)鏈，從ai的頭開(kāi)始，可以找到包含ai的所有頻繁模式。第114頁(yè)，共176頁(yè)，2023年，2月20日，星期五FP-growth與Apriori的比較DatasetT25I20D10K第115頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3聚類(lèi)3.3.1定義3.3.2聚類(lèi)算法

3.1.2.1聚類(lèi)方法分類(lèi)

3.1.2.2K均值算法

3.1.2.3K中心點(diǎn)算法

3.1.2.4C均值算法

第116頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.1定義聚類(lèi)分析從紛繁復(fù)雜的數(shù)據(jù)中，根據(jù)最大化類(lèi)內(nèi)相似性、最小化類(lèi)間相似性的原則進(jìn)行聚類(lèi)或分組。即使得在一個(gè)簇內(nèi)的對(duì)象具有高相似性，而不同簇間的對(duì)象具有低相似性的過(guò)程。第117頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.2.1聚類(lèi)方法分類(lèi)基于劃分的聚類(lèi)方法基于層次的聚類(lèi)方法基于密度的聚類(lèi)方法基于網(wǎng)格的聚類(lèi)方法基于模型的聚類(lèi)方法

第118頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.2.1聚類(lèi)方法分類(lèi)基于劃分的聚類(lèi)方法給定一個(gè)由n個(gè)對(duì)象組成的數(shù)據(jù)集合，對(duì)此數(shù)據(jù)集合構(gòu)建k個(gè)劃分，每個(gè)劃分代表一個(gè)簇，即將數(shù)據(jù)集合分成多個(gè)簇的算法。要求：①每個(gè)簇至少有一個(gè)對(duì)象；②每個(gè)對(duì)象必須且僅屬于一個(gè)簇。典型算法k-均值和k-中心點(diǎn)算法等。第119頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.2.1聚類(lèi)方法分類(lèi)基于層次的聚類(lèi)方法對(duì)給定的數(shù)據(jù)集合進(jìn)行層層分解的聚類(lèi)過(guò)程，具體地主要包括凝聚法和分裂法。凝聚法指起初每個(gè)對(duì)象被認(rèn)為是一個(gè)簇，然后不斷合并相似的簇，直到達(dá)到一個(gè)令人滿意的終止條件；分裂法恰恰相反，先把所有的數(shù)據(jù)歸于一個(gè)簇，然后不斷分裂彼此相似度最小的數(shù)據(jù)集，使簇被分裂成更小的簇，直到達(dá)到一個(gè)令人滿意的終止條件。根據(jù)簇間距離度量方法的不同，層次法可分為不同的種類(lèi)。常用的距離度量方法包括：最小距離、最大距離、平均值距離和平均距離等。

典型算法：CURE、Chameleon和BIRCH等

第120頁(yè)，共176頁(yè)，2023年，2月20日，星期五基于層次的聚類(lèi)方法這類(lèi)方法不需要預(yù)先給定參數(shù)（聚類(lèi)數(shù)），但需要終止條件。Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)第121頁(yè)，共176頁(yè)，2023年，2月20日，星期五CURE算法描述隨機(jī)選取s個(gè)樣本；將所有樣本劃分為p個(gè)簇，每個(gè)簇的樣本數(shù)是s/p；

將每個(gè)簇劃分為q個(gè)子集，每個(gè)子集樣本數(shù)是s/pq

刪除孤立點(diǎn)數(shù)據(jù)隨機(jī)取如果一個(gè)簇變化緩慢，則刪除該簇合并其中的部分子集

第122頁(yè)，共176頁(yè)，2023年，2月20日，星期五CURE算法－DataPartitioningandClusterings=50p=2s/p=25xxxyyyyxyxs/pq=5第123頁(yè)，共176頁(yè)，2023年，2月20日，星期五CURE算法－ShrinkingRepresentativePointsxyxyShrinkthemultiplerepresentativepointstowardsthegravitycenterbyafractionof.Multiplerepresentativescapturetheshapeofthecluster第124頁(yè)，共176頁(yè)，2023年，2月20日，星期五CHAMELEON算法CHAMELEON算法是由G.Karypis,E.H.Han和V.Kumar在1999年提出的一種動(dòng)態(tài)層次聚類(lèi)方法。基于動(dòng)態(tài)模型計(jì)算相似性只有當(dāng)兩個(gè)類(lèi)之間的相似性高于類(lèi)內(nèi)對(duì)象的相似性時(shí)合并兩個(gè)類(lèi)。本質(zhì)上，是一個(gè)兩階段算法1.首先，使用圖分割算法將數(shù)據(jù)集合劃分為多個(gè)子集；2.然后，使用層次聚類(lèi)中的凝聚方法將這些子集進(jìn)行反復(fù)的合并，直至獲得最終的聚類(lèi)結(jié)果。第125頁(yè)，共176頁(yè)，2023年，2月20日，星期五CHAMELEON算法ConstructSparseGraphPartitiontheGraphMergePartitionFinalClustersDataSet第126頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.2.1聚類(lèi)方法分類(lèi)基于密度的聚類(lèi)方法這類(lèi)算法的思想是，只要某簇鄰近區(qū)域的密度超過(guò)設(shè)定的某一閾值，則擴(kuò)大簇的范圍，繼續(xù)聚類(lèi)。這類(lèi)算法可以獲得任意形狀的簇。典型算法：DBSCAN、OPTICS和DENCLUE等第127頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.2.1聚類(lèi)方法分類(lèi)基于網(wǎng)格的聚類(lèi)方法基于網(wǎng)格的聚類(lèi)算法首先將問(wèn)題空間量化為有限數(shù)目的單元，形成一個(gè)空間網(wǎng)格結(jié)構(gòu)，隨后聚類(lèi)在這些網(wǎng)格之間進(jìn)行。這類(lèi)算法速度較快。典型算法：STING、WareCluster和CLIQUE等

第128頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.2.1聚類(lèi)方法分類(lèi)基于模型的聚類(lèi)方法基于模型的聚類(lèi)算法為每個(gè)簇假定一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。所基于的假設(shè)是：數(shù)據(jù)是根據(jù)潛在的概率分布生成的。典型算法：COBWEB和神經(jīng)網(wǎng)絡(luò)算法等。第129頁(yè)，共176頁(yè)，2023年，2月20日，星期五3.3.2.1聚類(lèi)方法分類(lèi)上述方法屬于傳統(tǒng)聚類(lèi)的范疇。一般地，傳統(tǒng)聚類(lèi)算法對(duì)于維度較低的數(shù)據(jù)集較有效，而當(dāng)維度較高時(shí)，可能就不適合了。此外，大型數(shù)據(jù)庫(kù)的聚類(lèi)研究受到越來(lái)越多的重視。隨著數(shù)據(jù)庫(kù)技術(shù)的普及，積累了大量的數(shù)據(jù)信息，因此這一分支成為一個(gè)研究熱點(diǎn)。

第130頁(yè)，共176頁(yè)，2023年，2月20日，星期五模式矩陣一般地，數(shù)據(jù)對(duì)象采用矢量表示法，即通過(guò)一個(gè)在多維空間中的矢量，來(lái)描述一個(gè)對(duì)象多方面的特征。矢量的每個(gè)維度描述對(duì)象的一個(gè)特征。多個(gè)對(duì)象的矢量構(gòu)成一個(gè)模式矩陣（PatternMatrix），即（xij）mn

其中每行代表一個(gè)對(duì)象，每列描述一個(gè)特征。第131頁(yè)，共176頁(yè)，2023年，2月20日，星期五相似度在各種聚類(lèi)算法中，通常是需要借助量化的指標(biāo)以表征數(shù)據(jù)對(duì)象之間的特征差異和不同，稱(chēng)之為聚類(lèi)統(tǒng)計(jì)量。聚類(lèi)統(tǒng)計(jì)量包括：距離或相似度。第132頁(yè)，共176頁(yè)，2023年，2月20日，星期五標(biāo)準(zhǔn)化由于不同的特征采用不同的度量標(biāo)準(zhǔn)或尺度，這將對(duì)聚類(lèi)結(jié)果產(chǎn)生不同的影響，為了消除這一差別，常進(jìn)行標(biāo)準(zhǔn)化變換，使所有的特征能用一個(gè)共同的標(biāo)準(zhǔn)度量。第133頁(yè)，共176頁(yè)，2023年，2月20日，星期五距離的計(jì)算標(biāo)準(zhǔn)化處理后，計(jì)算對(duì)象間的距離最常用：歐氏距離，曼哈頓距離（又稱(chēng)絕對(duì)距離）、明考斯基（Minkovski）距離等方法。

第134頁(yè)，共176頁(yè)，2023年，2月20日，星期五相似度的計(jì)算n個(gè)對(duì)象彼此之間的相似性或近似性可通過(guò)相似（異）度矩陣（DissimilarityMatrix）表示。它是一個(gè)nm維、對(duì)角線元素為1的對(duì)稱(chēng)矩陣，即（rij）nm。其中，rij是i對(duì)象和j之間相似性的量化表示。通常其值是非負(fù)的。對(duì)象和關(guān)系越親密，其絕對(duì)值越接近1；彼此關(guān)系越疏遠(yuǎn)，其值越接近于0。對(duì)象間相似度的計(jì)算方法包括：夾角余弦法、相關(guān)系數(shù)法及指數(shù)相似系數(shù)法等。

第135頁(yè)，共176頁(yè)，2023年，2月20日，星期五評(píng)價(jià)聚類(lèi)方法的標(biāo)準(zhǔn)聚類(lèi)分析是一種無(wú)監(jiān)督的學(xué)習(xí)，事先對(duì)給定數(shù)據(jù)集合的結(jié)構(gòu)一無(wú)所知，沒(méi)有利用任何先驗(yàn)知識(shí)。無(wú)論采用哪種聚類(lèi)算法，其聚類(lèi)結(jié)果的合理性和有效性都有待評(píng)價(jià)。

聚類(lèi)有效性對(duì)聚類(lèi)分析具有重要意義，被認(rèn)為是聚類(lèi)分析的一個(gè)瓶頸。對(duì)于相同的數(shù)據(jù)集合，采用不同的聚類(lèi)方法，可能得到不同的聚類(lèi)結(jié)果。

即便是采用同一種聚類(lèi)方法，若選擇不同的初始參數(shù)（如聚類(lèi)數(shù)、聚類(lèi)中心等）也可能會(huì)得到不同的聚類(lèi)結(jié)果。

第136頁(yè)，共176頁(yè)，2023年，2月20日，星期五例如，采用相同的k-均值聚類(lèi)算法對(duì)同一個(gè)wine測(cè)試集進(jìn)行聚類(lèi)實(shí)驗(yàn)，當(dāng)預(yù)設(shè)聚類(lèi)類(lèi)別數(shù)分別為1～8時(shí)，則所得到的聚類(lèi)正確率是不同的，如柱狀圖所示。第137頁(yè)，共176頁(yè)，2023年，2月20日，星期五評(píng)價(jià)聚類(lèi)方法的標(biāo)準(zhǔn)可伸縮性即算法中模式數(shù)發(fā)生變化的情況。有些算法在模式數(shù)小的條件下，算法的性能很好，但是模式數(shù)增大后，算法性能下降。如PAM算法是一種k-中心點(diǎn)算法，它對(duì)小的數(shù)據(jù)集合非常有效，但對(duì)大的數(shù)據(jù)集合則沒(méi)有良好的可伸縮性。高維性即算法中模式屬性個(gè)數(shù)發(fā)生變化的情況。同樣，有些算法只擅長(zhǎng)處理低維數(shù)據(jù)。在高維空間中聚類(lèi)是一個(gè)挑戰(zhàn)，特別是數(shù)據(jù)有可能非常稀疏和偏斜。

第138頁(yè)，共176頁(yè)，2023年，2月20日，星期五評(píng)價(jià)聚類(lèi)方法的標(biāo)準(zhǔn)發(fā)現(xiàn)任意形狀的聚類(lèi)一個(gè)簇可能是任意形狀的，但一般的聚類(lèi)算法是基于歐氏距離和曼哈頓距離度量實(shí)現(xiàn)聚類(lèi)，更趨于發(fā)現(xiàn)球狀簇。在這方面，基于密度的聚類(lèi)方法較好。處理噪聲數(shù)據(jù)的能力噪聲數(shù)據(jù)可能是數(shù)據(jù)本身不完整