淺談聚類算法

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

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

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

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