胡春玲　汪川　馬婷婷　汪方旭　朱孝城

摘要：聚類是一個將數(shù)據(jù)集劃分為若干個簇的過程，在機器學(xué)習(xí)和數(shù)據(jù)挖掘中的有廣泛的應(yīng)用。該文綜述了經(jīng)典的聚類算法，在酵母基因表達數(shù)據(jù)集上實現(xiàn)了 K-means聚類算法，并對聚類結(jié)果進行了分析。

關(guān)鍵詞：聚類；K-means算法；基因表達數(shù)據(jù)

中圖分類號：TP181 文獻標識碼：A 文章編號：1009-3044(2014)26-6155-03

Abstract: Clustering divides a data set into several clusters, which is widely used in machine learning and data mining. The paper reviews the classical clustering algorithms, implements K means clustering algorithm on yeast gene expression data set, and the clustering results are analyzed.

Key words: Clustering; K-means algorithm; gene expression data

聚類是一個將數(shù)據(jù)集劃分為若干簇或類的過程,由聚類所組成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一簇中的對象彼此類似，與其他簇中的對象相異。聚類分析具有堅實的理論基礎(chǔ)，并形成了系統(tǒng)的方法學(xué)體系。聚類算法在數(shù)據(jù)挖掘中的應(yīng)用非常廣泛。

1 聚類算法

目前，聚類算法有很多種。算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和應(yīng)用。由于各種聚類算法之間存在很多交集，它們之間并不是完全獨立的，所以很難對聚類算法進行嚴格意義上的劃分。聚類算法可進行如下大致劃分。

1) 基于層次的聚類方法

層次聚類法對給定的數(shù)據(jù)對象集合進行層次分解。按層次分解的形成方式，層次法可分為凝聚和分裂兩大類。凝聚的方法是一種自底向上的方法，初始狀態(tài)下，每個對象構(gòu)成單獨的一個類，然后按照選擇的度量標準，相繼地合并相近的簇，直到所有的簇合并為設(shè)定的類別數(shù)為止。分裂的方法是一種自頂向下的方法，一開始將所有的對象置于一個類中。在迭代的每一步中，簇被分裂為更小的簇，直到得到用戶定義的希望得到的簇的數(shù)目為止。

在簇的合并或分裂過程中，需要選擇度量標準。簇間距離廣泛采用的度量標準有最小距離、最大距離和平均距離等。層次聚類方法中代表算法有Birch、Cure、Rock等[1-2]。

2) 基于劃分的聚類方法

針對包含n個數(shù)據(jù)對象的數(shù)據(jù)集，劃分法構(gòu)建數(shù)據(jù)的預(yù)先設(shè)定k個劃分(k≤n)，即k個類或簇。首先根據(jù)要構(gòu)建的劃分數(shù)目k，創(chuàng)建一個初始劃分。然后根據(jù)選擇的度量標準，采用迭代方法，嘗試通過對象在劃分間移動來優(yōu)化劃分。判定一個好的劃分的 準則是：在同一個簇中的對象之間盡可能接近，在不同簇中的對象之間盡可能遠離 ，即使所選擇的度量標準取得最小值?；趧澐值姆椒ǖ牡湫退惴ㄓ蠯-means、K-medoids、大型數(shù)據(jù)庫劃分方法（Clarans）等。[3-4]

3) 基于密度的聚類方法

絕大多數(shù)劃分方法基于對象之間的距離進行聚類，這類方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上有困難。因此，出現(xiàn)了基于密度的聚類方法，其主要思想是：簇是由稠密數(shù)據(jù)點組成，簇與簇之間由稀疏區(qū)域分割，即在一個給定范圍的區(qū)域簇中必須至少包含某個數(shù)目的點。K-means算法首先隨機的選擇K個數(shù)據(jù)點作為K個簇的初始中心，根據(jù)最近鄰原則，為每個簇選擇初始數(shù)據(jù)點，在每一次的迭代過程中，更新每個簇的中心，更新每個簇的數(shù)據(jù)點，直到目標函數(shù)取得最優(yōu)值為止。

的基本思想是首先從含有n個數(shù)據(jù)對象的數(shù)據(jù)集中隨機選擇K個數(shù)據(jù)對象作為初始中心，然后計算每個數(shù)據(jù)對象到各中心的距離，，所有數(shù)據(jù)對象將會被劃分到離它最近的那個中心所代表的簇中，接著分別計算新生成的各簇中數(shù)據(jù)對象的均值作為各簇新的中心，比較新的中心和上一次得到的中心，如果新的中心沒有發(fā)生變化，則算法收斂，輸出結(jié)果，如果新的中心和上一次的中心相比發(fā)生變化，則要根據(jù)新的中心對所有數(shù)據(jù)對象重新進行劃分。直到滿足算法的收斂條件為止。

2) 算法主要步驟

4 結(jié)束語

聚類是一種常用的數(shù)據(jù)挖掘方法，在生物信息挖掘領(lǐng)域有廣闊的應(yīng)用前景，該文在酵母基因表達數(shù)據(jù)集上實現(xiàn)了經(jīng)典聚類算法K-means，今后將針對基因表達數(shù)據(jù)的特點，開發(fā)更為高效的聚類算法。

參考文獻:

[1] 周迎春,駱嘉偉. 一種改進的BIRCH聚類分析算法及其應(yīng)用研究[J]. 湛江師范學(xué)院學(xué)報, 2009(3).

[2] 雷小鋒,高韜,謝昆青,等.擴展空間對象聚類問題的研究[J]. 計算機工程與應(yīng)用,2003(23).

[3] 于麗.一種改進的K-means聚類算法[J]. 遼寧師專學(xué)報, 2010(2).

[4] 王秀坤. 基于劃分的聚類算法研究與應(yīng)用[D].大連理工大學(xué),2008.

[5] 榮秋生,顏君彪,郭國強.基于DBSCAN聚類算法的研究與實現(xiàn)[J]. 計算機應(yīng)用,2004(4).

[6] 張建偉,王玲艷,姚云磊.一種基于OPTICS聚類的流量分類算法[J].鄭州輕工業(yè)學(xué)院學(xué)報,2013(2).