聚類分析演算法

Ⅰ 聚類分析的基本步驟

聚類分析的主要步驟
聚類分析的主要步驟
1.數據預處理，
2.為衡量數據點間的相似度定義一個距離函數，
3.聚類或分組，
4.評估輸出。
數據預處理包括選擇數量，類型和特徵的標度，它依靠特徵選擇和特徵抽取，特徵選擇選擇重要的特徵，特徵抽取把輸入的特徵轉化為一個新的顯著特徵，它們經常被用來獲取一個合適的特徵集來為避免「維數災」進行聚類，數據預處理還包括將孤立點移出數據，孤立點是不依附於一般數據行為或模型的數據，因此孤立點經常會導致有偏差的聚類結果，因此為了得到正確的聚類，我們必須將它們剔除。
既然相類似性是定義一個類的基礎，那麼不同數據之間在同一個特徵空間相似度的衡量對於聚類步驟是很重要的，由於特徵類型和特徵標度的多樣性，距離度量必須謹慎，它經常依賴於應用，例如，通常通過定義在特徵空間的距離度量來評估不同對象的相異性，很多距離度都應用在一些不同的領域，一個簡單的距離度量，如Euclidean距離，經常被用作反映不同數據間的相異性，一些有關相似性的度量，例如PMC和SMC，能夠被用來特徵化不同數據的概念相似性，在圖像聚類上，子圖圖像的誤差更正能夠被用來衡量兩個圖形的相似性。
將數據對象分到不同的類中是一個很重要的步驟，數據基於不同的方法被分到不同的類中，劃分方法和層次方法是聚類分析的兩個主要方法，劃分方法一般從初始劃分和最優化一個聚類標准開始。CrispClustering，它的每一個數據都屬於單獨的類；FuzzyClustering，它的每個數據可能在任何一個類中，CrispClustering和FuzzyClusterin是劃分方法的兩個主要技術，劃分方法聚類是基於某個標准產生一個嵌套的劃分系列，它可以度量不同類之間的相似性或一個類的可分離性用來合並和分裂類，其他的聚類方法還包括基 於密度的聚類，基於模型的聚類，基於網格的聚類。
評估聚類結果的質量是另一個重要的階段，聚類是一個無管理的程序，也沒有客觀的標准來評價聚類結果，它是通過一個類有效索引來評價，一般來說，幾何性質，包括類間的分離和類內部的耦合，一般都用來評價聚類結果的質量，類有效索引在決定類的數目時經常扮演了一個重要角色，類有效索引的最佳值被期望從真實的類數目中獲取，一個通常的決定類數目的方法是選擇一個特定的類有效索引的最佳值，這個索引能否真實的得出類的數目是判斷該索引是否有效的標准，很多已經存在的標准對於相互分離的類數據集合都能得出很好的結果，但是對於復雜的數據集，卻通常行不通，例如，對於交疊類的集合。

Ⅱ 聚類演算法有哪幾種

聚類分析計算方法主要有： 層次的方法(hierarchical method)、劃分方法(partitioning method)、基於密度的方法(density-based method)、基於網格的方法(grid-based method)、基於模型的方法(model-based method)等。其中，前兩種演算法是利用統計學定義的距離進行度量。
k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心;而對於所剩下其它對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然 後再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。
其流程如下：
(1)從 n個數據對象任意選擇 k 個對象作為初始聚類中心;
(2)根據每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離;並根據最小距離重新對相應對象進行劃分;
(3)重新計算每個(有變化)聚類的均值(中心對象);
(4)循環(2)、(3)直到每個聚類不再發生變化為止(標准測量函數收斂)。
優點： 本演算法確定的K個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對於處理大數據集，這個演算法是相對可伸縮和高效的，計算的復雜度為 O(NKt)，其中N是數據對象的數目，t是迭代的次數。
缺點：
1. K 是事先給定的，但非常難以選定;
2. 初始聚類中心的選擇對聚類結果有較大的影響。

Ⅲ 聚類分析方法應用於哪些問題的研究

