Python工程應(yīng)用-數(shù)據(jù)分析基礎(chǔ)與實(shí)踐課件-第11章

第一章概論西華大學(xué)機(jī)器學(xué)習(xí)第十一章K均值聚類XXX學(xué)校XXX2022目錄Contents模型介紹居民家庭消費(fèi)調(diào)查物流公司最佳配送路徑問題

知識引入3

有這樣一個問題，在“雙十一”期間，物流公司要給M城市的100個客戶配送貨物?？蛻舴植荚贛市的各個地方，假設(shè)公司只有5輛貨車，請問如何配送才能讓客戶能盡快收到包裹？

這個問題可以用本章介紹的聚類方法，將待配送的客戶聚為5類，使得每個類別內(nèi)部的客戶距離相對較近，這樣就可以為每個類別分配一輛配送車即可。

本章知識圖譜4模型介紹一1模型介紹6

前面章節(jié)介紹的機(jī)器學(xué)習(xí)方法，都是監(jiān)督學(xué)習(xí)的方法，也就是說，給定的訓(xùn)練樣本都是事先標(biāo)注好類別的，知道訓(xùn)練樣本本身屬于哪一類的。但在實(shí)際生活中，要獲得大量的有標(biāo)注的樣本，本身就是比較困難的，因?yàn)闃颖镜臉?biāo)注成本非常高。盡管現(xiàn)在有了一些諸如眾包法等方式可以發(fā)動廣大讀者一起來進(jìn)行數(shù)據(jù)標(biāo)注，但仍然需要很高的成本。因此，我們需要針對沒有標(biāo)注的數(shù)據(jù)進(jìn)行處理，而這樣的問題就叫做無監(jiān)督學(xué)習(xí)。聚類，就是一種非常典型的無監(jiān)督學(xué)習(xí)方法，而本章介紹的K均值聚類，就是最簡單的聚類算法。1.1模型概述7

顧名思義，聚類，就是指物以類聚，把具有相似特征的樣本聚集在一起，形成一類。K均值(K-means)是一種聚類算法，是發(fā)現(xiàn)給定數(shù)據(jù)集的k個簇的算法。簇個數(shù)k是由用戶給定的，每個簇通過其質(zhì)心(centroid)，即簇中所有點(diǎn)的中心來描述。初始化質(zhì)心每個點(diǎn)找距離最近的質(zhì)心分配點(diǎn)到對應(yīng)的簇更新質(zhì)心1.1模型概述8K均值聚類屬于無監(jiān)督學(xué)習(xí)，無須準(zhǔn)備訓(xùn)練集原理簡單，實(shí)現(xiàn)起來較為容易結(jié)果可解釋性較好，但在算法開始預(yù)測之前，需要手動設(shè)置k值，即估計(jì)數(shù)據(jù)大概的類別個數(shù)，不合理的k值會使結(jié)果缺乏解釋性；可能收斂到局部最小值，在大規(guī)模數(shù)據(jù)集上收斂較慢；對于異常點(diǎn)、離群點(diǎn)敏感。1.2基本的K均值聚類算法9算法偽代碼：選擇k個點(diǎn)作為初始質(zhì)心(通常隨機(jī))repeat對每個質(zhì)心計(jì)算距離，將每個點(diǎn)指派到最近的質(zhì)心，形成k個簇重新計(jì)算每個簇的質(zhì)心until質(zhì)心不發(fā)生變化1.2基本的K均值聚類算法10

可以使用誤差的平方和(SumoftheSquaredError,SSE)作為度量聚類質(zhì)量的目標(biāo)函數(shù)。我們計(jì)算每個數(shù)據(jù)點(diǎn)的誤差，即它到最近質(zhì)心的歐氏距離，然后計(jì)算誤差的平方和。SSE形式地定義如下：

其中，dist是歐氏空間中兩個對象之間的標(biāo)準(zhǔn)歐氏距離。若數(shù)據(jù)集為：

1.2基本的K均值聚類算法11

