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

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

3[合并or和ok].將類or和ok合并成一個新類ork; /*現有的類數將減1*/

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