聚類算法課件

實(shí)驗(yàn)十十一聚類算法實(shí)驗(yàn)十十一聚類算法主要內(nèi)容1、聚類和聚類分析2、數(shù)據(jù)類型3、相似度量方法4、聚類方法的分類5、劃分聚類的方法6、層次聚類方法7、基于空間索引的聚類方法8、聚類的應(yīng)用案例主要內(nèi)容1、聚類和聚類分析1聚類和聚類分析概述1.1聚類的起源1.2聚類舉例1.3聚類的定義和相關(guān)概念1聚類和聚類分析概述1.1聚類的起源1.1聚類的起源人們認(rèn)識(shí)世界的一種方法是將認(rèn)識(shí)的對(duì)象按照一定的特征進(jìn)行劃分同一類事物之間有著相似的屬性劃分種類的方式包含分類和聚類1.1聚類的起源人們認(rèn)識(shí)世界的一種方法是將認(rèn)識(shí)的對(duì)象按照一1.2分類舉例1.2分類舉例1.2聚類舉例(一)對(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)行分類。應(yīng)聘者12345678910X28181121262016142422Y29232223292322232927Z281816222622222424241.2聚類舉例(一)對(duì)10位應(yīng)聘者做智能檢驗(yàn)。3項(xiàng)指標(biāo)X，1.2聚類舉例(二)例如當(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)聚為一類，從而達(dá)到簡(jiǎn)化指標(biāo)體系的目的。1.2聚類舉例(二)例如當(dāng)我們對(duì)企業(yè)的經(jīng)濟(jì)效益進(jìn)行評(píng)價(jià)時(shí)，1.3聚類的定義及相關(guān)概念1.聚類的定義無監(jiān)督的知識(shí)發(fā)現(xiàn)把物理或抽象對(duì)象的集合分成相似的對(duì)象類的過程成為聚類。2.相關(guān)概念簇:數(shù)據(jù)對(duì)象的集合距離:數(shù)據(jù)對(duì)象間的距離好的聚類：簇內(nèi)部對(duì)象的距離小，而簇之間的距離大1.3聚類的定義及相關(guān)概念1.聚類的定義假如要分兩個(gè)簇，如何分?假如要分兩個(gè)簇，如何分?2數(shù)據(jù)類型2.1數(shù)據(jù)類型的分類2.2數(shù)值型數(shù)據(jù)的標(biāo)準(zhǔn)化2數(shù)據(jù)類型2.1數(shù)據(jù)類型的分類2.1數(shù)據(jù)類型的分類從數(shù)據(jù)聚類的角度看，數(shù)據(jù)可以分為分類型和數(shù)值型分類型：名義型、等級(jí)型和布爾型名義型：屬性值之間沒有順序，屬性值的加減沒有意義等級(jí)型：屬性值之間有大小順序，但不知道一個(gè)值比另一個(gè)值究竟大多少布爾型：分類型的特例，只有兩個(gè)屬性值數(shù)值型屬性：屬性值的加減、排序等均有意義2.1數(shù)據(jù)類型的分類從數(shù)據(jù)聚類的角度看，數(shù)據(jù)可以分為聚類算法課件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ì)算是聚類的核心，有兩種主要的方法：距離和相似度。3相似度量方法對(duì)象間的相似性計(jì)算是聚類的核心，有兩種主要的3.1距離1距離的要求3.1距離1距離的要求2常見的距離曼哈頓距離：歐式距離：切比雪夫距離：2常見的距離例子:分析上海股市和深圳股市的距離例子:分析上海股市和深圳股市的距離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ǔ)充聚類算法課件4聚類方法的分類4.1平凡聚類和不平凡聚類4.2覆蓋聚類和非覆蓋聚類4.3層次聚類和非層次聚類4.4數(shù)值型聚類、分類型聚類和混合型聚類4.5從聚類的方法進(jìn)行分類4聚類方法的分類4.1平凡聚類和不平凡聚類4.1平凡聚類和不平凡聚類一組數(shù)據(jù)D有N個(gè)對(duì)象，分成M個(gè)簇平凡聚類：整個(gè)聚類只有一個(gè)簇或者每個(gè)對(duì)象單獨(dú)成為一個(gè)簇非平凡聚類：其它的情況4.1平凡聚類和不平凡聚類一組數(shù)據(jù)D有N個(gè)對(duì)象，分成M個(gè)簇4.2覆蓋聚類和非覆蓋聚類覆蓋聚類：每個(gè)對(duì)象至少屬于一個(gè)簇，則為覆蓋聚類否則為非覆蓋聚類4.2覆蓋聚類和非覆蓋聚類覆蓋聚類：4.3層次聚類和非層次聚類如果存在兩個(gè)聚類，其中一個(gè)聚類是另一個(gè)聚類的子集，則稱為層次聚類，否則為非層次聚類4.3層次聚類和非層次聚類如果存在兩個(gè)聚類，其中一個(gè)聚類是4.4數(shù)值型聚類、分類型聚類和混合型聚類根據(jù)屬性的類型進(jìn)行劃分只包含數(shù)值屬性的——數(shù)值型聚類只包含分類型屬性的——分類型聚類同時(shí)包含數(shù)值屬性和分類型屬性——混合型聚類4.4數(shù)值型聚類、分類型聚類和混合型聚類根據(jù)屬性的類型進(jìn)行4.5從聚類的方法進(jìn)行聚類劃分聚類層次聚類基于密度的聚類網(wǎng)格聚類4.5從聚類的方法進(jìn)行聚類劃分聚類5劃分聚類方法5.1常見的劃分聚類的方法5.2K-means算法的一般過程5.3例子5劃分聚類方法5.1常見的劃分聚類的方法5.1常見的劃分聚類的方法1劃分聚類的含義：對(duì)于一組數(shù)據(jù)集合D，給定聚類數(shù)目k和目標(biāo)函數(shù)F，劃分聚類算法把D劃分成k個(gè)組，使得目標(biāo)函數(shù)在此劃分下達(dá)到最優(yōu)。目標(biāo)函數(shù)通常是：各個(gè)點(diǎn)到每個(gè)聚類中心的距離最短。5.1常見的劃分聚類的方法1劃分聚類的含義：2常見的劃分聚類的方法有K-meansK-medoids等等2常見的劃分聚類的方法有5.2k-means算法5.2.1聚類結(jié)果的表示形式每個(gè)聚類至少有一個(gè)樣本每個(gè)樣本至少屬于一個(gè)聚類5.2k-means算法5.2.1聚類結(jié)果的表示形式5.2.2K-means算法的過程(1)確定輸入輸出(2)具體處理流程(3)k-means算法的結(jié)束條件(4)5.2.2K-means算法的過程(1)確定輸入輸出(1)K-means算法的輸入輸出

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

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

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

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

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

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

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

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

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

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