（系统分析与集成专业论文）聚类挖掘研究及其在隧道病害评价中的应用.pdf

韭塞窑适太堂亟堂焦监塞空塞撞重 中文摘要 摘要：信息社会对海量数据的处理能力提出了更高的要求。数据挖掘技术伴 随着这种需求应运而生，已成为信息技术研究的热点之一。而聚类挖掘是数据挖 掘技术中被广泛采用的技术之一。 本文主要对模糊聚类算法f c m 进行了改进：结合竞争聚类算法c a ，健壮性 算法n c 和关系型聚类算法f r c ，提出了新的目标函数，并借鉴以上几种算法的 推导方法，推导出隶属度的迭代公式。该算法具有以下特点：第一，通过竞争因 子，使大量的初始聚类逐渐退化到最佳数目的聚类，可以解决传统算法由于缺乏 先验知识而产生的聚类数目不合理的问题；第二，通过引入噪声类项，使得算法 对孤立点有良好的适应性，从而更加健壮：第三，在目标函数中直接引入相异度 函数，使得算法可以直接适用于非欧几里德距离的关系数据。此外，在研究基于 划分的聚类算法的基础上，对肛均值算法进行改进，提出p k m 算法，通过计算机 仿真验证了算法的优越性。 结合隧道病害检测数据的特点，提出了从预处理到评价的有效方法。首先， 对数据进行清洗，采用离散化和归一化方法对数据进行转换，并给出数据的集成 方法；随后，针对预处理后的数据，应用病害数据相似( 异) 度的度量方法求解 隧道之间的相异度；最后，采用改进的模糊聚类算法以及瘸害等级评价方法，对 7 5 8 条隧道的病害检测数据进行聚类分析，得出聚类结果，并将结果按照严重程度 划分为四个等级，对应病害的四种健康状况。通过对病害状况的初步分析，提出 若干意见和建议，为隧道病害预防和整治提供有用参考。 关键词：数据挖掘；聚类；模糊聚类；f r c ；隧道病害 分类号：t p 3 l l j b 豆銮适丕堂亟堂僮监塞旦s ! 丛! a b s t r a c t a b s t r a c t ：t h e c h a l l e n g ef o rp e o p l ei ni n f o r m a t i o ns o c i e t yi st od e a lw i t hm a s s d a t aw i t hh i 啦a b i l i t i e s d a t am i n i n gt e c h n i q u eh a sb e e nr a i s e nt ot h ec h a l l e n g ea n d b e e nah o tr e s e a r c ht o p i c c l u s t e r i n gm i n i n gi so n eo ft h em o s ti m p o r t a n td a t am i n i n g t e c h n o l o g i e st h a th a v eb e e nw i d e l yu s e d t h i sp a p e rm a i n l ym a k e si m p r o v e m e n t0 1 1f u z z yc l u s t e r i n ga l g o r i t h m sf c m a n e wo b j e c tf u n c t i o ni sp u tf o r w a r do i lt h eb a s i so fc o m p e t i t i v ea g g l o m e r a t i o n ，n o i s e c l u s t e r i n ga n df r c o nr e l a t i o n a ld a t a a c c o r d i n gt ot h ed e d u c em e t h o d sm e n t i o n e di n t h ea b o v ea l g o r i t h m s ，t h en e c e s s a r yc o n d i t i o n sf o rm i n i m i z a t i o na r ed e r i v e dt h r o u g hn s e o fd i r e c to b j e c t i v ef u n c t i o nm i n i m i z a t i o nb a s e do i lt h el a g r a n g em u l t i p l i e rt e c h n i q u e t h ea l g o r i t h mh a st h ef o l l o w i n ga d v a n t a g e * ：f i r s t ，a st h ei t e r a t i o np r o c e e d s ，t h ef i n a l p a r t i t i o ni s t a k e nt oh a v et h e ”o p t i m a l ”n u m b e ro fc l u s t e r sb a s e d0 1 1c o m p e t i t i v e t e c h n i q u ew i t h o u ta p r i o r ik n o w l e d g eb yi n t r o d u c i n gc o m p e t i t i v ei t e m ；s e c o n d ，t h e a l g o r i t h mb e c o m e sm o r er o b u s tt h r o u g hi n t r o d u c i n gn o i s ep a r a m e t e r ；t h i r d ，i tc a nb e d i r e c t l yu s e do nn o n e u c l i d e a nd a t aw i l l lt h ed i s s i m i l a r i t yp a r a m e t e r i na d d i t i o n , o nt h e b a s i so fp a r t i t i o n i n gm e t h o d s 矾i m p r o v e dk - m e a n sa l g o r i t h mi sg i v e n t h r o u g h c o m p u t e re m u l a t i o n , t h ea d v a n t a g e so f t h ea l g o r i t h ma r ev a l i d a t e d c o n s i d e r i n gt h ec h a r a c t e ro ft h et u n n e ld a m a g ec h e c k i n gd a t a , e f f e c t i v em e t h o d s o nd a t ap r e p r o c e s s i n g , s i m i l a r i t yc o m p u t i n g , c l u s t e r i n ga n dd a m a g ee v a l u a t i o na r e i n t r o d u c e d t h ef i r s ts t e pi sd a t ac l e a n i n g , i n t e g r a t i o na n dt r a n s f o r m a t i o n s e c o n d ， a p p r o a c h e so ns i m i l a r i t yc o m p u t i n go ft u n n e ld a t aa r ei n t r o d u c e d a tl a s t ，i m p r o v e d f u z z yc l u s t e r i n ga l g o r i t h mi sg i v e na sw e l la sa p p r o a c ho nd a m a g ee v a l u a t i o n t h r o u g h c l u s t e ra n a l y s i so n7 5 8t u n n e ld a t ar e c o r d s ，i n i t i a lc l u s t e rr e s u l t sa r eo b t a i n e da n d d i v i d e di n t o4r a n k sa c c o r d i n gt ot h ed a m a g ed e g r e e , w h i c hc o r r e s p o n dt o4k i n d so f d a m a g es i t u a t i o n s s o m es u g g e s t i o n s a r eg i v e ni no r d e rt h a t t h e y c a l l p r o v i d e d e c i s i o n - m a k i n gd u r i n gt h ep r o c e s so f p r e v e n t i o na n da 鹏 k e y w o r d s ：d a t am i n i n g ；c l u s t e r i n g ；f u z z yc l u s t e r i n g ；f r c ；t u n n e ld a m a g e c l a s s n o ：t p 3l l 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：a ； 嘏雪 签字日期：彻7 年2 月加日 f u 日珂 y ， 似 年 分7 与以 如 名 期 签 日 师 字 导 签 j e 丞窑适盔堂亟鲎僮监塞 独剑娃直嘎 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除 了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名：王羽婧 签字日期：盈 哕年 ，2 月o e t 致谢 本论文的工作是在我的导师徐维祥教授的悉心指导下完成的，徐维祥教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响，在学习上和生活上都 给予了我很大的关心和帮助。在此衷心感谢三年来徐维祥老师对我的关心和指导。 钟雁教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心 的感谢。 在实验室工作及撰写论文期间，张翼、王晓冬等同学对我论文中的编程工作 给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 i e 塞銮通塞堂亟堂僮逾塞 i i 直 1 1 论文研究的目的和意义 1 引言 随着信息技术在各行各业的普遍应用，人们获得并存储下来的数据呈爆炸式 增长，适用于海量信息存储和分析的数据仓库以及数据集市已经被用于商业管理、 政府办公、科学研究和工程开发等领域。海量数据的出现也带来了一些亟待解决 的问题；获得海量数据是否就意味着获得了海量的信息，这些数据究竟能够带给 人们多少有用的信息，而这些信息又能够用来做什么呢? 要想使数据真正成为能 够被人利用并且带来效益的资源，只有充分的认识数据，并且懂得利用适当的方 法从中获取知识。信息需要从数据中获取，于是基于数据库的数据挖掘技术应运 而生，目前已是数据库和信息处理领域的最新研究热点。 聚类挖掘是数据挖掘的一个重要分支，聚类挖掘能够根据数据本身的特征产 生分类，而不是通过训练已有的数据产生规则，进而产生分类。这使得聚类挖掘 在未知领域能够发挥很大的作用，可以使用户对数据基本的类别有清晰的了解。 “均值方法和f c m 方法是聚类挖掘技术的典型代表。 肛均值算法是最早提出的聚类算法之一，是基于划分思想的聚类算法的鼻祖。 针对小数据量数据，如均值算法具有运算快速以及有效性高的特点，迄今为止，仍 然有很多聚类任务都采用该方法。舡均值算法也存在很多问题，包括如何选取初始 点，如何定义合理的聚类数目，以及如何增强其抗噪声能力等，这些问题限制了 该算法的进一步应用。针对上述问题对“均值算法进行改进，至今仍是硬聚类研究 的重要方向。 f c m 算法是人们继承了缸均值算法的思想，并结合模糊理论提出的基于迭代的 模糊聚类算法。通过引入模糊因子，聚类算法与现实结合得更加紧密，已经成为 非常实用的聚类算法之一。然而，该算法同样存在着致命的缺点：难于准确选取 初始聚类中心并确定聚类数目，易受到噪声的影响，不能够适用于特定类型的数 据等。为了使f c m 算法在网站日志分析、金融、电信以及铁路隧道检测数据分析 等领域获得更广泛的应用，对f c m 算法进行改进是非常必要的。 我国自1 8 8 8 年开始建造第一座铁路隧道阻来，迄今已经有1 1 0 余年的修建历 史。至2 0 0 5 年，我国已成功修建了7 5 0 0 多座、总延长4 3 0 0 多公里的铁路隧道，隧 道数量和总长度均居世界前列【l 】。铁路部门每年对这些铁路隧道进行一次大规模的 病害检查，目的是找出病害严重的隧道，及时进行修理，以确保铁路行车的安全 韭塞窑适太堂亟堂焦垒塞 i ! 壹 畅通。据铁道部统计资料显示，部分运营隧道的病害问题相当严重，甚至已经危 及到行车安全( 1 l 。虽然统计数据已经足够多，但对数据的应用仍只局限在简单的查 询及统计上，隧道健康状况评价方法也仅仅局限在定性的层次分析法层面。由此， 有必要对铁路隧道病害数据进行深入挖掘，为隧道病害的整治以及日常维护提供 科学的决策支持。聚类方法就是认识病害的有力工具，根据病害的严重程度，可 以将隧道分为不同的类型，有利于从宏观上对成千上万条病害隧道有一个清晰的 认识。得到初始聚类之后，还可以对每种聚类中的隧道进一步聚类，将每个聚类 划分为更小的聚类单元，如此反复，可以找出具有相似病害的隧道之间的共性和 特性。此外，由于每条隧道的各个部分的基本建设条件都不同，基础数据对隧道 的不同施工段落都有详细的记录，还可以以隧道的不同段落为对象进行聚类，进 一步得出具体影响因素和病害状况共同决定的聚类结果。因此，聚类挖掘在隧道 病害评价中的应用具有具有较强的现实意义。 综上，对经典聚类算法，尤其是f c m 算法进行改进，不仅具有理论价值，而 且将f c m 改进算法应用到隧道病害检测中具有实用价值。因此选定“聚类挖掘研 究及其在隧道病害评价中的应用”作为论文题目。 1 2 研究现状 1 2 1数据挖掘技术及研究现状 随着人类社会从工业时代向信息时代迈进，各个行业和领域都会产生或遇到 海量的数据，随之带来的问题也是人们从来没有遇到过的，因为在缺乏强有力的 分析工具的情况下，人的理解和概括能力面对海量数据已经变得无能为力。为了 避免在爆炸性增长的海量数据中迷茫，看清海量数据中潜藏的信息，并利用这些 有用的信息获得更大的进步，各种新技术和自动信息处理工具得到了快速发展。 知识发现k d d ( k n o w l c d g cd i s c o v e r y i nd a t a b a s e ) 和数据挖掘d m ( d a t am i n i n g ) 作为 新技术的代表，得到了前所未有的大发展。 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的实际应用数据中， 提取隐含在其中的、事先未知的、但又潜在有用的知识的过程。它是数据库技术 发展演变的结果，是信息技术领域最有前途的交叉学科之一。数据挖掘汇聚了不 同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方 面的学者和工程技术人员。在信息领域，有很多说法都与数据挖掘相似，如数据 库中的知识发现0 c d d ) 、数据分析( d a t aa n a l y s i s ) 、数据融合( d a t af u s i o n ) 等。 由于数据来源于各个行业的实践，因此数据挖掘技术从一开始就是面向应用 2 j e 峦銮适本堂亟堂僮监塞 i l 壹 的。这就使得对数据进行挖掘的方式集合了各种统计的、分析的、综合的和推理 的方法。这些方法用于准确地指导实际问题的求解，对混乱的数据进行清晰的分 类、快速发现事件之间的关联，利用已有的数据对未来将要发生的事情和趋势进 行预测等。然而，数据挖掘发现的知识，其合理有效都是相对的，因为某一种数 据挖掘方法只是针对某一类问题，是在特定约束条件下提出的，这是至今还很难 产生通用数据挖掘算法的原因。数据挖掘发现的知识不仅可以用于信息管理、查 询优化、决策支持、过程控制等，还可以用于数据自身的维护。这些知识还要以 容易被用户理解的方式表达，最好能用自然语言表达发现结果，因此数据挖掘的 研究成果很讲求实际。 数据挖掘过程是一个完整的过程，该过程从大型数据库中挖掘先前未知的、 有效的、可实用的信息，并利用这些信息做出决策或丰富认识【孙。 数据挖掘的流程如下图所示： 图1 - 1 数据挖掘过程 f i g u r el 一1d a t am i n i n gp r o c e s s 上述过程包括以下5 个步骤： 1 确定挖掘对象和方法 明确需要解决的问题以及数据挖掘的目的。虽然数据挖掘的最后结果是不可 预测的，但是在挖掘之前要明确研究对象以及涉及的各种问题，这样才能尽可能 减少盲目性，保证研究结果的有效性。 2 数据准备 ( 1 ) 数据的选择 根据挖掘的目的，尽可能多的搜集与业务对象有关的内部和外部的数据信息， 并根据实际需要，从中选择挖掘对象。 ( 2 ) 数据的清洗 为了排除噪声的干扰，需要对数据质量进行评价，清洗掉不合理的噪声数据， 并对不合要求的数据进行标准化，为进一步分析做准备。 ( 3 ) 数据的转换 建立适合挖掘算法的分析模型是数据挖掘成功的关键。针对挖掘目的和数据 的具体特征，将数据转换成分析模型需要的格式。 3 数据的挖掘 根据数据的特征，对挖掘算法进行研究和改进，并编程实现。 4 结果分析 根据数据挖掘操作，选择适当的分析方法对挖掘结果进行评估，同时结合应 用实际进行比较分析，还有可能使用可视化技术。通过结果分析将数据挖掘结果 转化为有用的知识。 5 知识的同化 同化过程是将有用的知识集成到实际应用的信息系统组织结构中去，从而作 为系统的一个模块，实现特定的功能。 数据挖掘流程可以通过数据挖掘环境直观地表示出来，如下图所示： 图卜2 数据挖掘环境 f i g u r e1 2d a t am i n i n ge n v i r o n m e n t 数据挖掘发现的知识主要包括以下几种：( 1 ) 广义型知识，反映同类事物共性 的知识；( 2 ) 特征型知识，反映事物各方面特征的知识；( 3 ) 差异型知识，反映不 同事物之间属性差别的知识；( 4 ) 关联型知识，反映事物之间相互依赖或关联的知 识；( 5 ) 预测型知识，根据历史及当前数据推测未来数据的知识；( 6 ) 偏离型知识， 揭示事物偏离常规出现异常现象的知识。 用于知识发现的挖掘算法主要有分类、聚类、预测、关联规则四大类，常用 的实现技术有可视化、决策树、不确定性处理等。随着互联网、图像和多媒体的 快速发展，知识发现的原始数据既可能是结构化的，如关系型数据库中的数据， 也可能是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型 数据。原始数据的演变对挖掘算法提出了更高的要求，己成为数据挖掘发展的重 要推动力。 目前，对数据挖掘知识的研究方兴未艾。伴随着t b 级数据的产生，数据挖掘 技术会被更多的人认识，不仅仅是研究者，普通用户也逐渐需要挖掘技术辅助决 策。虽然当前只有针对结构化数据的挖掘算法比较成熟，但是可以预计，以下几 韭塞窑通友堂亟堂建途塞 l ! 壹 个方向很可能成为数据挖掘领域的研究热点：( 1 ) 专门用于知识发现的标准化数据 挖掘语言；( 2 ) 数据挖掘过程中的可视化方法，使得知识发现过程容易被用户理解， 也便于在知识发现过程中的人机交互；( 3 ) 网络环境下的数据挖掘技术，特别是在 i n t e m e t 3 z 建立d m k d 服务器，与数据库服务器配合，实现数据挖掘；( 4 ) 非结构化 数据的挖掘，如文本数据、图形图像数据、多媒体数据。 1 2 2 聚类技术研究及应用现状 聚类是研究数据之间逻辑上或物理上的相互关系的技术，把数据集分解划分 成组，使同组中的点彼此相似，不同组中的点尽可能不同，它通过事物最自然的 属性产生最自然的子类【引。聚类结果不仅能够揭示数据之间的内在联系与区别，同 时也为进一步的数据分析与知识发现提供依据，如数据闻的关联规则，分类模式 以及数据的变化趋势等。聚类技术最早作为统计学的重要研究内容之一，后来扩 展到人工智能领域，逐渐打下了坚实的理论基础并形成了系统的方法学体系。然 而，基于统计学的聚类方法多限于理论分析，并依赖数据分布概率假设，很少考 虑实际数据特征。随着数据挖掘技术的崛起和方法体系的建立，聚类技术在数据 库领域得到新的发展，逐渐向智能化方向发展。 聚类技术算法有很多，大体分为四大类；基于层次的、基于划分的、基于密 度的和基于网格的，如图1 3 所示【4 】。 图l - 3 聚类算法的分类 f i g u r e1 - 3c l u s t e r i n ga l g o r i t h m sc l a s s i f i c a t i o n 韭塞窑适友堂亟堂焦垃塞 i i 直 针对以上四类算法的改进一直都是研究热点，但是由于每种改进算法针对的 数据类型和分布都不同，改进算法本身只解决某一个类型的问题，因此，绝大多 数改进算法又在不断的探索中，聚类技术被研究得越来越深入，并在逐渐走向成 熟。随着模糊数学理论的发展和广泛应用，用模糊的手段处理聚类问题逐渐成为 研究的主流。最早系统地表述和研究模糊聚类问题的是著名学者r u s p i n i ，他率先 定义了模糊划分【5 的概念。利用这一概念，人们相继提出了多种模糊聚类方法，比 较典型的有：基于相似性关系 日和模糊关系的方法啊、基于模糊等价关系的传递闭 包方法网、基于模糊图论的最大树方法 9 1 、以及基于数据集的凸分解【1 0 1 、动态规划 1 1 1 和难以辨识关系等方法【12 1 。然而，上述方法均不适用于大数据量的情况，难以 满足实时性要求较高的场合，因此在实际中应用并不广泛。 实际中受到人们普遍欢迎的是基于目标函数的模糊聚类方法，这种方法把聚 类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和 聚类。这类方法设计简单、解决问题的范围广，还可以转化为优化问题从而借助 经典数学的非线性规划理论求解，并且易于计算机实现【”】。随着计算机的应用和 发展，基于目标函数的模糊聚类算法成为新的研究热点。 基于目标函数的模糊聚类有三个主要的研究方向【1 4 】：对目标函数的研究，对 算法实现途径的研究，以及对算法有效性度量的研究。 1 目标函数研究 对目标函数进行研究就必须对模糊划分矩阵、相似性准则和数据集特性进行 研究。以下分别简要介绍这几方面的研究进展： ( 1 ) 模糊划分矩阵 传统的聚类是一种硬划分，为了表达模式间的相近信息，人们引入了模糊划 分的概念，但是模糊划分中隶属度仅仅能够表示样本在聚类之间的分享程度，而 无法反映其典型性，v g 以k r i s h n a p u r a m ”蝽提出可能性划分的概念，放松了该约束。 为了结合硬聚类和模糊聚类的优点，s e l i m 和i s m a i l 16 】在1 9 8 4 年提出了半模糊划分 的概念，只保留划分矩阵中较模糊的元素，对其余元素进行去模糊处理。这样使 划分矩阵既具有一定的明晰性，又保持了样本在空间分布的模糊性，从而提高了 分类的正确性。后来，k a m e l 和s e l i m 1 7 提出了改进型的半模糊划分方法，即闽值 型软聚类方法。 ( 2 ) 相似性准则 没有种聚类准则能够解决所有可能的无监督分类问题，目前，研究者己经 提出一些相似性准则，如最大似然准则1 帅、最大熵准则n 9 】、最小体积准则【2 0 1 、非 计量的准则【2 1 1 ，s u g e n o 模糊测度准则【捌和信息论准则等。然而在实际应用中， 最常见的，也是最简单的是基于最小类内加权平方误差和准则。j a j u g a 2 4 及 6 j t 塞塞适太堂亟堂焦论銮 j i 壹 b o b r o w s k i 和b e z d e k t 2 5 1 分别讨论了l l 和k 范数下的模糊聚类算法( 即h a m m i n g 和 m a x i m u m 距离) ，发现在许多情况下它们比常用的欧氏范数l 2 能获得更好的结果。 另p m a h a l a n o b i s 距离的一种特例，即加权欧氏距离还被广泛地使用于模式各维特 征对分类贡献不同的应用背景【2 6 】。 ( 3 ) 数据集 在实际的数据挖掘应用中经常需要处理不同类型的数据，除了常见的数值型 数据以外，还有其他类型的数据，如关系数据 朋、方向数据f 2 8 】、区问型数据、模 糊数值【2 9 】和符号数据【删等。对于多种结构并存的数据，只有g u s t a f s o n 和k e s s e l 3 1 】 提出的模糊协方差聚类方法能同时检测椭球形结构和线性结构的模式子集，而 j a w a h a r t 3 2 1 对不同的几何结构聚类的检测做了一定的尝试，目前相应的研究比较少。 2 实现途径 模糊聚类算法实现途径主要是指对目标函数进行优化，以获得最佳聚类。现 有的优化算法主要分为：基于交替优化、神经网络和自然计算等三类方法。以下 分别简要介绍这三方面的研究进展： ( 1 ) 基于交替优化的实现 在优化目标函数的过程中，很多方法被尝试过，如动态规划、分支定界和凸 切割等方法，但是大量的存贮空间和运行时间限制了这些方法的应用。实际中应 用最广的是d u a n t s l 和b e z d e k t 3 3 1 提出的基于迭代优化算法，模糊“均值类型的算法。 模糊“均值算法有一个致命的缺点，因为算法本质上属于局部搜索的爬山法， 所以很容易陷入局部极值点，因此对初始化较敏感。 ( 2 ) 基于神经网络的实现 神经网络在聚类技术中的应用源于k o h o n e n 【3 4 】的两项工作：学习矢量量化 ( l v q ) 和自组织特征映射( s o f m ) ，以及g r o s s b e r 套”】的自适应共振( a r t ) 理论。 在数据挖掘中大数据集聚类计算是相当耗时的，而采用神经网络实现聚类计 算最显著的优势在于神经网络能够并行处理，节省运行时间。然而，上述两种神 经网络聚类存在一个缺陷，即只能实现球型的硬聚类。为此，人们不断的对模糊 聚类网络进行研究，p a l 和b e z d e k 3 6 】提出的基于竞争学习的模糊聚类网络，解决了 球型分布样本的模糊聚类；x 一7 】提出的带惩罚项的竞争学习算法，可以自动确定 聚类的数目；2 h a n g p 即提出的基于高斯非线性的竞争学习算法，用于模糊聚类并给 出了硬件实现方法。 ( 3 ) 基于自然计算的实现 自然计算( n a t u r e - i n s p i r e dc o m p u t a t i o n ) 是以自然界机理为算法设计基础的计算 方法。它包括进化计算、免疫计算、生态计算、量子计算和复杂自适应系统等研 究领域。其中进化计算已经被广泛应用在聚类计算中，形成了一系列基于进化计 j t 塞銮适太堂亟堂熊硷鸾 l 直 算的聚类算法。例如，基于模拟退火的方法【3 9 1 、基于遗传算法【4 0 3 和进化策略【4 l 】的 方法等。但是利用免疫计算、生态计算，量子计算等新兴的技术应用于聚类计算 的研究还有待于进一步的深入展开。 3 数据集和有效性研究 数据集是聚类过程的开始，也是聚类的对象，并不是所有的数据集不经过任 何处理就可以应用于聚类。对于给定的数据集，首先需要判断其中有无聚类结构， 此为聚类趋势研究；如果己经确认有聚类结构则需要用算法来确定这些结构，即 聚类计算研究；得到聚类结构后，则需要分析聚类的结果是否合理，也称为聚类 有效性研究。 传统的有关聚类有效性问题的研究大都是基于硬“均值和模糊缸均值算法的。 现有的聚类有效性函数按其定义方式可分为：基于数据集模糊划分的、基于数据 集几何结构的和基于数据集统计信息三类，三类的理论基础和特点均列述在表 1 1 t 1 4 】中。 现有的聚类有效性函数多是针对小均值算法的，而且，这些聚类有效性函数大 都是针对于数值型数据集的，对于其它比如类属型数据的聚类有效性度量有待于 进一步研究，以完善聚类有效性理论和应用。 聚类技术的应用范围十分广泛，在各个可能应用到聚类技术的领域都已经有 学者提出基本的应用方法，而这些新方法的提出使得聚类算法不断的适应于新的 领域，从而也推进理论的创新。 表1 - 1 有效性函数分类 t a b l e l 一1v a l i d i t yf u n c t i o nc a t e g o r y 比较项目基于模糊划分基于几何结构基于统计信息 好的聚类对应于数据聚类内部紧凑，聚类最佳分类的数据结构 理论基础 集较“分明”的划分 之间尽可能分离提供的统计信息最好 对结构明晰的数据集对分布明显的数据集 优点简单、运算量小 的聚类效果好的聚类效果好 与数据集的结构特征性能以来统计假设与 缺点表述复杂、运算量大 缺乏直接联系数据集分布的一致性 聚类技术的传统应用包括：在商务上，聚类能帮助市场分析人员从客户库中 发现不同的客户群，并且用购买模式来刻画不同客户群的特征；在生物学上，聚 类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认 识；聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，以及 根据房子的类型、价值和地理位置对一个城市中的房屋进行分组也可以发挥作用； 聚类还能够用于对w e b 文档进行分类，以发现信息，对w 曲日志进行信息提取，为 韭立窑迢盘兰亟堂焦诠塞 曼l 直 分析用户访问模式提供支持【3 】。 随着在各个领域对聚类技术的深入研究，聚类技术还被最新应用于以下领域： 图像识别【4 2 】：将聚类方法应用于图像识别系统中，通过对模板匹配的结果进 行聚类，能够更精确的找出物体的运动曲线。在边缘检测、图像增强、图像压缩、 图象平滑等众多方面，聚类方法也在发挥越来越大的作用。 交通流预钡8 【4 3 】：模糊控制算法是交通流控制领域中很有效的一种算法。在城 市交通流诱导系统中，利用检测器的交通数据，根据城市路网节点交通流量之间 的相互关系进行相似分析、聚类分析，可以较好地实现无检测器交叉口交通流量 的预测和交叉口的宏观管理。 情报分析】：在情报学中应用聚类方法将各种形态的情报研究对象按其不同 的特征进行聚类，揭示情报的动态关系，从而研究它们的内在联系以及发生、传 播、生长点等内在规律。 作为数据挖掘一个重要分支，聚类技术能够作为一种独立的工具来获得数据 分布情况，观察每个类的特点，集中对特定的某些聚类做进一步的分析。此外， 聚类技术还可以作为其他算法的预处理步骤。 1 2 3隧道病害评价研究现状 近年来，随着铁路跨越式发展战略的实施，列车的行车速度大幅度提高，机 车车辆轴重不断增加，使得铁路隧道的安全问题变得不容忽视，铁路隧道安全监 测和安全信息管理水平亟待提高。这就需要采用先进的信息采集、数据处理以及 数据挖掘技术，及时、准确地掌握既有隧道安全状态的变化，采取正确对策，消 除影响隧道行车安全的隐患，确保运营隧道行车安全。 目前我国并没有对铁路隧道健康状况进行深入的研究，对隧道病害数据的利 用仅仅停留在获取和查询的层面上。面对行车速度韵不断提高，铁路隧道的日趋 老化，这些简单的评价方法变得越来越不可靠，国内的研究方法已经落后于国外 的研究水平。铁路隧道病害检测数据是掌握隧道健康状态的基础资料。病害数据 不仅能够直接反映出隧道的健康状况，也能够间接地反映出更多信息，如隧道病 害的严重程度可以分为几个等级，每个等级对应的隧道病害具有什么样的特征， 隧道病害之间存在着什么样的关联，以及预铡病害恶化的趋势等等。 隧道病害检测数据量非常大，其中蕴含的有用信息和规律，用人工方法难以 获得。聚类技术能够产生忠实于数据属性的自然分类，并不关心聚类结果中数据 的规律，从而成为初步认识数据的关键技术。将聚类技术应用于隧道数据的实际 意义在于，它可以简单快速地发现有用的深层次信息，节省大量的人力物力资源。 9 韭立奎适太堂亟堂焦途塞 ! 直 铁路隧道病害的形成原因包括地质、岩石等自然条件的变化，施工建材的老 化，以及施工设计考虑不周等。对于形成原因的分析可以为今后的隧道建设提供 参考，也可以为隧道病害的防治提供依据。因此需要将多种数据挖掘方法应用于 隧道病害数据，而不是仅仅局限在聚类挖掘方法上，最终形成一整套合理的挖掘 方法体系，也是今后该领域的重要研究方向。 1 3论文的主要内容及组织结构 本文主要对模糊聚类算法进行了改进：结合竞争聚类算法c a 、健壮性算法 n c 和关系型聚类算法f r c ，提出了新的目标函数，并借鉴以上几种算法的推导方 法，推导出隶属度的迭代公式。此外，结合隧道病害检测数据的特点，本文提出 了从预处理到病害等级评价的有效方法。采用改进的模糊聚类算法，对7 5 8 条隧 道的病害检测数据进行聚类分析，得出聚类结果，并将结果按照严重程度划分为 四个等级，对应病害的四种健康状况。通过对病害状况的初步分析，提出若干意 见和建议，为隧道病害整治和防治提供有用参考。 本文还结合图论方法对经典如均值算法进行改进，得到性能稳定的聚类算法 p k m 。 文章组织结构如下： 第一部分首先介绍了选题背景，对选题的理论意义和实用价值进行分析；随 后介绍了数据挖掘技术和聚类技术研究现状；最后对论文的主要内容进行概括并 说明论文的组织结构。 第二部分首先对聚类基础知识以及经典聚类算法进行介绍；随后基于对经典 聚类算法的研究，对舡均值算法进行改进，提出一种新的聚类算法p k m 并通过编 程实现，验证改进算法的性能。 第三部分，介绍f c m 、n c 、c a 等几种有代表性的模糊聚类算法，并结合各 算法的优点，提出改进的模糊聚类算法c a f r c ，推导出该算法最优解的迭代公式。 最后编程实现c a f r c 算法在日志关系数据上的应用，算法效果得到初步验证。 第四部分，针对2 0 0 3 年隧道病害情况，分析隧道病害数据的特点，提出改进 的模糊聚类算法在隧道病害检测中的应用模型和方法，包括预处理方法、相异度 计算模型、改进的聚类模型以及聚类结果的评价方法。聚类结果表明，这种基于 数据本身特征产生的自然聚类的结果，可以作为基于传统层次分析法进行危害等 级评价的方法的有益补充，能够为隧道安全管理决策提供有用参考。 第五部分总结全文，给出数据挖掘在隧道病害检测中应用的进一步研究工作 建议。 1 0 垫夏窑适丕堂亟圭堂擅趁塞 丝基鐾袭簋鎏星基夔选 2 经典聚类算法及其改进 本章主要研究基于划分的经典硬聚类算法。首先对聚类问题、聚类中的数据 类型和数据结构进行描述，随后介绍如均值、k - m e d o i d s 等经典聚类算法，最后针 对b 均值算法的初始值选取问题提出改进方法，引入“最小圈”概念，提出p k m 算法。与“均值算法相比，p k m 算法可以获得准确且稳定的聚类结果，并通过计 算机仿真验证了p k m 算法的优越性。 2 。1聚类问题描述 2 1 1聚类概念 聚类是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过 程。类是一组数据对象的集合，同一个类中的对象彼此相似，不同类中的对象彼 此相异。聚类计算是机器学习领域中的无指导学习的一个例子，它不依赖于预先 定义的类和带类标号的训练实例，是一种观察式的学习。得到聚类结果之后，通 过对每个类的分析来描述类的含义，给出合理的解释，提取出需要的模式。聚类 实际上是在一定规则约束条件下的优化问题，只是不同的聚类方法对应的数据属 性值和目标函数不同。 在聚类技术里，二维聚类模型是最常用、最简单的概念模型。而数据分析处 理的大多是矩阵型的数据，或者是经过预处理后可以表示为矩阵的数据。相应地， 二维模型也是建立在由数据对象及其属性值组成的矩阵上，将二维空间的数据划 分为不同的类别。二维迭代聚类模型有以下两种【1 3 】： 定义2 1 ：给定有以个对象的数据集群= 缸i , x 2 , ，确1 ，定义距离( 相似度) 函数d ， 给定正整数，将数据集合破m 分为t 个不连接的部分( c l ，c 2 ，c d ，聚类就是通过迭 代对公式( 2 1 ) 给出的目标函数最小化来产生_ | 个分类( c 1 ，c 2 ，c 0 。二维聚类模型的 目标函数和约束条件表达式如下： f 歹( c ，x ) = ：。，d ( o ，研) i 2 。蜥- l ，蜥 o ，1 ( 2 1 ) 其中，d 2 ( c f ，却) 表示数据点畸与聚类中心c i 的距离，距离计算公式见2 2 1 节。 在式( 2 1 ) 基础上，引入模糊因子可以得到二维模糊聚类模型。 定义2 2 ：二维模糊聚类模型的目标函数和约束条件表达如下： i e 立銮遣盘堂亟竺逵诠塞 丝塾塞耋篡鎏盈基墼显 f ，( u ，c ) = 爰。蛳) dc i ，巧) i ：。蛳- 1 ，o u u l ，i - - 1 2 。k ，j = l 2 ，n ( 2 2 ) 公式( 2 - 2 ) 中，【，- “奠表示隶属度矩阵。 聚类的过程就是求公式( 2 - 2 ) q 6 目标函数最小的近似最优解( 配c ) 的过程，一般 是一个n p 问题。a n d e r b e r g 证明了将n 个数据项划分为七个类存在品种可能 嚣= 去：。( 一1 ) “。口加 ( 2 - 3 ) 例如，将2 5 个数据对象划分为1 0 个类的可能有5 ( 1 0 ) - 1 0 1 8 种，可见在所有可行解上 进行穷举搜索是不现实的【1 3 1 。 2 1 2聚类结果的表达 硬聚类结果可以表示为一个露n 的矩阵l m 砌t 。，其中u j 满足条件如下【4 5 1 ， f 蛳= 谥瓮 皂 j 1 ：扣_ 1 ( 2 - 4 ) i ii = l2 ，j9 k ，j = 1 ，2 ，” 随着可视化技术的日趋成熟，聚类结果的表达方式多种多样。既可以用图表 来表示，如散点图、直方图、分类表等( 其中在散点图中，用不同的符号表示不 同的类别，或者用不同的颜色区分不同类别的点) ，也可以用曲线表示，直观的画 出每个类的边界范围。可视化技术的应用，使得聚类结果的表达更加直观，更易 于理解。 2 1 3聚类有效性评价 针对同一个数据集，采用不同的聚类算法，会得到不同的聚类结果，因此需 要对聚类结果进行评价，以找到相对最佳的聚类算法。一般对于给定的数据集， 每种聚类算法都会发现聚类，不论能否产生聚类结果。因此，在聚类之前需要对 数据集进行测试，检验数据集能否得到聚类结果，最后对聚类结果进行有效性测 试，检验聚类结果是否有效合理。 通常采用有效性函数对聚类结果进行有效性评价。用于评价硬聚类的有效性 的函数称为量化函数，可以实现对划分的紧致度的度量。量化函数的选择往往依 赖于实际经验而不是一些严格的形式化标准。 评价模糊聚类的有效性函数主要包括划分系数、划分熵、划分指数和分离系 数。下面介绍三种评价函数的公式 4 6 1 ： ( 1 ) 分离系数公式：f 弘五) = ：，e ，嘲办。其中蠹为聚类结果的数目，设q 为所有的聚类结果，则是的最优化选择由下式给出：m k a x m a x f ( u ，) ， k = 2 ，3 ，n l 。分离系数指示了所有输入的样本相对于聚类中心的接近程度。如 果所有样本都属于同一类，且此时“较大，那么数据的不确定性较小。 ( 2 ) 划分熵公式：上“以= ，：，坳1 0 9 ( u , 3 n 。其中j j 为聚类结果的数目， 设q 为所有的聚类结果，则蠡的最优化由下式给出：m 鹫 唾n 日眠七) ， 七= 2 ，3 ，玎一1 。若所有的“口接近o 或1 ，贝熵就小，所得聚类结果就好；反之，若 “旃l 近于o 5 ，则聚类的模糊程度就高，熵就越大，聚类结果就差。 ( 3 ) 紧致与分离性函数：s ( u ，助= j ：。2 哪b q 1 2 睁b c f l 2 。设q 为 所有的聚类结果，则矗的优化方法由下式给出：m 肛蛳n s ( 以露) ) ，七= 2 ，3 ，n 一1 。 颞u 秘是数据到聚类中心距离的平均值与到聚类中心最小距离的比值。一个好的聚 类应当使各聚类中心的间距尽可能大，数据与其聚类中心的间距尽可能小。在上 述三个函数中，双以助的性能最好。 2 2数据类型与数据结构 2 2 i数据类型与相异度度量 聚类算法对于数据类型有很强的依赖性，不是每一种算法都适用于所有类型 的数据。一般而言，聚类计算中的数据类型有以下几种【3 】： 1 区间变量 区间变量是一个粗略线性标度的连续度量，如高度和重量。度量单位的选取 会直接影响聚类结果，一般而言，所用的度量单位越小，变量可能的值域就越大， 对聚类结果的影响也越大。为了避免聚类结果对度量单位的依赖，需要对数据进 行标准化处理，赋予所有的变量相等的权重，当然也可以根据需要赋予某些变量 较大的权重。区间变量的标准化方法如下： ( 1 ) 计算平均绝对偏差勘毋= ( 1 w 一嘶h 恐，一r e ：l + + l 劢一聊i ) 厶。其中 j t 夏窑适盔堂亟堂焦监塞丝基壅羞簋逵丛墓馥进 劫( i = 1 ，乏，”) 是变量厂的n 个度量值，即是厂的平均值，研= ( 柏，+ 琦+ + 晰) 加。 ( 2 ) 计算标准化