模糊聚类分析应用

本科生毕业论文（设计）（2011届）论文（设计）题目模糊聚类分析应用作者舒海波系、专业理学分院数学与应用数学班级应数072指导教师（职称）何颖俞（讲师）字数9403字成果完成时间2011年4月10日杭州师范大学钱江学院教学部制2模糊聚类分析应用数学与应用数学专业0702班指导教师何颖俞摘要：模糊聚类简单而言就是把数据中的指标分类。本文利用的是最大树法对等价矩阵进行聚类，然后利用fcm法对相似矩阵的求法进行比较。关键字：模糊聚类，等价矩阵，最大树，相似矩阵TheapplicationoffuzzyclusteringShuhaiboInstructor:HeYingYuAbstract:Fuzzyclusteringisamethodtoclassifythegivendatabasedonsomeindexes.InthispaperIusethemethodofthemaximaltreetoclassifytheequivalentmatrix,andthenuseclusteringanalysismethodofFCMtocomparisonthesolutionsofthesimilarmatrices.Keyword:fuzzyclustering,equivalencematrix,themaximaltree,similarmatrix1目录1绪论...................................................................12模糊聚类分析方法........................................................12.1距离和相似系数....................................................12.2F相似关系.......................................................22.2.1定义.........................................................22.2.2定理........................................................22.3聚类分析..........................................................32.3.1最大树法.....................................................43算法分类................................................................43.1聚类方法的分类....................................................53.1.1划分方法（partitioningmethod）..............................53.1.2层次方法(hierarchicalmethod)................................53.1.3基于密度的方法(density-basedmethod).........................53.1.4基于网格的方法(grid-basedmethod)............................53.1.5基于模型的方法(model-basedmethod)...........................53.2．数据挖掘领域中常用的聚类算法.....................................53.2.1CLARANS算法（随机搜索聚类算法）.............................53.2.2CURE算法（利用代表点聚类）..................................63.2.3BIRCH算法（利用层次方法的平衡迭代归约和聚类）...............63.2.4DBSCAN算法（基于高密度连接区域的密度聚类方法）..............63.2.5STING算法（统计信息风格）...................................73.2.6COBWEB算法（流行的简单增量概念聚类算法）....................73.2.6模糊聚类算法FCM.............................................83.3聚类算法的性能比较...............................................84实际应用................................................................95总结...................................................................13参考文献：..............................................................132致谢....................................................................15附录....................................................................161模糊聚类分析应用数学与应用数学专业072班舒海波指导教师何颖俞1绪论聚类分析又称群分析，它是研究（样品或指标）分类问题的一种多元统计方法，所谓类，通俗地说，就是指相似元素的集合。严格的数学定义是较麻烦的，在不同问题中类的定义是不同的。聚类分析起源于分类学，在考古的分类学中，人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展，人类的认识不断加深，分类越来越细，要求也越来越高，有时光凭经验和专业知识是不能进行确切分类的，往往需要定性和定量分析结合起来去分类，于是数学工具逐渐被引进分类学中，形成了数值分类学。后来随着多元分析的引进，聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。在社会经济领域中存在着大量分类问题，比如对我国30个省市自治区独立核算工业企业经济效益进行分析，一般不是逐个省市自治区去分析，而较好地做法是选取能反映企业经济效益的代表性指标，如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等，根据这些指标对30个省市自治区进行分类，然后根据分类结果对企业经济效益进行综合评价，就易于得出科学的分析。又比如若对某些大城市的物价指数进行考察，而物价指数很多，有农用生产物价指数、服务项目价指数、食品消费物价指数、建材零售价格指数等等。由于要考察的物价指数很多，通常先对这些物价指数进行分类。总之，需要分类的问题很多，因此聚类分析这个有用的数学工具越来越受到人们的重视，它在许多领域中都得到了广泛的应用。值得提出的是将聚类分析和其它方法联合起来使用，如判别分析、主成分分析、回归分析等往往效果更好。聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。本文主要介绍模糊聚类法。2模糊聚类分析方法2.1距离和相似系数为了将样品（或指标）进行分类，就需要研究样品之间关系。目前用得最多的方法有两个：一种方法是用相似系数，性质越接近的样品，它们的相似系数的绝对值越接近1，而彼此无关的样品，它们的相似系数的绝对值越接近于零。比较相似的样品归为一类，不怎么相似的样品归为不同的类。另一种方法是将一个样品看作P维空间的一个点，并在空间定义距离，距离越近的点归为一类，距离较远的点归为不同的类。但相似系数和距离有各种各样的定义，而这些定义与变量的类型关系极大，因此先介绍变量的类型。由于实际问题中，遇到的指标有的是定量的（如长度、重量等），有的是定性的（如性别、职业等），因此将变量（指标）的类型按以下三种尺度划分：间隔尺度：变量是用连续的量来表示的，如长度、重量、压力、速度等等。在间隔尺度中，如果存在绝对零点，又称比例尺度，本书并不严格区分比例尺度和间隔尺度。有序尺度：变量度量时没有明确的数量表示，而是划分一些等级，等级之间有次序关系，如某产品分上、中、下三等，此三等有次序关系，但没有数量表示。名义尺度：变量度量时、既没有数量表示，也没有次序关系，如某物体有红、黄、白三种颜色，2又如医学化验中的阴性与阳性，市场供求中的“产”和“销”等。不同类型的变量，在定义距离和相似系数时，其方法有很大差异，使用时必须注意。研究比较多的是间隔尺度，因此本章主要给出间隔尺度的距离和相似系数的定义。设有n个样品，每个样品测得p项指标（变量），原始资料阵为pxxxnpnnppnxxxxxxxxxXXXX2122221112112121其中(1,,;1,,)ijxinjp为第i个样品的第j个指标的观测数据。第i个样品iX为矩阵X的第i行所描述，所以任何两个样品XK与XL之间的相似性，可以通过矩阵X中的第K行与第L行的相似程度来刻划；任何两个变量Kx与Lx之间的相似性，可以通过第K列与第L列的相似程度来刻划。2.2F相似关系2.2.1定义设)(UUFR，如果具有自反和对称关系，则称R为U上的一个F相似关系（F表示模糊）当论域U为有限时，F相似关系可以用F矩阵表示。具有F相似关系的矩阵，称为F相似矩阵。在实际应用时，通常只能得到自反矩阵和对称举证，即相似矩阵。现在的问题是对具有相似关系的元素怎样进行分类，也就是如何将相似矩阵改造为等价矩阵。2.2.2定理若TRR，则称R为对称矩阵。（1）若RI（I是单位矩阵），则称R为自反矩阵。（2）若2RR,则称R为传递的F关系。（3）若满足上面三点则称为等价矩阵。定理1：相似矩阵nnRu的传递闭包是等价矩阵，且nRR。证只需要证明R是自反的、对称的。因R是自反的，故RI，2RR。不难得到nR不减，因此1nknkRRRI，即R是自反的。因为TRR，()()nTTnnRRR，故R是对称的。有定理1可见，要想将相似矩阵改变为等价矩阵，只需求相似矩阵的传递闭包。定理2：设nnRu是自反矩阵，则任意自然数mn，都有3mRR证由R自反性推得2......nRRR当mn时，有1nmkkRRRRR2.3聚类分析所谓聚类分析，就是用数学的方法对事物进行分类，它有广泛的实际应用。在模糊数学产生之前，聚类分析已是数理统计多元分析的一个分支，然而现实的分类问题往往伴有模糊性。例如，环境污染分类、春天连阴雨预报、临床症状资料分类、岩石分类，等等。对这些伴有模糊性的聚类问题，用模糊数学语言来表达更为自然。模糊聚类分析的步骤：第一步建立模糊相似关系。设12{,,,}nUuuu为待分类的全体。其中每一待分类对象由一组数据表征如下：12(,,...,)miiiiuxxx现在的问题是如何建立iu和ju之间的相似关系。这有许多方法（这里选一些，列在下面），我们可以按照实际情况，选其中一种来求iu与ju的相似关系(,)ijijRuur。数量积法111.kkmijijkijrxxijM当当其中M为一适当选择之正数，满足,1max(.)kkmijijkMxx相似系数法12211||||().()kkkkmiijjkijmmiijjkkxxxxrxxxx其中11111,kkmiijjkkxxxxmm最大最小法411min(,)max(,)kkkkmijkijmijkxxrxx算术平均最小法11mi