聚類(lèi)算法課件

實(shí)驗(yàn)十十一聚類(lèi)算法實(shí)驗(yàn)十十一聚類(lèi)算法主要內(nèi)容1、聚類(lèi)和聚類(lèi)分析2、數(shù)據(jù)類(lèi)型3、相似度量方法4、聚類(lèi)方法的分類(lèi)5、劃分聚類(lèi)的方法6、層次聚類(lèi)方法7、基于空間索引的聚類(lèi)方法8、聚類(lèi)的應(yīng)用案例主要內(nèi)容1、聚類(lèi)和聚類(lèi)分析1聚類(lèi)和聚類(lèi)分析概述1.1聚類(lèi)的起源1.2聚類(lèi)舉例1.3聚類(lèi)的定義和相關(guān)概念1聚類(lèi)和聚類(lèi)分析概述1.1聚類(lèi)的起源1.1聚類(lèi)的起源人們認(rèn)識(shí)世界的一種方法是將認(rèn)識(shí)的對(duì)象按照一定的特征進(jìn)行劃分同一類(lèi)事物之間有著相似的屬性劃分種類(lèi)的方式包含分類(lèi)和聚類(lèi)1.1聚類(lèi)的起源人們認(rèn)識(shí)世界的一種方法是將認(rèn)識(shí)的對(duì)象按照一1.2分類(lèi)舉例1.2分類(lèi)舉例1.2聚類(lèi)舉例(一)對(duì)10位應(yīng)聘者做智能檢驗(yàn)。3項(xiàng)指標(biāo)X，Y和Z分別表示數(shù)學(xué)推理能力，空間想象能力和語(yǔ)言理解能力。其得分如下，選擇合適的統(tǒng)計(jì)方法對(duì)應(yīng)聘者進(jìn)行分類(lèi)。應(yīng)聘者12345678910X28181121262016142422Y29232223292322232927Z281816222622222424241.2聚類(lèi)舉例(一)對(duì)10位應(yīng)聘者做智能檢驗(yàn)。3項(xiàng)指標(biāo)X，1.2聚類(lèi)舉例(二)例如當(dāng)我們對(duì)企業(yè)的經(jīng)濟(jì)效益進(jìn)行評(píng)價(jià)時(shí)，建立了一個(gè)由多個(gè)指標(biāo)組成的指標(biāo)體系，由于信息的重疊，一些指標(biāo)之間存在很強(qiáng)的相關(guān)性，所以需要將相似的指標(biāo)聚為一類(lèi)，從而達(dá)到簡(jiǎn)化指標(biāo)體系的目的。1.2聚類(lèi)舉例(二)例如當(dāng)我們對(duì)企業(yè)的經(jīng)濟(jì)效益進(jìn)行評(píng)價(jià)時(shí)，1.3聚類(lèi)的定義及相關(guān)概念1.聚類(lèi)的定義無(wú)監(jiān)督的知識(shí)發(fā)現(xiàn)把物理或抽象對(duì)象的集合分成相似的對(duì)象類(lèi)的過(guò)程成為聚類(lèi)。2.相關(guān)概念簇:數(shù)據(jù)對(duì)象的集合距離:數(shù)據(jù)對(duì)象間的距離好的聚類(lèi)：簇內(nèi)部對(duì)象的距離小，而簇之間的距離大1.3聚類(lèi)的定義及相關(guān)概念1.聚類(lèi)的定義假如要分兩個(gè)簇，如何分?假如要分兩個(gè)簇，如何分?2數(shù)據(jù)類(lèi)型2.1數(shù)據(jù)類(lèi)型的分類(lèi)2.2數(shù)值型數(shù)據(jù)的標(biāo)準(zhǔn)化2數(shù)據(jù)類(lèi)型2.1數(shù)據(jù)類(lèi)型的分類(lèi)2.1數(shù)據(jù)類(lèi)型的分類(lèi)從數(shù)據(jù)聚類(lèi)的角度看，數(shù)據(jù)可以分為分類(lèi)型和數(shù)值型分類(lèi)型：名義型、等級(jí)型和布爾型名義型：屬性值之間沒(méi)有順序，屬性值的加減沒(méi)有意義等級(jí)型：屬性值之間有大小順序，但不知道一個(gè)值比另一個(gè)值究竟大多少布爾型：分類(lèi)型的特例，只有兩個(gè)屬性值數(shù)值型屬性：屬性值的加減、排序等均有意義2.1數(shù)據(jù)類(lèi)型的分類(lèi)從數(shù)據(jù)聚類(lèi)的角度看，數(shù)據(jù)可以分為聚類(lèi)算法課件2.2數(shù)值型屬性的標(biāo)準(zhǔn)化1為什么要標(biāo)準(zhǔn)化數(shù)值型屬性的量綱和單位不同，必須把不同的度量單位統(tǒng)一成相同的度量單位2.2數(shù)值型屬性的標(biāo)準(zhǔn)化1為什么要標(biāo)準(zhǔn)化2標(biāo)準(zhǔn)化的常用方法Z-score標(biāo)準(zhǔn)化：均值為0，方差為1減去均值，除以絕對(duì)方差標(biāo)準(zhǔn)化值域，將值域映射到[0,1]除以均值：令均值為1除以最大值：令最大值為1前提：所有數(shù)值均為正值2標(biāo)準(zhǔn)化的常用方法3注意：不要為了標(biāo)準(zhǔn)化而標(biāo)準(zhǔn)化當(dāng)我們需要比較的兩個(gè)（或多個(gè)）序列是同一量綱下的，則不必標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化是按照屬性進(jìn)行標(biāo)準(zhǔn)化3注意：對(duì)哪些數(shù)列進(jìn)行標(biāo)準(zhǔn)化對(duì)哪些數(shù)列進(jìn)行標(biāo)準(zhǔn)化作業(yè)：數(shù)列標(biāo)準(zhǔn)化(按小組交)設(shè)計(jì)一個(gè)excel表，實(shí)現(xiàn)數(shù)列標(biāo)準(zhǔn)化作業(yè)：數(shù)列標(biāo)準(zhǔn)化(按小組交)設(shè)計(jì)一個(gè)excel表，實(shí)現(xiàn)數(shù)列標(biāo)3相似度量方法對(duì)象間的相似性計(jì)算是聚類(lèi)的核心，有兩種主要的方法：距離和相似度。3相似度量方法對(duì)象間的相似性計(jì)算是聚類(lèi)的核心，有兩種主要的3.1距離1距離的要求3.1距離1距離的要求2常見(jiàn)的距離曼哈頓距離：歐式距離：切比雪夫距離：2常見(jiàn)的距離例子:分析上海股市和深圳股市的距離例子:分析上海股市和深圳股市的距離2.2相似系數(shù)1.相似系數(shù)的要求2.2相似系數(shù)1.相似系數(shù)的要求2相似度的度量方式數(shù)量積法相關(guān)系數(shù)法2相似度的度量方式例子:分析上海股市和深圳股市的相似系數(shù)例子:分析上海股市和深圳股市的相似系數(shù)簡(jiǎn)單匹配法累積匹配的屬性個(gè)數(shù)，匹配屬性所占的比例作為相似系數(shù)大家利用匹配算法計(jì)算一下樣本3和4、8和11的相似系數(shù)簡(jiǎn)單匹配法匹配系數(shù)針對(duì)二值型匹配系數(shù)=匹配系數(shù)大家利用匹配系數(shù)計(jì)算上證指數(shù)和深證成指的相似性大家利用匹配系數(shù)計(jì)算上證指數(shù)和深證成指的相似性補(bǔ)充補(bǔ)充聚類(lèi)算法課件4聚類(lèi)方法的分類(lèi)4.1平凡聚類(lèi)和不平凡聚類(lèi)4.2覆蓋聚類(lèi)和非覆蓋聚類(lèi)4.3層次聚類(lèi)和非層次聚類(lèi)4.4數(shù)值型聚類(lèi)、分類(lèi)型聚類(lèi)和混合型聚類(lèi)4.5從聚類(lèi)的方法進(jìn)行分類(lèi)4聚類(lèi)方法的分類(lèi)4.1平凡聚類(lèi)和不平凡聚類(lèi)4.1平凡聚類(lèi)和不平凡聚類(lèi)一組數(shù)據(jù)D有N個(gè)對(duì)象，分成M個(gè)簇平凡聚類(lèi)：整個(gè)聚類(lèi)只有一個(gè)簇或者每個(gè)對(duì)象單獨(dú)成為一個(gè)簇非平凡聚類(lèi)：其它的情況4.1平凡聚類(lèi)和不平凡聚類(lèi)一組數(shù)據(jù)D有N個(gè)對(duì)象，分成M個(gè)簇4.2覆蓋聚類(lèi)和非覆蓋聚類(lèi)覆蓋聚類(lèi)：每個(gè)對(duì)象至少屬于一個(gè)簇，則為覆蓋聚類(lèi)否則為非覆蓋聚類(lèi)4.2覆蓋聚類(lèi)和非覆蓋聚類(lèi)覆蓋聚類(lèi)：4.3層次聚類(lèi)和非層次聚類(lèi)如果存在兩個(gè)聚類(lèi)，其中一個(gè)聚類(lèi)是另一個(gè)聚類(lèi)的子集，則稱(chēng)為層次聚類(lèi)，否則為非層次聚類(lèi)4.3層次聚類(lèi)和非層次聚類(lèi)如果存在兩個(gè)聚類(lèi)，其中一個(gè)聚類(lèi)是4.4數(shù)值型聚類(lèi)、分類(lèi)型聚類(lèi)和混合型聚類(lèi)根據(jù)屬性的類(lèi)型進(jìn)行劃分只包含數(shù)值屬性的——數(shù)值型聚類(lèi)只包含分類(lèi)型屬性的——分類(lèi)型聚類(lèi)同時(shí)包含數(shù)值屬性和分類(lèi)型屬性——混合型聚類(lèi)4.4數(shù)值型聚類(lèi)、分類(lèi)型聚類(lèi)和混合型聚類(lèi)根據(jù)屬性的類(lèi)型進(jìn)行4.5從聚類(lèi)的方法進(jìn)行聚類(lèi)劃分聚類(lèi)層次聚類(lèi)基于密度的聚類(lèi)網(wǎng)格聚類(lèi)4.5從聚類(lèi)的方法進(jìn)行聚類(lèi)劃分聚類(lèi)5劃分聚類(lèi)方法5.1常見(jiàn)的劃分聚類(lèi)的方法5.2K-means算法的一般過(guò)程5.3例子5劃分聚類(lèi)方法5.1常見(jiàn)的劃分聚類(lèi)的方法5.1常見(jiàn)的劃分聚類(lèi)的方法1劃分聚類(lèi)的含義：對(duì)于一組數(shù)據(jù)集合D，給定聚類(lèi)數(shù)目k和目標(biāo)函數(shù)F，劃分聚類(lèi)算法把D劃分成k個(gè)組，使得目標(biāo)函數(shù)在此劃分下達(dá)到最優(yōu)。目標(biāo)函數(shù)通常是：各個(gè)點(diǎn)到每個(gè)聚類(lèi)中心的距離最短。5.1常見(jiàn)的劃分聚類(lèi)的方法1劃分聚類(lèi)的含義：2常見(jiàn)的劃分聚類(lèi)的方法有K-meansK-medoids等等2常見(jiàn)的劃分聚類(lèi)的方法有5.2k-means算法5.2.1聚類(lèi)結(jié)果的表示形式每個(gè)聚類(lèi)至少有一個(gè)樣本每個(gè)樣本至少屬于一個(gè)聚類(lèi)5.2k-means算法5.2.1聚類(lèi)結(jié)果的表示形式5.2.2K-means算法的過(guò)程(1)確定輸入輸出(2)具體處理流程(3)k-means算法的結(jié)束條件(4)5.2.2K-means算法的過(guò)程(1)確定輸入輸出(1)K-means算法的輸入輸出

