Python數(shù)據(jù)挖掘與機器學習第2版 課件 魏偉一 第 7 章 分類；第 8 章 聚類

Python數(shù)據(jù)挖掘與機器學習第7章分類第7章分類本章內容分類概述決策樹規(guī)約K近鄰算法支持向量機樸素貝葉斯分類模型評估與選擇組合分類10十一月202421

分類概述3分類是一種重要的數(shù)據(jù)分析形式。數(shù)據(jù)分類也稱為監(jiān)督學習，包括學習階段（構建分類模型）和分類階段（使用模型預測給定數(shù)據(jù)的類標號）兩個階段。數(shù)據(jù)分類方法主要有決策樹歸納、貝葉斯分類、K-近鄰分類、支持向量機SVM等方法。2

決策樹規(guī)約4決策樹屬于經典的十大數(shù)據(jù)挖掘算法之一，是一種類似于流程圖的樹型結構，其規(guī)則就是if…then…的思想，用于數(shù)值型因變量的預測和離散型因變量的分類。決策樹算法簡單直觀，容易解釋，而且在實際應用中具有其他算法難以比肩的速度優(yōu)勢。決策樹方法在分類、預測和規(guī)則提取等領域有廣泛應用。在20世紀70年代后期和80年代初期，機器學習研究人員J.RossQuinlan開發(fā)了決策樹算法，稱為迭代的二分器（IterativeDichotomiser,ID3），使得決策樹在機器學習領域得到極大發(fā)展。Quinlan后來又提出ID3的后繼C4.5算法，成為新的監(jiān)督學習算法的性能比較基準。1984年幾位統(tǒng)計學家又提出了CART分類算法。2

決策樹規(guī)約5決策樹的構建原理決策樹是樹狀結構，它的每個葉結點對應著一個分類，非葉結點對應著在某個屬性上的劃分，根據(jù)樣本在該屬性上的不同取值將其劃分為若干子集。ID3、C4.5和CART算法都采用貪心（即非回溯）方法，以自頂向下遞歸的分治方式構造，隨著樹的構建，訓練集遞歸地被劃分為子集。2

決策樹規(guī)約62

決策樹規(guī)約7ID3算法ID3算法是決策樹系列中的經典算法之一，包含了決策樹作為機器學習算法的主要思想。但ID3算法在實際應用中有諸多不足，因此之后提出了大量的改進算法，如C4.5算法和CART算法。構造決策樹的核心問題是在每一步如何選擇恰當?shù)膶傩詫颖咀霾鸱?。ID3算法使用信息增益作為屬性選擇度量，C4.5使用增益率進行屬性選擇度量，CART算法則使用基尼指數(shù)。2

決策樹規(guī)約82

決策樹規(guī)約92

決策樹規(guī)約10Gain（A）表明通過A上的劃分獲得了多少信息增益。選擇具有最高信息增益的屬性A作為結點N的分裂屬性，等價于在“能做最佳分類”的屬性A上劃分，可以使得完成元組分類還需要的信息最小。2

決策樹規(guī)約112

決策樹規(guī)約10十一月2024122

決策樹規(guī)約緊接著，計算每個屬性的期望信息需求。從屬性年齡開始，需要對每個類考察“是”和“否”元組的分布。對于年齡的類“青年”，有5個取值，分別對應2個“是”和3個“否”，即為I(2,3)，同理，類“中年”對應的是I(4,0)，類“老年”對應的是I(3,2)，因此，如果元組根據(jù)年齡劃分，則對D中的元組進行分類所需要的期望信息為：10十一月2024132

決策樹規(guī)約10十一月2024142

決策樹規(guī)約假設屬性A是連續(xù)的，必須確定A的最佳分裂點，其中分裂點是A上的閾值。首先，對屬性A的取值排序。典型地，每對相鄰值的中點被看作可能的分裂點，給定A的v個值，需要計算v-1個可能的劃分。確定A的最佳分裂點只需掃描一遍這些值，對每個可能分裂點，分別計算其信息增益值，具有最大信息增益的分裂點即為最佳分裂值。自該分裂點把整個取值區(qū)間劃分為兩部分，相應的依據(jù)記錄在該屬性上的取值，也將記錄劃分為兩部分。10十一月2024152

決策樹規(guī)約ID3算法的優(yōu)缺點ID3算法理論清晰，方法簡單，學習能力較強。但也存在以下一些缺點。（1）信息增益的計算依賴于特征數(shù)目較多的特征，而屬性取值最多的屬性并不一定最優(yōu)。比如一個變量有2個值，各為1/2，另一個變量為3個值，各為1/3，其實他們都是完全不確定的變量，但是取3個值比取2個值的信息增益大。（2）ID3沒考慮連續(xù)特征，比如長度、密度都是連續(xù)值，無法在ID3運用。（3）ID3算法是單變量決策樹（在分支結點上只考慮單個屬性），許多復雜概念的表達困難，屬性相互關系強調不夠，容易導致決策樹中子樹的重復或有些屬性在決策樹的某一路徑上被檢驗多次；（4）算法的抗噪性差，訓練例子中正例和反例的比例較難控制，而且沒有考慮缺失值和過擬合問題。10十一月2024162

決策樹規(guī)約C4.5算法原理Quinlan在1993年提出了ID3的改進版本C4.5算法。它與ID3算法的不同主要有以下幾點。（1）分支指標采用增益比例，而不是ID3所使用的信息增益；（2）按照數(shù)值屬性值的大小對樣本排序，從中選擇一個分割點，劃分數(shù)值屬性的取值區(qū)間，從而將ID3的處理能力擴充到數(shù)值屬性上來；（3）將訓練樣本集中的位置屬性值用最常用的值代替，或者用該屬性的所有取值的平均值代替，從而處理缺少屬性值的訓練樣本；（4）使用K次迭代交叉驗證，評估模型的優(yōu)劣程度；（5）根據(jù)生成的決策樹，可以產生一個if-then規(guī)則的集合，每一個規(guī)則代表從根結點到葉結點的一條路徑。10十一月2024172

決策樹規(guī)約10十一月2024182

