第一章Microarray 介绍
1.1 生物信息处理
基于对生物体“硬件”和“软件”的认识 ,提出暂时地撇开生物的物理属性 ,着重研究其信息属性 ,从而进入到生物信息处理 (关于生命硬件的信息和软件的信息 ,即生理信息和生命信息 )的一个分支 ,生物信息学。于是 ,为揭开生命之秘、揭示与生命现象相关的复杂系统的运作机制打开一条新的途径。
什么是生物信息处理
生物信息处理的英文是Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ。 1994年初 ,诺贝尔医学奖获得者美国教授Ｍ·罗德贝尔发表一篇评论 ,题为《生物信息处理 :评估环境卫生的新方法》。他认为生物信息处理是在基因数据库基础上 ,计算机驱动的能快速获得表达基因部分序列的方法。通过ＭＥＤＬＩＮＥ数据库 ,可以查阅到很多与生物信息处理 (Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ)有关的记录，其中ＪＦＡｉｔｏｎ认为生物信息处理是基于计算机的数据库和信息服务;ＲＰＭｕｒｒａｙ认为生物信息处理包括两方面：第一是大量现存数据的自动化处理 ,第二是新的信息资源的生成；ＤＢｅｎｔｏｎ在题为《生物信息处理———一个新的多学科工具的原理和潜力》的文章中说 ,生物信息处理的材料是生物学数据 ,其方法来自广泛的各种各样的计算机技术。其方法来自广泛的各种各样的计算机技术。近年来 ,生物学数据在爆炸式增长 ,新的计算机方法在不断产生。这些方法在结构生物学、遗传学、结构化药品和分子演变学中是研究工作进展的基础。如果生物医学工程要在各个领域都从研究进展中获取最大好处 ,那么生物学数据健全的基础设施的开发与维护是同等重要的。尽管生物信息处理已经作出重要贡献 ,但是在它成熟时就会面临更大的需求在爆炸式增长 ,新的计算机方法在不断产生。这些方法在结构生物学、遗传学、结构化药品和分子演变学中是研究工作进展的基础。如果生物医学工程要在各个领域都从研究进展中获取最大好处 ,那么生物学数据健全的基础设施的开发与维护是同等重要的。尽管生物信息处理已经作出重要贡献 ,但是在它成熟时就会面临更大的需求。
在整体上可以看出 ,生物信息处理的两个基本内容是生物数据库建立和计算机信息服务 ,也就是生物数据处理的计算机数据库化和程序化。当前这种数据库的内容主要是目录、期刊、遗传基因和细胞三维结构学。服务程序主要用于信息检索和基因序列分析。
所以 ,严格地说 ,当前生物信息处理远未形成独立的学科 ,它同计算机生物学应用并无重大区别。在1998年第九届世界医药信息学大会上 ,它才作为一个讨论题目被列出来。可以说，生物信息处理技术是一项年轻的研究领域。
1．2 Microarray 技术
1．2．1 Microarray 技术原理
微阵列技术是利用分子杂交的原理，用自动化仪器arrayer把不同的，数以百计、千计、万计已知部分序列的DNA探针“印”在玻璃片或者尼龙膜上面成阵列。为了比较两份标本中核酸表达的丰度，两份标本中核酸用同位素或者荧光素（红和绿两种）标记，再于微阵列杂交，然后检测杂交信号的强度，通过一定的数据处理系统，把它们转化成两份不同标本中特异基因的丰度，最后对这些数据进行分析。
根据微阵列技术原理，微阵列技术的处理流程如下：
1. 实验设计
2. 样品制备（指mRNA或总RNA样品，包括对照组和实验组）
3. 芯片制备（包括PCR，纯化，点样等步骤）
4. 芯片杂交（将mRNA或总RNA分别进行逆转录生成cDNA，在此步骤中
将对照组和实验组cDNA分别标记CY3和CY5荧光信号）
5. 芯片扫描（采用激光扫描仪，分别用532nm和635nm波长激光扫描芯片，
对于每张芯片，得到CY3和CY5通道两幅图象）
6. 图象处理（采用专门软件，对图象进行分析，提取每个点上的数字信号），
得到原始数据表。
7. 数据校正和筛选（对cy5或cy3信号进行校正，消除实验或扫描等各环节
因素对数据的影响，同时利用筛选规则对数据中的“坏点”，“小点”，“低信号点”进行筛选，并作标记。）
8. 差异表达基因的确定（采用ratio值对差异基因进行判断，或采用统计方
法如线性回归、主成分分析、调整P值算法等对差异基因进行统计推断）
9. 生物信息学分析（如cluster 算法、差异基因的同源性比对，差异基因的
相关文献检索等）
一个最简单的配置应包括微阵列制作系统 (ａｒｒａｙｅｒ) ,信号收集系统(ｓｃａｎｎｅｒ) ,计算机和软件 (操作系统和微阵列技术处理的相关软件 )。
1．2．2 Microarray 技术应用领域
Microarray 技术是近几年兴起的新技术，但短短几年中，该技术已经被分子生物学的很多领域接受，并广泛应用于以下领域：
1、基因表达分析和检测
微阵列技术已经被许多研究小组应用于与基因表达有关的工作中,如对细菌、动植物和人类的研究。包括：特异性相关的基因、差异表达的基因、基因功能研究、健康状况的检测、毒理学研究、药物作用机制的研究、定位克隆。
2、功能分析
检测到基因表达差异之后 ,下一步是寻找这些差异的生物学功能。
最近Ｄａｖｉｓ等人[1 7]发明了一种新的方法。主要是应用插入一个独特序列或标记的突变酵母链。分子标记在特殊的的生长条件下从生存链中扩增 ,并与高密度微阵列进行杂交。这样不仅可以确定这条链的相对丰度 ,而且可以在不同时间点反复进行 ,同时还可以精确比较每条缺失链的适应性。
3、基因作图
微阵列技术的应用补充了基因表达研究的方法 ,加强了对疾病易感性和疾病本质的研究。这种方法无论是在速度上还是在准确性上都远胜于传统方法 ,它将会改变基因制图的方法。
1．2．3 Microarray 技术发展现状
DNA微阵列技术（DNA microarray technology）是近几年发展起来的应用DNA 微阵列进行基因功能研究的新的生物技术。微阵列自1995年在《Ｓｃｉｅｎｃｅ》上报道后 ,被认为是该年度《Ｓｃｉｅｎｃｅ》上发表的最有影响的文章之一。微阵列是新出现的分子生物学技术 ,是本世纪重要的科学进展 ,它能够高效率、大规模地获取相关生物信息 ,是现代生物技术、微电子技术、机械制造技术、计算机技术的结合。其对科学的深远影响将远胜过ＤＮＡ测序和ＰＣＲ等,使人们更大规模
地获取生物信息 ,使人类基因组计划早日实现。
微阵列技术的迅速发展已经引起了各方面的广泛关注。许多实验室、专业公司和制药公司都在大力开发与此相关的技术。在制作设备、分析设备、支持软件和探针的构建等方面均投入巨资 ,尤其是一些新兴的从事微阵列相关产业的公司如Ａｆｆｙｍｅｔｒｉｘ ,Ｉｎｃｙｔｅ,Ｓｙｎｔｅｎｉ,Ｃｌｏｎｔｅｃｈ等公司均已研制生产出相关的产品。有供诊断用的芯片如ＨＩＶ ,ｐ53和细胞色素ｐ450的芯片 ;
有可供研究用的人、大鼠、小鼠不同基因类别的芯片 ;有与不同疾病如肿瘤、心血管疾病、神经系统疾病相关的芯片也已投入使用。而且很多公司可根据需要定制各种微阵列系统 ,为研究人员提供方便。国内也开展了此项工作 ,清华大学、上海细胞生物所、军事医学科学院放射医学研究所及广州等地正在进行此项研究。微阵列技术的发展为探索生命科学提供了强有力的工具。使一些原本复杂的工作变得简捷。正如ＮＩＨ的主任ＨａｒｏｌｄＶａｒｍｕｓ在旧金山美国细胞生物学年会上指出的 :“应用微阵列技术 ,我们将最终揭示单个细胞的全部基因表达 ,甚至整个机体的基因概况”。同时 ,他还预言 :“微阵列技术将改变我们对生命本质的认识”。
1．3 本次毕业设计的目标
微阵列（Microarray ）技术是一门新兴学科，它是结合了生物学、计算机技术、电子技术、生物信息学的特征而形成的一门交叉学科。
微阵列技术发展到现在，虽然已经取得了惊人的改变和进步，广泛应用于分子生物学领域。但是，微阵列技术毕竟是一门新学科、一种新的思维方法，还需要在新的环境和领域下进行试验和完善，特别是在于其它学科、技术的结合方面，还需要研究人员花一定时间来研究和试验。
本次毕业设计要达到以下的目标：
（1）学习生物信息学的背景知识和微阵列技术的处理流程；
（2）学习聚类分析中的主要概念和技术方法，并阐述聚类分析在微阵列技术中的重要地位；
（3）分析几种常用的聚类方法，将其中存在的一些问题提炼出来加以分析；
（4）在前几步的基础之上，结合所分析的常用算法设计一种改进算法；
（5）用C语言实现设计的聚类算法和数据预处理工作。
第二章聚类分析方法概述
2．1 聚类分析及相关概念
簇（Cluster）是指一个数据对象的集合。聚类就是将物理或抽象对象的集合分组成为由类似的对象组成的多个簇的过程。由聚类所生成的簇是一组数据对象的集合，这些对象于同一个簇中的对象彼此相似，与其它簇中的对象相异。在许多应用中可以将一个簇中的对象作为一个整体来对待。
聚类是通过对数据对象本身数据的分析，从而将数据对象分成不同的类。聚类是一种无监督分类法，没有预先指定的类别。在机器学习领域，聚类是无指导学习（unsupervised clustering）。与分类不同，聚类和无指导学习不依赖预先定义的类和带类标号的训练实例。由于这个原因，聚类是观察式学习，而不是示例式学习。
聚类分析已经广泛的应用在许多领域中，包括模式识别、数据分析、图像处理、以及市场研究。通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。
“聚类的典型应用是什么？”在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。聚类在地球观测数据库中相似地区的确定和汽车保险单持有者的分组上也可以发挥作用。聚类也能用于对Web上的文挡进行分类，以发现信息。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇作进一步的分析，获得对种群中固有结构的认识。此外，聚类分析可以作为其他算法（如特征和分类等）的预处理步骤，这些算法再在生成的簇上进行处理。
数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘，统计学，机器学习，空间数据库技术，生物学，以及市场营销。由于数据库中收集了大量的数据，聚类分析已经成为生物学种生物信息分析研究领域中一个非常活跃的研究课题。
聚类是一个富有挑战性的研究领域，那么怎样才算是一个好的聚类方法?最重要的是，一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：
高的簇内相似性 低的簇间相似性
此外，在不同的领域有一些对聚类更深入的要求，例如在生物信息学中对聚类算法的更深一步要求如下：
1．能应付脏数据。绝大多数现实世界中的数据库都包含了孤立点、空缺、未知数据或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。
2．对于数据不同的顺序不敏感。一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的顺序提交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。 3．模型可解释性和可使用性。用户希望聚类结果是可解释的、可理解的和可用的。也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。
2．2 聚类分析中的数据类型
在本节，我们研究在聚类分析中经常出现的数据类型，以及如何对其进行预处理。许多基于内存的聚类算法选择如下两种有代表性的数据结构：
·数据矩阵（data matrix ，或称为对象与变量结构）：它用p 个变量（也称为度量或属性）来表现n 个对象，例如用年龄、身高、体重、性别、种族等属性来表现对象“人”。这种数据结构是关系表的形式，或者看成n ×p （n 个对象×p 个变量）
的矩阵。图示如下：
·相异度矩阵（dissimilarity matrix ，或称为对象－对象结构）：存储n 个对象两两之间的近似性，表现形式是一个n ×n 维的矩阵。图示如下：
??????????????????np x ...
nf
x ...
n1
x ...............ip x ...if x
...i1x ...............1p x
...1f
x (11)
x ???????
?
?????
?
??0...
)
2,()
1,(:::)2,3()...
n d n d 0d d(3,10d(2,1)
在这里d(i ，j)是对象i 和对象j 之间相异性的量化表示，通常它是一个非负的数值，当对象i 和j 越相似或“接近”，其值越接近0；两个对象越不同，其值越大。其中d(i,j)=d(j,i)，而且，d(i,i)=0。关于相异度，我们在下面的内容中进行详细探讨。
聚类分析中的数据类型
区间标度变量
区间标度变量是一个粗略现行标度的连续度量。典型的例子包括重量和高度、经度和纬度坐标（如聚类房屋），以及大气温度。度量单位的选取对于聚类的结果的很重要的。例如将身高的单位从米变为尺，将体重的单位从公斤变为磅将对聚类的结果产生很大的影响。为了避免出现这种情况，我们必须将数据标准化，将数据的单位化成同样的权重，并将数据中的单位“去掉”。当没有关于数据的先验知识时，这样做是十分有用的。
因为在Microarray 分析技术中，涉及到的数据类型是区间标度变量，所以，下面就对区间标度变量作详细的介绍和讨论，其它的数据类型只做简单的介绍。
“怎样将一个变量的数据标准化？”为了实现度量值的标准化，一种方法是将原来的度量值转换为无单位的值。给定一个变量f 的度量值，可以进行如下的变换：
计算绝对偏差的平均值:
其中
|)
|...|||(|121f nf f f f f f m x m x m x n s -++-+-=.
)...211nf
f
f f x x (x n
m +
++=
计算标准度量值 (z-score )
使用绝对偏差的平均值比使用标准偏差更健壮（robust ）。两个对象之间的相异度（相似度）通常是基于对象间的距离来计算的。
最常用的距离度量方法是欧几里德距离，它的定义如下：
其中 i = (x i1, x i2, …, x ip ) 和 j = (x j1, x j2, …, x jp ) 是两个p 维的数据对象
另一个著名的度量方法是曼哈坦距离，其定义如下：
其中 i = (x i1, x i2, …, x ip ) 和 j = (x j1, x j2, …, x jp ) 是两个p 维的数据对象
上面的距离函数有如下特性：
d(i,j) >= 0：距离是一个非负的数值。d(i,i) = 0：一个对象与自身的距离是零
d(i,j) = d(j,i)：距离函数具有对称性
d(i,j)<= d(i,k) + d(k,j)：从对象i 到对象j 的直接距离不会大于途经任何其它对象 h 的距离（三角不等式）。
明考斯基距离（ Minkowski distance ）是欧几里德距离和曼哈坦距离的概化，它的定义如下：
其中 i = (x i1, x i2, …, x ip ) 和 j = (x j1, x j2, …, x jp ) 是两个p 维的数据对象, q 是一个正整数。
f
f
if
if s
m
x
z -=)
||...|||(|),(2
222211p
p j x i x j x i x j x i x j i d -++-+-=
||...||||),(2211p
p j x i x j x i x j x i x j i d -++-+-=q q
p
p q q j x i x j x i x j x i x j i d )||...|||(|),(2211-++-+-=
当q = 1时, d 称为曼哈坦距离（ Manhattan distance）；当q=2时, d 就成为欧几里德距离；当变量的重要性不同时，可以根据每个变量的重要性赋予一个权重。
对于区间标度变量来说，一旦选定一种距离作为衡量相异度（相似度）的基础，对象之间的距离越近，表示两个对象之间越相似，否则，表示两个对象之间越相异。对于类也是这样定义的：两个类之间的距离越近，表示两个类之间越相似，否则，表示两个类之间越相异。但是，类间距离的定义有几种方法，下面给出了四种常用
测定两个类之间距离的方法，这儿的m
i 是类c
i
的中间值，n
i
是c
i
中记录的个数，
|p-p’|是两个记录之间的距离。
1．单连通方法（single-link method）：取两个类中最近记录的距离为类的距离，
即Minimum distance： Dmin(C
i ,C
j
)=Min|p-p’|(这儿p在类C
i
中p’在C
j
中)。
此种方法可以生成细长的蛇形类，不适于应用在典型的一堆堆记录集合在一起的情况。
2．完全连通方法（complete-link method）：取两个类中最远记录的距离为类的距
离，即Maximum distance：Dmax(C
i ,C
j
)=Max|p-p’|(这儿p在类C
i
中p’在C
j
中)。
同第1中方法相反，此种方法易生成很小的记录都聚集在一起的类。
3．平均连通方法（group-average link）：计算两个类中所有记录对的距离平均值，
即Average distance： Davg(C
i ,C
j
)=(1/n
i
*n
j
)∑p∈Ci∑p’ ∈Cj。效果介于1、
2种算法之间。
4．Ward方法（Ward’s method）：计算两个类中所有记录的距离的和，即Sum
distance： Dsum(C
i ,C
j
)=∑p?Ci∑p’ ?Cj。易于用在生成类层次的情况，对例
外的数据（outliers）很敏感，很难应用于生成蛇形类。
5．类平均值连通方法：取两个类中间值的距离为类的距离，即Mean distance：
Dmean(Ci,Cj)=|mi-mj|（m
i 是类c
i
的中间值）。此种方法是一种结合上面各种方法
的措施，生成的聚类效果各项指标比较平均。
二元变量
一个二元变量只有两个状态：0或1，0表示该变量为空，1表示该变量存在。例如，给出一个描述病人的变量smoker，1表示病人抽烟，而0表示病人不抽烟。二元变量要采用特定的方法来计算其相异度。
标称变量
标称变量是二元变量的推广，它可以具有多于两个的状态，比如变量
map_color可以有 red, yellow, blue, green四种状态。
序数型变量
一个序数型变量可以是离散的也可以是连续的。离散的序数型变量类似于标称变量，除了它的M个状态是以有意义的序列排序的，比如职称；连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。
比例标度型变量
比例标度型变量是总取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如 Ae Bt or Ae-Bt。
混合类型的变量
在许多真实的数据库中。对象是被混合类型的变量描述的。一般来说，一个数据库可能包含上面列出的全部六种变量类型。
上面介绍的非区间标度变量是不能像处理区间标度变量来对待的，否则，会误导聚类结果，所以要采用特定的方法来计算其相异度。
2．3 主要聚类分析方法分类
目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，已发现数据可能揭示的结果。
大体上，主要的聚类算法可以划分为如下几类：
（1）划分方法（partitioning method）：给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚簇，并且k<=n。也就是说，他将数据划分为k个组，同时满足如下的要求：（i）每个组至少包含一
个对象；（ii）每个对象必须属于且只属于一个组。注意在某些模糊划分技术中的二个要求可以放宽。
给定要构件的划分的数目k，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是：在同一个类中的对象之间进可能“接近”或相关，而不同类中的对象之间尽可能“远离”或“不同”。还有许多其它划分质量的评判准则。
为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：（i）k－平均算法，在该算法中，每个簇用该簇中对象的平均值来表示。（ii）k－中心点算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法对中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。
（2）层次的方法（hierarchical method）：层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自低向上的方法，一开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。
层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。但是，该技术的一个主要问题是它不能更正错误的决定。
（3）基于密度的方法（density-based method）：绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阀值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。DBSCAN是一个由代表性的基于密度的方法，它根据一个密度阀值来控制簇的增长。
（4）基于网络的方法（grid-based method）：基于网络的方法把对象空间尽量化为有限数目的单元，形成一个网络结构。所有的聚类操作都在这个网络结
构（即量化的空间）上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维单元数目有关。
（5）基于模型的方法（model-based method）：基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。
一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚类标准，要求综合多个聚类技术。
2．4 聚类分析在Microarray分析中的位置及应用
微阵列（Microarray）技术在基因表达分析中的工作流程简单概括起来，分为以下几个过程：基因数据的收集、数据预处理、数据聚类分析、预测。聚类分析在整个过程中是承上启下的作用，聚类分析的对象（基因数据）来源于前期收集的数据，通过聚类分析，可以发现已经收集数据的正误，同时，也能根据数据本身的特征对数据进行分类，最后的聚类成果将为后面的预测工作提供材料。可以说，聚类分析在整个Microarray分析工程中非常重要，聚类分析算法的选择将影响到数据预处理过程，也将影响到最后的预测结果。所以，选择合适的聚类分析算法将有益于及时发现源数据中的“脏数据（有误的数据）”并修正源数据，对源数据进行高质量的聚类，产生高质量的聚类结果，为后面的预则过程提供高质量的材料，从而改善预测结果，这样，就提高了整个微阵列（Microarray）分析技术的工作质量！
第三章聚类分析方法的分析
3．1 评价聚类分析方法好坏的准则
在微阵列（Microarray）分析中，保证最后聚类的质量是最重要的，以下几个方面是Microarray分析中对聚类算法选择的要求：
1．高的簇内相似性。
2．低的簇间相似性。
聚类定义的内涵就是：将一个对象的集合分割成几个类，每个类内的对象
之间是相似的，但与其他类的对象是不相似的。所以说，这两点是一个聚
类算法最根本也是最重要的要求。但是，一般来说一个数据库没有一种最
好的分类方法。这是因为，聚类算法中的“相似度”是人为主观定义的，
“相似性”也是根据算法中“相似度”的定义来判断的。因此，好的聚类
算法要在类中对象的相似程度和类的数目之间找到一个最佳的结合点。
3．能应付脏数据。绝大多数现实世界中的数据库都包含了孤立点、空缺、未知数据或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。
4．对于数据不同的顺序不敏感。一些聚类算法对于输入数据的顺序是敏感的。
例如，同一个数据集合，当以不同的顺序提交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。
5．模型可解释性和可使用性。用户希望聚类结果是可解释的、可理解的和可用的。也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。
3．2 常见聚类分析方法的分析
3．2．1 划分方法
划分方法: 将一个包含n个数据对象的数据库组织成k个划分（k<=n），其中每个划分代表一个簇（Cluster）。也就是给定一个k，要构造出k个簇。通常会采用一个划分准则（经常称为相似度函数），例如距离，以便在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。
典型的划分方法有：k-平均和k-中心点
1．k-平均方法（基于质心的技术）
k-平均方法以k为参数，把n个对象分为n个簇，以使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（被看做簇的重心）来进行。
给定k，算法的处理流程如下:
算法：k-平均。划分的k-平均算法基于簇中的平均值。
输入：簇的数目k和包含个n对象的数据库
输出：k个簇，效果最好的聚类
方法：
1．随机的选择k个对象作为初始的簇中心；
2．repeat
3．计算每个簇的平均值，并用该平均值代表相应的簇；
4. 将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；
5．更新簇的平均值，即计算每个簇中对象的平均值；
6. until直到不再有新的分配发生
该算法流程的图示如下：
对k-平均方法的分析如下：
优点
1、当结果簇是密集的，而簇于簇之间区别明显时，它的效果较好；
2、对于处理大数据集，该算法是相对高效的: 算法复杂度O(tkn), 其中n 是数据
对象的个数, k 是簇的个数, t是迭代的次数，通常k, t << n；
3、算法通常终止于局部最优解。
缺点
1、只有当平均值有意义的情况下才能使用，对于类别字段不适用；
2、必须事先给定要生成的簇的个数k；
3、对“噪声”和异常数据敏感，少量的该类数据能够对平均值产生极大的影响；
4、不能发现非凸面形状的数据；
5、对初始簇的随机选择算法对聚类结果也会产生随机的影响。
由于上述的几个缺点，简单的用k-平均方法来处理Microarray分析中的聚类问题是不满足要求的，需要改进其中的步骤、流程，或者是和其它的方法结合起来用。
2．k-中心点方法（基于有代表性的对象的技术）
从上面对k-平均方法的分析我们可以看出：一个有极大值的对象可能相当程度上扭曲数据的分布，k-平均算法对于脏数据是敏感的。那么，“如何修改这个算法来消除这种敏感性？”不采用簇中对象的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点。这样的划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。这是k-中心点方法的基础。
k-中心点聚类算法的基本策略如下所示：
算法：k-中心点。对基于中心点或中心对象的划分的典型k-中心点算法。
输入：簇的数目k和包含个n对象的数据库。
输出：k个簇，使得所有对象与其最近中心点的相异度总和最小。
方法：
1．随机的选择k个对象作为初始的簇中心；
2．repeat
3．指派每个剩余的对象给离它最近的中心点所代表的簇；
4. 随机的选择一个非中心点对象O random；
5．计算用O random代替O j的总代价S；
6．If S<0,then O random替换O j，形成新的k个中心点的集合；
7. until直到不再有新的变化发生
可以说，k-中心点方法是k-平均方法的改进，这种改进是为了防止有极大值脏数据。但是，k-中心点方法的执行代价比k-平均方法高。此外，以下的两个缺点没有得到解决：
1、必须事先给定要生成的簇的个数k；
2、对初始簇的随机选择算法对聚类结果也会产生随机的影响。
3．2．2 层次方法
层次聚类，按照聚类的层次结构可以把所有的记录层次聚类可以分为两种：凝聚的方式和分割的方式，取决于聚类层次结构的形成是自顶向下的还是自底向上的。
凝聚的方式：这是一种至底向上的方法，将每一条记录看作一个类，然后根据一些规则将他们聚合成越来越大的类，直到满足一些预先设定的条件。大多数的层次聚类方法属于这一类。
分割的方式：这种自顶向下的方法是一个与凝聚的方式相反的过程，将整个数据库作为一个大的类，然后按照一些规则将这个类分成小的类，直到满足一些预定的条件，例如类的数目到了预定值，最近的两个类之间的最小距离大于设定值。
下图给出了对于集合{a,b,c,d,e}层次聚类两种方式的聚类过程。从这个图我们可以看出，凝聚的方式是将每一个记录看作一个类，再按照一定的规则逐步将这些类合并。举个例子，如果类C1和类C2之间的距离小于预定的最小距离，那么他们就会被合并为一个类，这儿两个类的距离是由两个类中距离最近的一对记录来确定的。
分割的方式则是先将所有的记录作为一个大的类，然后再根据一些规则将它进行分割，例如最近的两个记录之间的距离。
无论凝聚的方式还是分割方式，用户都可以根据自己的要求来设定所得类的个数，也可以不需要指定聚类的个数，但用户可以指定希望得到的簇的数目作为一个结束条件。
层次方法的主要缺点：
1、没有良好的伸缩性：时间复杂度至少是O(n2)；
2、一旦一个合并或分裂被执行，就不能修复，在选择合并或分裂的时候特别值得
注意。前面介绍的划分方法和层次方法都是用距离来衡量相似度的，下面给出
了四种常用测定两个类之间距离的方法，这儿的m
i 是类C
i
的中间值，n
i
是C
i
中记
录的个数，|p-p’|是两个记录之间的距离。
Minimum distance： Dmin(C
i ,C
j
)=Min|p-p’|;(这儿p在类C
i
中p’在C
j
中)
Maximum distance：Dmax(C
i ,C
j
)=Max|p-p’|;(这儿p在类C
i
中p’在C
j
中)
Mean distance： Dmean(C
i ,C
j
)=|m
i
-m
j
|;
Average distance ： Davg(C i ,C j )=(1/n i *n j )∑p∈C i ∑p’ ∈ C j ;
层次聚集虽然比较简单，但是在选择凝聚或者分割点的时候经常会遇到一些困难，这个是非常关键的，因为一旦记录被凝聚或者分割以后，下一步的工作是建立在新形成的类的基础之上的。因此，如果其中任何一步没有做好的话，就会影响最终聚集的结果。这个方法并不是太好，因为要牵涉到很大数量的类和记录。
一个比较有前途的能够提高聚集质量的方向是将层次聚集和其它的聚集结合起来进行。
3．2．3 基于密度的方法
上面介绍的两种聚类方法都是基于距离来判断对象之间、类之间相似度的，这两种聚类方法有一个共同点，就是只能发现球状的聚类结果，为了发现任意形状的聚类结果，提出了基于密度的聚类方法。这类方法将簇看做是数据空间中被低密度区域分割开的高密度对象区域。下面就介绍一种基于密度的聚类方法。
DBSCAN(基于高密度连接区域的密度聚类方法)
DBSCAN （Density-Based Spatial Clustering of Applications with Noise ）是一个基于密度的聚类算法。该算法将于有足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。
基于密度的聚类的基本想法涉及一些新的定义。我们先给出这些定义，然后用一个例子加以说明。 定义
ε 邻域N ε(q): 给定对象半径ε 内的区域，即{q ∈ D | distance(p,q) <= ε} 核心对象 ：如果一个对象的ε-领域至少包含最小数目MinPts 个对象，则称该对象为核心对象。用数学表达法就是：q ∈ D ，|N ε(q)|≥MinPts
对象p 从对象q 出发是直接密度可达 ：给定义个对象集合D ，如果p 是在q 的ε- 邻域内，而q 是一个核心对象，我们说对象p 从对象q 出发是直接密度可达的，用数学表达法就是：p ∈N ε(q) 且|N ε(q)| ≥ MinPts
对象p 从对象q 关于 ε 和MinPts 密度可达：存在对象链p 1，p 2，…，p n ，p 1=q ，p n =p ，p i ∈D ，p i+1是从p i 关于 ε 和MinPts 直接密度可达的（非对称）
对象p和q关于ε和MinPts密度相连：存在对象o ∈D，使得对象p和q 从o关于ε和MinPts密度可达
在上图中，给定ε圆的半径，MinPts=3。基于上述的定义：
·在被标记的点中，P、M、O、R及S都是核心对象，因为它们在ε-领域内至少包含了三个点。
·Q是从M直接密度可达的，M是从P值直接密度可达的。
·因为Q是从M值直接密度可达的。M是从P直接密度可达的，所以Q是从P密度可达的。
·O、R和S都是密度相连的。
DBSCAN基本思想如下：
簇：基于密度可达性的最大的密度相连对象的集合
噪音：不在任何簇中的对象
边界对象：不是核心对象，但在簇中，即至少从一个核心对象直接可达
如下图所示：
DBSCAN算法流程如下：
算法：DBSCAN。基于高密度连接区域的密度聚类方法。
输入：阀值ε、MinPts和包含个n对象的数据库。
输出：基于密度的聚类结果。
方法：
1）任意选择没有加簇标签的点p；
2）找到从p关于ε和MinPts密度可达的所有点；
3）如果|Nε(q)|≥MinPts ，则p是核心对象,形成一个新的簇，给簇内所有的对象点加簇标签；
4）如果p是边界点, 则处理数据库的下一点；
5）重复上述过程，直到所有的点处理完毕。
示意图如下：
空间聚类的研究现状及其应用＊ 戴晓燕1 过仲阳1 李勤奋2 吴健平1 (1华东师范大学教育部地球信息科学实验室 上海 200062) (2上海市地质调查研究院 上海 200072) 摘 要 作为空间数据挖掘的一种重要手段,空间聚类目前已在许多领域得到了应用。文章在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 关键词 空间聚类 K-均值法 散度 1 前言 随着GPS、GI S和遥感技术的应用和发展,大量的与空间有关的数据正在快速增长。然而,尽管数据库技术可以实现对空间数据的输入、编辑、统计分析以及查询处理,但是无法发现隐藏在这些大型数据库中有价值的模式和模型。而空间数据挖掘可以提取空间数据库中隐含的知识、空间关系或其他有意义的模式等[1]。这些模式的挖掘主要包括特征规则、差异规则、关联规则、分类规则及聚类规则等,特别是聚类规则,在空间数据的特征提取中起到了极其重要的作用。 空间聚类是指将数据对象集分组成为由类似的对象组成的簇,这样在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大,即相异度较大。作为一种非监督学习方法,空间聚类不依赖于预先定义的类和带类标号的训练实例。由于空间数据库中包含了大量与空间有关的数据,这些数据来自不同的应用领域。例如,土地利用、居住类型的空间分布、商业区位分布等。因此,根据数据库中的数据,运用空间聚类来提取不同领域的分布特征,是空间数据挖掘的一个重要部分。 空间聚类方法通常可以分为四大类:划分法、层次法、基于密度的方法和基于网格的方法。算法的选择取决于应用目的,例如商业区位分析要求距离总和最小,通常用K-均值法或K-中心点法;而对于栅格数据分析和图像识别,基于密度的算法更合适。此外,算法的速度、聚类质量以及数据的特征,包括数据的维数、噪声的数量等因素都影响到算法的选择[2]。 本文在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 2 划分法 设在d维空间中,给定n个数据对象的集合D 和参数K,运用划分法进行聚类时,首先将数据对象分成K个簇,使得每个对象对于簇中心或簇分布的偏离总和最小[2]。聚类过程中,通常用相似度函数来计算某个点的偏离。常用的划分方法有K-均值(K-means)法和K-中心(K-medoids)法,但它们仅适合中、小型数据库的情形。为了获取大型数据库中数据的聚类体,人们对上述方法进行了改进,提出了K-原型法(K-prototypes method)、期望最大法EM(Expectation Maximization)、基于随机搜索的方法(ClAR ANS)等。 K-均值法[3]根据簇中数据对象的平均值来计算 ——————————————— ＊基金项目:国家自然科学基金资助。(资助号: 40371080) 收稿日期:2003-7-11 第一作者简介:戴晓燕,女,1979年生,华东师范大学 地理系硕士研究生,主要从事空间数 据挖掘的研究。 · 41 · 2003年第4期 上海地质 Shanghai Geology
肤色在各颜色空间的聚类分析 摘要肤色是人体表面最显著的特征之一。对不同肤色在RGB、YCbCr颜色空间内和同一肤色在不同亮度环境下的聚类情况进行深入的分析研究,发现肤色在YCbCr空间内聚类效果更好,更适合做肤色分割。然后在此基础上对黑色肤色、黄色肤色及白色肤色在YCbCr空间内进行肤色分割,达到较好的分割效果。 关键词肤色;颜色空间;肤色分割;YCbCr空间 肤色是人体表面最显著的特征之一,由于它对姿势、旋转、表情等变化不敏感,因此将人体的肤色特征应用于人脸检测与识别、表情识别、手势识别具有很大的优势,所以肤色特征是人脸识别、表情识别、与手势识别中最为常用的分割方法。然而,若要利用肤色进行分割,我们首先应该对肤色以及肤色的聚类情况进行分析。 世界上的人种主要有三种,即尼格罗—澳大利亚人种(黑色皮肤),蒙古人种(黄色皮肤),欧罗巴人种(白色皮肤)。尽管人的肤色因人种的不同而不同,呈现出不同的颜色,但是有学者指出:排除亮度、周围环境等对肤色的影响后,皮肤的色调基本一致。本文对在不同环境下的不同肤色进行取样,然后分别在RGB、YCbCr颜色空间进行统计,从而对比分析肤色在各颜色空间聚类的情况。 1肤色在各颜色空间的聚类比较 1.1不同肤色在RGB和YCbCr颜色空间上的分布 图1—图2给出了黄色、黑色和白色肤色分别在RGB、YCbcr空间的分布情况。 由图1—图2可以得出,不同肤色在RGB、YCbCr空间的分布有如下特征: 1)不同肤色在不同颜色空间均分布在很小的范围内。 2)不同肤色在不同颜色空间内不是随机分布,而是在某固定区域呈聚类分布。 3)不同肤色在YCbCr空间内分布的聚类状态要好于在RGB空间内分布的聚类状态。 4)不同肤色在亮度上的差异远远高于在色度上的差异。 1.2肤色在不同亮度下的分布 图3—图4给出了不同亮度下的同一肤色分别在RGB、YCbCr空间的分布情况。图(a)至图(d)的肤色来源于同一人在不同亮度下的照片。
空间聚类概念 空间聚类作为聚类分析的一个研究方向，是指将空间数据集中的对象分成由相似对象组成的类。同类中的对象间具有较高的相似度，而不同类中的对象间差异较大。作为一种无监督的学习方法，空间聚类不需要任何先验知识，比如预先定义的类或带类的标号等。由于空间聚类方法能根据空间对象的属性对空间对象进行分类划分，其已经被广泛应用在城市规划、环境监测、地震预报等领域，发挥着较大的作用。同时，空间聚类也一直都是空间数据挖掘研究领域中的一个重要研究分支。目前，己有许多文献资料提出了针对不同数据类型的多种空间聚类算法，一些著名的软件，如WEAK、SPSS、SAS等软件中已经集成了各种聚类分析软件包。 1 空间数据的复杂性 空间聚类分析的对象是空间数据。由于空间数据具有空间实体的位置、大小、形状、方位及几何拓扑关系等信息，使得空间数据的存储结构和表现形式比传统事务型数据更为复杂，空间数据的复杂特性表现： (1)空间属性间的非线性关系。由于空问数据中蕴含着复杂的拓扑关系，因此，空间属性间呈现出一种非线性关系。这种非线性关系不仅是空间数据挖掘中需要进一步研究的问题，也是空问聚类所面临的难点之一。 (2)空间数据的尺度特征。空间数据的尺度特征足指在不同的层次上，空间数据所表现出来的特征和规律都不尽相同。虽然在空间信息的概化和细化过程中可以利用此特征发现整体和局部的不同特点，但对空间聚类任务来说，实际上是增加了空间聚类的难度。 (3) 间信息的模糊性。空间信息的模糊性足指各种类型的窄问信息中，包含大量的模糊信息，如空问位置、间关系的模糊性，这种特性最终会导致空间聚类结果的不确定性。 (4)空间数据的高维度。空问数据的高维度性是指空间数据的属性(包括空间属性和非空间属性)个数迅速增加，比如在遥感领域，获取的空间数据的维度已经快速增加到几十甚至上百个，这会给空间聚类的研究增加很大的困难。 2 空间聚类算法 目前，研究人员已经对空间聚类问题进行了较为深入的研究，提出了多种算法。根据空间聚类采用的不同思想，空间聚类算法主要可归纳为以下几种：基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法以及其它形式的聚类算法，如图l所示。 (1)基于划分的聚类 基于划分的聚类方法是最早出现并被经常使用的经典聚类算法。其基本思想是：在给定的数据集随机抽取n个元组作为n个聚类的初始中心点，然后通过不断计算其它数据与这几个中心点的距离(比如欧几里得距离)，将每个元组划分到其距离最近的分组中，从而完成聚类的划分。由于基于划分的聚类方法比较容易理解，且易实现，目前其已被广泛的弓l入到空间聚类中，用于空间数据的分类。其中最为常用的几种算法是：k一平均(k-means)算法、kl中心点(k—medoids)算法和EM(expectation maximization)算法。k一平均算法’使
2006年 8月第42卷 第4期北京师范大学学报(自然科学版) Jour nal of Beijing N ormal U niver sity (N atural Science )A ug.2006 V ol.42 N o.4 应用空间聚类进行点数据分布研究* 林冬云1) 刘慧平1,2,3)? (1)北京师范大学地理学与遥感科学学院;2)北京师范大学遥感科学国家重点实验室; 3)北京师范大学环境遥感与数字城市北京市重点实验室:100875,北京) 摘要 空间数据挖掘是寻找大数据量空间分布的重要方法,应用地理信息系统(G IS )进行空间数据挖掘是目前进行海量数据分析的重要手段之一.应用空间聚类方法对北京市海淀区54325个企业点数据进行量化分析研究,通过空间位置聚类,进行属性指标量化,从而进行属性指标分层聚类,得到企业空间分布特征.研究表明,空间聚类方法是进行点数据空间分布研究的有效方法. 关键词 空间聚类;企业分布;地理信息系统;量化 *国家自然科学基金资助项目(40271035);国家“十五”科技攻关课题资助项目(2003BA808A16-6) ?通讯作者 收稿日期:2005-11-23 随着数据获取和处理技术的迅速发展及数据库管 理系统的广泛应用,人们积累的数据越来越多,但在激增的数据背后隐藏着许多重要的信息,由于缺乏有效的方法,导致了一种“数据爆炸但知识贫乏”的现象[1],面对这一挑战,数据挖掘(data mining ,DM )和知识发现(know ledge discovery in database s ,KDD )技术应运而生并得到迅速发展,它的出现为自动和智能地把海量的数据转化成为有用的信息和知识提供了手段. 作为DM 技术一个新的分支,空间DM 也称基于空间数据库的数据挖掘和知识发现(spatial data mining and know ledge disco very ),是指从空间数据库中提取隐含的、用户感兴趣的空间和非空间的模式、普遍特征、规则和知识的过程[2]. 空间聚类方法是空间数据挖掘中的主要方法之一,是在一个比较大的多维数据集中根据距离的度量找出簇或稠密区域.聚类算法无需背景知识,能直接从空间数据库中发现有意义的空间聚类结构[3].在无先验知识的情况下,聚类分析技术是进行数据挖掘时的首选[4],因而运用空间数据聚类方法来处理海量数据,对于提取大型空间数据库中有用的信息和知识具有十分重要的现实意义. 目前,对于空间聚类的研究主要集中在算法研究和应用研究上,存在2种偏向,一是从事GIS 理论方法和技术工具研究的工作者大多根据空间对象的地理坐标进行聚类,即只考虑对象的空间邻近性,而不考虑对象属性特征的相似性[2,5];另一种是从事GIS 应用和地学研究的工作者,直接套用传统聚类分析方法,根据属性特征集进行分析,忽视了对象的空间邻近性[6]. 而空间对象本质上具有地理位置和属性特征双重含 义,二者结合才能完整地描述空间特征和空间差异.将地理位置和属性特征纳入统一的空间距离测度和空间聚类分析系统,将会改善空间分析和空间DM 的信息 质量[7-9] . 本文主要应用GIS 分析技术,采用空间DM 中的空间聚类方法,通过将空间位置与属性相结合的聚类方法,对北京市海淀区5万多个企事业单位的点分布数据进行分析,探讨对于属性是定性描述的点分布数据的量化方法. 1 研究区和数据来源 海淀区是北京市重要近郊区,占地面积大,人口众多,交通发达,存在着大量的居民和村民混居现象,是中心城市自上而下的扩散能力最强、城乡一体化程度最高、城乡联系最密切的地区,也是大都市空间扩展的主要地区[10]. 研究使用的数据来源是2001年北京市企业数据的统计表,经数字化处理生成企业单位点位分布图,按照数据文件中企业注册地址信息,结合参考北京市电子地图、北京市街道胡同地图集、北京市地图、网上北京市地图以及有关企事业单位的网站,将海淀区共计54325条记录生成5万多个企业的点分布图. 2 研究方法 应用GIS 提取企事业单位分布空间坐标,进行按位置距离聚类分析,获得位置聚类小区,然后进行属性指标的量化,应用聚类分析进行属性聚类,分析企事业