輸入：聚類(lèi)個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)。輸出：滿(mǎn)足方差最小標(biāo)準(zhǔn)的k個(gè)聚類(lèi)。(1)K-means算法的輸入輸出輸入：聚類(lèi)個(gè)數(shù)k(2)處理流程：

(1)從n個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類(lèi)中心。

(2)使用歐氏距離將剩余實(shí)例賦給距離它們最近的簇中心

(3)使用每簇中的實(shí)例計(jì)算每個(gè)簇對(duì)象的均值(中心對(duì)象)，計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離，并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行分類(lèi)。

(4)重新計(jì)算每個(gè)(有變化)聚類(lèi)的均值(中心對(duì)象)，直至新平均值等于上次迭代的平均值，算法結(jié)束。(2)處理流程：假設(shè)空間數(shù)據(jù)對(duì)象分布如圖(a)所示，設(shè)是k＝3，也就是需要將數(shù)據(jù)集劃分為3份(聚類(lèi))。假設(shè)空間數(shù)據(jù)對(duì)象分布如圖(a)所示，設(shè)是k＝3，也就是需要將聚類(lèi)算法課件(3)K-means算法的結(jié)束條件：目標(biāo)函數(shù)值不再下降兩次迭代得到的聚點(diǎn)相同兩次迭代得到的劃分相同達(dá)到最大的迭代次數(shù)(3)K-means算法的結(jié)束條件：目標(biāo)函數(shù)值不再下降（4）K-means算法的關(guān)鍵之處1.樣本距離的確定2.樣本中心點(diǎn)的確定對(duì)于數(shù)值型屬性而言，對(duì)應(yīng)屬性求均值對(duì)于分類(lèi)型屬性而言，則復(fù)雜一些：選擇頻率最大的。（4）K-means算法的關(guān)鍵之處1.樣本距離的確定思考：三者中心如何確定思考：三者中心如何確定6層次聚類(lèi)法6.1層次聚類(lèi)的定義6.2層次聚類(lèi)的步驟6.3聚類(lèi)之間距離的定義6層次聚類(lèi)法6.1層次聚類(lèi)的定義6.1層次聚類(lèi)層次聚類(lèi)方法是指遞歸地對(duì)對(duì)象進(jìn)行合并和分裂，直到滿(mǎn)足某一終止條件為止。6.1層次聚類(lèi)層次聚類(lèi)方法是指遞歸地對(duì)對(duì)象進(jìn)行合并和分裂，6.2層次聚類(lèi)的過(guò)程(1)計(jì)算對(duì)象兩兩之間的距離；(2)構(gòu)造n個(gè)單成員聚類(lèi)C1,C2,…,Cn,每個(gè)聚類(lèi)高度為0；(3)找到兩個(gè)距離最近的聚類(lèi)Ci和Cj，聚類(lèi)的個(gè)數(shù)減1，以被合并的兩個(gè)類(lèi)之間的間距作為上層的高度(4)重復(fù)3直到滿(mǎn)足終止條件6.2層次聚類(lèi)的過(guò)程(1)計(jì)算對(duì)象兩兩之間的距離；6.3聚類(lèi)之間距離的定義最大距離、最小距離、類(lèi)平均距離、中心距離6.3聚類(lèi)之間距離的定義最大距離、最小距離、類(lèi)平均距離、中思考1分成兩個(gè)聚類(lèi)，大家計(jì)算各聚類(lèi)之間的距離思考1分成兩個(gè)聚類(lèi)，大家計(jì)算各聚類(lèi)之間的距離思考2:層次聚類(lèi)結(jié)果思考2:層次聚類(lèi)結(jié)果練習(xí)利用最長(zhǎng)距離法，寫(xiě)出層次聚類(lèi)結(jié)果編號(hào)1234512345004045071550練習(xí)利用最長(zhǎng)距離法，寫(xiě)出層次聚類(lèi)結(jié)果編號(hào)127、基于空間索引的聚類(lèi)方法7.1幾個(gè)重要概念：核心對(duì)象和邊界對(duì)象核心對(duì)象：在給定半徑r的領(lǐng)域中的對(duì)象個(gè)數(shù)大于密度閾值minNum，則該對(duì)象稱(chēng)為核心對(duì)象。邊界對(duì)象：其它令r=5,minNum=3核心對(duì)象有哪些？非核心對(duì)象有哪些？編號(hào)12345123450040450715507、基于空間索引的聚類(lèi)方法7.1幾個(gè)重要概念：編號(hào)1直接密度可達(dá)、密度可達(dá)、密度聯(lián)通直接密度可達(dá)：如果p是一個(gè)核心對(duì)象，q屬于p的領(lǐng)域，則稱(chēng)p直接密度可達(dá)q。問(wèn)：這是能不能稱(chēng)q直接密度可達(dá)p？為什么？令p1=p,pk=q;其中pi直接密度可達(dá)pi+1，則稱(chēng)p密度可達(dá)q。問(wèn)：p密度可達(dá)q是否意味著q密度可達(dá)p?為什么？直接密度可達(dá)、密度可達(dá)、密度聯(lián)通如果存在o，使得o密度可達(dá)p，o也密度可達(dá)q，則稱(chēng)p與q是密度聯(lián)通的。問(wèn)1：若p密度聯(lián)通q，那么q是否密度聯(lián)通p問(wèn)2：p密度聯(lián)通q，是否意味著p密度可達(dá)q?若p密度可達(dá)q，是否意味著p密度聯(lián)通q?問(wèn)3：如果存在o，使得p密度可達(dá)o，q也密度可達(dá)o，能否稱(chēng)p與q是密度聯(lián)通的？如果存在o，使得o密度可達(dá)p，o也密度可達(dá)q，則稱(chēng)p與q是密點(diǎn)1和點(diǎn)5有哪些關(guān)系？(密度可達(dá)、密度直接可達(dá)、密度聯(lián)通)點(diǎn)2和點(diǎn)4有哪些關(guān)系？(密度可達(dá)、密度直接可達(dá)、密度聯(lián)通)r=5,minNum=3編號(hào)1234512345004045071550點(diǎn)1和點(diǎn)5有哪些關(guān)系？(密度可達(dá)、密度直接可達(dá)、密度聯(lián)通)編基于密度的聚類(lèi)步驟1.標(biāo)記出核心對(duì)象Ci和邊界對(duì)象Ni2.當(dāng)ci和cj彼此密度可達(dá)，則ci和cj在同一個(gè)類(lèi)中3.若ci密度可達(dá)Ni,則Ni所在類(lèi)與ci相同，否則Ni單獨(dú)歸于一類(lèi)基于密度的聚類(lèi)步驟1.標(biāo)記出核心對(duì)象Ci和邊界對(duì)象Ni思考：已知r=5,minNum=3，求下表的聚類(lèi)結(jié)果編號(hào)1234512345004045071550思考：已知r=5,minNum=3，求下表的聚類(lèi)結(jié)果編號(hào)18聚類(lèi)的應(yīng)用案例8.1旅游上的應(yīng)用情景：大家成立了一個(gè)旅行社，打算做一個(gè)調(diào)查問(wèn)卷，針對(duì)學(xué)生進(jìn)行宣傳，發(fā)展學(xué)生旅游市場(chǎng)，請(qǐng)問(wèn)你會(huì)怎么做？8聚類(lèi)的應(yīng)用案例8.1旅游上的應(yīng)用實(shí)驗(yàn)十十一聚類(lèi)算法實(shí)驗(yàn)十十一聚類(lèi)算法主要內(nèi)容1、聚類(lèi)和聚類(lèi)分析2、數(shù)據(jù)類(lèi)型3、相似度量方法4、聚類(lèi)方法的分類(lèi)5、劃分聚類(lèi)的方法6、層次聚類(lèi)方法7、基于空間索引的聚類(lèi)方法8、聚類(lèi)的應(yīng)用案例主要內(nèi)容1、聚類(lèi)和聚類(lèi)分析1聚類(lèi)和聚類(lèi)分析概述1.1聚類(lèi)的起源1.2聚類(lèi)舉例1.3聚類(lèi)的定義和相關(guān)概念1聚類(lèi)和聚類(lèi)分析概述1.1聚類(lèi)的起源1.1聚類(lèi)的起源人們認(rèn)識(shí)世界的一種方法是將認(rèn)識(shí)的對(duì)象按照一定的特征進(jìn)行劃分同一類(lèi)事物之間有著相似的屬性劃分種類(lèi)的方式包含分類(lèi)和聚類(lèi)1.1聚類(lèi)的起源人們認(rèn)識(shí)世界的一種方法是將認(rèn)識(shí)的對(duì)象按照一1.2分類(lèi)舉例1.2分類(lèi)舉例1.2聚類(lèi)舉例(一)對(duì)10位應(yīng)聘者做智能檢驗(yàn)。3項(xiàng)指標(biāo)X，Y和Z分別表示數(shù)學(xué)推理能力，空間想象能力和語(yǔ)言理解能力。其得分如下，選擇合適的統(tǒng)計(jì)方法對(duì)應(yīng)聘者進(jìn)行分類(lèi)。應(yīng)聘者12345678910X28181121262016142422Y29232223292322232927Z281816222622222424241.2聚類(lèi)舉例(一)對(duì)10位應(yīng)聘者做智能檢驗(yàn)。3項(xiàng)指標(biāo)X，1.2聚類(lèi)舉例(二)例如當(dāng)我們對(duì)企業(yè)的經(jīng)濟(jì)效益進(jìn)行評(píng)價(jià)時(shí)，建立了一個(gè)由多個(gè)指標(biāo)組成的指標(biāo)體系，由于信息的重疊，一些指標(biāo)之間存在很強(qiáng)的相關(guān)性，所以需要將相似的指標(biāo)聚為一類(lèi)，從而達(dá)到簡(jiǎn)化指標(biāo)體系的目的。1.2聚類(lèi)舉例(二)例如當(dāng)我們對(duì)企業(yè)的經(jīng)濟(jì)效益進(jìn)行評(píng)價(jià)時(shí)，1.3聚類(lèi)的定義及相關(guān)概念1.聚類(lèi)的定義無(wú)監(jiān)督的知識(shí)發(fā)現(xiàn)把物理或抽象對(duì)象的集合分成相似的對(duì)象類(lèi)的過(guò)程成為聚類(lèi)。2.相關(guān)概念簇:數(shù)據(jù)對(duì)象的集合距離:數(shù)據(jù)對(duì)象間的距離好的聚類(lèi)：簇內(nèi)部對(duì)象的距離小，而簇之間的距離大1.3聚類(lèi)的定義及相關(guān)概念1.聚類(lèi)的定義假如要分兩個(gè)簇，如何分?假如要分兩個(gè)簇，如何分?2數(shù)據(jù)類(lèi)型2.1數(shù)據(jù)類(lèi)型的分類(lèi)2.2數(shù)值型數(shù)據(jù)的標(biāo)準(zhǔn)化2數(shù)據(jù)類(lèi)型2.1數(shù)據(jù)類(lèi)型的分類(lèi)2.1數(shù)據(jù)類(lèi)型的分類(lèi)從數(shù)據(jù)聚類(lèi)的角度看，數(shù)據(jù)可以分為分類(lèi)型和數(shù)值型分類(lèi)型：名義型、等級(jí)型和布爾型名義型：屬性值之間沒(méi)有順序，屬性值的加減沒(méi)有意義等級(jí)型：屬性值之間有大小順序，但不知道一個(gè)值比另一個(gè)值究竟大多少布爾型：分類(lèi)型的特例，只有兩個(gè)屬性值數(shù)值型屬性：屬性值的加減、排序等均有意義2.1數(shù)據(jù)類(lèi)型的分類(lèi)從數(shù)據(jù)聚類(lèi)的角度看，數(shù)據(jù)可以分為聚類(lèi)算法課件2.2數(shù)值型屬性的標(biāo)準(zhǔn)化1為什么要標(biāo)準(zhǔn)化數(shù)值型屬性的量綱和單位不同，必須把不同的度量單位統(tǒng)一成相同的度量單位2.2數(shù)值型屬性的標(biāo)準(zhǔn)化1為什么要標(biāo)準(zhǔn)化2標(biāo)準(zhǔn)化的常用方法Z-score標(biāo)準(zhǔn)化：均值為0，方差為1減去均值，除以絕對(duì)方差標(biāo)準(zhǔn)化值域，將值域映射到[0,1]除以均值：令均值為1除以最大值：令最大值為1前提：所有數(shù)值均為正值2標(biāo)準(zhǔn)化的常用方法3注意：不要為了標(biāo)準(zhǔn)化而標(biāo)準(zhǔn)化當(dāng)我們需要比較的兩個(gè)（或多個(gè)）序列是同一量綱下的，則不必標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化是按照屬性進(jìn)行標(biāo)準(zhǔn)化3注意：對(duì)哪些數(shù)列進(jìn)行標(biāo)準(zhǔn)化對(duì)哪些數(shù)列進(jìn)行標(biāo)準(zhǔn)化作業(yè)：數(shù)列標(biāo)準(zhǔn)化(按小組交)設(shè)計(jì)一個(gè)excel表，實(shí)現(xiàn)數(shù)列標(biāo)準(zhǔn)化作業(yè)：數(shù)列標(biāo)準(zhǔn)化(按小組交)設(shè)計(jì)一個(gè)excel表，實(shí)現(xiàn)數(shù)列標(biāo)3相似度量方法對(duì)象間的相似性計(jì)算是聚類(lèi)的核心，有兩種主要的方法：距離和相似度。3相似度量方法對(duì)象間的相似性計(jì)算是聚類(lèi)的核心，有兩種主要的3.1距離1距離的要求3.1距離1距離的要求2常見(jiàn)的距離曼哈頓距離：歐式距離：切比雪夫距離：2常見(jiàn)的距離例子:分析上海股市和深圳股市的距離例子:分析上海股市和深圳股市的距離2.2相似系數(shù)1.相似系數(shù)的要求2.2相似系數(shù)1.相似系數(shù)的要求2相似度的度量方式數(shù)量積法相關(guān)系數(shù)法2相似度的度量方式例子:分析上海股市和深圳股市的相似系數(shù)例子:分析上海股市和深圳股市的相似系數(shù)簡(jiǎn)單匹配法累積匹配的屬性個(gè)數(shù)，匹配屬性所占的比例作為相似系數(shù)大家利用匹配算法計(jì)算一下樣本3和4、8和11的相似系數(shù)簡(jiǎn)單匹配法匹配系數(shù)針對(duì)二值型匹配系數(shù)=匹配系數(shù)大家利用匹配系數(shù)計(jì)算上證指數(shù)和深證成指的相似性大家利用匹配系數(shù)計(jì)算上證指數(shù)和深證成指的相似性補(bǔ)充補(bǔ)充聚類(lèi)算法課件4聚類(lèi)方法的分類(lèi)4.1平凡聚類(lèi)和不平凡聚類(lèi)4.2覆蓋聚類(lèi)和非覆蓋聚類(lèi)4.3層次聚類(lèi)和非層次聚類(lèi)4.4數(shù)值型聚類(lèi)、分類(lèi)型聚類(lèi)和混合型聚類(lèi)4.5從聚類(lèi)的方法進(jìn)行分類(lèi)4聚類(lèi)方法的分類(lèi)4.1平凡聚類(lèi)和不平凡聚類(lèi)4.1平凡聚類(lèi)和不平凡聚類(lèi)一組數(shù)據(jù)D有N個(gè)對(duì)象，分成M個(gè)簇平凡聚類(lèi)：整個(gè)聚類(lèi)只有一個(gè)簇或者每個(gè)對(duì)象單獨(dú)成為一個(gè)簇非平凡聚類(lèi)：其它的情況4.1平凡聚類(lèi)和不平凡聚類(lèi)一組數(shù)據(jù)D有N個(gè)對(duì)象，分成M個(gè)簇4.2覆蓋聚類(lèi)和非覆蓋聚類(lèi)覆蓋聚類(lèi)：每個(gè)對(duì)象至少屬于一個(gè)簇，則為覆蓋聚類(lèi)否則為非覆蓋聚類(lèi)4.2覆蓋聚類(lèi)和非覆蓋聚類(lèi)覆蓋聚類(lèi)：4.3層次聚類(lèi)和非層次聚類(lèi)如果存在兩個(gè)聚類(lèi)，其中一個(gè)聚類(lèi)是另一個(gè)聚類(lèi)的子集，則稱(chēng)為層次聚類(lèi)，否則為非層次聚類(lèi)4.3層次聚類(lèi)和非層次聚類(lèi)如果存在兩個(gè)聚類(lèi)，其中一個(gè)聚類(lèi)是4.4數(shù)值型聚類(lèi)、分類(lèi)型聚類(lèi)和混合型聚類(lèi)根據(jù)屬性的類(lèi)型進(jìn)行劃分只包含數(shù)值屬性的——數(shù)值型聚類(lèi)只包含分類(lèi)型屬性的——分類(lèi)型聚類(lèi)同時(shí)包含數(shù)值屬性和分類(lèi)型屬性——混合型聚類(lèi)4.4數(shù)值型聚類(lèi)、分類(lèi)型聚類(lèi)和混合型聚類(lèi)根據(jù)屬性的類(lèi)型進(jìn)行4.5從聚類(lèi)的方法進(jìn)行聚類(lèi)劃分聚類(lèi)層次聚類(lèi)基于密度的聚類(lèi)網(wǎng)格聚類(lèi)4.5從聚類(lèi)的方法進(jìn)行聚類(lèi)劃分聚類(lèi)5劃分聚類(lèi)方法5.1常見(jiàn)的劃分聚類(lèi)的方法5.2K-means算法的一般過(guò)程5.3例子5劃分聚類(lèi)方法5.1常見(jiàn)的劃分聚類(lèi)的方法5.1常見(jiàn)的劃分聚類(lèi)的方法1劃分聚類(lèi)的含義：對(duì)于一組數(shù)據(jù)集合D，給定聚類(lèi)數(shù)目k和目標(biāo)函數(shù)F，劃分聚類(lèi)算法把D劃分成k個(gè)組，使得目標(biāo)函數(shù)在此劃分下達(dá)到最優(yōu)。目標(biāo)函數(shù)通常是：各個(gè)點(diǎn)到每個(gè)聚類(lèi)中心的距離最短。5.1常見(jiàn)的劃分聚類(lèi)的方法1劃分聚類(lèi)的含義：2常見(jiàn)的劃分聚類(lèi)的方法有K-meansK-medoids等等2常見(jiàn)的劃分聚類(lèi)的方法有5.2k-means算法5.2.1聚類(lèi)結(jié)果的表示形式每個(gè)聚類(lèi)至少有一個(gè)樣本每個(gè)樣本至少屬于一個(gè)聚類(lèi)5.2k-means算法5.2.1聚類(lèi)結(jié)果的表示形式5.2.2K-means算法的過(guò)程(1)確定輸入輸出(2)具體處理流程(3)k-means算法的結(jié)束條件(4)5.2.2K-means算法的過(guò)程(1)確定輸入輸出(1)K-means算法的輸入輸出