決策樹規(guī)約10十一月202419C4.5算法的優(yōu)缺點C4.5是基于ID3算法進行改進的算法，目標是通過學習，找到一個從屬性值到類別的映射關系，并且這個映射能用于對新的未知類別進行分類。C4.5算法產生的分類規(guī)則易于理解，準確率高，改進了ID3算法傾向于選擇具有最大增益率的屬性作為分裂屬性的缺點，而且相比于ID3算法，能處理非離散數(shù)據(jù)或不完整數(shù)據(jù)。C4.5由于使用了熵模型，里面有大量的耗時的對數(shù)運算，如果是連續(xù)值還需要大量的排序運算，而且C4.5只能用于分類。2

決策樹規(guī)約10十一月202420CART算法原理：分類回歸樹（ClassificationAndRegressionTree,CART）算法最早由Breiman等人提出，目前已在統(tǒng)計領域和數(shù)據(jù)挖掘技術中普遍使用。Python中的scikit-learn模塊的Tree子模塊主要使用CART算法實現(xiàn)決策樹。基尼指數(shù)CART算法用基尼系數(shù)代替熵模型?；嶂笖?shù)度量數(shù)據(jù)分區(qū)或訓練元組D的不純度，定義為：2

決策樹規(guī)約10十一月202421樹剪枝隨著決策樹深度的增加，模型的準確度肯定會越來越好。但是對于新的未知數(shù)據(jù)，模型的表現(xiàn)會很差，產生的決策樹會出現(xiàn)過分適應數(shù)據(jù)的問題。而且，由于數(shù)據(jù)中的噪聲和孤立點，許多分枝反映的是訓練數(shù)據(jù)中的異常，對新樣本的判定很不精確。為防止構建的決策樹出現(xiàn)過擬合，需要對決策樹進行剪枝。決策樹的剪枝方法一般有預剪枝和后剪枝方法。2

決策樹規(guī)約10十一月2024221.預剪枝當在某一結點選擇使用某一屬性作為劃分屬性時，會由于本次劃分而產生幾個分支。預剪枝就是對劃分前后兩棵樹的泛化性能進行評估，根據(jù)評估結果決定該結點是否進行劃分。如果在一個結點劃分樣本將導致低于預定義臨界值的分裂（如使用信息增益度量）則提前停止樹的構造，但是選擇一個合適的臨界值往往非常困難。2.后剪枝在后剪枝方法中，先構造一顆完整的決策樹，然后從下向上計算每個結點的經驗熵，遞歸地從決策樹的葉子結點進行回縮，通過計算回縮前后的損失函數(shù)并進行比較判斷是否進行剪枝。剪枝可以只在樹的某一部分進行，即局部剪枝，這樣極大提高了剪枝的效率。第7章

決策樹11/10/2024表7.2ID3、C4.5和CART算法的主要特點算法支持模型樹結構特征選擇連續(xù)值處理缺失值處理剪枝屬性多次使用ID3分類多叉樹信息增益不支持不支持不支持不支持C4.5分類多叉樹信息增益率支持支持支持不支持CART分類回歸二叉樹基尼指數(shù)支持支持支持支持2

決策樹規(guī)約10十一月202424sklearn.tree.DecisionTreeClassifier實現(xiàn)了決策樹的構建，在該方法中，參數(shù)criterion規(guī)定了該決策樹所采用的

最佳分割屬性的判決方法，取值有“gini”和“entropy”兩種；max_depth限定了決策樹的最大深度，對于防止過擬合非常有用。參數(shù)min_samples_leaf限定了葉子結點包含的最小樣本數(shù)。iris=load_iris()X_train,X_test,y_train,y_test=train_test_split(iris.data,iris.target,test_size=0.20,random_state=30,shuffle=True)clf=tree.DecisionTreeClassifier(criterion='entropy')#criterion缺省為'gini'clf=clf.fit(X_train,y_train)plt.figure(dpi=150)tree.plot_tree(clf,feature_names=iris.feature_names,class_names=iris.target_names)第

7章分類10十一月202425最近鄰分類算法KNN

(k-NearestNeighbor)3K近鄰算法10十一月202426K近鄰（k-NearestNeighborClassification，KNN）算法是機器學習算法中最基礎、最簡單的算法之一，屬于惰性學習法。3K近鄰算法KNN算法基于類比學習，即通過將給定的檢驗元組與和它相似的元組進行比較來學習。訓練元組用n個屬性描述，每個元組代表n維空間的一個點。所有的訓練元組都存放在n維模式空間中。當給定一個未知元組時，KNN搜索模式空間，根據(jù)距離函數(shù)計算待分類樣本X和每個訓練樣本的距離（作為相似度），選擇與待分類樣本距離最小的K個樣本作為X的K個最近鄰，最后以X的K個最近鄰中的大多數(shù)樣本所屬的類別作為X的類別。10十一月2024273K近鄰算法如圖7-4所示，有方塊和三角形兩類數(shù)據(jù)，它們分布在二維特征空間中。假設有一個新數(shù)據(jù)（圓點）需要預測其所屬的類別，根據(jù)“物以類聚”，可以找到離圓點最近的幾個點，以它們中的大多數(shù)點的類別決定新數(shù)據(jù)所屬的類別。如果k=3，由于圓點近鄰的3個樣本中，三角形占比2/3，則認為新數(shù)據(jù)屬于三角形類別。同理，k=5，則新數(shù)據(jù)屬于正方形類別。10十一月2024283K近鄰算法如何度量樣本之間的距離（或相似度）是KNN算法的關鍵步驟之一。常見的數(shù)值屬性的相似度度量方法包括：閔可夫斯基距離（當參數(shù)p=2時為歐幾里得距離，參數(shù)p=1時為曼哈頓距離）余弦相似度、皮爾遜相似系數(shù)、漢明距離、杰卡德相似系數(shù)等。在計算距離之前，需要把每個屬性的值規(guī)范化。對于算法中的K值，一般通過實驗確定。K-最近鄰算法是一種非參數(shù)模型。10十一月2024293K近鄰算法10十一月2024303K近鄰算法10十一月202431優(yōu)點：1.算法思路較為簡單，易于實現(xiàn)；2.當有新樣本要加入訓練集中時，無需重新訓練（即重新訓練的代價低）；3.計算時間和空間線性于訓練集的規(guī)模，對某些問題而言這是可行的。缺點：1.分類速度慢。2.各屬性的權重相同，影響準確率。3.樣本庫容量依賴性較強.4.K值不好確定。K=3時，綠色未知點屬于

