第18卷第3期 系
统 仿 真 学 报 Vol. 18 No. 3
2006年3月 Journal of System Simulation Mar.， 2006
空间聚类算法中的K值优化问题研究
李永森，杨善林，马溪骏，胡笑旋，陈增明
（合肥工业大学计算机网络系统研究所，合肥 230009）
摘 要：在典型的空间聚类算法K-平均法和K-中心法中，K一般为用户事先确定的值，然而，实际中K值很难被精确地确定，往往表现为一个模糊的取值区间。在此提出距离代价函数的概念，建立了相应的数学模型并设计了一个新的K值优化算法，对空间聚类K值优化问题进行了初步的研究。
关键词：空间聚类；K-平均算法；距离代价函数；K值优化
中图分类号：TP311 文献标识码：A 文章编号：1004-731X (2006) 03-0573-04
Optimization Study on K Value of Spatial Clustering
LI Yong-sen, YANG Shan-lin, MA Xi-jun, HU Xiao-xuan, CHEN Zeng-ming
(Institute of Computer Network System, Hefei University of Technology, Hefei 230009, China)
Abstract: The value of K is always confirmed in advance to exert K-means algorithm of spatial clustering. However, it can
not be clearly and easily confirmed in fact for its uncertainty. A distance cost function was recommended. A corresponding math model was set up and a new optimization algorithm of K value was designed. A preliminary study on the optimization of K value for spatial clustering was realized by a simulation design.
Key words: spatial clustering; K-means algorithm; distance cost function; optimization of K.
引 言
空间聚类是空间数据挖掘和知识发现领域一个重要研究方向，它与传统聚类方法的区别在于引入了空间距离维度，意在对具有空间分布属性的研究对象实现空间聚类。在空间聚类中，最著名和经典的类别划分方法是K-平均法，K-中心法以及它们的变种[1~4]。其中，K-平均和K-中心这两种算法的思路和算法过程在本质上是一致的，本文仅对K-平均算法的K值优化问题展开讨论。
典型的K-平均法在空间聚类各算法中一直处于核心地位，该算法以平方误差准则较好地实现了空间聚类，对于大数据集的处理效率较高[5]。但是，该算法要求用户必须事先给出精确的K（要聚类的数目）值，这是该算法最大的缺点，也在一定程度上影响了该算法的应用合理性。在实际中，K值是难以准确界定的，用户不是数据分析专家，也不是知识专家，他并不知道采用什么样的K值聚类会对自己更有利，因此，确定的K虽然对算法本身更方便，但对实际问题并不有效。
本文提出了距离代价函数的概念，建立了相应的数学模
型，并以距离代价最小准则实现了K值优化算法。文章第一部分概述了K-平均算法及其实现过程；第二部分提出了距离代价函数的概念，并建立了基于距离代价函数的K值优化算法；第三部分以实例实现了K值优化算法过程，并证实了该算法的应用合理性；第四部分为全文总结。
1 空间聚类典型算法——K-平均法
空间聚类分析是一种空间数据划分或分组处理的重要手段和方法。它是将研究对象的空间距离指标按照相似性准则划分到若干个子集中，使得相同子集中各元素间差别最小，而不同子集中各元素间差别最大。通常的空间聚类算法是建立在各种距离基础上的，如欧几里得距离、曼哈顿距离和明考斯距离等。其中，最常用的是欧几里得距离：
d(i,j)（1）
其中，i=(xi1,xi2,...,xin)和j=(xj1,xj2,...,xjn)是两个n
维的数据对象。该方程满足的数学条件是：
1）d(i,j)≥0；
2）d(i,i)=0； 3）d(i,j)=d(j,i)； 4）d(i,j)≤d(i,v)+d(v,j)。
根据空间聚类的一般原则，类别的划分应使得同一类（簇）的内部相似度最大、差异度最小，而不同类（簇）间的相似度最小、差异度最大。空间聚类一般使用距离作为划分准则，即任一空间对象与该对象所属簇的几何中心之间的距离比该对象到任何其他簇的几何中心的距离都小。
K-平均法算法设计过程。首先，由用户确定所要聚类的
收稿日期：2005-01-12
修回日期：2005-11-29
基金项目：国家自然科学基金（70471046） 作者简介：李永森（1971-），男，安徽庐江人，博士生，研究方向为空间信息处理、空间数据挖掘和决策支持系统；杨善林（1948-），男，安徽怀宁人，教授，博导，研究方向为管理信息系统、决策科学与技术；马溪骏（1952-），女，安徽六安人，副教授，研究方向为管理信息系统；胡笑旋（1978-），男，安徽桐城人，博士生，研究方向为数据挖掘、人工智能和决策支持系统；陈增明（1978-）山东潍坊人，博士生，研究方向为定性推理和智能决策支持系统。
• 573 •
2006年3月 系 统 仿 真 学 报 Mar., 2006
准确数目K，并随机选择K个对象，每一个对象代表一个簇（类）的均值或中心，对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值形成新的聚类中心，这个过程重复进行，直到下列（2）式准则函数收敛为止。
E=
的配送中心，这是一个战略决策问题，实际可以看作一个空间聚类问题来处理。该用户对于建立多少个配送中心并不能提供一个准确的数据，他仅能根据以往的经验或直觉提供一个大致的范围，这种情况下，直接运用K-平均算法难以解决问题，必须对K值进行优化处理。考虑到运输成本对于物流企业的重要影响，必须保证在完成相同业务量的同时使得运输成本达到最小，这里运用距离代价函数求解比较合理。
（Kr∈K）个簇，定义1：假设n个空间对象被聚类为Kr
定义类际距离为所有分中心（每个簇的均值）到全域中心（所有空间对象均值）的距离之和：
L=
Kr
∑∑
k
2
p−mi （2）
i=1p∈Ci
这里的E是所有研究对象的平方误差总和，p为空间的点，即数据对象，mi是簇Ci的平均值。按照这个准则生成的结果簇趋向于独立和紧凑。
K-平均算法的过程可以描述为：
算法：K-平均。划分的K-平均法算基于簇中对象的平均值。
输入：簇的数目K和包含n个对象的数据库。 输出：平方误差总和最小条件下的K个簇。 方法：
1） 任意选择K个对象作为初始的簇中心； 2） 将所有对象划分到相应的簇中；
将所有对象重新赋给3） 计算每个簇中对象的平均值，最类似的簇；
4） Repeat；
5） until不再发生变化。
首先K-平均算法过程实质是一个逐步求精的迭代过程，任意选择K个对象作为初始的簇中心，也称为种子（图1），按照种子间中垂线原理[6]可以将空间对象分配给所属的种子形成初始聚类，再对初始的每个簇求出其中心（均值），然后以此作为新的种子，重新聚类，直到所有新种子不再更新为止。
∑
mi−m （3）
i=1
式中，L为类际距离，m为全部研究对象的均值，mi为簇Ci所含研究对象的均值，Kr为聚类的个数，Kr∈K，K为聚类区间。
定义2：假设n个空间对象被聚类为Kr个簇，定义类内距离为所有聚类内部距离的总和（其中每个聚类的内部距离为该聚类所有空间对象到其中心的距离之和）：
D=
kr
∑∑
p−mi （4）
i=1p∈Ci
式中，D为类内距离；p为任一空间研究对象；m，mi，Ci含义与（3）式相同。
定义3：定义距离代价函数为类际距离与类内距离之和，当该函数达到最小值时，表明以距离代价为依据的聚类结果为最优：
S=L+D （5）
式中，S为距离代价；L和D分别为上述定义1和定义2中的类际距离和类内距离。
在运用距离代价函数作为空间聚类有效性检验函数时，
本文确定了距离代价最小准则，即当距离代价函数达到最小值时，空间聚类结果为最优。在进行优化分析时，利用函数图像揭示K值与距离代价的函数关系可以快速找到优化的甚至最佳的K值。由（5）式可知，距离代价函数S实际上
是由两部分组成的，其中，L为类际距离，是一个增函数，而D为类内距离，是一个减函数；S的变化取决于两者的合成（图2）。一般情况下，当有n个空间对象时，K值总会在0~n之间的某个数值上使距离代价函数达到最小。极端情况下，当所有对象归为一类时，L为0，D达到最大化，而当n个对象被划分为n类时，D为0，L达到最大化，显然，所有研究对象聚类为1类和聚类为n个类，其距离代价函数是相等的，并且达到最大。
直观上，当L很小时，其随K值的变化不是很明显，因为每增加或减少一个聚类（簇），仅涉及到较少对象较小的距离变化（图2）；而D随K的变化则不同，当K较小时，每增加或减少一个聚类（簇），涉及到较多对象和较大距离的变化，随着K值的增大，这种趋势逐渐趋缓。上述两个没有严格的单调曲线变化趋势的综合使得S曲线变化复杂，
2 K值优化算法
很多学者在研究空间聚类问题时，习惯于追求模型的精巧和算法的完美，而忽视了一个最为关键的问题，即模型设计的合理性问题，漂亮的数学模型并不一定受用户欢迎，只有合理的模型才是好的模型。作为空间聚类最常用的方法——K-平均算法虽然具有一定的理论合理性，但其对K值的严格要求限制了其应用的广泛性。例如，在实际中，某物流公司准备在一个新的国家或地区拓展其物流配送业务，公司根据该区域居民点密度和市场需求状况拟投资建设一定数量• 574 •
2006 2006年3月 李永森, 等：空间聚类算法中的K值优化问题研究 Mar.,
性。经验表明，当L=D时，即两个曲线的交点（图2）处达到S的一个极值点；显然，这个交点对应的一定是优化的K值，但不一定是最优解，不过，找到这个点，离最优解Kr*
小区（居民点），小区空间分布状况如图3(a)所示，公司决策层准备在该地区投资建设一个物流中心，并建设1~3个分中心，考虑到交通运输成本对于公司的利润有重要影响，决策方案要尽量使得公司利润最大化，即完成相同运输量的情况下运输距离最短。这一问题可以看作一个空间聚类问题，由于用户（物流公司）提供的聚类数目不是一个确定的数字，需要进行优化处理。具体过程如下：
首先，将该区域研究对象的地理坐标转化为数学上的二维坐标（欧几里得距离，如表1）。按照经典的K-平均算法，K2=2，K3=3时的空间聚类，分别对9个研究对象进行K1=1，
形成如图3(a)，图4(a)，图5(a)的空间聚类结果。
表1 研究对象空间坐标
P1
P2
P3
P4
P5
P6
P7
P8
P9103
K值优化算法的过程可以描述为：
算法：在K-平均算法基础上，通过距离代价函数优化K值。
输入：由用户给定的簇的数目Kr（Kr∈K）和包含n个对象的数据库。
输出：距离代价函数最小条件下的Kr*个簇。 方法：
1） 用K-平均算法实现Kr中所有数目下的空间聚类； 2） 根据距离代价函数分别计算不同聚类数目Kr下的S值；
3） 搜寻距离代价函数最小的S*，并记下相应的Kr*；4） 结束。
x 1 2 3 3 4 2 8 9y 1 2 1 4 5 5 3 2
然后，按照上文基于距离代价函数最小原则的K值优化算法，分别计算K=1，（分K=2，K=3时的距离代价函数值别按图3(b)，图4(b)，图5(b)方式计算距离代价函数S），结果分别为：S1=30.0, S2=21.04, S3=18.77。
根据距离代价函数最小原则，S3达到最小值，相应的Kr=3应为最优解。
显然，当聚类的数目逐步增大的时候，算法的复杂度也将大大增加，为了减少算法的开销，可以借助图像分析方法迅速缩小K值的范围。实例中的距离代价函数变化如图2所示，图2中，L和D的交点为距离代价函数数S最小值点，该点距离K=3处最近，实际分析表明，K3*=3正是最优解。其他距离这个交点较远的整数解可以排除。
3 K值优化算法实例
某物流公司拟对一个新区拓展物流业务，该地区有9个
(a) K=1时的聚类状况图 (b) 一个聚类的距离代价（30.0）
图3 一个聚类及其距离代价
(a) K=2时的聚类状况图 (b) 两个聚类的距离代价（21.04）
图4 两个聚类及其距离代价
• 575 •
2006年3月 系 统 仿 真 学 报 Mar., 2006
图4 三个聚类及其距离代价
（８）: 68-75.
[2] M Indulska，M E Orlowska. Gravity based spatial clustering [C]//
Proceedings of the 10th ACM international symposium on Advances in geographic information systems. United States: Association for Computing Machinery, 2002：125-130.
[3] Bottou L, Bengio Y. Convergence Properties of the K-Means
Algorithms[M]. Advances in Neural Information Processing System 7, Tesauro G.,et al. (eds.)，MIT Press, Cambridge, MA, 1995：585-592. [4]
Treshansky A, McGraw R. An overview of clustering algorithms [C]// Proceedings of SPIE, The International Society for Optical Engineering. United States: SPIE, 2001(4367)：41-51.
[5] Jiawei Han，Micheline Kamber. 数据挖掘概念与技术[M]. 范明,
孟小峰等译. 北京: 机械工业出版社, 2001. [6]
Michael J A Berry, Gordon S Linoff. 数据挖掘——客户关系管理的科学和艺术[M]. 袁卫译. 北京：中国财政经济出版社，2004.
4 结论
典型的空间聚类算法是在K被准确给定条件下实现的，算法本身较为完善、高效。但是，在实际应用中，决策者（用户）对K值的把握是模糊的，因此，在应用经典的K-平均或K-中心点算法实现空间聚类时需要作进一步的优化和改进。本文考虑到距离在空间聚类中的核心作用，通过设置距离代价函数，确定了K值优化算法，并通过仿真实例讨论了K值变化趋势，以及寻找最优K值的图像分析方法，大大提高了算法的效率。
参考文献：
[1] G. Karypis, E H Han, V Kumar. CHAMELEON: A hierarchical
clustering algorithm using dynamic modeling [J]. Computer，1999, 32
（上接第553页）
从表2和表3可以看出，适应性模拟退火算法求得的各电路的布局结果是好于模拟退火算法的，其得出的总线长度及计算时间都有优势。从表4和表5可以看出，适应性模拟退火算法求得的各电路的布局结果是好于Dragon布局工具得出的结果，其得出的总线长度平均约有5％的改进，因无法和Dragon布局工具在计算时间上做比较，故省去。从图4和图5可以看出，适应性模拟退火算法求解标准单元布局问题是可行的，有效的。
Design Automation Conference, Orlando: IEEE Computer Society, 1990: 96-102.
[3] Saurabh Adya, Igor Markov, Villarrubia P G, Improving Min-cut
Placement for VLSI Using Analytical Techniques [C]// IBM ACAS Conference. Austin: IEEE Computer Society Press, 2003：55-62.
[4] Alupoaei S, Katkoori S, Net-based force-directed macrocell
placement for wirelength optimization [J]. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on (S1063-8210)，2002, 10( 6): 824 –835.
[5] Suit S M, Youssef H, Barada H R, Al-Yamani A, A parallel tabu
search algorithm for VLSI standard-cell placement [C]// Circuits and Systems. the 2000 IEEE International Symposium on. Geneva :Press Polytechniques et Universitaries Romandes, 2000：2: 581-584.
[6] Manikas T W, Mickle M H, A genetic algorithm for mixed macro and
standard cell placement [J]. Circuits and Systems(S1057-7130), 2002, 2: 4-7.
[7] Valenzuela C L, Wang P Y, VLSI placement and area optimization
using a genetic algorithm to breed normalized postfix expressions [J]. Evolutionary Computation, IEEE Transactions on, (S1089-778X)，2002, 6(4): 390-401.
[8] Aykanat C, Bultan T, Haritaoglu o, A fast neural-network algorithm
for VLSI cell placement [J]. Neural Networks (S1045-9227), 1998, 11: 1671-1684.
[9] Hentschke R F, Reis R A, Improving simulated annealing placement
by applying random and greedy mixed perturbations [C]//Proceedings of the 16th symposium on Integrated circuits and systems design, Washington: IEEE Computer Society, 2003: 267 – 272.
[10] Lihong Zhang, Kleine U, A genetic approach to analog module
placement with simulated annealing [J]. Circuits and Systems (S1057-7130), 2002，1：345-348.
[11] Xj yang. introduce of Dragon tool [EB/OL]. [2004-01-30].
http://www.cs.ucla.edu/~xjyang/Dragon/ gsrcmcnc-dragon.html.
5 结论
针对传统模拟退火算法求解标准单元布局存在的几个问题，提出了一种基于适应性模拟退火的标准单元布局算法。引入适应性初始温度，解决了算法初期由于电路大小不同引起的较差解接受概率问题；引入适应性搜索区域，使之能很好的解决算法后期的无效搜索问题；通过及时更新单元坐标，简化了标准单元布局中目标函数中的惩罚项。该算法用于对一组标竿电路进行测试，在线长和时间等性能上均显示出优越性。
参考文献：
[1]
Bo Yao, Wenting Hou, Xianlong Hong, Yici Cai. FAME: A Fast Detailed Placement Algorithm for Standard Cell Layout Based on Mixed Min-cut and Enumeration [J]. Journal of Semiconductors, 2000, 21(8): 744-753. (In Chinese) [2]
Terai M, Takahashi K, Sato K. A new min-cut placement algorithm for timing assurance layout design meeting net length constrain [C]//
• 576 •
第18卷第3期 系
统 仿 真 学 报 Vol. 18 No. 3
2006年3月 Journal of System Simulation Mar.， 2006
空间聚类算法中的K值优化问题研究
李永森，杨善林，马溪骏，胡笑旋，陈增明
（合肥工业大学计算机网络系统研究所，合肥 230009）
摘 要：在典型的空间聚类算法K-平均法和K-中心法中，K一般为用户事先确定的值，然而，实际中K值很难被精确地确定，往往表现为一个模糊的取值区间。在此提出距离代价函数的概念，建立了相应的数学模型并设计了一个新的K值优化算法，对空间聚类K值优化问题进行了初步的研究。
关键词：空间聚类；K-平均算法；距离代价函数；K值优化
中图分类号：TP311 文献标识码：A 文章编号：1004-731X (2006) 03-0573-04
Optimization Study on K Value of Spatial Clustering
LI Yong-sen, YANG Shan-lin, MA Xi-jun, HU Xiao-xuan, CHEN Zeng-ming
(Institute of Computer Network System, Hefei University of Technology, Hefei 230009, China)
Abstract: The value of K is always confirmed in advance to exert K-means algorithm of spatial clustering. However, it can
not be clearly and easily confirmed in fact for its uncertainty. A distance cost function was recommended. A corresponding math model was set up and a new optimization algorithm of K value was designed. A preliminary study on the optimization of K value for spatial clustering was realized by a simulation design.
Key words: spatial clustering; K-means algorithm; distance cost function; optimization of K.
引 言
空间聚类是空间数据挖掘和知识发现领域一个重要研究方向，它与传统聚类方法的区别在于引入了空间距离维度，意在对具有空间分布属性的研究对象实现空间聚类。在空间聚类中，最著名和经典的类别划分方法是K-平均法，K-中心法以及它们的变种[1~4]。其中，K-平均和K-中心这两种算法的思路和算法过程在本质上是一致的，本文仅对K-平均算法的K值优化问题展开讨论。
典型的K-平均法在空间聚类各算法中一直处于核心地位，该算法以平方误差准则较好地实现了空间聚类，对于大数据集的处理效率较高[5]。但是，该算法要求用户必须事先给出精确的K（要聚类的数目）值，这是该算法最大的缺点，也在一定程度上影响了该算法的应用合理性。在实际中，K值是难以准确界定的，用户不是数据分析专家，也不是知识专家，他并不知道采用什么样的K值聚类会对自己更有利，因此，确定的K虽然对算法本身更方便，但对实际问题并不有效。
本文提出了距离代价函数的概念，建立了相应的数学模
型，并以距离代价最小准则实现了K值优化算法。文章第一部分概述了K-平均算法及其实现过程；第二部分提出了距离代价函数的概念，并建立了基于距离代价函数的K值优化算法；第三部分以实例实现了K值优化算法过程，并证实了该算法的应用合理性；第四部分为全文总结。
1 空间聚类典型算法——K-平均法
空间聚类分析是一种空间数据划分或分组处理的重要手段和方法。它是将研究对象的空间距离指标按照相似性准则划分到若干个子集中，使得相同子集中各元素间差别最小，而不同子集中各元素间差别最大。通常的空间聚类算法是建立在各种距离基础上的，如欧几里得距离、曼哈顿距离和明考斯距离等。其中，最常用的是欧几里得距离：
d(i,j)（1）
其中，i=(xi1,xi2,...,xin)和j=(xj1,xj2,...,xjn)是两个n
维的数据对象。该方程满足的数学条件是：
1）d(i,j)≥0；
2）d(i,i)=0； 3）d(i,j)=d(j,i)； 4）d(i,j)≤d(i,v)+d(v,j)。
根据空间聚类的一般原则，类别的划分应使得同一类（簇）的内部相似度最大、差异度最小，而不同类（簇）间的相似度最小、差异度最大。空间聚类一般使用距离作为划分准则，即任一空间对象与该对象所属簇的几何中心之间的距离比该对象到任何其他簇的几何中心的距离都小。
K-平均法算法设计过程。首先，由用户确定所要聚类的
收稿日期：2005-01-12
修回日期：2005-11-29
基金项目：国家自然科学基金（70471046） 作者简介：李永森（1971-），男，安徽庐江人，博士生，研究方向为空间信息处理、空间数据挖掘和决策支持系统；杨善林（1948-），男，安徽怀宁人，教授，博导，研究方向为管理信息系统、决策科学与技术；马溪骏（1952-），女，安徽六安人，副教授，研究方向为管理信息系统；胡笑旋（1978-），男，安徽桐城人，博士生，研究方向为数据挖掘、人工智能和决策支持系统；陈增明（1978-）山东潍坊人，博士生，研究方向为定性推理和智能决策支持系统。
• 573 •
2006年3月 系 统 仿 真 学 报 Mar., 2006
准确数目K，并随机选择K个对象，每一个对象代表一个簇（类）的均值或中心，对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值形成新的聚类中心，这个过程重复进行，直到下列（2）式准则函数收敛为止。
E=
的配送中心，这是一个战略决策问题，实际可以看作一个空间聚类问题来处理。该用户对于建立多少个配送中心并不能提供一个准确的数据，他仅能根据以往的经验或直觉提供一个大致的范围，这种情况下，直接运用K-平均算法难以解决问题，必须对K值进行优化处理。考虑到运输成本对于物流企业的重要影响，必须保证在完成相同业务量的同时使得运输成本达到最小，这里运用距离代价函数求解比较合理。
（Kr∈K）个簇，定义1：假设n个空间对象被聚类为Kr
定义类际距离为所有分中心（每个簇的均值）到全域中心（所有空间对象均值）的距离之和：
L=
Kr
∑∑
k
2
p−mi （2）
i=1p∈Ci
这里的E是所有研究对象的平方误差总和，p为空间的点，即数据对象，mi是簇Ci的平均值。按照这个准则生成的结果簇趋向于独立和紧凑。
K-平均算法的过程可以描述为：
算法：K-平均。划分的K-平均法算基于簇中对象的平均值。
输入：簇的数目K和包含n个对象的数据库。 输出：平方误差总和最小条件下的K个簇。 方法：
1） 任意选择K个对象作为初始的簇中心； 2） 将所有对象划分到相应的簇中；
将所有对象重新赋给3） 计算每个簇中对象的平均值，最类似的簇；
4） Repeat；
5） until不再发生变化。
首先K-平均算法过程实质是一个逐步求精的迭代过程，任意选择K个对象作为初始的簇中心，也称为种子（图1），按照种子间中垂线原理[6]可以将空间对象分配给所属的种子形成初始聚类，再对初始的每个簇求出其中心（均值），然后以此作为新的种子，重新聚类，直到所有新种子不再更新为止。
∑
mi−m （3）
i=1
式中，L为类际距离，m为全部研究对象的均值，mi为簇Ci所含研究对象的均值，Kr为聚类的个数，Kr∈K，K为聚类区间。
定义2：假设n个空间对象被聚类为Kr个簇，定义类内距离为所有聚类内部距离的总和（其中每个聚类的内部距离为该聚类所有空间对象到其中心的距离之和）：
D=
kr
∑∑
p−mi （4）
i=1p∈Ci
式中，D为类内距离；p为任一空间研究对象；m，mi，Ci含义与（3）式相同。
定义3：定义距离代价函数为类际距离与类内距离之和，当该函数达到最小值时，表明以距离代价为依据的聚类结果为最优：
S=L+D （5）
式中，S为距离代价；L和D分别为上述定义1和定义2中的类际距离和类内距离。
在运用距离代价函数作为空间聚类有效性检验函数时，
本文确定了距离代价最小准则，即当距离代价函数达到最小值时，空间聚类结果为最优。在进行优化分析时，利用函数图像揭示K值与距离代价的函数关系可以快速找到优化的甚至最佳的K值。由（5）式可知，距离代价函数S实际上
是由两部分组成的，其中，L为类际距离，是一个增函数，而D为类内距离，是一个减函数；S的变化取决于两者的合成（图2）。一般情况下，当有n个空间对象时，K值总会在0~n之间的某个数值上使距离代价函数达到最小。极端情况下，当所有对象归为一类时，L为0，D达到最大化，而当n个对象被划分为n类时，D为0，L达到最大化，显然，所有研究对象聚类为1类和聚类为n个类，其距离代价函数是相等的，并且达到最大。
直观上，当L很小时，其随K值的变化不是很明显，因为每增加或减少一个聚类（簇），仅涉及到较少对象较小的距离变化（图2）；而D随K的变化则不同，当K较小时，每增加或减少一个聚类（簇），涉及到较多对象和较大距离的变化，随着K值的增大，这种趋势逐渐趋缓。上述两个没有严格的单调曲线变化趋势的综合使得S曲线变化复杂，
2 K值优化算法
很多学者在研究空间聚类问题时，习惯于追求模型的精巧和算法的完美，而忽视了一个最为关键的问题，即模型设计的合理性问题，漂亮的数学模型并不一定受用户欢迎，只有合理的模型才是好的模型。作为空间聚类最常用的方法——K-平均算法虽然具有一定的理论合理性，但其对K值的严格要求限制了其应用的广泛性。例如，在实际中，某物流公司准备在一个新的国家或地区拓展其物流配送业务，公司根据该区域居民点密度和市场需求状况拟投资建设一定数量• 574 •
2006 2006年3月 李永森, 等：空间聚类算法中的K值优化问题研究 Mar.,
性。经验表明，当L=D时，即两个曲线的交点（图2）处达到S的一个极值点；显然，这个交点对应的一定是优化的K值，但不一定是最优解，不过，找到这个点，离最优解Kr*
小区（居民点），小区空间分布状况如图3(a)所示，公司决策层准备在该地区投资建设一个物流中心，并建设1~3个分中心，考虑到交通运输成本对于公司的利润有重要影响，决策方案要尽量使得公司利润最大化，即完成相同运输量的情况下运输距离最短。这一问题可以看作一个空间聚类问题，由于用户（物流公司）提供的聚类数目不是一个确定的数字，需要进行优化处理。具体过程如下：
首先，将该区域研究对象的地理坐标转化为数学上的二维坐标（欧几里得距离，如表1）。按照经典的K-平均算法，K2=2，K3=3时的空间聚类，分别对9个研究对象进行K1=1，
形成如图3(a)，图4(a)，图5(a)的空间聚类结果。
表1 研究对象空间坐标
P1
P2
P3
P4
P5
P6
P7
P8
P9103
K值优化算法的过程可以描述为：
算法：在K-平均算法基础上，通过距离代价函数优化K值。
输入：由用户给定的簇的数目Kr（Kr∈K）和包含n个对象的数据库。
输出：距离代价函数最小条件下的Kr*个簇。 方法：
1） 用K-平均算法实现Kr中所有数目下的空间聚类； 2） 根据距离代价函数分别计算不同聚类数目Kr下的S值；
3） 搜寻距离代价函数最小的S*，并记下相应的Kr*；4） 结束。
x 1 2 3 3 4 2 8 9y 1 2 1 4 5 5 3 2
然后，按照上文基于距离代价函数最小原则的K值优化算法，分别计算K=1，（分K=2，K=3时的距离代价函数值别按图3(b)，图4(b)，图5(b)方式计算距离代价函数S），结果分别为：S1=30.0, S2=21.04, S3=18.77。
根据距离代价函数最小原则，S3达到最小值，相应的Kr=3应为最优解。
显然，当聚类的数目逐步增大的时候，算法的复杂度也将大大增加，为了减少算法的开销，可以借助图像分析方法迅速缩小K值的范围。实例中的距离代价函数变化如图2所示，图2中，L和D的交点为距离代价函数数S最小值点，该点距离K=3处最近，实际分析表明，K3*=3正是最优解。其他距离这个交点较远的整数解可以排除。
3 K值优化算法实例
某物流公司拟对一个新区拓展物流业务，该地区有9个
(a) K=1时的聚类状况图 (b) 一个聚类的距离代价（30.0）
图3 一个聚类及其距离代价
(a) K=2时的聚类状况图 (b) 两个聚类的距离代价（21.04）
图4 两个聚类及其距离代价
• 575 •
2006年3月 系 统 仿 真 学 报 Mar., 2006
图4 三个聚类及其距离代价
（８）: 68-75.
[2] M Indulska，M E Orlowska. Gravity based spatial clustering [C]//
Proceedings of the 10th ACM international symposium on Advances in geographic information systems. United States: Association for Computing Machinery, 2002：125-130.
[3] Bottou L, Bengio Y. Convergence Properties of the K-Means
Algorithms[M]. Advances in Neural Information Processing System 7, Tesauro G.,et al. (eds.)，MIT Press, Cambridge, MA, 1995：585-592. [4]
Treshansky A, McGraw R. An overview of clustering algorithms [C]// Proceedings of SPIE, The International Society for Optical Engineering. United States: SPIE, 2001(4367)：41-51.
[5] Jiawei Han，Micheline Kamber. 数据挖掘概念与技术[M]. 范明,
孟小峰等译. 北京: 机械工业出版社, 2001. [6]
Michael J A Berry, Gordon S Linoff. 数据挖掘——客户关系管理的科学和艺术[M]. 袁卫译. 北京：中国财政经济出版社，2004.
4 结论
典型的空间聚类算法是在K被准确给定条件下实现的，算法本身较为完善、高效。但是，在实际应用中，决策者（用户）对K值的把握是模糊的，因此，在应用经典的K-平均或K-中心点算法实现空间聚类时需要作进一步的优化和改进。本文考虑到距离在空间聚类中的核心作用，通过设置距离代价函数，确定了K值优化算法，并通过仿真实例讨论了K值变化趋势，以及寻找最优K值的图像分析方法，大大提高了算法的效率。
参考文献：
[1] G. Karypis, E H Han, V Kumar. CHAMELEON: A hierarchical
clustering algorithm using dynamic modeling [J]. Computer，1999, 32
（上接第553页）
从表2和表3可以看出，适应性模拟退火算法求得的各电路的布局结果是好于模拟退火算法的，其得出的总线长度及计算时间都有优势。从表4和表5可以看出，适应性模拟退火算法求得的各电路的布局结果是好于Dragon布局工具得出的结果，其得出的总线长度平均约有5％的改进，因无法和Dragon布局工具在计算时间上做比较，故省去。从图4和图5可以看出，适应性模拟退火算法求解标准单元布局问题是可行的，有效的。
Design Automation Conference, Orlando: IEEE Computer Society, 1990: 96-102.
[3] Saurabh Adya, Igor Markov, Villarrubia P G, Improving Min-cut
Placement for VLSI Using Analytical Techniques [C]// IBM ACAS Conference. Austin: IEEE Computer Society Press, 2003：55-62.
[4] Alupoaei S, Katkoori S, Net-based force-directed macrocell
placement for wirelength optimization [J]. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on (S1063-8210)，2002, 10( 6): 824 –835.
[5] Suit S M, Youssef H, Barada H R, Al-Yamani A, A parallel tabu
search algorithm for VLSI standard-cell placement [C]// Circuits and Systems. the 2000 IEEE International Symposium on. Geneva :Press Polytechniques et Universitaries Romandes, 2000：2: 581-584.
[6] Manikas T W, Mickle M H, A genetic algorithm for mixed macro and
standard cell placement [J]. Circuits and Systems(S1057-7130), 2002, 2: 4-7.
[7] Valenzuela C L, Wang P Y, VLSI placement and area optimization
using a genetic algorithm to breed normalized postfix expressions [J]. Evolutionary Computation, IEEE Transactions on, (S1089-778X)，2002, 6(4): 390-401.
[8] Aykanat C, Bultan T, Haritaoglu o, A fast neural-network algorithm
for VLSI cell placement [J]. Neural Networks (S1045-9227), 1998, 11: 1671-1684.
[9] Hentschke R F, Reis R A, Improving simulated annealing placement
by applying random and greedy mixed perturbations [C]//Proceedings of the 16th symposium on Integrated circuits and systems design, Washington: IEEE Computer Society, 2003: 267 – 272.
[10] Lihong Zhang, Kleine U, A genetic approach to analog module
placement with simulated annealing [J]. Circuits and Systems (S1057-7130), 2002，1：345-348.
[11] Xj yang. introduce of Dragon tool [EB/OL]. [2004-01-30].
http://www.cs.ucla.edu/~xjyang/Dragon/ gsrcmcnc-dragon.html.
5 结论
针对传统模拟退火算法求解标准单元布局存在的几个问题，提出了一种基于适应性模拟退火的标准单元布局算法。引入适应性初始温度，解决了算法初期由于电路大小不同引起的较差解接受概率问题；引入适应性搜索区域，使之能很好的解决算法后期的无效搜索问题；通过及时更新单元坐标，简化了标准单元布局中目标函数中的惩罚项。该算法用于对一组标竿电路进行测试，在线长和时间等性能上均显示出优越性。
参考文献：
[1]
Bo Yao, Wenting Hou, Xianlong Hong, Yici Cai. FAME: A Fast Detailed Placement Algorithm for Standard Cell Layout Based on Mixed Min-cut and Enumeration [J]. Journal of Semiconductors, 2000, 21(8): 744-753. (In Chinese) [2]
Terai M, Takahashi K, Sato K. A new min-cut placement algorithm for timing assurance layout design meeting net length constrain [C]//
• 576 •