淺談聚類算法

淺談聚類算法第1頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月1.引言數(shù)據(jù)挖掘：指從大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中提取隱含的、先前未知的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則。它是人工智能和數(shù)據(jù)庫(kù)發(fā)展相結(jié)合的產(chǎn)物，是國(guó)際上數(shù)據(jù)庫(kù)和信息決策系統(tǒng)最前沿的研究方向之一。數(shù)據(jù)挖掘主要的算法有分類模式、關(guān)聯(lián)規(guī)則、決策樹、序列模式、聚類模式分析、神經(jīng)網(wǎng)絡(luò)算法等等。聚類是數(shù)據(jù)挖掘中的一個(gè)非常重要的研究課題，廣泛應(yīng)用于各個(gè)領(lǐng)域，它對(duì)未知數(shù)能達(dá)到合理的效果。研究和運(yùn)用聚類是完成數(shù)據(jù)挖掘任務(wù)的重要手段，因此對(duì)聚類的研究具有重要的理論價(jià)值和現(xiàn)實(shí)意義。第2頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月2.聚類算法基本原理概述俗話說：“人以群分，物以類聚”。聚類就是利用計(jì)算機(jī)技術(shù)來實(shí)現(xiàn)這一目的的一種技術(shù)。聚類是指將物理或抽象對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè)類的過程。聚類與分類不同：分類問題中我們知道數(shù)據(jù)集的分類屬性。而聚類問題則需要我們從數(shù)據(jù)集中找這個(gè)分類屬性。迄今為止,聚類還沒有一個(gè)學(xué)術(shù)界公認(rèn)的定義.這里給出Everitt在1974年關(guān)于聚類所下的定義:一個(gè)類簇內(nèi)的實(shí)體是相似的,不同類簇的實(shí)體是不相似的;一個(gè)類簇是測(cè)試空間中點(diǎn)的會(huì)聚,同一類簇的任意兩個(gè)點(diǎn)間的距離小于不同類簇的任意兩個(gè)點(diǎn)間的距離;類簇可以描述為一個(gè)包含密度相對(duì)較高的點(diǎn)集的多維空間中的連通區(qū)域,它們借助包含密度相對(duì)較低的點(diǎn)集的區(qū)域與其他區(qū)域(類簇)相分離.。聚類的標(biāo)準(zhǔn)是使簇內(nèi)相似度盡可能大，簇間相似度盡可能小。第3頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月3.數(shù)據(jù)挖掘算法對(duì)聚類的典型要求伸縮性：聚類算法對(duì)小數(shù)據(jù)集和大規(guī)模數(shù)據(jù)集要同樣有效。處理不同類型屬性的能力：實(shí)際應(yīng)用要求算法能夠處理不同類型的數(shù)據(jù)。能發(fā)現(xiàn)任意形狀的聚類：聚類特征的未知性決定聚類算法要能發(fā)現(xiàn)球形的、嵌套的、中空的等任意復(fù)雜形狀和結(jié)構(gòu)的聚類。使決定輸入?yún)?shù)的領(lǐng)域知識(shí)最小化：聚類算法要盡可能地減少用戶估計(jì)參數(shù)的最佳取值所需要的領(lǐng)域知識(shí)。能夠有效地處理噪聲數(shù)據(jù)：聚類算法要能處理現(xiàn)實(shí)世界的數(shù)據(jù)庫(kù)中普遍包含的孤立點(diǎn)，空缺或者錯(cuò)誤的數(shù)據(jù)。第4頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月對(duì)于輸入紀(jì)錄的順序不敏感：聚類算法對(duì)不同的次序的記錄輸入應(yīng)具有相同的聚類結(jié)果。高維性：聚類算法不僅要擅長(zhǎng)處理低維的數(shù)據(jù)集，而且要能處理高維、數(shù)據(jù)可能非常稀疏且高度偏斜的數(shù)據(jù)集?；诩s束的聚類：聚類結(jié)果既要滿足特定的約束。又要具有良好聚類特性。可解釋性和可用性：聚類結(jié)果應(yīng)該是可解釋的、可理解的和可用的。第5頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月4.聚類算法分類研究沒有任何一種聚類技術(shù)(聚類算法)可以普遍適用于揭示各種多維數(shù)據(jù)集所呈現(xiàn)出來的多種多樣的結(jié)構(gòu).根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則以及應(yīng)用這些規(guī)則的方法,有多種聚類算法.聚類算法有多種分類方法,這里將聚類算法大致分成層次化聚類算法、劃分式聚類算法、基于密度和網(wǎng)格的聚類算法和其他聚類算法.