紅色三角；K=5時，屬于藍色正方形3K近鄰算法3K近鄰算法10十一月202433支持向量機（SupportVetorMachine，SVM）10十一月2024344支持向量機支持向量機（SupportVetorMachine，SVM）由Vapnik等人于1995年首先提出，在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并推廣到人臉識別、行人檢測和文本分類等其他機器學習問題中。SVM建立在統(tǒng)計學習理論的VC維理論和結構風險最小原理基礎上，根據(jù)有限的樣本信息在模型的復雜性和學習能力之間尋求最佳平衡，以求獲得最好的推廣能力。SVM可以用于數(shù)值預測和分類。10十一月2024354支持向量機36支持向量機（SupportVetorMachine，SVM）是一種對線性和非線性數(shù)據(jù)進行分類的方法。SVM使用一種非線性映射，把原訓練數(shù)據(jù)映射到較高的維上，在新的維上，搜索最佳分離超平面。由簡至繁SVM可分類為三類：線性可分（linearSVMinlinearlyseparablecase）的線性SVM、線性不可分的線性SVM、非線性（nonlinear）SVM4支持向量機算法原理：支持向量機是一種對線性和非線性數(shù)據(jù)進行分類的方法。它使用一種非線性映射，把原始訓練數(shù)據(jù)映射到較高的維上，在新的維上，搜索最佳分離超平面。SVM可分類為三類：線性可分的線性SVM、線性不可分的線性SVM、非線性SVM。如果訓練數(shù)據(jù)線性可分，則通過硬間隔最大化學習一個線性分類器即線性可分支持向量機，也稱為硬間隔支持向量機；如果訓練數(shù)據(jù)近似線性可分，則通過軟間隔最大化學習得到一個線性分類器即線性支持向量機，也稱為軟間隔支持向量機；對于數(shù)據(jù)非線性可分的情況，通過擴展線性SVM的方法，得到非線性的SVM，即采用非線性映射把輸入數(shù)據(jù)變換到較高維空間，在新的空間搜索分離超平面。10十一月2024374支持向量機1.數(shù)據(jù)線性可分的情況SVM的主要目標是找到最佳超平面，以便在不同類的數(shù)據(jù)點之間進行正確分類。超平面的維度等于輸入特征的數(shù)量減去1。圖7-5顯示了分類的最佳超平面和支持向量（實心的數(shù)據(jù)樣本）。10十一月202438?4支持向量機10十一月202439DistancetoHyperplane40xx'原點到超平面的距離點x到超平面的距離：4支持向量機Margins41“PredictClass=+1”zone“PredictClass=-1”zoneH1：wx+b=1H2：wx+b=-1x-x+M=MarginWidth從分離超平面到到H1上任意點的距離是因此最大邊緣是4支持向量機4支持向量機10十一月2024424支持向量機10十一月2024434支持向量機10十一月2024444支持向量機10十一月2024454支持向量機數(shù)據(jù)非線性可分的情況在某些情況下，訓練數(shù)據(jù)甚至連近似的線性劃分也找不到，線性超平面無法有效劃分正類與負類，而是需要超曲面等非線性劃分。然而，非線性的優(yōu)化問題很難求解。通常的做法是將輸入向量從輸入的空間投射到另一個空間，如圖7-6所示。在這個特征空間中，投射后的特征向量線性可分或者近似線性可分，然后通過線性支持向量機的方法求解。10十一月2024464支持向量機然而這樣做也帶來一個新的問題，即使得投射后的特征向量（近似）線性可分的特征空間維度往往比原輸入空間的維度高很多，甚至具有無限個維度。為了解決新特征空間維度高的問題，引入核方法（KernalMethod），在計算中不需要直接進行非線性變換，從而避免由計算高維度向量帶來的問題。10十一月2024474支持向量機在sklearn中SVM的算法庫分為兩類，一類是分類的算法庫，包括SVC、NuSVC和LinearSVC3個類。另一類是回歸算法庫，包括SVR、NuSVR和LinearSVR3個類。相關的類都包括在sklearn.svm模塊之中。10十一月2024484支持向量機SVM本是二分類的分類算法，但由于其強大的分類性能，也被廣泛應用于多分類領域。在方法SVC中的參數(shù)ovo和ovr就是多分類時需要進行選擇的兩種不同策略。參數(shù)ovo（oneversusone）即一對一的分類器，這時對K個類別需要構建K*(K-1)/2個分類器；ovr（oneversusrest）指一對其他，這時對K個類別只需要構建K個分類器。11/10/20245樸素貝葉斯網絡貝葉斯分類是一類分類算法的總稱，這類算法均以貝葉斯定理（BayesTheorem）為基礎，采用了概率推理方法。貝葉斯定理提供了一種計算假設概論的方法。10十一月2024505樸素貝葉斯網絡10十一月2024515樸素貝葉斯網絡高斯樸素貝葉斯分類10十一月2024525樸素貝葉斯網絡10十一月2024535樸素貝葉斯網絡10十一月2024545樸素貝葉斯網絡多項式樸素貝葉斯分類多項式樸素貝葉斯（MultinomialNa?veBayes）經常被用于處理多分類問題，比起原始的樸素貝葉斯分類效果有了較大的提升。其公式如下：10十一月2024555樸素貝葉斯網絡Scikit-learn模塊中有Na?veBayes子模塊，包含了各種貝葉斯算法。關鍵在于將分類器設置為樸素貝葉斯分類器，接著調用分類器訓練并進行分類。10十一月2024566模型評估與選擇構建的分類器總是希望有較好的性能，如何評估分類器性能，需要一些客觀的指標進行評判。比如，如何評估分類器的準確率（模型評估）以及如何在多個分類器中選擇“最好的”一個。分類器性能的度量10十一月2024576模型評估與選擇1.混淆矩陣根據(jù)實際類別與機器學習預測類別的組合（混淆矩陣，ConfusionMatrix）可分為真正例（TruePositive，TP）、假正例（FalsePositive，F(xiàn)P）、假負例（FalseNegative，F(xiàn)N）和真負例（TrueNegative，TN）四種情況。10十一月2024586模型評估與選擇分類器常用評估量（1）準確率和錯誤率分類器在檢驗集上的準確率（Accuracy）被定義為被該分類器正確分類的元組所占的百分比。（2）靈敏性和特效性敏感性又稱真正類率(truepositiverate,TPR)，它表示了分類器所識別出的正實例占所有正實例的比例。特效性是真負例率，即正確識別的負元組的百分比。10十一月2024596模型評估與選擇分類器常用評估量（3）精度和召回率精度和召回率也在分類中廣泛使用。精度（Precision）定義為標記為正例的元組實際為正類的百分比，可以看作精確度的度量，也被稱為查準率。召回率（Recall）定義為正元組標記為正的百分比，是完全性的度量，也被稱為查全率。10十一月2024606模型評估與選擇分類器常用評估量10十一月2024616模型評估與選擇除了基于準確率的度量外，還可以在其他方面進行分類器的比較，主要因素有：速度：構建和使用分類器的計算開銷。魯棒性：對有噪聲或缺失值數(shù)據(jù)分類器做出正確預測的能力。通常魯棒性用噪聲和缺失值漸增的一系列合成數(shù)據(jù)集進行評估?？缮炜s性：對于給定大量數(shù)據(jù)有效構造分類器的能力。通常，可伸縮性用規(guī)模漸增的一系列數(shù)據(jù)集評估?？山忉屝裕簩Ψ诸惼魈峁┑睦斫夂投床焖??？山忉屝允侵饔^的，因為很難評估。比如決策樹和分類規(guī)則一般容易解釋，但隨著它們變得更復雜，其可解釋性也隨之消失。10十一月2024626模型評估與選擇分類器常用評估量（5）P-R曲線評價一個模型的好壞，不能僅靠精確率或者召回率，最好構建多組精確率和召回率，繪制出模型的P-R曲線。在繪制P-R曲線的橫軸是召回率，縱軸是精確率。P-R曲線上的一個點代表著，在某一閾值下，模型將大于該閾值的結果判定為正樣本，小于該閾值的結果判定為負樣本，此時返回結果對應的召回率和精確率。10十一月2024636模型評估與選擇分類器常用評估量（6）接收者操作特征曲線接收者操作特征曲線(ReceiverOperatingCharacteristicCurve，ROC)是一種反映分類模型敏感性和特異性連續(xù)變量的綜合指標，顯示了給定模型的真正例率（TPR）和假正例率（FPR）之間的權衡。ROC通過將連續(xù)變量設定出多個不同的臨界值，從而計算出一系列敏感性和特異性，并以TPR為縱坐標、FPR為橫坐標繪制曲線，曲線下面積越大，診斷準確性越高。ROC曲線上每個點反映著對同一信號刺激的感受性，最靠近坐標圖左上方的點為敏感性和特異性均較高的臨界值。10十一月2024646模型評估與選擇10十一月2024656模型評估與選擇模型選擇當假設空間含有不同的復雜度的模型時，會面臨模型選擇(ModelSelection)問題。我們希望所選擇的模型要與真模型的參數(shù)個數(shù)相同，所選擇的模型的參數(shù)向量與真模型的參數(shù)向量相近。然而，一味追求提高分類器的預測能力，所選擇的模型的復雜度會比真模型要高，這種現(xiàn)象被稱為過擬合（Over-fitting）。過擬合指學習時選擇的模型所含的參數(shù)過多，導致該模型對已知數(shù)據(jù)預測的很好，但對未知數(shù)據(jù)預測很差的現(xiàn)象。因此，模型選擇旨在避免過擬合并提高模型的預測能力。在模型選擇時，不僅要考慮對已知數(shù)據(jù)的預測能力，還要考慮對未知數(shù)據(jù)的預測能力。10十一月2024666模型評估與選擇奧卡姆剃刀定律是機器學習選擇算法時可參照的標準之一。其含義是：在其他條件一樣的情況下，選擇簡單的那個。該定律的意義在于數(shù)據(jù)的擬合和低復雜性之間實際上存在著折衷。理論上假設的解決方案越復雜，就越能擬合數(shù)據(jù)，訓練數(shù)據(jù)誤差就會越低（左下圖）。11/10/2024訓練數(shù)據(jù)誤差未知數(shù)據(jù)的泛化誤差6模型評估與選擇泛化數(shù)據(jù)誤差實際是訓練數(shù)據(jù)誤差與另一個名為過擬合誤差的函數(shù)之和。在泛化誤差最小得情況下，可獲得最佳復雜性。在現(xiàn)實生活中，通常只會獲得訓練數(shù)據(jù)誤差。但實踐表明，如果你不去選擇能夠使訓練數(shù)據(jù)誤差最小化的模型，而是選擇復雜性低一點的模型，算法的表現(xiàn)往往會更好。過擬合是機器學習算法性能不佳得主要緣由。這也是在機器學習中應用奧卡姆剃刀定律的原因。11/10/20246模型評估與選擇1.模型選擇方法模型選擇方法主要有正則化和交叉驗證方法。（1）正則化模型選擇的典型方法是正則化（Regularization）。正則化是結構風險最小化策略的實現(xiàn)，是在經驗風險上加一個正則化項（Regularizer）或懲罰項（Penalty）。正則化項一般是模型復雜度的單調遞增函數(shù)，模型越復雜，正則化值就越大，比如，正則化項可以是模型參數(shù)向量的范數(shù)。10十一月2024696模型評估與選擇10十一月202470正則化符合奧卡姆剃刀（Occam’srazor）原理。奧卡姆剃刀原理應用于模型選擇時認為，在所有可能選擇的模型中，能夠很好地解釋已知數(shù)據(jù)并且盡可能簡單才是最好的模型，也就是應該選擇的模型。從貝葉斯估計的角度來看，正則化項對應于模型的先驗概率?？梢约僭O復雜的模型有較大的先驗概率，簡單的模型有較小的先驗概率。6模型評估與選擇（2）交叉驗證另一種常用的模型選擇方法是交叉驗證（CrossValidation）。如果給定的樣本數(shù)據(jù)充足，進行模型選擇的一種簡單方法是隨機地將數(shù)據(jù)集劃分為訓練集（Trainingset）、驗證集（ValidationSet）和測試集（TestSet）三部分。10十一月2024716模型評估與選擇

