（管理科学与工程专业论文）基于约束的聚类算法及其应用研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 随着计算机技术、网络通信技术和信息处理技术的发展，战争的信息化程度 越来越高，战时装备应急机动保障也趋向智能化。战时装备应急保障中物资配送 线路的优化选择和维修点的设置，对应急保障的速度、成本、效益和安全至关重 要。对保障区域进行划分，实施分块保障可以提高保障效率、减少运输费用、增 大安全性、简化保障程序。数据挖掘中的聚类分析为装备保障区域自动划分问题 提供了一种有效的解决方法。 本文在研究数据挖掘中已有聚类算法的基础上，结合装备保障区域自动划分 问题的特点，深入剖析划分要求，采用基于图论的聚类算法对该问题进行建模求 解；针对划分后所得的装备保障区域可能是任意形状多密度的情况，结合图建模 方法提出了一种最小生成树聚类算法m s t c i u s t ，该算法通过邻边权值的比值来控 制聚类过程：根据m s t c i u s t 算法生成的最小生成子树中边权值的统计信息，结合 控制参数构建了一个聚类结果评价函数，当该函数取值最小时聚类结果最佳；运 用上述聚类结果评价函数，通过改变控制参数对该函数的最小值进行搜索，实现 了参数的自动设置；在装备保障区域划分时可能存在一些约束条件，本文借鉴 m s t c l u s t 的思想改造了著名的k r u s k a l 算法，提出了一种处理约束的最小生成树聚 类算法c o p m s t c i u s t ；采用人工数据集和u c i 真实数据集对上述算法的效果和性 能进行了实验验证；最后，进行仿真实验分析，说明了基于约束的聚类算法 c o p m s t c i u s t 在装备保障区域划分问题中的合理性和可行性。 本文首次采用基于约束的聚类分析对装备应急保障区域划分问题进行建模求 解；提出了两种效果良好、性能优越的聚类算法，特别是c o p m s t c i u s t 算法还 可以处理多种约束的聚类问题；并通过仿真实验证明了算法在解决装备保障区域 动态自动划分问题上的合理性和有效性，为我军装备应急机动保障机制提供了一 种有价值的技术参考。 主题词：聚类分析最小生成树基于约束的聚类装备应急机动保障装 备保障区域划分 第i 页 国防科学技术大学研究生院硕十学何论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e ，n e tc o m m u n i c a t i o na n di n f o r m a t i o n p r o c e s s i n gt e c h n o l o g y ，t h ew a ri sm o r ea n dm o r ei n f o r m a t i o n i z a t i o nt h ee m e r g e n c y m a n e u v e re q u i p m e n ts u p p o r ti nw a r t i m et e n d st oi n t e l l i g e n t i z e d t h ec h o i c ea n d o p t i m i z i n go fe q u i p m e n td e l i v e r i n gp a t ha n ds e t t i n go fe q u i p m e n tm a i n t a i n i n gp o i n ta r e v e r yi m p o r t a n tt ot h es p e e d ，c o s t ，b e n e f i ta n ds e c u r i t yo fe m e r g e n c ym a n e u v e r e q u i p m e n ts u p p o r t i no r d e rt oi m p r o v ee f f i c i e n c y ，r e d u c ef r e i g h t ，i n c r e a s et h es e c u r i t y a n ds i m p l i f yt h es u p p o r tp r o c e d u r e ，w en e e dt od i v i d et h em a i n t e n a n c ea r e ai n t os e v e r a l r e g i o n st oi m p l e m e n te q u i p m e n ts u p p o r t t h ec l u s t e r i n ga n a l y s i so fd a t am i n i n g p r o v i d e sag o o ds o l u t i o nf o rt h i sp r o b l e m w i t hd e e p l ya n a t o m i z i n gt h ec h a r a c t e r i s t i c sa n dr e q u i r e m e n t so ft h em a i n t e n a n c e a r e ap a r t i t i o na n db a s e do nr e s e a r c h i n gt h ee x i s t i n gc l u s t e r i n ga l g o r i t h m so fd a t am i n i n g ， t h i st h e s i su s e sg r a p h b a s e dc l u s t e r i n ga l g o r i t h mt os o l v et h ep r o b l e m i na l l u s i o nt ot h e i s s u et h a tt h er e g i o n sm a yb e a r b i t r a r y s h a p ea n dm u l t i r e s o l u t i o n i tp r o p o s e sa m i n i m u ms p a n n i n gt r e ec l u s t e r i n ga l g o r i t h m sn a m e dm s t c l u s tb yu s i n gt h eg r a p h m o d e l i n gm e t h o d ，w h i c hc o n t r o l st h ep r o c e s s eo fc l u s t e r i n gt h r o u g ht h er a t i oo ft h e n e i g h b o re d g e s w e i g h t s b a s e do nt h es t a t i s t i c a l i n f o r m a t i o no ft h es u bt r e ea sar e s u l t o fm s t c i u s ta n dt h ec o n t r o l - p a r a m e t e r s ，i tc o n s t r u c t sac l u s t e r i n gr e s u l t e v a l u a t i n g f u n c t i o n ，w h i c hi n d i c a t e st h a tt h ec l u s t e r i n gr e s u l ti st h eb e s tw h e ni tr e a c h e st h e m i n i m u mv a l u e b yu s i n gt h ef u n c t i o n ，i tc a nm a k et h ep a r a m e t e r sa u t o s e t t i n gb y s e a r c h i n gt h em i n i m u mv a l u eo ft h ef u n c t i o n t h e r em u s tb es o m ec o n s t r a i n t sw h e n p a r t i n gt h em a i n t e n a n c ea r e a s oi tp r e s e n t sac o n s t r a i n t - b a s e dm i n i m u ms p a n n i n gt r e e c l u s t e r i n ga l g o r i t h mc a l l e dc o p m s t c l u s tw h i c ht a k e st h ei d e ao fm s t c l u s tt o r e c o n s t r u c tt h ek r u s k a la l g o r i t h m t h e nw et a k ea ne x p e r i m e n tt op r o v et h er e s u l ta n d t h ep e r f o r m a n c eo ft h ea l g o r i t h m su s i n gs y n t h e t i cd a t a s e t sa n dr e a ld a t a s e t sf r o mu c i a tl a s ti td e m o n s t r a t st h er a t i o n a l i t ya n df e a s i b i l i t yo f u s i n gt h ec o p m s t c l u s tt os o l v e t h ep r o b l e mo fm a i n t e n a n c e p a r t i t i o nt h r o u g ha n a l y z i n ga n ds i m u l a t i n go na ni n s t a n c e i nt h i st h e s i s ，w ea d o p t e dt h ec l u s t e r i n ga n a l y s i sm e t h o dt os o l v et h ep r o b l e mo f m a i n t e n a n c ea r e ap a r t i t i o nf o rt h ef i r s tt i m e ；i t p r e s e n t st w oe f f e c t i b l ea n dg r e a t p e r f o r m a b l ec l u s t e r i n ga l g o r i t h m s ，a n de s p e c i a l l y ，t h ec o p - m s t c i u s tc a nd e a lw i t h m u l t i c o n s t r a i n t sp r o b l e m s ；a n di td e m o n s t r a t st h er a t i o n a l i t ya n dv a l i d i t yo fu s i n gt h e c o p - m s t c i u s tt os o l v et h ep r o b l e mb ya n a l y z i n ga n ds i m u l a t i n go na ni n s t a n c e i ti sa v a l u a b l er e f e r e n c ef o rt h ee m e r g e n c ym a n e u v e re q u i p m e n t s u p p o r tf o ro u ra r m y k e yw o r d s ：c l u s t e r i n ga n a l y s i s ， c l u s t e r i n g ，e m e r g e n c y m a n e u v e r p a r t i t i o n m i n i m u m s p a n n i n gt r e e c o n s t r a i n t b a s e d e q u i p m e n ts u p p o r t ，m a i n t e n a n c ea r e a 第i i 页 国防科学技术人学研究生院硕士学位论文 表目录 表2 1 不同的属性类型比较9 表2 2 简单属性的相似度和相异度1o 表2 3k m e a n s 聚类中邻近度、质心、与目标函数的搭配方式1 6 表2 4 常见聚类算法比较表2 1 表3 1 参数设置对d s l 聚类效果的影响3 6 表3 2 参数设置对c o m p l e x 9 聚类效果的影响3 6 表4 1k r u s k a l 算法步骤4 3 第1 i l 页 国防科学技术人学研究生院硕十学位论文 图目录 图1 1论文研究思路5 图2 1二维数据点的聚类7 图2 2 聚类分析过程图8 图2 3 聚类算法分类1 4 图2 4k m e a n s 聚类流程图16 图2 5层次聚类算法过程示意图17 图2 6 密度可达和密度连通2 0 图2 7 新型数据挖掘模型2 2 图2 8 约束属性示图2 4 图2 9c h a m e l e o n 算法聚类过程2 6 图3 1 传统m s t 聚类算法2 8 图3 2 数据集d s l 和c o m p l e x 9 3 4 图3 3m s t c l u s t 算法实验程序界面3 4 图3 4 各种算法在数据集d s l 和c o m p l e x 9 上的聚类效果3 5 图3 5目标函数随参数的变化曲线3 6 图3 6 锯齿线简化为负斜率直线3 6 图3 7 数据集规模与时间复杂度的关系3 7 图4 1c a n n o t l i n k 相似度传递性4 1 图4 2c o p m s t c l u s t 算法框架4 2 图4 3 数据集d a t a s e t l 和d a t a s e t 2 分布4 6 图4 4c o p m s t c l u s t 算法仿真实验界面4 7 图4 5d a t a s e t l 和d a t a s e t 2 聚类结果4 8 图4 6c o p m s t c i u s t 算法性t i n 试图4 8 图4 7c o p m s t c l u s t 算法约束对正确率的影响4 9 图4 8i r i s 数据集二维散点图5 0 图5 1部队分布示意图5 1 图5 2部队之间道路网络图5 3 图5 3装备保障区域自动划分系统框架5 5 图5 4 部队之问道路网络简化图5 6 图5 5 保障区划分结果示意图5 6 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名：土! 叠! 日期： 作者指导教师签名：日期： 渺g 年 踏年 1 | 茂1 0 b l | 其 ob 国防科学技术大学研究生院硕+ 学位论文 第一章绪论 1 1 研究背景及意义 各种数据以前所未有的速度收集、整理并存储在计算机中，其数量和复杂程 度远远超过了人的分析能力。因为缺乏有效的方法和工具从这些海量数据中发现 潜在的规则和知识，人们便陷入了“数据爆炸”和“知识贫乏 并存的尴尬境地。 因此，人们希望能通过计算机技术进行数据的分析和理解，发现其中的关联和知 识，预测未来的发展趋势，基于海量数据做出决策，于是知识发现( k d d ：k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 技术就应运而生。知识发现是指从大量数据中提取可信的、 新颖的、有效的、潜在有用的并能被人理解的模式的非平凡处理过程i l 】。数据挖掘 ( d m - d a t am i n i n g ) 是从大型数据库的数据中挖掘人们感兴趣的知识的过程，它 常常被认为是知识发现的一个步骤【l 】。数据挖掘获得的知识是隐含的、事先未知的、 潜在有用的信息，提取的知识表示为概念、规则、规律、模式等形式。数据挖掘 是一个包含多学科的领域，这些学科包括数据库技术，人工智能，模式识别、统 计学、可视化等等。1 9 8 9 年8 月第11 届国际人工智能会议上提出数据挖掘的概念 后，数据挖掘就得到了学术界的广泛关注和深入研究。 聚类分析是数据挖掘的一个重要任务，它根据对象之间的相似度把一个对象 集划分成若干个簇，使同一簇中的对象彼此相似，不同簇中的对象尽可能不同。 在聚类中，没有预定义的类和样本，记录完全依赖其相似度被归类。聚类分析的 应用领域十分广泛，如生物学家创建的所有生物的系统分类学【2 】：界、门、纲、目、 科、属、种( 根据层次结构) 。聚类在电子商务、图像处理、自然语言识别、文 本学习、商业智能、客户关系管理等活动中有着重要的应用价值。不同症状的集 合也许代表不同的疾病，不同客户属性簇也许表示不同的市场份额。聚类的另一 个应用就是离群点检测，通过离群点检测就可以发现信用卡欺诈和网络入侵等犯 罪活动。聚类分析在很多研究领域扮演着重要的角色，包括：生物学、统计学、 模式识别、信息检索、机器学习、心理学和其它社会科学等。总之，聚类分析具 有很高研究价值，一直受到国内外学者们的广泛关注。 对不同领域的数据进行数据挖掘时要受到相关的领域知识的约束和限制，这 种约束和限制从某种意义上来说是对数据挖掘的一种指导，减少数据挖掘过程的 盲目性，使得挖掘结果更符合实际应用、正确率更高。带约束条件的数据挖掘已 经成为一个新的研究热点，近来基于约束的聚类分析( 也称半监督的学习) 也受 到了广泛的关注，它是通过先验知识对聚类的过程进行监督指导，使得聚类结果 更实用、更有意义。 第1 页 国防科学技术大学研究生院硕十学位论文 随着计算机技术、网络通信技术和信息处理技术的发腱，战争的信息化程度 越来越高，未来战争制胜的法宝就是对信息的掌控。信息化战争使军事理论、作 战样式、部队编制发生革命性突变的同时，对装备保障的影响也是巨大的。它将 从根本上改变传统的装备保障观念、理论和方式，引发装备保障的重大变革。在 未来多维战场信息空间中，系统之间对抗的时效性越来越强，如何高效地对部队 进行应急机动保障，是我军装备保障中的一个重要的研究课题1 3 j 。定量研究一体化 联合作战战区装备保障力量体系结构是深入研究装备保障力量体系的必然要求【4 】。 战场环境瞬息万变，如何将保障物资准确而高效地运送到作战单元，直接关系到 保障的效益和效果，如果按照传统的以编制为基础的保障形式进行保障就很难适 应部队战时的需要，而且花费的代价可能会很高。假如能采用一种自动化技术根 据战时各个部队和仓库的相关数据，在计算机辅助下对保障区域进行自动划分， 然后实施灵活机动保障，就可以在满足部队需要的情况下尽可能节省运输资源， 增加保障线路的安全性，提高保障效率。在整个装备保障物资的配送过程中，配 送线路的优化选择，对整个保障的速度、成本、效益和安全至关重要1 5 i 。对保障对 象的选择和配送车辆的优化调度，不仅可以提高保障的效率、实现安全保障，也 是建立现代战场装备保障机制，发展智能保障技术的基础。现代信息处理方式为 提高装备保障效能提供了一种有效的解决方案，数据挖掘就是其中的一种有效的 方法。通过数据挖掘发现装备维修中存在的规律，实现装备维修的自动诊断，通 过聚类技术实现装备保障区域的自动划分，实施动态高效的保障等。 装备保障区域自动划分就是将各个待保障单位，在定的条件约束下划分为 一些分组，使得每个分组内部各个待保障点具有较强的可达性，从而使保障所花 费的代价最小，时效性和安全性最高。划分时存在各种约束条件，如：保障物资 比较相似，需求总量不超过一定范围等。实际上装备保障区域划分问题就是对待 保障单位在一定约束条件下的一个聚类，通过数据挖掘中的聚类分析能有效地解 决该问题。而该问题涉及到的聚类又不同于传统的聚类分析，它是在一定的约束 条件下对一个道路网络中的节点进行的聚类分析。基于约束的聚类分析1 6 7 j ( c o n s t r a i n t b a s e dc l u s t e r i n g ) 已经引起了学术界的广泛研究，本课题将着重对基 于约束的道路网络节点的聚类方法进行研究，提出适合解决课题背景问题的聚类 算法，为保障区域自动划分提供技术支持，具有重要的理论价值和实用价值。研 究成果在物流博j 、电网架设等领域也具有一定的应用f j 景。 1 2 研究现状及发展趋势 数据挖掘作为一门新兴的多学科交叉研究领域，在过去二十年中得到了学者 们的广泛关注，有了长足的发展，到目自 已经出现了多种数据挖掘方法、技术和 第2 页 国防科学技术大学研究生院硕士学位论文 产品。数据挖掘的任务有：关联分析、聚类分析、分类分析、异常检测、演变分 析【i l 等。近年来，聚类分析一直是数据挖掘领域的研究热点，到目前已经有很多的 成熟的聚类算法，根据聚类算法的特点可以分为：划分方法、层次方法、基于密 度的方法、基于网格的方法和基于模型的方法。划分方法中具有代表性的算法有 k m e a n s 9 1 和c l a r a n s1 1 0 l ，较著名的层次聚类算法有b i r c h l l 、r o c k l l 2 l 和 c h 姗e l e o n 【1 3 1 ，基于密度方法的算法有d b s c a n l l 4 1 、d e n c l u e l l 5 1 和o p t i c s l l6 1 ， 基于网格方法的算法有c l i q u e 1 7 1 和s t i n g l l 引，基于模型的算法有c o b w e b l l 9 1 和c l a s s i t l 2 0 1 。另外还有基于图论的聚类方法如：基于最小生成树的聚类算法【2 u 和基于优势集的聚类算法 2 2 1 ，基于图论的方法也可归并到划分方法或层次聚类算 法中去。各种聚类算法针对不同的问题、不同的需要效果也不同，到目前还没有 一个统一的评价标准来衡量聚类算法的好坏，在实际问题中针对具体应用选择与 之相适应的算法。聚类算法的研究一直受到学者们的重视，每年都有新的算法提 出，经典的算法也在不断改进中，这些都是为了满足人们在不同领域对聚类算法 的需求。对于实际问题，有时并非按照属性所得到的相似度或相异度就能决定哪 些对象属于同一簇哪些属于不同的簇，而是要根据实际问题所在领域的领域知识“ 或者先验知识进行综合考虑的，通过这些知识对聚类过程进行指导，这就提出了 基于约束的聚类分析( c c ：c o n s t r a i n tb a s e dc l u s t e r i n g ) ，在机器学习中称之为半 监督的分类。 文献【2 3 】最早提出了领域知识( d o m a i nk n o w l e d g e ) 在数据挖掘中的重要地位， 并将领域知识分为：层次泛化树( h g t r e e - h i e r a r c h i c a lg e n e r a l i z a t i o nt r e e ) 、 属性关系规则( a r r u l e s ：a t t r i b u t er e l a t i o n s h i pr u l e s ) 和基于环境的约束( e b c ： e n v i r o n m e n t b a s e dc o n s t r a i n t s ) 三种。文献 2 4 】中从查询驱动的系统功能出发，讨 论了基于约束的多维数据挖掘，通过一个数据挖掘查询实例进一步阐述了这些约 束及所产生的关联规则，并用数据挖掘查询语- 言( d m q l ) 进行表达；它介绍和讨论 了关联规则的处理，在挖掘关联规则中联合使用维层约束和规则约束能够带来高 效的挖掘过程，一个规则约束如果能被较深地插入到分层结构里并在当前提取层 和较深层上进行深入挖掘是非常有价值的；它最后给出了一种联机分析挖掘系统 的结构，并对其组成、功能及特点进行了描述。文献【2 5 】针对数据挖掘时的效率问 题，提出了给决策树加上规模和精确度约束以及在序列模式发现1 2 6 j 中；b h k 结构和 规则表达约束，用以增加数据挖掘的可伸缩性。基于约束的数据挖掘方法正在蓬 勃发展，将成为一个具有广阔f j 景的研究方向。 c c 问题最早出现在文献 2 7 中，该文就工厂选址问题进行了研究，而后k i r i w a g s t a 和c l a i r ec a r d i e 在文献 6 中提出了两种的约束条件即m u s t l i n k 和 c a n n o t l i n k ，并说明了约束条件不仅可以提高聚类结果的正确性而且可以减少算 第3 页 国防科学技术人学研究生院硕+ 学位论文 法的时间消耗。韩加炜等人对c c 问题进行了深入总结和分析【7j ，最常见的约束聚 类问题就是障碍约束的空间对象聚类( c o e t 2 8 j ：c l u s t e r i n gw i t ho b s t a c l e e n t i t i e s ) ，在对空间对象进行聚类时往往因为有高山大河等障碍物的存在使得 聚类时本来距离很近的两个对象不能聚到同一个簇中。经过几年的研究在解决障 碍约束的聚类问题时，已经有了几种较成熟的算法如：c o dc l a 凡州s 1 2 、 a u t o c l u s t + 1 3 0 1 、c p o l 3 1 1 、d b c i u c l 3 2 】和d b r s + 1 3 3 1 。国内在研究该问题上也涌现 了一批成果，在文献 3 4 3 6 】中，张雪萍教授主要用进化算法来改进传统的聚类算 法使其能解决c o e 问题，文献 3 7 ，3 8 j 恿过改进传统聚类算法来解决障碍约束的空 间对象聚类问题。本文将针对不同类型的约束条件进行分析，对约束条件实施区 别对待，不同的约束采用不同的处理方法。 理论研究是要用来解决实际问题的，考虑到实际的需要，在领域知识约束下 的数据挖掘必将成为数据挖掘的一个发展方向，c c 问题也将成为聚类分析的一个 研究热点，当前的研究成果主要集中在约束条件的建模以及各种算法的提出上。 随着我军装备保障技术的不断发展，未来信息化战争中参战力量多元化， c 4 i s r 系统广泛使用，使得装备保障趋向一体化、自动化。传统的树状指挥体系将 被网状指挥控制体系所取代，各军兵种之间的界限将逐渐模糊，转而成为联合作 战的一体化方式。作战力量的一体化和武器装备保障的横向一体化导致装备保障 也朝着一体化保障方向发展，各个部队的协同保障要求更紧密配合、资源共享、 协调维修【3 9 1 。装备保障区域自动划分将帮助解决协同保障过程中出现的保障资源 分配不均、计划不周、预测不准等问题，能够充分利用现有资源，缩短装备保障 的平均等待时间，在最短时间内恢复装备的战斗力，最大限度地保持和恢复装备 的完好性，提高装备的高强度快速出动力，为战争赢得主动权；同时也缓解保障 经费不足的问题。 1 3 研究目内容与思路 首先，通过对课题背景问题的深入分析，选择了用图论聚类算法对该问题进 行求解，将装备保障区域自动划分问题建模成一个图划分问题；其次，提出能够 解决该课题背景问题的基于最小生成树的聚类算法；然后，通过对算法进行实验 证明其性能和效果；最后，将文中提出的算法应用于装备保障区域自动划分问题 中进行实例分析。 本文的主要工作将从以下几个方面展开： ( 一) 根据课题背景，提出一种合适的聚类算法。经过研究发现在现有的算 法中几乎没有适合解决装备保障区域划分问题。该问题主要是以空间道路网络为 基础，将问题描述为在考虑物资需求和簇大小等约束条件下的一个聚类问题，其 第4 页 国防科学技术大学研究生院硕十学位论文 结构能够用一个图进行建模，本文将采用图论聚类方法，也就是把要进行聚类分 析的对象看作是图的节点，对象之间的道路看作是图的边，将图划分为若干个满 足要求的子图，每个子图就是一个簇。文中提出的m s t c l u s t 算法是一种基于最小 生成树的聚类算法，该算法能在输入很少参数的情况下获取任意形状任意密度的 簇，并通过实验证明了该算法的效果和性能。 ( 二) 在m s t c i u s t 的基础上，提出了一个综合子树中的边权值的统计信息和 控制参数的目标函数，该目标函数是对聚类质量的一种评估。目标函数是关于控 制参数的一个跳跃函数，当参数取值合适时就能使目标函数达到最小值，此时达 到最佳聚类。根据这个函数，就能通过对函数最小值的搜索实现聚类算法控制参 数的自动设置。 ( 三) 提出一种基于约束的聚类算法。运用m s t c i u s t 算法的思想改造k r u s k a l 算法【4 0 1 ，将约束条件和控制参数引入到最小生成树构建过程的合并子树步骤中， 使得算法能解决带约束的聚类问题。通过实验验证该算法的性能和效果，算法还 能处理多种类型的约束条件。 ( 四) 对装备保障区域自动划分问题进行建模分析，通过约束条件下的聚类 分析方法对该问题进行求解。对存在的约束条件进行分析建模，将约束条件进行 分类考虑，对于不同的约束条件采用不同的解决策略。实验证明基于约束的聚类 分析在装备保障区域自动划分问题上是可行的。 本文的研究思路如下图所示： 图1 1 论文研究思路 第5 页 国防科学技术人学研究生院硕十学位论文 1 4 论文的组织结构 本文主要以装备保障区域自动划分为背景，重点研究数据挖掘中的聚类分析 方法，在现有算法基础上提出一种更好的适合课题背景的基于约束的聚类算法。 论文的组织结构如下： 第一章绪论。分析了高技术、信息化战争中装备应急机动保障的需求，提 出了装备保障区域自动划分的必要性，选择了数据挖掘中聚类技术来解决该问题， 总结了的国内外研究现状，阐述了研究内容和意义。 第二章相关技术研究。首先，介绍了聚类分析的基础知识，包括聚类的目 标，相似度的度量等：其次，对已有的聚类算法进行了总结比较，分析存在的不 足；最后，对基于约束聚类算法的发展状况进行了研究。 第三章提出了一种最小生成树聚类算法。本章首先提出一种基于最小生成 树的聚类算法，并通过实验证明了该算法的优越性。其次根据该算法构建了一个 聚类结果评价函数，该函数是控制参数的一个跳跃函数函数，每个跳跃点就是聚 类结果改变的点。当函数达到最小值时对应的聚类结果最佳，控制参数最合适； 因此可以通过搜索函数最小值实现输入参数的自动设置。最后用实验证明了该函 数的收敛性。 第四章提出基于约束的最小生成树聚类算法。本章中首先对背景问题中可 能存在的约束条件进行分析建模，对不类型的约束采用不同的处理方法，最后都 引入到最小生成树聚类算法中，提出了一种基于约束的最小生成树聚类算法，然 后通过实验证明了该算法的优越性。 第五章对装备保障区域自动划分技术进行研究。利用前面提出的算法，对 背景问题进行建模分析，通过对一个实例分析说明了文中所提算法在装备保障区 域划分中的科学性和可行性。 最后对全文进行了总结，并提出了下一步的研究工作。 第6 页 国防科学技术大学研究生院硕十学位论文 2 1 1 聚类分析基础 第二章聚类分析概述 2 1 聚类问题描述 聚类分析是数据挖掘中的一个重要研究方向，在许多领域都有实际应用价值， 近年来得到了学者们广泛而深入的研究。聚类所涉及的应用领域有：生物学、统 计学、模式识别、信息检索、机器学习、数据挖掘、心罩学和其它社会科学等。 聚类是一项重要的人类活动，人们擅长将对象划分为有意义的簇，并将特定的对 象指派到这些簇中。 2 1 1 1 聚类分析的概念 将物理或抽象对象的集合，根据对象之间的相似( 相异) 度进行分组的过程 称为聚类。一个好的聚类方法获取的聚类结果应该具有如下特性：同一组内的对 象之间相似度较大，不同组之间的对象相似度很小。与数据挖掘中的分类分析相 比，传统的聚类分析是一种无监督的分类方法，没有任何先验知识可用。二维数 据点的聚类过程如图2 1 所示： 图2 1 二维数据点的聚类 【定义2 1 】簇( c l u s t e r ) 是一组物理或抽象对象的集合，也就是聚类结果中 的分组，每个分组称为一个簇。 【定义2 2 】根据对象之间的相似性，将对象集s 划分为 s i ，s 2 ，s 七) 的过 程称为聚类分析，其中s = s ，i o f 疗 ，k ，7 ，划分满足： s 矽，sss ( i = 1 ，2 ，尼) 七 u s , = s 式( 2 1 ) - l s n s , = ，i ，= 1 ，2 ，k ；i ； 聚类的基本过程如下1 4 1 1 ： 第7 页 国防科学技术大学研究生院硕+ 学位论文 ( 1 ) 数据准备：包括特征标准化和降维。 ( 2 ) 特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。 ( 3 ) 特征提取：通过对所选择的特征进行转换形成新的突出特征。 ( 4 ) 聚类：首先选择适合特征类型的相似( 相异) 度函数，或构造新的相 似( 相异) 度函数进行邻近程度的度量，然后执行聚类分析。 ( 5 ) 聚类结果评估：是指对聚类结果好坏的评价。评估主要有3 种：外部 有效性评估、内部有效性和相关性测试评估。 一个完整的聚类过程是需要反馈的，如图2 2 所示。 反馈 图2 2 聚类分析过程图 2 1 1 2 聚类的数据基础 对客观世界中的对象、过程、系统和关系的描述，都要用到数据，数据包括 各种各样的形式，如文本、图形图像、视频和声音等。数据是通过把感兴趣的实 体以某种测量映射成的符号表示，测量就是把实体的每个属性与一个变量联系起 来【4 2 】。假设一个对象有d 个属性，则若干个具有d 个属性的数据对象就构成了d 维 空间，在d 维空间中，数据对象被称为d 维数据点，则d 维数据点x 可表示为 j c = ( x i , x 2 ，x a ) ，其中x i 表示第f 个属性值，d 表示空间的维数。具有刀个数据对 象的数据集可以表示为： x 1 l x 1 2 x 2 1x 2 2 x d lx d 2 聚类中的数据属性值有如下性质【2 】： ( 1 ) 相异性= 和。 ( 2 ) 序歹0 和 ( 3 ) 加法+ 和一 ( 4 ) 乘法和 根据这些性质，可以将定义四种属性类型：标称( n o m i n a l ) 、序数( o r d i n a l ) 、 区间( i n t e r v a l ) 和比率( r a t i o ) 。表2 1 给出这些类型的定义，以及每种类型上合 法的统计操作等信息【2 1 。 第8 页 疗 疗 h 嘞 国防科学技术人学研究生院硕十学位论文 表2 1 不同的属性类型比较 属性类型描述例子操作变换注释 标称属性的值邮政编码、众数、熵、任何一对一如果所有雇员 仅仅只是不同雇员i d 号、列联相关变换，例如值的l d 号都重新 标的名字，即标称眼球颜色、 、x 2 检验 的一个排列赋值，不会导 称 值只提供足够性质致任何不同 的信息以区分 分类的对象( = 。) ( 定性的) 序数属性的值矿t i 硬度、中数、百 属性值的保包括概念好、 提供足够的信 好，较分位、秩 序变换，即：较好、最好的 序 息确定对象的 好，最好) 、相关、符新值属性可以完全 序( s ，)成绩、号检验。 = ( 旧值) 等价地则值 列 街道号码 其中厂是 1 ，2 ，3 或 单调函数 0 ，5 ，1 0 ) 表示 对于| 又：间属性，日历日期、均值、标新值= a 旧华氏和摄氏温 区 值之间的若是摄氏或华准著、皮值+ b度零度的位置 间 有意义的，即存氏温度尔逊相 其中口、b 是 和1 度的位置 在测量单位关、t 和 常数 的大小( 单位) 数值的 ( + ，一) f 检验不同 ( 定量的) 对丁比率变量，绝对温度、儿何平新值= ax 旧长度可以川米 比 著和比率都是货币鹫、计均、调和值或英尺度量 有意义的( ， 数、年龄、平均、百 奎 质量、长分比变差 ) 度、电流 标称和序数属性统称分类( c a t e g o r i c a l ) 或定性的( q u a l i t a t i v e ) 属性。顾名思 义，定性属性( 如雇员i d ) 只是一个符号表示，即使它是用数字符号表示的也不 具有数的性质。其它两种类型的属性，区间和比率属性，统称定量的( q u a n t i t a t i v e ) 或数值的( n u m e r i c ) 属性。定量属性用数表示，并且具有数的大部分性质。用属 性取值的个数和范围描述数据有： 离散的( d i s c r e t e ) ，离散属性具有有限或无限个可数取值。这样的属性可以 是分类的，如邮政编码或i d 号，或者是数值的，如计数等。 连续的( c o n t i n u o u s ) ，连续属性是取实数值的属性。如：温度、高度或重量 等属性，通常连续属性用浮点变量表示。 数据集的类型有多种，并且随着数据挖掘的发展与成熟，更多类型的数据集 将用于分析。数据集的一般特性1 2 j ： 【定义2 。3 】维度( d i m e n s i o n a l i t y ) ：数据集的维度是数据集中对象的属性 个数。低维数据与中、高维数据有质的不同。 【定义2 4 】稀疏性( s p a r s i t y ) ：对于一些具有非对称特征的数据集，一个 对象大部分属性上的值都为0 ，在许多情况下非零项不到1 。实际上稀疏性是一 第9 页 国防科学技术大学研究生院硕+ 学位论文 个优点，因为只有非零值j 需要存储处理。 【定义2 5 】分辨率( r e s o l u t i o n ) ：常常可以在不同的分辨率下得到不同的 数据，并且在不同分辨率下数据的性质也不同。 2 1 1 3 相似度度量 聚类是根据对象之间的相似( 相异) 度对对象进行分组的，如何定义和度量 对象之问的相似( 相异) 度是聚类开始之前非常重要的一项准备工作。 ( 1 ) 相似( 相异) 度度量 对象之间的属性可能是各种类型的，不同类型属性的相似( 相异) 度度量方 法不同，文献【2 】对一些简单属性相似( 相异) 度度量方法进行了总结，具体如表 2 2 所示，其中x ，y 表示两个对剃2 。 表2 2 简单属性的相似度和相异度 属性类型相异度相似度 ，f 0 如果x = y f1 如果x = y 标称的 拈1 l 如瓢y s2 1 0 如黜y 序列的d = l 弘棚( 值映射到区间 s = l d 0 ，1 】，其中”是值的个数) s = 一d ，s = p ， 1 | 又：间或 d = l x - y i j = 一 1 + d 。 比率的 s = 1 _ m a x 口一i n 仃l d nd 对于不同类型属性的组合可以将相似度投影到o 到1 上，用一个权值表示每 个属性的重要性，对象之间的相似度【2 】用组合属性表示为： 式( 2 2 ) ，y ) = 弋f f 一 式( 2 2 ) 其中表示对象第七个属性的权重，反是第七个属性上的一个指示变量，当 两个对象在该属性上的值都为空，或者其中一个对象在该属性上取值为空时 瓯= 0 ，否则瓯= 1 。( x ，y ) 是对象x 与y 在第k 个属性上的相似度。 ( 2 ) 对象之间的距离 对象之i n j 的相异度通常通过对象之l 、日j 的距离来度量，对象之间的距离可分为 闵可夫斯基距离、马氏距离和余弦距离，最为常用的是闵可夫斯基距离，定义如 下： 第1 0 页