针对微阵列基因表达数据的聚类算法应用研究

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

摘要：聚类是一个将数据集划分为若干个簇的过程，在机器学习和数据挖掘中的有广泛的应用。该文综述了经典的聚类算法，在酵母基因表达数据集上实现了 K-means聚类算法，并对聚类结果进行了分析。

关键词：聚类；K-means算法；基因表达数据

中图分类号：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

聚类是一个将数据集划分为若干簇或类的过程,由聚类所组成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此类似，与其他簇中的对象相异。聚类分析具有坚实的理论基础，并形成了系统的方法学体系。聚类算法在数据挖掘中的应用非常广泛。

1 聚类算法

目前，聚类算法有很多种。算法的选择取决于数据的类型、聚类的目的和应用。由于各种聚类算法之间存在很多交集，它们之间并不是完全独立的，所以很难对聚类算法进行严格意义上的划分。聚类算法可进行如下大致划分。

1) 基于层次的聚类方法

层次聚类法对给定的数据对象集合进行层次分解。按层次分解的形成方式，层次法可分为凝聚和分裂两大类。凝聚的方法是一种自底向上的方法，初始状态下，每个对象构成单独的一个类，然后按照选择的度量标准，相继地合并相近的簇，直到所有的簇合并为设定的类别数为止。分裂的方法是一种自顶向下的方法，一开始将所有的对象置于一个类中。在迭代的每一步中，簇被分裂为更小的簇，直到得到用户定义的希望得到的簇的数目为止。

在簇的合并或分裂过程中，需要选择度量标准。簇间距离广泛采用的度量标准有最小距离、最大距离和平均距离等。层次聚类方法中代表算法有Birch、Cure、Rock等[1-2]。

2) 基于划分的聚类方法

针对包含n个数据对象的数据集，划分法构建数据的预先设定k个划分(k≤n)，即k个类或簇。首先根据要构建的划分数目k，创建一个初始划分。然后根据选择的度量标准，采用迭代方法，尝试通过对象在划分间移动来优化划分。判定一个好的划分的 准则是：在同一个簇中的对象之间尽可能接近，在不同簇中的对象之间尽可能远离 ，即使所选择的度量标准取得最小值。基于划分的方法的典型算法有K-means、K-medoids、大型数据库划分方法（Clarans）等。[3-4]

3) 基于密度的聚类方法

绝大多数划分方法基于对象之间的距离进行聚类，这类方法只能发现球状的簇，而在发现任意形状的簇上有困难。因此，出现了基于密度的聚类方法，其主要思想是：簇是由稠密数据点组成，簇与簇之间由稀疏区域分割，即在一个给定范围的区域簇中必须至少包含某个数目的点。K-means算法首先随机的选择K个数据点作为K个簇的初始中心，根据最近邻原则，为每个簇选择初始数据点，在每一次的迭代过程中，更新每个簇的中心，更新每个簇的数据点，直到目标函数取得最优值为止。

的基本思想是首先从含有n个数据对象的数据集中随机选择K个数据对象作为初始中心，然后计算每个数据对象到各中心的距离，，所有数据对象将会被划分到离它最近的那个中心所代表的簇中，接着分别计算新生成的各簇中数据对象的均值作为各簇新的中心，比较新的中心和上一次得到的中心，如果新的中心没有发生变化，则算法收敛，输出结果，如果新的中心和上一次的中心相比发生变化，则要根据新的中心对所有数据对象重新进行划分。直到满足算法的收敛条件为止。

2) 算法主要步骤

4 结束语

聚类是一种常用的数据挖掘方法，在生物信息挖掘领域有广阔的应用前景，该文在酵母基因表达数据集上实现了经典聚类算法K-means，今后将针对基因表达数据的特点，开发更为高效的聚类算法。

参考文献:

[1] 周迎春,骆嘉伟. 一种改进的BIRCH聚类分析算法及其应用研究[J]. 湛江师范学院学报, 2009(3).

[2] 雷小锋,高韬,谢昆青,等.扩展空间对象聚类问题的研究[J]. 计算机工程与应用,2003(23).

[3] 于丽.一种改进的K-means聚类算法[J]. 辽宁师专学报, 2010(2).

[4] 王秀坤. 基于划分的聚类算法研究与应用[D].大连理工大学,2008.

[5] 荣秋生,颜君彪,郭国强.基于DBSCAN聚类算法的研究与实现[J]. 计算机应用,2004(4).

[6] 张建伟,王玲艳,姚云磊.一种基于OPTICS聚类的流量分类算法[J].郑州轻工业学院学报,2013(2).