1.簡單交叉驗證簡單交叉驗證方法是隨機地將已給數(shù)據(jù)分為訓練集和測試集（如70%的數(shù)據(jù)作為訓練集，30%的數(shù)據(jù)作為測試集），然后用訓練集在各種條件下（如不同的參數(shù)個數(shù)）訓練模型在測試集上評價各個模型的測試誤差，選出測試誤差最小的模型。10十一月202472fromsklearn.model_selectionimporttrain_test_splitimportnumpyasnpX=np.array([[1,2],[3,4],[5,6],[7,8]])y=np.array([1,2,2,1])X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.50,random_state=5)print("X_train:\n",X_train)print("y_train:\n",y_train)print("X_test:\n",X_test)print("y_test:\n",y_test)11/10/20242.k-折交叉驗證在k-折交叉驗證（k-foldCross-Validation）中，首先隨機地將已給數(shù)據(jù)劃分為k個互不相交的大小相同的子集，然后利用k-1個子集的數(shù)據(jù)訓練模型，利用余下的子集測試模型。將這一過程對可能的k種選擇重復進行，最后選出k次評測中平均測試誤差最小的模型。fromsklearn.model_selectionimportKFoldimportnumpyasnpX=np.array([[1,2],[3,4],[5,6],[7,8]])y=np.array([1,2,2,1])kf=KFold(n_splits=2)fortrain_index,test_indexinkf.split(X):print("Train:",train_index,"Validation:",test_index)X_train,X_test=X[train_index],X[test_index]y_train,y_test=y[train_index],y[test_index]6模型評估與選擇