1.聚類分析的特點
聚類分析（cluster analysis）是根據事物本身的特性研究個體的一種方法,目的在於將相似的事物歸類.它的原則是同一類中的個體有較大的相似性,不同類的個體差異性很大.這種方法有三個特徵：適用於沒有先驗知識的分類.如果沒有這些事先的經驗或一些國際、國內、行業標准,分類便會顯得隨意和主觀.這時只要設定比較完善的分類變數,就可以通過聚類分析法得到較為科學合理的類別；可以處理多個變數決定的分類.例如,要根據消費者購買量的大小進行分類比較容易,但如果在進行數據挖掘時,要求根據消費者的購買量、家庭收入、家庭支出、年齡等多個指標進行分類通常比較復雜,而聚類分析法可以解決這類問題；聚類分析法是一種探索性分析方法,能夠分析事物的內在特點和規律,並根據相似性原則對事物進行分組,是數據挖掘中常用的一種技術.
這種較成熟的統計學方法如果在市場分析中得到恰當的應用,必將改善市場營銷的效果,為企業決策提供有益的參考.其應用的步驟為：將市場分析中的問題轉化為聚類分析可以解決的問題,利用相關軟體（如SPSS、SAS等）求得結果,由專家解讀結果,並轉換為實際操作措施,從而提高企業利潤,降低企業成本.
2.應用范圍
聚類分析在客戶細分中的應用

消費同一種類的商品或服務時,不同的客戶有不同的消費特點,通過研究這些特點,企業可以制定出不同的營銷組合,從而獲取最大的消費者剩餘,這就是客戶細分的主要目的.常用的客戶分類方法主要有三類：經驗描述法,由決策者根據經驗對客戶進行類別劃分；傳統統計法,根據客戶屬性特徵的簡單統計來劃分客戶類別；非傳統統計方法,即基於人工智慧技術的非數值方法.聚類分析法兼有後兩類方法的特點,能夠有效完成客戶細分的過程.
例如,客戶的購買動機一般由需要、認知、學習等內因和文化、社會、家庭、小群體、參考群體等外因共同決定.要按購買動機的不同來劃分客戶時,可以把前述因素作為分析變數,並將所有目標客戶每一個分析變數的指標值量化出來,再運用聚類分析法進行分類.在指標值量化時如果遇到一些定性的指標值,可以用一些定性數據定量化的方法加以轉化,如模糊評價法等.除此之外,可以將客戶滿意度水平和重復購買機會大小作為屬性進行分類；還可以在區分客戶之間差異性的問題上納入一套新的分類法,將客戶的差異性變數劃分為五類：產品利益、客戶之間的相互作用力、選擇障礙、議價能力和收益率,依據這些分析變數聚類得到的歸類,可以為企業制定營銷決策提供有益參考.
以上分析的共同點在於都是依據多個變數進行分類,這正好符合聚類分析法解決問題的特點；不同點在於從不同的角度尋求分析變數,為某一方面的決策提供參考,這正是聚類分析法在客戶細分問題中運用范圍廣的體現.

聚類分析在實驗市場選擇中的應用