SSE值越小表示數(shù)據(jù)點(diǎn)越接近于它們的質(zhì)心，聚類效果也越好。1.3K均值聚類算法的代碼實(shí)現(xiàn)121.loadDataSet()完成的功能是加載數(shù)據(jù)集。創(chuàng)建空矩陣返回矩陣存入矩陣讀取文件處理數(shù)據(jù)2.distEclud()主要負(fù)責(zé)計(jì)算兩個向量的歐氏距離(也可以采用其他距離來衡量

計(jì)算方法為各個對應(yīng)特征值差的平方和開方。1.3K均值聚類算法的代碼實(shí)現(xiàn)133.randCent()負(fù)責(zé)為給定的數(shù)據(jù)集創(chuàng)建一個包含k個隨機(jī)質(zhì)心的集合。創(chuàng)建k行n列0矩陣隨機(jī)獲得質(zhì)心存儲質(zhì)心1.3K均值聚類算法的代碼實(shí)現(xiàn)144.

實(shí)現(xiàn)k均值聚類算法初始化聚類矩陣創(chuàng)建初始質(zhì)心取第i個數(shù)據(jù)計(jì)算該數(shù)據(jù)與第j個質(zhì)心的歐氏距離獲取cent個質(zhì)心所有數(shù)據(jù)計(jì)算平均值，得到最終質(zhì)心結(jié)果與存儲的質(zhì)心比對更新最近距離，最近質(zhì)心m行2列矩陣(m為樣本數(shù)據(jù)個數(shù))k行n列矩陣（k為質(zhì)心數(shù)，n為特征數(shù)量）循環(huán)k次循環(huán)m次存儲i行數(shù)據(jù)最新質(zhì)心與距離存儲k個質(zhì)心循環(huán)k次1.3K均值聚類算法的代碼實(shí)現(xiàn)155.驗(yàn)證效果1.4二分k-均值算法16算法偽代碼：初始化簇表，使之包含由所有的點(diǎn)組成的簇。repeat從簇表中取出一個簇(選取對其劃分能最大程度降低SSE值的簇)。{對選定的簇進(jìn)行多次二分“試驗(yàn)”} fori=1to試驗(yàn)次數(shù)do

使用基本k均值，二分選定的簇。 endfor從二分試驗(yàn)中選擇具有最小總SSE的兩個簇。將這兩個簇添加到簇表中。until簇表中包含k個簇。案例：居民家庭消費(fèi)調(diào)查二2.1案例介紹18案例數(shù)據(jù)：

現(xiàn)有1999年全國31個省份城鎮(zhèn)居民家庭平均每月消費(fèi)性支出的主要類型數(shù)據(jù)，分別是食品、衣著、家庭設(shè)備用品及服務(wù)、醫(yī)療保健、交通和通訊、娛樂教育文化服務(wù)、居住以及雜項(xiàng)商品和服務(wù)。案例目標(biāo)：

請嘗試?yán)靡延袛?shù)據(jù)，對31個省份進(jìn)行聚類。2.2案例實(shí)現(xiàn)19Sklearn庫中的cluster模塊中提供了KMeans類，該類可以實(shí)現(xiàn)K-均值聚類，其構(gòu)造函數(shù)如下：sklearn.cluster.KMeans(n_clusters=8,init=’k-means++’,n_init=10,max_iter=300,tol=0.0001,precompute_distances=’auto’,verbose=0,random_state=None,copy_x=True,n_jobs=None,algorithm=’auto’)主要參數(shù)含義：n_clusters：可選，默.認(rèn)為8。要形成的簇的數(shù)目，即類的數(shù)量。n_init：默認(rèn)為10，用不同種子運(yùn)行k-均值算法的次數(shù)。max_iter：默認(rèn)300，單次運(yùn)行的k-均值算法的最大迭代次數(shù)。返回KMeans對象的屬性包括：cluster_centers_:數(shù)組類型，各個簇中心的坐標(biāo)。labels_:每個數(shù)據(jù)點(diǎn)的標(biāo)簽。inertia_:浮點(diǎn)型，數(shù)據(jù)樣本到它們最接近的聚類中心的距離平方和。n_iter_:運(yùn)行的迭代次數(shù)。2.2案例實(shí)現(xiàn)20

案例實(shí)現(xiàn)過程

導(dǎo)入數(shù)據(jù)集初始化聚類器訓(xùn)練聚類器輸出聚類結(jié)果聚成2類時(n_clusters=2)輸出如下：聚成3類時(n_clusters=3)輸出如下：物流公司最佳配送路徑問題三3.1案例介紹22案例數(shù)據(jù)：

“雙十一”期間，物流公司要給M城市的100個客戶配送貨物。假設(shè)公司只有5輛貨車，客戶的地理坐標(biāo)在testSet.txt文件中。案例目標(biāo)：

使用k-means算法，將文件內(nèi)的地址數(shù)據(jù)聚成5類。由于每類的客戶地址相近，可以分配給同一輛貨車。3.2案例實(shí)現(xiàn)23初始化聚類矩陣創(chuàng)建初始質(zhì)心取第i個數(shù)據(jù)計(jì)算該數(shù)據(jù)與第j個質(zhì)心的歐氏距離獲取cent個質(zhì)心所有數(shù)據(jù)計(jì)算平均值，得到最終質(zhì)心結(jié)果與存儲的質(zhì)心比對更新最近距離，最近質(zhì)心m行2列矩陣(m為樣本數(shù)據(jù)個數(shù))k行n列矩陣（k為質(zhì)心數(shù)，n為特征數(shù)量）循環(huán)k次循環(huán)m次存儲i行數(shù)據(jù)最新質(zhì)心與距離存儲k個質(zhì)心循環(huán)k次注：此案例選取樣本中的前k個點(diǎn)作為初始聚類中心3.1案例實(shí)現(xiàn)24程序運(yùn)行結(jié)果：想一想：在物流公司最佳配送路徑問題的案例中：1、可否使用余弦距離？該怎么修改？2、隨機(jī)選的種子，選哪個有區(qū)別嗎？3、你認(rèn)為K值怎么確定？

思考題251.現(xiàn)有20只球隊(duì)的比賽信息，包括2019國際排名，2018世界杯排名，2015亞洲杯排名。請聚類分析各球隊(duì)狀況。

思考題262.下面的代碼可以生成半環(huán)形的數(shù)據(jù)集，嘗試補(bǔ)充完整下列對其用K-Means進(jìn)行聚類的代碼。你發(fā)現(xiàn)了什么問題嗎？#環(huán)形數(shù)據(jù)importmatplotlib.pyplotaspltfromsklearn.clusterimportKMeansfromsklearn.datasetsimportmake_moons#生成環(huán)形數(shù)據(jù)集X,Y=make_moons(n_samples=200,noise=0.05,random_state=0)#=============以下需要補(bǔ)全=====================#=============以上需要補(bǔ)全=====================

#繪制聚類結(jié)果圖plt.scatter(X[:,0],X[:,1],c=Y_