3.留一交叉驗證k折交叉驗證的特殊情形是k=N，即k設置為元組的個數(shù)，稱為留一交叉驗證（Leave-one-outCrossValidation），往往在數(shù)據(jù)缺乏的情況下使用。10十一月202474fromsklearn.model_selectionimportLeaveOneOutimportnumpyasnpX=np.array([[1,2],[3,4],[5,6],[7,8]])y=np.array([1,2,2,1])loo=LeaveOneOut()loo.get_n_splits(X)fortrain_index,test_indexinloo.split(X):print("train:",train_index,"validation:",test_index)第7章分類組合分類器（Ensemble）10十一月2024757組合分類組合分類器（Ensemble）是一個復合模型，由多個分類器組合而成。組合分類器往往比它的成員分類器更準確。10十一月202476VS.7組合分類7組合分類袋裝（Bagging）是一種采用隨機有放回的抽樣選擇訓練數(shù)據(jù)構造分類器進行組合的方法。如同找醫(yī)生看病，選擇多個醫(yī)生，根據(jù)多個醫(yī)生的診斷結果做出最終結果（多數(shù)表決），每個醫(yī)生具有相同的投票權重。10十一月2024787組合分類在sklearn中，Bagging方法由BaggingClassifier統(tǒng)一提供，以用戶輸入的基模型和劃分子集的方法作為參數(shù)。其中，max_samples和max_features控制子集的大小，而bootstrap和bootstrap_features控制數(shù)據(jù)樣本和屬性是否替換。Oob_score=True可使得估計時采用已有的數(shù)據(jù)劃分樣本。10十一月2024797組合分類提升和AdaBoost考慮找醫(yī)生看病的另外一種情況，選擇多個醫(yī)生，根據(jù)多個醫(yī)生的診斷結果做出最終結果（加權表決），每個醫(yī)生具有不同的投票權重。這就是提升（Boosting）的基本思想。10十一月2024807組合分類10十一月2024817組合分類10十一月2024827組合分類10十一月202483scikit-learn中Adaboost類庫包括AdaBoostClassifier和AdaBoostRegressor兩個，AdaBoostClassifier用于分類，AdaBoostRegressor用于回歸。7組合分類隨機森林隨機森林就是通過集成學習的思想將多棵樹集成的一種算法，它的基本單元是決策樹。想象組合分類器中的每個分類器都是一棵決策樹，因此分類器的集合就是一個“森林”。更準確說，每一棵樹都依賴于獨立抽樣，并與森林中所有樹具有相同分布的隨機向量值。隨機森林是利用多個決策樹對樣本進行訓練、分類并預測的一種算法，主要應用于回歸和分類場景。在對數(shù)據(jù)進行分類的同時，還可以給出各個變量的重要性評分，評估各個變量在分類中所起的作用。分類時，每棵樹都投票并且返回得票最多的類。10十一月2024847組合分類隨機森林算法流程（1）訓練總樣本的個數(shù)為N，則單棵決策樹從N個訓練集中有放回的隨機抽取N個作為此單棵樹的訓練樣本（2）令訓練樣例的輸入特征的個數(shù)為M，m遠遠小于M，則我們在每棵決策樹的每個結點上進行分裂時，從M個輸入特征里隨機選擇m個輸入特征，然后從這m個輸入特征里選擇一個最好的進行分裂。m在構建決策樹的過程中不會改變。（3）每棵樹都一直這樣分裂下去，直到該結點的所有訓練樣例都屬于同一類，不需要剪枝。10十一月2024857組合分類2.隨機森林的兩種形式（1）Forest-RI：使用裝袋算法與隨機屬性選擇結合構建。給定d個元組的訓練集D，為組合分類器產生k棵決策樹的一般過程如下：對于每次迭代i（i=1,2,3,…，k），使用有放回的抽樣，由D產生d個元組的訓練集Di。也就是說，每個Di都是D的一個自助樣本，使得某些元組可能在Di出現(xiàn)多次，而另一些可能不出現(xiàn)。設F是用來在每個結點決定劃分的屬性數(shù)，其中F遠小于可用的屬性數(shù)。為了構造決策樹分類器Mi，在每個結點隨機選擇F個屬性作為結點劃分的候選屬性。使用CART算法的方法來增長樹。樹增長達最大規(guī)模，并且不剪枝。10十一月2024867組合分類2.隨機森林的兩種形式（2）Forest-RC：使用輸入屬性的隨機線性組合。它不是隨機的選擇一個屬性子集，而是由已有屬性的線性組合創(chuàng)建一些新屬性（特征）。即一個屬性由指定的L個原屬性組合產生。在每個給定的結點，隨機選取L個屬性，并且從[-1,1]中隨機選取的數(shù)作為系數(shù)相加。產生F個線性組合，并且其中搜索到最佳劃分。當只有少量屬性可用時，為了降低個體分類器之間的相關性，這種形式的隨機森林是有用的。10十一月2024877組合分類10十一月202488本章小結分類是一種數(shù)據(jù)分析形式，它提取描述數(shù)據(jù)類的模型。分類器預測類別標號(類)。數(shù)值預測建立連續(xù)值函數(shù)模型。分類和數(shù)值預測是兩類主要的預測問題。決策樹歸納是一種自頂向下遞歸樹歸納算法，它使用一種屬性選擇度量為樹的每個非樹葉結點選擇測試屬性。ID3、C4.5和CART都是這種算法的例子，它們使用不同的屬性選擇度量。樸素貝葉斯分類基于后驗概率的貝葉斯定理。它假定類條件獨立，即一個屬性值對給定類的影響獨立于其他屬性的值。10十一月202489本章小結支持向量機(SVM)是一種用于線性和非線性數(shù)據(jù)的分類算法。它把源數(shù)據(jù)變換到較高維空間，使用稱作支持向量的基本元組，從中發(fā)現(xiàn)分離數(shù)據(jù)的超平面?；煜仃嚳梢杂脕碓u估分類器的質量。評估分類器預測能力的度量包括準確率、靈敏度(又稱為召回率)、特效性、精度、F和Fβ。分類器的構造與評估需要把標記的數(shù)據(jù)集劃分成訓練集和檢驗集。保持、隨機抽樣、交叉驗證和自助法都是用于這種劃分的典型方法。10十一月202490本章小結組合方法可以通過學習和組合一系列個體（基）分類器模型來提高總體準確率。裝袋、提升和隨機森林都是流行的組合方法。當感興趣的主類只由少量元組代表時就會出現(xiàn)類不平衡問題。處理這一問題的策略包括過抽樣、欠抽樣、閾值移動和組合技術。10十一月202491Python數(shù)據(jù)挖掘與機器學習第8章聚類第8章聚類本章內容聚類分析K-Means聚類層次聚類基于密度的聚類其他聚類方法聚類評估10十一月202493第8章聚類94無監(jiān)督學習（UnsuperviseLearning）著重于發(fā)現(xiàn)數(shù)據(jù)本身的分布特點。與監(jiān)督學習（SupervisedLearning）不同，無監(jiān)督學習不需要對數(shù)據(jù)進行標記。從功能角度講，無監(jiān)督學習模型可以發(fā)現(xiàn)數(shù)據(jù)的“群落”，同時也可以尋找“離群”的樣本。另外，對于特征維度非常高的數(shù)據(jù)樣本，同樣可以通過無監(jiān)督學習進行數(shù)據(jù)降維，保留最具有區(qū)分性的低維度特征。聚類是一個將數(shù)據(jù)對象集劃分為多個組或簇的過程，使得簇內的數(shù)據(jù)對象具有很高的相似性，但不同簇間的對象具有很高的相異性。第8章聚類95聚類算法分類隨著聚類分析技術的蓬勃發(fā)展，目前已有很多類型的聚類算法。但很難對聚類方法進行簡單的分類，因為這些類別的聚類可能重疊，從而使得一種方法具有一些交叉的特征。一般而言，聚類算法被劃分為以下幾類：1.劃分方法2.基于層次的方法3.基于密度的方法4.局域網格的方法K-Means聚類聚類分析中最廣泛使用的算法為K-Means聚類算法。10十一月202496給定一個n個對象或元組的數(shù)據(jù)庫，一個劃分方法構建數(shù)據(jù)的k個劃分，每個劃分表示一個簇，k<=n，而且滿足：（1）每個組至少包含一個對象；（2）每個對象屬于且僅屬于一個組。劃分時要求同一個聚類中的對象盡可能地接近或相關，不同聚類中的對象盡可能地遠離或不同。K-Means算法是一個迭代的優(yōu)化算法，最終使得下面均方誤差最小。