實驗調查法是市場調查中一種有效的一手資料收集方法,主要用於市場銷售實驗,即所謂的市場測試.通過小規模的實驗性改變,以觀察客戶對產品或服務的反應,從而分析該改變是否值得在大范圍內推廣.
實驗調查法最常用的領域有：市場飽和度測試.市場飽和度反映市場的潛在購買力,是市場營銷戰略和策略決策的重要參考指標.企業通常通過將消費者購買產品或服務的各種決定因素（如價格等）降到最低限度的方法來測試市場飽和度.或者在出現滯銷時,企業投放類似的新產品或服務到特定的市場,以測試市場是否真正達到飽和,是否具有潛在的購買力.前述兩種措施由於利益和風險的原因,不可能在企業覆蓋的所有市場中實施,只能選擇合適的實驗市場和對照市場加以測試,得到近似的市場飽和度；產品的價格實驗.這種實驗往往將新定價的產品投放市場,對顧客的態度和反應進行測試,了解顧客對這種價格的是否接受或接受程度；新產品上市實驗.波士頓矩陣研究的企業產品生命周期圖表明,企業為了生存和發展往往要不斷開發新產品,並使之向明星產品和金牛產品順利過渡.然而新產品投放市場後的失敗率卻很高,大致為66%到90%.因而為了降低新產品的失敗率,在產品大規模上市前,運用實驗調查法對新產品的各方面（外觀設計、性能、廣告和推廣營銷組合等）進行實驗是非常有必要的.
在實驗調查方法中,最常用的是前後單組對比實驗、對照組對比實驗和前後對照組對比實驗.這些方法要求科學的選擇實驗和非實驗單位,即隨機選擇出的實驗單位和非實驗單位之間必須具備一定的可比性,兩類單位的主客觀條件應基本相同.
通過聚類分析,可將待選的實驗市場（商場、居民區、城市等）分成同質的幾類小組,在同一組內選擇實驗單位和非實驗單位,這樣便保證了這兩個單位之間具有了一定的可比性.聚類時,商店的規模、類型、設備狀況、所處的地段、管理水平等就是聚類的分析變數

Ⅳ 聚類分析方法有什麼好處

聚類分析：將個體（樣品）或者對象（變數）按相似程度（距離遠近）劃分類別，使得同一類中的元素之間的相似性比其他類的元素的相似性更強。目的在於使類間元素的同質性最大化和類與類間元素的異質性最大化。其主要依據是聚到同一個數據集中的樣本應該彼此相似，而屬於不同組的樣本應該足夠不相似。
常用聚類方法：系統聚類法，K-均值法，模糊聚類法，有序樣品的聚類，分解法，加入法。
注意事項：
1. 系統聚類法可對變數或者記錄進行分類，K-均值法只能對記錄進行分類；
2. K-均值法要求分析人員事先知道樣品分為多少類；
3. 對變數的多元正態性，方差齊性等要求較高。
應用領域：細分市場，消費行為劃分，設計抽樣方案等
優點：聚類分析模型的優點就是直觀，結論形式簡明。
缺點：在樣本量較大時，要獲得聚類結論有一定困難。由於相似系數是根據被試的反映來建立反映被試間內在聯系的指標，而實踐中有時盡管從被試反映所得出的數據中發現他們之間有緊密的關系，但事物之間卻無任何內在聯系，此時，如果根據距離或相似系數得出聚類分析的結果，顯然是不適當的，但是，聚類分析模型本身卻無法識別這類錯誤。

Ⅳ 什麼是聚類分析