輸入：聚類(lèi)個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)。輸出：滿(mǎn)足方差最小標(biāo)準(zhǔn)的k個(gè)聚類(lèi)。(1)K-means算法的輸入輸出輸入：聚類(lèi)個(gè)數(shù)k(2)處理流程：

(1)從n個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類(lèi)中心。

(2)使用歐氏距離將剩余實(shí)例賦給距離它們最近的簇中心

(3)使用每簇中的實(shí)例計(jì)算每個(gè)簇對(duì)象的均值(中心對(duì)象)，計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離，并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行分類(lèi)。

(4)重新計(jì)算每個(gè)(有變化)聚類(lèi)的均值(中心對(duì)象)，直至新平均值等于上次迭代的平均值，算法結(jié)束。(2)處理流程：假設(shè)空間數(shù)據(jù)對(duì)象分布如圖(a)所示，設(shè)是k＝3，也就是需要將數(shù)據(jù)集劃分為3份(聚類(lèi))。假設(shè)空間數(shù)據(jù)對(duì)象分布如圖(a)所示，設(shè)是k＝3，也就是需要將聚類(lèi)算法課件(3)K-means算法的結(jié)束條件：目標(biāo)函數(shù)值不再下降兩次迭代得到的聚點(diǎn)相同兩次迭代得到的劃分相同達(dá)到最大的迭代次數(shù)(3)K-means算法的結(jié)束條件：目標(biāo)函數(shù)值不再下降（4）K-means算法的關(guān)鍵之處1.樣本距離的確定2.樣本中心點(diǎn)的確定對(duì)于數(shù)值型屬性而言，對(duì)應(yīng)屬性求均值對(duì)于分類(lèi)型屬性而言，則復(fù)雜一些：選擇頻率最大的。（4）K-means算法的關(guān)鍵之處1.樣本距離的確定思考：三者中心如何確定思考：三者中心如何確定6層次聚類(lèi)法6.1層次聚類(lèi)的定義6.2層次聚類(lèi)的步驟6.3聚類(lèi)之間距離的定義6層次聚類(lèi)法6.1層次聚類(lèi)的定義6.1層次聚類(lèi)層次聚類(lèi)方法是指遞歸地對(duì)對(duì)象進(jìn)行合并和分裂，直到滿(mǎn)足某一終止條件為止。6.1層次聚類(lèi)層次聚類(lèi)方法是指遞歸地對(duì)對(duì)象進(jìn)行合并和分裂，6.2層次聚類(lèi)的過(guò)程(1)計(jì)算對(duì)象兩兩之間的距離；(2)構(gòu)造n個(gè)單成員聚類(lèi)C1,C2,…,Cn,每個(gè)聚類(lèi)高度為0；(3)找到兩個(gè)距離最近的聚類(lèi)Ci和Cj，聚類(lèi)的個(gè)數(shù)減1，以被合并的兩個(gè)類(lèi)之間的間距作為上層的高度(4)重復(fù)3直到滿(mǎn)足終止條件6.2層次聚類(lèi)的過(guò)程(1)計(jì)算對(duì)象兩兩之間的距離；6.3聚類(lèi)之間距離的定義最大距離、最小距離、類(lèi)平均距離、中心距離6.3聚類(lèi)之間距離的定義最大距離、最小距離、類(lèi)平均距離、中思考1分成兩個(gè)聚類(lèi)，大家計(jì)算各聚類(lèi)之間的距離思考1分成兩個(gè)聚類(lèi)，大家計(jì)算各聚類(lèi)之間的距離思考2:層次聚類(lèi)結(jié)果思考2:層次聚類(lèi)結(jié)果練習(xí)利用最長(zhǎng)距離法，寫(xiě)出層次聚類(lèi)結(jié)果編號(hào)1234512345004045071550練習(xí)利用最長(zhǎng)距離法，寫(xiě)出層次聚類(lèi)結(jié)果編號(hào)127、基于空間索引的聚類(lèi)方法7.1幾個(gè)重要概念：核心對(duì)象和邊界對(duì)象核心對(duì)象：在給定半徑r的領(lǐng)域中的對(duì)象個(gè)數(shù)大于密度閾值minNum，則該對(duì)象稱(chēng)為核心對(duì)象。邊界對(duì)象：其它令r=5,minNum=3核心對(duì)象有哪些？非核心對(duì)象有哪些？編號(hào)123