K-Means聚類K-Means算法：10十一月202497用于劃分的K-Means算法，其中每個簇的中心都用簇中所有對象的均值來表示。K-Means聚類模型所采用的迭代算法直觀易懂且非常實用。但是具有容易收斂到局部最優(yōu)解和需要預先設定簇的數(shù)量的缺陷。K-Means聚類98K=2隨機劃分更新聚類中心更新聚類中心指派對象類標號Loopifneeded初始數(shù)據(jù)集k均值算法的評論優(yōu)點：可擴展性較好，算法復雜度為O(nkt)，其中n為對象總數(shù)，k是簇的個數(shù)，t是迭代次數(shù)。經常終止于局部最優(yōu)解k均值算法的評論缺點只有當簇均值有定義的情況下，k均值方法才能使用。（某些分類屬性的均值可能沒有定義）用戶必須首先給定簇數(shù)目不適合發(fā)現(xiàn)非凸形狀的簇，或者大小差別很大的簇對噪聲和離群點數(shù)據(jù)敏感k均值算法實現(xiàn)fromsklearn.datasetsimportload_irisfromsklearn.clusterimportKMeansiris=load_iris()#加載數(shù)據(jù)集X=iris.dataestimator=KMeans(n_clusters=3)#構造K-Means聚類模型estimator.fit(X)#數(shù)據(jù)導入模型進行訓練label_pred=estimator.labels_#獲取聚類標簽print(label_pred)#顯示各個樣本所屬的類別標簽[111111111111111111111111111111111111111111111111110020000000000000000000000002000000000000000000000020222202222220022220202022002222202222022202220220]11/10/2024k均值方法的變種k均值方法有些變種，他們的區(qū)別在于不同的初始k個均值的選擇不同的相異度計算不同的計算簇均值的策略k均值方法的變種聚類分類數(shù)據(jù)的方法：k眾數(shù)（mode）方法用眾數(shù)來替代簇的均值采用新的相異性度量處理分類對象采用基于頻率的方法更新簇的眾數(shù)可以集成k均值和k眾數(shù)方法，對具有數(shù)值和分類值的數(shù)據(jù)進行聚類K-Means聚類K-Means算法改進：1.K-means++算法K-means算法初始時隨機選取數(shù)據(jù)集中K個點作為聚類中心，不同的初始聚類中心可能導致完全不同的聚類結果。K-means++算法初始的聚類中心之間的相互距離要盡可能的遠。10十一月2024104K-Means聚類K-Means算法改進：2.ISODATA算法ISODATA的全稱是迭代自組織數(shù)據(jù)分析法，是在K-means算法的基礎上，增加對聚類結果的“合并”和“分裂”兩個操作，當屬于某個類別的樣本數(shù)過少時則刪除該類，當屬于某個類別的樣本數(shù)過多、分散程度較大時，把這個類分裂為兩個子類別。10十一月2024105K-Means聚類K-Means算法改進：3.MiniBatch-KMeansMiniBatch-KMeans是一種能盡量保持聚類準確性但能大幅度降低計算時間的聚類模型。MiniBatch-KMeans聚類每次迭代并不采用所有樣本，而是每次等量采樣獲得小的樣本集并把小樣本集中的樣本劃歸到距離最近的中心所在的簇，然后進行聚類中心點的更新。與K-Means算法相比，簇中心點的更新是在每個小的樣本集上。MiniBatch-KMeans可以大大減少算法運行時間，但產生的聚類效果只是略低與K-Means算法，適合于極大數(shù)據(jù)量的聚類分析。10十一月20241063.層次聚類算法原理層次聚類（HierarchicalClustering）就是按照某種方法進行層次分類，直到滿足某種條件為止。層次聚類主要分成兩類：凝聚：從下到上。首先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者滿足某個終結條件。分裂：從上到下。首先將所有對象置于同一個簇中，然后逐漸細分為越來越小的簇，直到每個對象自成一簇，或者達到了某個終止條件。10十一月20241073.層次聚類簇間距離度量1.最短距離法（最大相似度）最短距離被定義為兩個類中最靠近的兩個對象間的距離為簇間距離。2.最長距離法（最小相似度）最長距離被定義為兩個類中最遠的像個對象間的距離為簇間距離。10十一月20241083.層次聚類簇間距離度量3.類平均法計算兩類中任意兩個對象間的距離的平均值作為簇間距離4.中心法定義兩類的兩個中心點的距離為簇間距離。10十一月20241093.層次聚類分裂層次聚類DIANA分裂的層次聚類方法使用自頂向下的策略把對象劃分到層次結構中。從包含所有對象的簇開始，每一步分裂一個簇，直到僅剩單點簇或者滿足用戶指定的簇數(shù)為止。DIANA算法是典型的層次分裂聚類算法。DIANA算法中用到如下兩個定義：簇的直徑：計算一個簇中任意兩個數(shù)據(jù)點之間的歐式距離，選取距離中的最大值作為簇的直徑。平均相異度：兩個數(shù)據(jù)點之間的平均距離。10十一月20241103.層次聚類DIANA算法描述：10十一月20241113.層次聚類凝聚層次聚類AGNES凝聚的層次聚類方法使用自底向上的策略把對象組織到層次結構中。開始時以每個對象作為一個簇，每一步合并兩個最相似的簇。AGNES算法是典型的凝聚層次聚類，起始將每個對象作為一個簇，然后根據(jù)合并準則逐步合并這些簇。兩個簇間的相似度由這兩個不同簇中距離最近的數(shù)據(jù)點的相似度確定。聚類的合并過程反復進行直到所有對象最終滿足終止條件設置的簇數(shù)目。10十一月20241123.層次聚類凝聚層次聚類AGNES10十一月20241133.層次聚類凝聚層次聚類AGNES10十一月20241143.層次聚類凝聚層次聚類AGNES10十一月20241153.層次聚類層次聚類應用Python中層次聚類的函數(shù)是AgglomerativeClustering()，最重要的參數(shù)有3個：n_clusters為聚類數(shù)目，affinity為樣本距離定義，linkage是類間距離的定義，有3種取值：ward：組間距離等于兩類對象之間的最小距離average：組間距離等于兩組對象之間的平均距離complete：組間距離等于兩組對象之間的最大距離10十一月20241164基于密度的聚類Generateclustersofarbitraryshapes.Robustagainstnoise.NoKvaluerequiredinadvance.Somewhatsimilartohumanvision.117劃分和層次方法旨在發(fā)現(xiàn)球狀簇，很難發(fā)現(xiàn)任意形狀的簇。4基于密度的聚類基于密度的聚類算法的主要思想是：只要鄰近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個閾值