類通過把目標數據放入少數相對同源的組或「類」（cluster）里。分析表達數據，（1）通過一系列的檢測將待測的一組基因的變異標准化，然後成對比較線性協方差。（2）通過把用最緊密關聯的譜來放基因進行樣本聚類，例如用簡單的層級聚類（hierarchical clustering）方法。這種聚類亦可擴展到每個實驗樣本，利用一組基因總的線性相關進行聚類。（3）多維等級分析（multidimensional scaling analysis,MDS）是一種在二維Euclidean 「距離」中顯示實驗樣本相關的大約程度。（4）K-means方法聚類，通過重復再分配類成員來使「類」內分散度最小化的方法。
聚類方法有兩個顯著的局限：首先，要聚類結果要明確就需分離度很好（well-separated）的數據。幾乎所有現存的演算法都是從互相區別的不重疊的類數據中產生同樣的聚類。但是，如果類是擴散且互相滲透，那麼每種演算法的的結果將有點不同。結果，每種演算法界定的邊界不清，每種聚類演算法得到各自的最適結果，每個數據部分將產生單一的信息。為解釋因不同演算法使同樣數據產生不同結果，必須注意判斷不同的方式。對遺傳學家來說，正確解釋來自任一演算法的聚類內容的實際結果是困難的（特別是邊界）。最終，將需要經驗可信度通過序列比較來指導聚類解釋。
第二個局限由線性相關產生。上述的所有聚類方法分析的僅是簡單的一對一的關系。因為只是成對的線性比較，大大減少發現表達類型關系的計算量，但忽視了生物系統多因素和非線性的特點。
從統計學的觀點看，聚類分析是通過數據建模簡化數據的一種方法。傳統的統計聚類分析方法包括系統聚類法、分解法、加入法、動態聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。採用k-均值、k-中心點等演算法的聚類分析工具已被加入到許多著名的統計分析軟體包中，如SPSS、SAS等。
從機器學習的角度講，簇相當於隱藏模式。聚類是搜索簇的無監督學習過程。與分類不同，無監督學習不依賴預先定義的類或帶類標記的訓練實例，需要由聚類學習演算法自動確定標記，而分類學習的實例或數據對象有類別標記。聚類是觀察式學習，而不是示例式的學習。
從實際應用的角度看，聚類分析是數據挖掘的主要任務之一。就數據挖掘功能而言，聚類能夠作為一個獨立的工具獲得數據的分布狀況，觀察每一簇數據的特徵，集中對特定的聚簇集合作進一步地分析。
聚類分析還可以作為其他數據挖掘任務（如分類、關聯規則）的預處理步驟。
數據挖掘領域主要研究面向大型資料庫、數據倉庫的高效實用的聚類分析演算法。
聚類分析是數據挖掘中的一個很活躍的研究領域，並提出了許多聚類演算法。
這些演算法可以被分為劃分方法、層次方法、基於密度方法、基於網格方法和
基於模型方法。
1 劃分方法(PAM:PArtitioning method) 首先創建k個劃分，k為要創建的劃分個數；然後利用一個循環
定位技術通過將對象從一個劃分移到另一個劃分來幫助改善劃分質量。典型的劃分方法包括：
k-means,k-medoids,CLARA(Clustering LARge Application),
CLARANS(Clustering Large Application based upon RANdomized Search).
FCM
2 層次方法(hierarchical method) 創建一個層次以分解給定的數據集。該方法可以分為自上
而下（分解）和自下而上（合並）兩種操作方式。為彌補分解與合並的不足，層次合
並經常要與其它聚類方法相結合，如循環定位。典型的這類方法包括：
第一個是;BIRCH(Balanced Iterative Recing and Clustering using Hierarchies) 方法，它首先利用樹的結構對對象集進行劃分；然後再利
用其它聚類方法對這些聚類進行優化。
第二個是CURE(Clustering Using REprisentatives) 方法，它利用固定數目代表對象來表示相應聚類；然後對各聚類按照指定
量（向聚類中心）進行收縮。
第三個是ROCK方法，它利用聚類間的連接進行聚類合並。
最後一個CHEMALOEN，它則是在層次聚類時構造動態模型。
3 基於密度方法，根據密度完成對象的聚類。它根據對象周圍的密度（如
DBSCAN）不斷增長聚類。典型的基於密度方法包括：
DBSCAN(Densit-based Spatial Clustering of Application with Noise):該演算法通過不斷生長足夠高密
度區域來進行聚類；它能從含有雜訊的空間資料庫中發現任意形狀的聚類。此方法將一個聚類定義
為一組「密度連接」的點集。
OPTICS(Ordering Points To Identify the Clustering Structure):並不明確產生一
個聚類，而是為自動交互的聚類分析計算出一個增強聚類順序。。
4 基於網格方法，首先將對象空間劃分為有限個單元以構成網格結構；然後利
用網格結構完成聚類。
STING(STatistical INformation Grid) 就是一個利用網格單元保存的統計信息進行基
於網格聚類的方法。
CLIQUE(Clustering In QUEst)和Wave-Cluster 則是一個將基於網格與基於密度相結合的方
法。
5 基於模型方法，它假設每個聚類的模型並發現適合相應模型的數據。典型的
基於模型方法包括：
統計方法COBWEB:是一個常用的且簡單的增量式概念聚類方法。它的輸入對象是采
用符號量（屬性-值）對來加以描述的。採用分類樹的形式來創建
一個層次聚類。
CLASSIT是COBWEB的另一個版本.。它可以對連續取值屬性進行增量式聚
類。它為每個結點中的每個屬性保存相應的連續正態分布（均值與方差）；並利
用一個改進的分類能力描述方法，即不象COBWEB那樣計算離散屬性（取值）
和而是對連續屬性求積分。但是CLASSIT方法也存在與COBWEB類似的問題。
因此它們都不適合對大資料庫進行聚類處理.

