带约束的聚类分析
作者：陈峰 吴艳乔 祝绍琪 杨树勤
单位：南通医学院医学统计学教研室 南通226001
关键词：系统聚类；带约束的聚类(条件系统聚类)；有序样品；方向数据
数理医药学杂志990209
摘要 提出了一种带约束的聚类方法，又称条件系统聚类法，该法基于系统聚类的思想，在聚类过程中按类(样品)与类(样品)相聚的条件进行聚类，不满足条件者不得相聚。传统的一维、二维有序样品的聚类是这种聚类的特例，另外，方向数据、圆周上的样品、周期数据等的聚类亦可看作这种聚类的特例。并结合实例详细阐述了该法的步骤。
1 问题的提出
聚类分析是利用数学手段对一群事物按其“属性”进行分类，在古老的分类学中，人们主要依靠经验和专业知识实现对事物的分类。随着多元分析、计算技术的不断发展，计算手段的日益更新，聚类分析和其他多元分析一样变得愈来愈易实现。但人们对世界的认识是不断发展和深入的，对分类的要求亦愈来愈高。比如，在研究先天畸形的区域发生模式时，需对地区进行聚类，但所聚成的类必须在地理上是相毗邻的。这是因为先天畸形的发生除与遗传因素有关外，还与地理环境、气候、经济文化水平等诸多因素有关。这就使得聚类受某种条件的限制或约束。我们称之为带约束的聚类(restrictive clustering)或条件系统聚类(conditional hierarchical clustering)。
, 百拇医药
2 基本原理
带约束的聚类分析类似于系统聚类，只是在聚类过程中，类(样品)与类(样品)的相聚受到某种条件的限制。
其基本思想是：先视各样品自成一类，计算样品间距离D=D(i,j)。△是聚类的条件，不访设其取值为“真”或“否”。只有当条件△(A，B)为“真”时，类A和B才有可能聚成新的类，即聚类受到条件△的约束。D与△共同组成了聚类的基础。在条件△为“真”时，寻找最小距离，并将其聚成新的一类；计算新类与其他各类之距离；定义或计算新类与其他各类相聚的条件。再在新的条件下寻找最小距离，循环往复，直至聚成预定的k类为止。此即带约束的聚类。
传统的数据预处理法，样本间距离的定义，类间距离的定义均可沿用[1,2]。
不难发现，有序样品的聚类是这种聚类的特例，其聚类条件是：只有前后两样品才能聚成一类。此外，圆周上样品的聚类亦是这种聚类的特例。它除了样品有序外，首尾两样品亦可聚类，这样也就无首尾之分了[3]。
, 百拇医药
3 实例分析
为说明问题，我们只选取北京、天津、河北、山西、内蒙、辽宁、吉林、黑龙江共八个省、市、自治区，对1987年10月到1988年9月监测的男婴神经管缺陷(NTD)资料进行聚类分析，聚类的条件是相邻地区才能聚类。
表1 8省、市、自治区的男婴NTD率(1/万) 地区
北京
天津
河北
山西
内蒙
辽宁
吉林
, 百拇医药
黑龙江
NTD率
18.5
20.9
47.8
68.5
22.3
19.3
39.7
28.5
这是一个二维有序数据的聚类问题。算得各样品间绝对值距离矩阵及聚类条件矩阵如下(为节省篇幅，将距离矩阵及条件矩阵合写在一起，划线者表示相应的两类满足聚类条件，即两地区相邻，下同。)：
, 百拇医药
(1)北京
(2)
天津
2.4
(2)天津
(3)
河北
29.3
26.9
(3)河北
(4)
山西
50.0
, 百拇医药
47.6
20.7
(4)山西
(5)
内蒙
3.8
1.4
25.5
46.2
(5)内蒙
(6)
辽宁
0.8
, 百拇医药
1.6
28.5
49.2
3.0
(6)辽宁
(7)
吉林
21.2
18.8
8.1
28.8
17.4
20.4
, 百拇医药
(7)吉林
(8)
黑龙江
10.0
7.6
19.3
40.0
6.2
9.2
11.2
首次聚类时，距离阵中D(1，6)=0.8最小，但北京(1)与辽宁(6)在地理上不相邻，暂不能聚成一类。在满足聚类条件的各类中，最小距离为D(1，2)=2.4，故将北京(1)与天津(2)聚成一类，设为第(9)类。按重心法计算第(9)类与其他各类之距离，得距离矩阵如下：
, 百拇医药
(9)北京+天津
(3)
河北
26.9
(3)河北
(4)
山西
47.6
20.7
(4)山西
(5)
内蒙
1.4
, 百拇医药
25.5
46.2
(5)内蒙
(6)
辽宁
0.8
28.5
49.2
3.0
(6)辽宁
(7)
吉林
18.8
, 百拇医药
8.1
28.8
17.4
20.4
(7)吉林
(8)
黑龙江
7.6
19.3
40.0
6.2
9.2
11.2
, http://www.100md.com
此时新的类与其他各类相聚的条件发生了改变。因此，需重新定义或计算第(9)类与其他各类相聚的聚类条件。
在满足条件的各类中，最小距离为D(5，6)=3.0，故将内蒙(5)与辽宁(6)聚成一类，设为第(10)类。黑龙江(8)与辽宁(6)是不相邻的，但内蒙(5)与辽宁(6)聚成一类后，由于内蒙(5)与黑龙江(8)相邻，故黑龙江(8)是与第10类(内蒙+辽宁)相邻的。按重心法计算第(10)类与其他各类之距离，及新的聚类条件矩阵。余类同。聚类过程如附图和表2所示。表2 8省、市、自治区男婴NTD率(1/万)聚类过程 类别
相聚的两类
地 区
NTD率(1/万)
聚类距离(绝对值)
(9)
, http://www.100md.com
(1)+(2)
北京+天津
19.7
2.4
(10)
(5)+(6)
内蒙+辽宁
20.8
3.0
(11)
(8)+(10)
内蒙+辽宁+黑龙江
23.4
, 百拇医药
7.7
(12)
(7)+(11)
内蒙+辽宁+吉林+黑龙江
27.4
16.3
(13)
(3)+(12)
内蒙+辽宁+吉林+黑龙江+河北
31.5
20.4
(14)
, http://www.100md.com
(4)+(13)
内蒙+辽宁+吉林+黑龙江+河北+北京+天津
8.1
11.8
(15)
(9)+(14)
内蒙+辽宁+吉林+黑龙江+河北+北京+天津+山西
33.2
40.4
附图 带约束的聚类分析结果示意图
, 百拇医药 从结果我们不难看到，带约束条件的聚类有其特殊性，主要表现在聚类距离不具有单调性，即第i次聚类时的聚类距离可能比第i-1次或前几次的聚类距离小。附图只是一个聚类过程的示意，但这并不影响对结果的分析，所得结论主要依据聚类的步骤。
本例如分为三类，则第一类：北京，天津；第二类：河北，内蒙，辽宁，吉林，黑龙江；第三类：山西。如分为四类，则第一类：北京，天津；第二类：内蒙，辽宁，吉林，黑龙江；第三类：山西；第四类：河北。
显见，这种分类，每类中各地区在地理上是相连接的，满足聚类的条件。
4 讨论
4.1 带约束的聚类分析沿用了传统系统聚类的基本原理、方法以及关于样品间距离的定义、类间距离的定义等，只是在聚类时受到某种条件的限制。正因为如此，系统聚类中的某些性质在此已不再成立。如系统聚类中，最短距离法、最长距离法、类平均法等有聚类距离的单调性，但在带约束的聚类分析中，这一性质不再成立，但这并不影响对结果的分析。
, 百拇医药
4.2 通常所用的(一维)有序样品的聚类是带约束聚类的一个特例，我们曾用该法对文献[2]中的例作了分析，得出了同样的结果。地区的聚类(二维有序样品的聚类)是这种聚类的又一特例，方开泰[4]曾用数论的方法讨论过这个问题，这里提供的方法显然更直观、更简单，为医学、生物学研究提供了必要的分层分类手段。
4.3 方向数据、圆周上的样品、周期数据等的聚类亦是这种聚类的特例[3]。我们曾对四川省1986～1990年神经管缺陷资料按一年中的月份聚类，要求所聚成的类在时间上是连续的，其中一月份和十二月份在年周期中是相临的，故可以聚成一类。结果将其分为两类：12月、1月～5月为第一类，6月～11月为第二类。显然，第一类为冬春季，第二类为夏秋季。
4.4 在聚类过程中，每聚成一新的类，都需重新定义或计算新类与其他各类相聚的聚类条件。在有序样品聚类时，条件的计算有两种方法。设类A与类B相聚成C，满足聚类条件者△=1,否则△=0。有：
, http://www.100md.com
方法1：
i≠A,B
方法2：
△(i,C)=△(i,A)+△(i,B)
i≠A,B
此时△≥1为“真”。
显然方法1与方法2是等价的，但方法2在计算和编程上更优越些。
4.5 文中所举例系用重心法计算各类间距离，以各地区NTD率的平均值作为新类的重心。亦可用各地区的合计NTD率作为新类的重心，本例所得结果相同。
4.6 将传统的系统聚类及带约束的聚类之结果进行比较分析常常是有益的。比如，设A、B、C三个地区，AB相连，BC相连，但AC不相连，如系统聚类中A，C聚成一类，而在带约束的聚类中，A与B或B与C的聚类又很勉强(聚类距离较大)，则可能提示B地区的特殊性。
, 百拇医药
注释：国家自然科学基金资助课题
作者简介：(吴艳乔 祝绍琪 杨树勤)华西医科大学卫生统计学教研室
参考文献
1 郭祖超主编.医用数理统计方法.第三版.人民卫生出版社，1988.
2 史秉璋，杨琦.医用多元分析.北京：人民卫生出版社，1990,3,203～218.
3 陈峰等.论方向数据的聚类分析.南通医学院学报，1996，16(4)：460～463.
4 方开泰.有序样品的一些聚类方法.应用数学学报，1982，5(1)：94～101.
收稿日期：1998-11-27, http://www.100md.com
单位：南通医学院医学统计学教研室 南通226001
关键词：系统聚类；带约束的聚类(条件系统聚类)；有序样品；方向数据
数理医药学杂志990209
摘要 提出了一种带约束的聚类方法，又称条件系统聚类法，该法基于系统聚类的思想，在聚类过程中按类(样品)与类(样品)相聚的条件进行聚类，不满足条件者不得相聚。传统的一维、二维有序样品的聚类是这种聚类的特例，另外，方向数据、圆周上的样品、周期数据等的聚类亦可看作这种聚类的特例。并结合实例详细阐述了该法的步骤。
1 问题的提出
聚类分析是利用数学手段对一群事物按其“属性”进行分类，在古老的分类学中，人们主要依靠经验和专业知识实现对事物的分类。随着多元分析、计算技术的不断发展，计算手段的日益更新，聚类分析和其他多元分析一样变得愈来愈易实现。但人们对世界的认识是不断发展和深入的，对分类的要求亦愈来愈高。比如，在研究先天畸形的区域发生模式时，需对地区进行聚类，但所聚成的类必须在地理上是相毗邻的。这是因为先天畸形的发生除与遗传因素有关外，还与地理环境、气候、经济文化水平等诸多因素有关。这就使得聚类受某种条件的限制或约束。我们称之为带约束的聚类(restrictive clustering)或条件系统聚类(conditional hierarchical clustering)。
, 百拇医药
2 基本原理
带约束的聚类分析类似于系统聚类，只是在聚类过程中，类(样品)与类(样品)的相聚受到某种条件的限制。
其基本思想是：先视各样品自成一类，计算样品间距离D=D(i,j)。△是聚类的条件，不访设其取值为“真”或“否”。只有当条件△(A，B)为“真”时，类A和B才有可能聚成新的类，即聚类受到条件△的约束。D与△共同组成了聚类的基础。在条件△为“真”时，寻找最小距离，并将其聚成新的一类；计算新类与其他各类之距离；定义或计算新类与其他各类相聚的条件。再在新的条件下寻找最小距离，循环往复，直至聚成预定的k类为止。此即带约束的聚类。
传统的数据预处理法，样本间距离的定义，类间距离的定义均可沿用[1,2]。
不难发现，有序样品的聚类是这种聚类的特例，其聚类条件是：只有前后两样品才能聚成一类。此外，圆周上样品的聚类亦是这种聚类的特例。它除了样品有序外，首尾两样品亦可聚类，这样也就无首尾之分了[3]。
, 百拇医药
3 实例分析
为说明问题，我们只选取北京、天津、河北、山西、内蒙、辽宁、吉林、黑龙江共八个省、市、自治区，对1987年10月到1988年9月监测的男婴神经管缺陷(NTD)资料进行聚类分析，聚类的条件是相邻地区才能聚类。
表1 8省、市、自治区的男婴NTD率(1/万) 地区
北京
天津
河北
山西
内蒙
辽宁
吉林
, 百拇医药
黑龙江
NTD率
18.5
20.9
47.8
68.5
22.3
19.3
39.7
28.5
这是一个二维有序数据的聚类问题。算得各样品间绝对值距离矩阵及聚类条件矩阵如下(为节省篇幅，将距离矩阵及条件矩阵合写在一起，划线者表示相应的两类满足聚类条件，即两地区相邻，下同。)：
, 百拇医药
(1)北京
(2)
天津
2.4
(2)天津
(3)
河北
29.3
26.9
(3)河北
(4)
山西
50.0
, 百拇医药
47.6
20.7
(4)山西
(5)
内蒙
3.8
1.4
25.5
46.2
(5)内蒙
(6)
辽宁
0.8
, 百拇医药
1.6
28.5
49.2
3.0
(6)辽宁
(7)
吉林
21.2
18.8
8.1
28.8
17.4
20.4
, 百拇医药
(7)吉林
(8)
黑龙江
10.0
7.6
19.3
40.0
6.2
9.2
11.2
首次聚类时，距离阵中D(1，6)=0.8最小，但北京(1)与辽宁(6)在地理上不相邻，暂不能聚成一类。在满足聚类条件的各类中，最小距离为D(1，2)=2.4，故将北京(1)与天津(2)聚成一类，设为第(9)类。按重心法计算第(9)类与其他各类之距离，得距离矩阵如下：
, 百拇医药
(9)北京+天津
(3)
河北
26.9
(3)河北
(4)
山西
47.6
20.7
(4)山西
(5)
内蒙
1.4
, 百拇医药
25.5
46.2
(5)内蒙
(6)
辽宁
0.8
28.5
49.2
3.0
(6)辽宁
(7)
吉林
18.8
, 百拇医药
8.1
28.8
17.4
20.4
(7)吉林
(8)
黑龙江
7.6
19.3
40.0
6.2
9.2
11.2
, http://www.100md.com
此时新的类与其他各类相聚的条件发生了改变。因此，需重新定义或计算第(9)类与其他各类相聚的聚类条件。
在满足条件的各类中，最小距离为D(5，6)=3.0，故将内蒙(5)与辽宁(6)聚成一类，设为第(10)类。黑龙江(8)与辽宁(6)是不相邻的，但内蒙(5)与辽宁(6)聚成一类后，由于内蒙(5)与黑龙江(8)相邻，故黑龙江(8)是与第10类(内蒙+辽宁)相邻的。按重心法计算第(10)类与其他各类之距离，及新的聚类条件矩阵。余类同。聚类过程如附图和表2所示。表2 8省、市、自治区男婴NTD率(1/万)聚类过程 类别
相聚的两类
地 区
NTD率(1/万)
聚类距离(绝对值)
(9)
, http://www.100md.com
(1)+(2)
北京+天津
19.7
2.4
(10)
(5)+(6)
内蒙+辽宁
20.8
3.0
(11)
(8)+(10)
内蒙+辽宁+黑龙江
23.4
, 百拇医药
7.7
(12)
(7)+(11)
内蒙+辽宁+吉林+黑龙江
27.4
16.3
(13)
(3)+(12)
内蒙+辽宁+吉林+黑龙江+河北
31.5
20.4
(14)
, http://www.100md.com
(4)+(13)
内蒙+辽宁+吉林+黑龙江+河北+北京+天津
8.1
11.8
(15)
(9)+(14)
内蒙+辽宁+吉林+黑龙江+河北+北京+天津+山西
33.2
40.4
附图 带约束的聚类分析结果示意图
, 百拇医药 从结果我们不难看到，带约束条件的聚类有其特殊性，主要表现在聚类距离不具有单调性，即第i次聚类时的聚类距离可能比第i-1次或前几次的聚类距离小。附图只是一个聚类过程的示意，但这并不影响对结果的分析，所得结论主要依据聚类的步骤。
本例如分为三类，则第一类：北京，天津；第二类：河北，内蒙，辽宁，吉林，黑龙江；第三类：山西。如分为四类，则第一类：北京，天津；第二类：内蒙，辽宁，吉林，黑龙江；第三类：山西；第四类：河北。
显见，这种分类，每类中各地区在地理上是相连接的，满足聚类的条件。
4 讨论
4.1 带约束的聚类分析沿用了传统系统聚类的基本原理、方法以及关于样品间距离的定义、类间距离的定义等，只是在聚类时受到某种条件的限制。正因为如此，系统聚类中的某些性质在此已不再成立。如系统聚类中，最短距离法、最长距离法、类平均法等有聚类距离的单调性，但在带约束的聚类分析中，这一性质不再成立，但这并不影响对结果的分析。
, 百拇医药
4.2 通常所用的(一维)有序样品的聚类是带约束聚类的一个特例，我们曾用该法对文献[2]中的例作了分析，得出了同样的结果。地区的聚类(二维有序样品的聚类)是这种聚类的又一特例，方开泰[4]曾用数论的方法讨论过这个问题，这里提供的方法显然更直观、更简单，为医学、生物学研究提供了必要的分层分类手段。
4.3 方向数据、圆周上的样品、周期数据等的聚类亦是这种聚类的特例[3]。我们曾对四川省1986～1990年神经管缺陷资料按一年中的月份聚类，要求所聚成的类在时间上是连续的，其中一月份和十二月份在年周期中是相临的，故可以聚成一类。结果将其分为两类：12月、1月～5月为第一类，6月～11月为第二类。显然，第一类为冬春季，第二类为夏秋季。
4.4 在聚类过程中，每聚成一新的类，都需重新定义或计算新类与其他各类相聚的聚类条件。在有序样品聚类时，条件的计算有两种方法。设类A与类B相聚成C，满足聚类条件者△=1,否则△=0。有：
, http://www.100md.com
方法1：
i≠A,B
方法2：
△(i,C)=△(i,A)+△(i,B)
i≠A,B
此时△≥1为“真”。
显然方法1与方法2是等价的，但方法2在计算和编程上更优越些。
4.5 文中所举例系用重心法计算各类间距离，以各地区NTD率的平均值作为新类的重心。亦可用各地区的合计NTD率作为新类的重心，本例所得结果相同。
4.6 将传统的系统聚类及带约束的聚类之结果进行比较分析常常是有益的。比如，设A、B、C三个地区，AB相连，BC相连，但AC不相连，如系统聚类中A，C聚成一类，而在带约束的聚类中，A与B或B与C的聚类又很勉强(聚类距离较大)，则可能提示B地区的特殊性。
, 百拇医药
注释：国家自然科学基金资助课题
作者简介：(吴艳乔 祝绍琪 杨树勤)华西医科大学卫生统计学教研室
参考文献
1 郭祖超主编.医用数理统计方法.第三版.人民卫生出版社，1988.
2 史秉璋，杨琦.医用多元分析.北京：人民卫生出版社，1990,3,203～218.
3 陈峰等.论方向数据的聚类分析.南通医学院学报，1996，16(4)：460～463.
4 方开泰.有序样品的一些聚类方法.应用数学学报，1982，5(1)：94～101.
收稿日期：1998-11-27, http://www.100md.com