，就把它加到與之相近的聚類中。也就是說，對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目的點。基于密度的聚類算法代表算法有：DBSCAN算法、OPTICS算法及DENCLUE算法等。

10十一月20241184基于密度的聚類兩個參數(shù):Eps:鄰域最大半徑MinPts:在Eps鄰域中的最少點數(shù)定義1（Eps鄰域）

給定一個對象

p，p的Eps鄰域

NEps（p）定義為以

p為核心，以Eps為半徑的d維超球體區(qū)域，即：其中，D為d維實空間上的數(shù)據(jù)集，dist(p,q)表示D中的2個對象p和q之間的距離。1194基于密度的聚類DBSCAN算法涉及2個參數(shù)5個定義：10十一月20241202個參數(shù):Eps:鄰域最大半徑MinPts:在Eps鄰域中的最少點數(shù)5個定義見表:定義內容Eps鄰域給定一個對象

p，p的Eps鄰域

NEps（p）定義為以

p為核心，以Eps為半徑的d維超球體區(qū)域核心點與邊界點對于對象p∈D，給定一個整數(shù)MinPts，如果p的Eps鄰域內的對象數(shù)滿足|NEps(p)|≥MinPts

，則稱p為(Eps，MinPts)條件下的核心點；不是核心點但落在某個核心點的Eps鄰域內的對象稱為邊界點4基于密度的聚類10十一月2024121直接密度可達給定

(Eps，MinPts)，如果對象p和

q同時滿足如下條件：p∈NEps(q)；|NEps(q)|≥MinPts

（即q是核心點），則稱對象

p是從對象

q出發(fā)，直接密度可達的密度可達給定數(shù)據(jù)集D，當存在一個對象鏈

p1，p2，p3，…，pn，

其中

p1=q，

pN=

p，對于

pi∈D，如果在條件(Eps，MinPts)下pi+1從pi

直接密度可達，則稱對象p從對象q在條件

(Eps，MinPts)下密度可達密度相連如果數(shù)據(jù)集D中存在一個對象o，使得對象p和q是從o在

(Eps，MinPts)條件下密度可達的，那么稱對象p和q在

(Eps，MinPts)條件下密度相連定義2（核心點與邊界點）