Ⅵ 什麼是聚類分析聚類演算法有哪幾種

聚類分析又稱群分析，它是研究（樣品或指標）分類問題的一種統計分析方法。聚類分析起源於

分類學，在古老的分類學中，人們主要依靠經驗和專業知識來實現分類，很少利用數學工具進行

定量的分類。隨著人類科學技術的發展，對分類的要求越來越高，以致有時僅憑經驗和專業知識

難以確切地進行分類，於是人們逐漸地把數學工具引用到了分類學中，形成了數值分類學，之後又

將多元分析的技術引入到數值分類學形成了聚類分析。

聚類分析內容非常豐富，有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論

聚類法、聚類預報法等。

聚類分析計算方法主要有如下幾種：分裂法(partitioning methods)：層次法(hierarchical

methods)：基於密度的方法(density-based methods): 基於網格的方法(grid-based

methods): 基於模型的方法(model-based methods)。

Ⅶ 聚類的計算方法

傳統的聚類分析計算方法主要有如下幾種：
1、劃分方法(partitioning methods)
給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：（1） 每一個分組至少包含一個數據紀錄；（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；對於給定的K，演算法首先給出一個初始的分組方法，以後通過反復迭代的方法改變分組，使得每一次改進之後的分組方案都較前一次好，而所謂好的標准就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。使用這個基本思想的演算法有：K-MEANS演算法、K-MEDOIDS演算法、CLARANS演算法；
大部分劃分方法是基於距離的。給定要構建的分區數k，劃分方法首先創建一個初始化劃分。然後，它採用一種迭代的重定位技術，通過把對象從一個組移動到另一個組來進行劃分。一個好的劃分的一般准備是：同一個簇中的對象盡可能相互接近或相關，而不同的簇中的對象盡可能遠離或不同。還有許多評判劃分質量的其他准則。傳統的劃分方法可以擴展到子空間聚類，而不是搜索整個數據空間。當存在很多屬性並且數據稀疏時，這是有用的。為了達到全局最優，基於劃分的聚類可能需要窮舉所有可能的劃分，計算量極大。實際上，大多數應用都採用了流行的啟發式方法，如k-均值和k-中心演算法，漸近的提高聚類質量，逼近局部最優解。這些啟發式聚類方法很適合發現中小規模的資料庫中小規模的資料庫中的球狀簇。為了發現具有復雜形狀的簇和對超大型數據集進行聚類，需要進一步擴展基於劃分的方法。
2、層次方法(hierarchical methods)
這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。例如在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表演算法有：BIRCH演算法、CURE演算法、CHAMELEON演算法等；
層次聚類方法可以是基於距離的或基於密度或連通性的。層次聚類方法的一些擴展也考慮了子空間聚類。層次方法的缺陷在於，一旦一個步驟（合並或分裂）完成，它就不能被撤銷。這個嚴格規定是有用的，因為不用擔心不同選擇的組合數目，它將產生較小的計算開銷。然而這種技術不能更正錯誤的決定。已經提出了一些提高層次聚類質量的方法。
3、基於密度的方法(density-based methods)
基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。這個方法的指導思想就是，只要一個區域中的點的密度大過某個閥值，就把它加到與之相近的聚類中去。代表演算法有：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等；
4、基於網格的方法(grid-based methods)
這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；
很多空間數據挖掘問題，使用網格通常都是一種有效的方法。因此，基於網格的方法可以和其他聚類方法集成。
5、基於模型的方法(model-based methods)
基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。通常有兩種嘗試方向：統計的方案和神經網路的方案。
當然聚類方法還有：傳遞閉包法，布爾矩陣法，直接聚類法，相關性分析聚類，基於統計的聚類方法等。

Ⅷ 四種聚類方法之比較