第6頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月4.1劃分式聚類算法劃分聚類算法把數(shù)據(jù)點(diǎn)集分為k個(gè)劃分，每個(gè)劃分作為一個(gè)聚類。它一般從一個(gè)初始劃分開始，然后通過重復(fù)的控制策略，使某個(gè)準(zhǔn)則函數(shù)最優(yōu)化，而每個(gè)聚類由其質(zhì)心來代表(K-MEANS算法)，或者由該聚類中最靠近中心的一個(gè)對(duì)象來代表(K-MEDOIDS算法)。劃分聚類算法收斂速度快，缺點(diǎn)在于它傾向于識(shí)別凸形分布大小相近、密度相近的聚類，不能發(fā)現(xiàn)分布形狀比較復(fù)雜的聚類，它要求類別數(shù)目k可以合理地估計(jì)，并且初始中心的選擇和噪聲會(huì)對(duì)聚類結(jié)果產(chǎn)生很大影響。劃分式聚類算法需要預(yù)先指定聚類數(shù)目或聚類中心，通過反復(fù)迭代運(yùn)算，逐步降低目標(biāo)函數(shù)的誤差值，當(dāng)目標(biāo)函數(shù)值收斂時(shí)，得到最終聚類結(jié)果。第7頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月K均值聚類1967年,MacQueen首次提出了K均值聚類算法(K-means算法).迄今為止,很多聚類任務(wù)都選擇該經(jīng)典算該算法的核心思想是找出K個(gè)聚類中心C1,C2,…,Ck,使得每一個(gè)數(shù)據(jù)點(diǎn)xi和與其最近的聚類中心Cv的平方距離和被最小化(該平方距離和被稱為偏差D).K均值(K-means)聚類算法(對(duì)n個(gè)樣本進(jìn)行聚類) 1[初始化].隨機(jī)指定K個(gè)聚類中心(C1,C2,…,Ck); 2[分配xi].對(duì)每一個(gè)樣本xi,找到離它最近的聚類中心Cv,并將其分配到Cv所標(biāo)明類; 3[修正Cw].將每一個(gè)Cw移動(dòng)到其標(biāo)明的類的中心; 4[計(jì)算偏差]. 5[D收斂?].如果D值收斂,則return(C1,C2,…,Ck)并終止本算法;否則,返回步驟K2.第8頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月K-means算法的優(yōu)點(diǎn)與不足。優(yōu)點(diǎn)：能對(duì)大型數(shù)據(jù)集進(jìn)行高效分類，其計(jì)算復(fù)雜性為O(tkmn)，其中，t為迭代次數(shù)，K為聚類數(shù)，m為特征屬性數(shù)，n為待分類的對(duì)象數(shù)，通常K、m、t<<n。在對(duì)大型數(shù)據(jù)集聚類時(shí)，K-means算法比層次聚類算法快得多。不足：通常會(huì)在獲得一個(gè)局部最優(yōu)值時(shí)終止；僅適合對(duì)數(shù)值型數(shù)據(jù)聚類。第9頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月4.2層次化聚類算法分層聚類算法把數(shù)據(jù)對(duì)象分組而形成一個(gè)聚類樹。分層聚類算法分為兩大類：聚結(jié)型和分裂型。聚結(jié)型算法采用自底向上的策略，首先把每個(gè)對(duì)象單獨(dú)作為一個(gè)聚類，然后根據(jù)一定的規(guī)則合并成為越來越大的聚類，直到最后所有的對(duì)象都?xì)w入到一個(gè)聚類中。大多數(shù)分層聚類算法都屬于聚結(jié)型算法，它們之間的區(qū)別在于類間相似度的定義不同。與聚結(jié)型算法相反，分裂型算法采用自頂向下的方法。一般情況下不使用分裂型方法，因?yàn)樵谳^高的層很難進(jìn)行正確的拆分。純粹的分層聚類算法的缺點(diǎn)在于一旦進(jìn)行合并或分裂之后，就無法再進(jìn)行調(diào)整。現(xiàn)在的一些研究側(cè)重于分層聚類算法與循環(huán)的重新分配方法的結(jié)合。適合于小型數(shù)據(jù)集的分類。第10頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月層次聚結(jié)算法該算法由樹狀結(jié)構(gòu)的底部開始逐層向上進(jìn)行聚合,假定樣本集S={o1,o2,…,on}共有n個(gè)樣本. 1[初始化].置每個(gè)樣本oi為一個(gè)類; /*共形成n個(gè)類:o1,o2,…,on*/ 2[找最近的兩個(gè)類],distance(or,ok)=min[distance(ou,ov)],其中ou,ov屬于S，但不相等. /*從現(xiàn)有的所有類中找出距離最近(相似度最大)的兩個(gè)類or和ok*/

