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

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

3.1.2.1決策樹算法

3.1.2.2CLS算法

3.1.2.3ID3算法

3.1.2.4C4.5算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

outlooktemperaturehumiditywindyclass

1sunnyhothighfalseN2sunnyhothightrueN3overcasthothighfalseP4rainhothighfalseP5raincoolnormalfalseP6raincoolnormaltrueN7overcastcoolnormaltrueP8sunnymildhighfalseN9sunnycoolnormalfalseP10rainmildnormalfalseP11sunnymildnormaltrueP12overcastmildhightrueP13overcasthotnormalfalseP14rainmildhightrueN

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

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

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

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

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

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

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

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

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

x

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

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

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

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

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

(1)語義相似

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

(3)目標特征

(4)個體相似性

2．相似性計算

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

(2)改進的Tversky匹配法

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

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

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

則

前

提規(guī)

則

結(jié)

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

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

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

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

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

R:X=>Y

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

關(guān)聯(lián)規(guī)則可以理解為一個命題，即如果一個交易支持項集X，則它也以一定的可能性支持項集Y，這一可能性稱之為規(guī)則的可信度，記為conf(R)或C(R)第85頁，共176頁，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頁，共176頁，2023年，2月20日，星期五3.2.1基本概念關(guān)聯(lián)規(guī)則的性質(zhì)規(guī)則的非結(jié)合性規(guī)則的不可分解性規(guī)則的不可傳遞性規(guī)則的可擴展性第87頁，共176頁，2023年，2月20日，星期五關(guān)聯(lián)規(guī)則挖掘?qū)嵗?/p>

通過發(fā)現(xiàn)顧客放入其購物籃中不同商品之間的聯(lián)系，分析顧客的購買習慣。通過了解哪些商品頻繁地被顧客同時購買，這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營銷策略。例如，在同一次購物中，如果顧客購買牛奶的同時，也購買面包（和什么類型的面包）的可能性有多大？這種信息可以引導銷售，可以幫助零售商有選擇地經(jīng)銷和安排貨架。例如，將牛奶和面包盡可能放近一些，可以進一步刺激一次去商店同時購買這些商品。第88頁，共176頁，2023年，2月20日，星期五關(guān)聯(lián)規(guī)則挖掘?qū)嵗徫锘@關(guān)聯(lián)分析實例圖第89頁，共176頁，2023年，2月20日，星期五3.2.1基本概念CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer“啤酒與尿布”的關(guān)聯(lián)規(guī)則第90頁，共176頁，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頁，共176頁，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頁，共176頁，2023年，2月20日，星期五3.2.2典型算法AIS算法的主要思想其主要思想是一邊掃描數(shù)據(jù)庫，一邊產(chǎn)生候選項集并累計支持度。具體地說，在對數(shù)據(jù)庫進行第k次掃描時，候選項集是由第k-1次掃描所產(chǎn)生的邊界集(frontierset)通過增加當前事務(wù)中的項得到，同時計算候選項集中元素的支持數(shù)，直到某次掃描所產(chǎn)生的邊界集為空。缺點：生成的候選項集太大。第93頁，共176頁，2023年，2月20日，星期五3.2.2典型算法Apriori算法的主要思想該算法利用了頻繁項集所具有的任意頻繁項集的子集都是頻繁項集的這一性質(zhì)對數(shù)據(jù)庫進行多次掃描:第一次掃描得到頻繁項集的集合L0

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

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

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

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

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

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

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

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

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

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

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

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

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

該算法主要是為了克服類Apriori算法的產(chǎn)生候選項集的缺點，通過采用一種新的數(shù)據(jù)結(jié)構(gòu)FP-tree來達到目的。優(yōu)點：只掃描數(shù)據(jù)庫二次，并且不用產(chǎn)生候選項集，提高了效率。第111頁，共176頁，2023年，2月20日，星期五FP-growth算法實現(xiàn)交易編號所有購物項（排序后的）頻繁項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頁，共176頁，2023年，2月20日，星期五FP-growth算法實現(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算法樹的構(gòu)造

第113頁，共176頁，2023年，2月20日，星期五FP-growth算法實例生成的FP樹

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

3.1.2.1聚類方法分類

3.1.2.2K均值算法

3.1.2.3K中心點算法

3.1.2.4C均值算法

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

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

典型算法：CURE、Chameleon和BIRCH等

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

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

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

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

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

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

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

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

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

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

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

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

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