四種聚類方法之比較
介紹了較為常見的k-means、層次聚類、SOM、FCM等四種聚類演算法，闡述了各自的原理和使用步驟，利用國際通用測試數據集IRIS對這些演算法進行了驗證和比較。結果顯示對該測試類型數據，FCM和k-means都具有較高的准確度，層次聚類准確度最差，而SOM則耗時最長。
關鍵詞:聚類演算法；k-means；層次聚類；SOM；FCM
聚類分析是一種重要的人類行為，早在孩提時代，一個人就通過不斷改進下意識中的聚類模式來學會如何區分貓狗、動物植物。目前在許多領域都得到了廣泛的研究和成功的應用，如用於模式識別、數據分析、圖像處理、市場研究、客戶分割、Web文檔分類等[1]。
聚類就是按照某個特定標准(如距離准則)把一個數據集分割成不同的類或簇，使得同一個簇內的數據對象的相似性盡可能大，同時不在同一個簇中的數據對象的差異性也盡可能地大。即聚類後同一類的數據盡可能聚集到一起，不同數據盡量分離。
聚類技術[2]正在蓬勃發展，對此有貢獻的研究領域包括數據挖掘、統計學、機器學習、空間資料庫技術、生物學以及市場營銷等。各種聚類方法也被不斷提出和改進，而不同的方法適合於不同類型的數據，因此對各種聚類方法、聚類效果的比較成為值得研究的課題。
1 聚類演算法的分類
目前，有大量的聚類演算法[3]。而對於具體應用，聚類演算法的選擇取決於數據的類型、聚類的目的。如果聚類分析被用作描述或探查的工具，可以對同樣的數據嘗試多種演算法，以發現數據可能揭示的結果。
主要的聚類演算法可以劃分為如下幾類：劃分方法、層次方法、基於密度的方法、基於網格的方法以及基於模型的方法[4-6]。
每一類中都存在著得到廣泛應用的演算法，例如：劃分方法中的k-means[7]聚類演算法、層次方法中的凝聚型層次聚類演算法[8]、基於模型方法中的神經網路[9]聚類演算法等。
目前,聚類問題的研究不僅僅局限於上述的硬聚類，即每一個數據只能被歸為一類，模糊聚類[10]也是聚類分析中研究較為廣泛的一個分支。模糊聚類通過隸屬函數來確定每個數據隸屬於各個簇的程度，而不是將一個數據對象硬性地歸類到某一簇中。目前已有很多關於模糊聚類的演算法被提出，如著名的FCM演算法等。
本文主要對k-means聚類演算法、凝聚型層次聚類演算法、神經網路聚類演算法之SOM,以及模糊聚類的FCM演算法通過通用測試數據集進行聚類效果的比較和分析。
2 四種常用聚類演算法研究
2.1 k-means聚類演算法
k-means是劃分方法中較經典的聚類演算法之一。由於該演算法的效率高，所以在對大規模數據進行聚類時被廣泛應用。目前，許多演算法均圍繞著該演算法進行擴展和改進。
k-means演算法以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。k-means演算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心;對剩餘的每個對象，根據其與各簇中心的距離，將它賦給最近的簇;然後重新計算每個簇的平均值。這個過程不斷重復，直到准則函數收斂。通常，採用平方誤差准則，其定義如下：

這里E是資料庫中所有對象的平方誤差的總和，p是空間中的點，mi是簇Ci的平均值[9]。該目標函數使生成的簇盡可能緊湊獨立，使用的距離度量是歐幾里得距離,當然也可以用其他距離度量。k-means聚類演算法的演算法流程如下：
輸入：包含n個對象的資料庫和簇的數目k；
輸出：k個簇，使平方誤差准則最小。
步驟：
(1) 任意選擇k個對象作為初始的簇中心；
(2) repeat；
(3) 根據簇中對象的平均值，將每個對象(重新)賦予最類似的簇；
(4) 更新簇的平均值，即計算每個簇中對象的平均值；
(5) until不再發生變化。
2.2 層次聚類演算法
根據層次分解的順序是自底向上的還是自上向下的，層次聚類演算法分為凝聚的層次聚類演算法和分裂的層次聚類演算法。
凝聚型層次聚類的策略是先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。絕大多數層次聚類屬於凝聚型層次聚類，它們只是在簇間相似度的定義上有所不同。四種廣泛採用的簇間距離度量方法如下：