3[合并or和ok].將類or和ok合并成一個(gè)新類ork; /*現(xiàn)有的類數(shù)將減1*/

4若所有的樣本都屬于同一個(gè)類,則終止本算法;否則,返回步驟HA2.第11頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月4.3基于網(wǎng)格和密度的聚類算法基于網(wǎng)格和密度的聚類方法是一類重要的聚類方法,它們?cè)谝钥臻g信息處理為代表的眾多領(lǐng)域有著廣泛應(yīng)用.特別是伴隨著新近處理大規(guī)模數(shù)據(jù)集、可伸縮的聚類方法的開發(fā),其在空間數(shù)據(jù)挖掘研究子域日趨活躍。很多算法中都使用距離來描述數(shù)據(jù)之間的相似性，但是，對(duì)于非凸數(shù)據(jù)集，只用距離來描述是不夠的。對(duì)于這種情況，要用密度來取代相似性，這就是基于密度的聚類算法?；诿芏?單位區(qū)域內(nèi)的實(shí)例數(shù))的算法從數(shù)據(jù)對(duì)象的分布密度出發(fā)，把密度足夠大的區(qū)域連接起來，從而可以發(fā)現(xiàn)任意形狀的類。此類算法除了可以發(fā)現(xiàn)任意形狀的類，還能夠有效去除噪聲。第12頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月基于網(wǎng)格的聚類算法，把空間量化為有限個(gè)單元(即長(zhǎng)方體或超長(zhǎng)方體)，然后對(duì)量化后的空間進(jìn)行聚類。此類算法具有很快的處理速度。缺點(diǎn)是只能發(fā)現(xiàn)邊界是水平或垂直的聚類，而不能檢測(cè)到斜邊界。此類算法具有很快的處理速度。時(shí)間復(fù)雜度一般由網(wǎng)格單元的數(shù)目決定，而與數(shù)據(jù)集的大小無關(guān)。此外，聚類的精度取決于網(wǎng)格單元的大小。此類算法不適用于高維情況，因?yàn)榫W(wǎng)格單元的數(shù)目隨著維數(shù)的增加而呈指數(shù)增長(zhǎng)。所有基于網(wǎng)格的聚類算法都存在下列問題：一是如何選擇合適的單元大小和數(shù)目；二是怎樣對(duì)每個(gè)單元中對(duì)象的信息進(jìn)行匯總。第13頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月5.聚類算法的用途與發(fā)展聚類分析是數(shù)據(jù)挖掘中一種非常有用的技術(shù)，它可作為特征和分類算法的預(yù)處理步驟，這些算法再在生成的簇上進(jìn)行處理，也可將聚類結(jié)果用于進(jìn)一步關(guān)聯(lián)分析。還可以作為一個(gè)獨(dú)立的工具來獲得數(shù)據(jù)分布的情況，觀察每個(gè)簇的特點(diǎn)，集中對(duì)特定的某些簇做進(jìn)一步分析。其應(yīng)用范圍涉及商務(wù)，生物，地理，web文檔分類，仿真等諸多領(lǐng)域。例如在商業(yè)上，聚類可以幫助市場(chǎng)分析人員從消費(fèi)者數(shù)據(jù)庫(kù)中區(qū)分出不同的消費(fèi)群體來，并且概括出每一類消費(fèi)者的消費(fèi)模式或者說習(xí)慣，然后指導(dǎo)自身的工作制造出更好的產(chǎn)品，制定出更高效的營(yíng)銷策略和模式。第14頁(yè)，課件共16頁(yè)，創(chuàng)作于2023年2月聚類能更好地應(yīng)用到現(xiàn)實(shí)生活中是很必要的。這些新算法正努力把靜態(tài)的聚類推向動(dòng)態(tài)的、適