對于對象p∈D，給定一個整數(shù)MinPts，如果p的Eps鄰域內的對象數(shù)滿足|NEps(p)|≥MinPts

，則稱p為(Eps，MinPts)條件下的核心點；不是核心點但落在某個核心點的Eps鄰域內的對象稱為邊界點。

CorePointNoisePointBorderPoint4基于密度的聚類4基于密度的聚類定義3（直接密度可達）

如圖所示，給定(Eps，MinPts)，如果對象

p和

q同時滿足如下條件：p∈NEps(q)；|NEps(q)|≥MinPts

（即q是核心點），

則稱對象

p是從對象

q出發(fā)，直接密度可達的。定義4（密度可達）

如圖所示，給定數(shù)據(jù)集D，當存在一個對象鏈

p1，p2，p3，…，pn，

其中

p1=q，

pN=

p，對于

pi∈D，如果在條件(Eps，MinPts)下

pi+1從pi

直接密度可達，則稱對象p從對象q在條件(Eps，MinPts)下密度可達。密度可達是非對稱的，即p從q密度可達不能推出q也從p密度可達。

4基于密度的聚類定義5（密度相連）

如圖所示，如果數(shù)據(jù)集D中存在一個對象o，使得對象p和q是從o在(Eps，MinPts)條件下密度可達的，那么稱對象p和q在(Eps，MinPts)條件下密度相連。密度相連是對稱的。4基于密度的聚類4基于密度的聚類126pqdirectlydensityreachablepqdensityreachableoqpdensityconnected4基于密度的聚類DBSCAN算法描述：10十一月2024127輸入：Eps、MinPts和包含n個對象的數(shù)據(jù)庫。

輸出：基于密度的聚類結果。

方法：（1）任意選取一個沒有加簇標簽的點p；（2）得到所有從p關于

Eps和

MinPts密度可達的點；（3）如果p是一個核心點，形成一個新的簇，給簇內所有對象點加簇標簽；（4）如果p是一個邊界點，沒有從p密度可達的點，DBSCAN將訪問數(shù)據(jù)庫中的下一個點；（5）繼續(xù)這一過程，直到數(shù)據(jù)庫中所有的點都被處理。-鄰域尋找聚類，將具有足夠高密度的區(qū)域劃分為簇，并可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。但是，DBSCAN算法對用戶設置的參數(shù)敏感，Eps和MinPts的設置會影響聚類的效果。針對這一問題，OPTICS（OrderingPointstoIdentifytheClusteringStructure）算法被提出，它通過引入核心距離和可達距離，使得聚類算法對輸入的參數(shù)不敏感。

4基于密度的聚類10十一月2024128DBSCAN需要對數(shù)據(jù)集中的每個對象進行考察，通過檢查每個點的4基于密度的聚類算法實現(xiàn)課本例8-3利用sklearn實現(xiàn)：11/10/2024importnumpyasnpimportmatplotlib.pyplotaspltfromsklearn.clusterimportDBSCANfromsklearnimportdatasetsiris=datasets.load_iris()data=iris.datadbscan=DBSCAN(eps=0.4,min_samples=10,metric='euclidean')dbscan.fit(data)label_pred=dbscan.labels_5其他聚類方法除了常用的劃分聚類、層次聚類和密度聚類方法之外，還有一些聚類方法如網格聚類方法STING、概念聚類COBWEB和模糊聚類方法等。1.STING算法STING（StatisticalInformationGrid_basedMethod）是一種基于網格的多分辨率的聚類技術，它將輸入對象的空間區(qū)域劃分成矩形單元，空間可以用分層和遞歸方法進行劃分。這種多層矩形單元對應不同的分辨率，并且形成一個層次結構，每個高層單元被劃分為低一層的單元。有關每個網格單元的屬性的統(tǒng)計信息（如均值、最大值和最小值）被作為統(tǒng)計參數(shù)預先計算和存儲。10十一月20241305其他聚類方法除了常用的劃分聚類、層次聚類和密度聚類方法之外，還有一些聚類方法如網格聚類方法STING、概念聚類COBWEB和模糊聚類方法等。2COBWEB概念聚類是機器學習中的一種聚類算法。大多數(shù)的概念聚類方法采用了統(tǒng)計學方法，在決定概念或聚類時使用概率度量。COBWEB算法即簡單增量概念聚類算法，以一個分類樹的形式創(chuàng)建層次聚類，它的輸入對象用分類屬性-值對進行描述。10十一月20241315其他聚類方法3模糊聚類10十一月2024132模糊C均值聚類（FuzzyC-means，F(xiàn)CM）融合了模糊理論的精髓。相較于K-means的硬聚類，F(xiàn)CM聚類提供了更加靈活的聚類結果，它對每個對象和每個簇賦予一個權值，指明對象屬于該簇的程度（隸屬度）。5其他聚類方法3模糊聚類10十一月2024133采用拉格朗日乘數(shù)法，求解得到參數(shù)的更新值：5其他聚類方法3模糊聚類10十一月2024134輸入：數(shù)據(jù)樣本X輸出：每個樣本屬于的隸屬度及聚類中心過程：（1）設置初始值：算法迭代時目標函數(shù)的精度閾值，模糊度和迭代的最大次數(shù);(2)初始化聚類中心和隸屬度矩陣;(3)使用公式8.9-8.10更新隸屬度矩陣

和聚類中心

;(4)加入

或迭代次數(shù)

結束迭代過程，否則轉步驟（3）;5其他聚類方法Python中提供了模糊運算的包scikit-fuzzy，簡稱skfuzzy，初次使用時需要安裝。skfuzzy中包含了FCM聚類方法：center,u,u0,d,jm,p,fpc=cmeans(x.T,m=2,c=k,error=0.5,maxiter=1000)其中的主要參數(shù)u是最終的隸屬度矩陣，u0是初始化隸屬度矩陣，d是每個數(shù)據(jù)到各個中心的歐式距離矩陣，jm是目標函數(shù)優(yōu)化，p是迭代次數(shù)，fpc是評價指標，0表示最差、1最好。11/10/20245其他聚類方法11/10/20245其他聚類方法11/10/20245其他聚類方法11/10/20245其他聚類方法11/10/20245其他聚類方法11/10/2024在sklearn中利用GaussianMixture方法實現(xiàn)高斯混合聚類，主要參數(shù)有