這里給出採用最小距離的凝聚層次聚類演算法流程：
(1) 將每個對象看作一類，計算兩兩之間的最小距離；
(2) 將距離最小的兩個類合並成一個新類；
(3) 重新計算新類與所有類之間的距離；
(4) 重復(2)、(3)，直到所有類最後合並成一類。
2.3 SOM聚類演算法
SOM神經網路[11]是由芬蘭神經網路專家Kohonen教授提出的，該演算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。
SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特徵。
演算法流程：
(1) 網路初始化，對輸出層每個節點權重賦初值；
(2) 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；
(3) 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；
(4) 提供新樣本、進行訓練；
(5) 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。
2.4 FCM聚類演算法
1965年美國加州大學柏克萊分校的扎德教授第一次提出了『集合』的概念。經過十多年的發展，模糊集合理論漸漸被應用到各個實際應用方面。為克服非此即彼的分類缺點，出現了以模糊集合論為數學基礎的聚類分析。用模糊數學的方法進行聚類分析，就是模糊聚類分析[12]。
FCM演算法是一種以隸屬度來確定每個數據點屬於某個聚類程度的演算法。該聚類演算法是傳統硬聚類演算法的一種改進。

演算法流程：
(1) 標准化數據矩陣；
(2) 建立模糊相似矩陣，初始化隸屬矩陣；
(3) 演算法開始迭代，直到目標函數收斂到極小值；
(4) 根據迭代結果，由最後的隸屬矩陣確定數據所屬的類，顯示最後的聚類結果。
3 四種聚類演算法試驗
3.1 試驗數據
實驗中，選取專門用於測試分類、聚類演算法的國際通用的UCI資料庫中的IRIS[13]數據集，IRIS數據集包含150個樣本數據，分別取自三種不同的鶯尾屬植物setosa、versicolor和virginica的花朵樣本,每個數據含有4個屬性，即萼片長度、萼片寬度、花瓣長度，單位為cm。在數據集上執行不同的聚類演算法，可以得到不同精度的聚類結果。
3.2 試驗結果說明
文中基於前面所述各演算法原理及演算法流程，用matlab進行編程運算，得到表1所示聚類結果。

如表1所示，對於四種聚類演算法，按三方面進行比較：(1)聚錯樣本數：總的聚錯的樣本數，即各類中聚錯的樣本數的和；(2)運行時間：即聚類整個過程所耗費的時間，單位為s；(3)平均准確度：設原數據集有k個類,用ci表示第i類，ni為ci中樣本的個數，mi為聚類正確的個數,則mi/ni為第i類中的精度，則平均精度為：

3.3 試驗結果分析
四種聚類演算法中，在運行時間及准確度方面綜合考慮，k-means和FCM相對優於其他。但是，各個演算法還是存在固定缺點：k-means聚類演算法的初始點選擇不穩定，是隨機選取的，這就引起聚類結果的不穩定，本實驗中雖是經過多次實驗取的平均值，但是具體初始點的選擇方法還需進一步研究；層次聚類雖然不需要確定分類數，但是一旦一個分裂或者合並被執行，就不能修正，聚類質量受限制；FCM對初始聚類中心敏感，需要人為確定聚類數，容易陷入局部最優解；SOM與實際大腦處理有很強的理論聯系。但是處理時間較長，需要進一步研究使其適應大型資料庫。
聚類分析因其在許多領域的成功應用而展現出誘人的應用前景，除經典聚類演算法外，各種新的聚類方法正被不斷被提出。

Ⅸ 聚類演算法有哪幾種

聚類演算法有：聚類分析是通過數據建模簡化數據的一種方法。傳統的統計聚類分析方法包括系統聚類法、分解法、加入法、動態聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。採用k均值、k中心點等演算法的聚類分析工具已被加入到許多著名的統計分析軟體包中，如SPSS、SAS等。