聚类算法dbscan和fcm算法实现.doc

西 南 交 通 大 学本科毕业设计（论文）I-MINER环境下聚类分析算法研究与实现 年 级: 2004 学 号: 20041892 姓 名: 徐 德 专 业: 计算机科学与技术 指导老师: 杨 燕 二零零八年六月 西南交通大学本科毕业设计(论文) 第61页 院 系 信息科学与技术学院 专 业 计算机科学与技术 年 级 2004级 姓 名 徐德 题 目 I-Miner环境下聚类分析算法研究与实现 指导教师评 语 指导教师 (签章)评 阅 人评 语 评 阅 人 (签章)成 绩 答辩委员会主任 (签章)年 月 日毕业设计任务书班 级 计算机3班 学生姓名 徐德 学 号 20041892 专业 计算机科学与技术 发题日期： 2008 年 1 月 10 日 完成日期： 2008 年 6 月 12 日题 目 I-Miner环境下聚类分析算法研究与实现 题目类型：工程设计 *技术专题研究 理论研究 软硬件产品开发一、 设计任务及要求1学习数据挖掘原理，了解当前聚类分析算法的研究现状。 2熟练掌握数据挖掘工具I-Miner的使用。 3分析各种聚类算法的特点，用I-Miner中S语言实现2-3种聚类算法，扩展I-Miner功能。4在I-Miner环境下用大量实例（包括Web文档）进行聚类算法性能对比。 二、 应完成的硬件或软件实验 用S语言实现2-3种聚类算法，对实例进行处理，观察聚类结果，对比各种算法优劣。 三、应交出的设计文件及实物（包括设计论文、程序清单或磁盘、实验装置或产品等）1. 毕业设计论文 2. 源程序清单 3. 已扩展功能的I-Miner 四、 指导教师提供的设计资料1.Jiawei han,Micheline Kamber,数据挖掘概念与技术（第2版），机械工业出版社，2007 2.邵峰晶，于忠清，数据挖掘原理与算法，中国水利水电出版社，2003，8 3.S+Miner入门手册，北京宏能畅然数据应用有限公司编译，2007，4 五、 要求学生搜集的技术资料（指出搜集资料的技术领域） 查找与聚类分析算法相关的文章10篇（中英文各5篇） 六、 设计进度安排第一部分 学习数据挖掘原理和聚类算法 （ 2 周）第二部分 学习掌握数据挖掘工具I-Miner的使用 （ 1 周）第三部分 用S语言实现2-3种聚类算法 （ 7 周）第四部分 用实例（包括Web文档）进行聚类算法性能对比 （ 5 周）第五部分 撰写论文 （ 2 周）评阅及答辩 （ 1 周） 指导教师： 年 月 日学院审查意见：审 批 人： 年 月 日 西南交通大学信息科学与技术学院 2008年摘 要由于计算机和数据采集技术的进步，数据挖掘获得了非常广泛的应用。数据挖掘帮助用户发现隐藏在大型数据库种的规律和模式，它融合了人工智能、统计、机器学习、模式识别和数据库等多种学科的理论、方法与技术。数据挖掘模型包括决策树、关联规则、聚类、神经网络、粗糙集、概念格、遗传算法、序列模式、贝叶斯、支持向量机、模糊集和基于案例的推理。其中，聚类是数据挖掘领域的核心技术，被广泛应用于相似搜索、顾客划分、趋势分析、金融投资和信息检索等领域。I-Miner是一个企业级的数据挖掘工具。在I-Miner的环境下可以方便的建立数据挖掘模型，并且能够嵌入其它数据挖掘模型。对于一个数据挖掘的非专业用户，都能够用I-Miner实现知识的发现。聚类分析是一种非监督型知识发现的方法，能有效的处理大量的、繁杂的、属性众多的且没有类标志的数据。聚类的目标是在没有任何经验知识的前提下，将数据聚集成不同的簇，使得相同簇中的元素尽可能相似，不同簇中的元素差别尽可能大。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。DBSCAN算法能实现任意形状的数据集的聚类，模糊C均值适合于那些在簇中心周围呈均匀分布的数据集，CABOSFV算法对于高维稀疏数据集（如WEB数据）能很好地聚类。本文在I-Miner中嵌入DBSCAN、CABOSFV和模糊C均值三种聚类分析算法，能够极大地满足用户的需要，建立数据挖掘模型，支持生产决策。关键词： 数据挖掘；聚类分析；DBSCAN算法；模糊C均值；CABOSFV算法AbstractAs the development of computer and data gathering technology, the data mining is widely used. Data mining which fused the theories, method and technology of many kinds of disciplines such as artificial intelligence, statistics, machine learning, pattern recognition and database help user find the rules and pattern which plant in the large-scale database.Data mining model includes decision tree, connection rule, clustering, neural network, rough collection, concept standard, genetic algorithm, sequence pattern, Bayes, support vector machines, fuzzy set and inference based on case. Clustering is the core technology in data mining domain, and is widely used in the similar search, the customer category, trend analysis, financial investment and information retrieval. I-Miner is an enterprise data mining tool, which might link up with the software which you are using. Building the data mining model based on the I-Miner is simple and inserting other data mining model. Regarding as a non-data mining specialized user, one can use I-Miner to realize the knowledge discovery. The clustering analysis is a non-inspector general knowledge discovery method, which can effectively process massive, numerous and diverse, the attribute numerous, and unlabeled data. The goal of clustering is to gather into the different clusters under no experience knowledge premise, which makes the element in the same cluster be as similar as possible, the element in different clusters be as far difference possible. Through clustering, one can distinguish the crowded and the sparse region, and discovers the overall situation distributed pattern, as well as the interesting relations between the data attributes. DBSCAN algorithm can achieve cluster of any shape of dataset, Fuzzy c-means is suitable for dataset which is uniform distribution around the cluster centers , CABoSFV algorithm can be a good clustering for high-dimensional dataset(such as WEB data). Embedding DBSCAN、FCM and CABoSFV three clustering analysis algorithm into I-Miner, can enormously satisfy the users need, establish the data mining model, and support the production decision-making.key words: Data Mining; Clustering analysis; DBSCAN(Density-Based Spatial Clustering of Applications with Noise); FCM(Fuzzy C-Means ); CABoSFV(Clustering Algorithm Based On Sparse Feature Vector)目 录摘 要IVAbstractV第1章 绪论11.1 引言11.2 数据挖掘研究现状与发展趋势11.2.1 数据挖掘研究现状11.2.2 数据挖掘发展趋势21.3 本文的主要内容和组织21.3.1 本文的主要内容21.3.2 本文的组织2第2章 数据挖掘简介42.1 数据挖掘42.1.1 数据挖掘的概念42.1.2 数据挖掘的分类42.1.3 数据挖掘的方法62.1.4 数据挖掘的任务72.1.5 数据挖掘的应用现状82.2 聚类分析82.2.1 聚类分析概述82.2.2 常用聚类分析算法9第3章 数据挖掘软件I-Miner123.1 I-Miner概述123.2 基于I-Miner的数据挖掘133.3 I-Miner的扩展功能及S语言简介16第4章 基于I-Miner聚类分析算法的实现184.1 DBSCAN算法的实现184.1.1 算法简介184.1.2 算法的实现194.1.3 算法的运行结果214.2 FCM算法的实现224.2.1 算法简介224.2.2 算法的实现234.3.3 算法的运行结果254.3 CABOSFV算法的实现264.3.1 算法简介264.3.2 算法的实现294.3.3 算法的运行结果29第5章 功能测试与分析315.1 基于二维数据的测试315.1.1 测试数据集简介315.1.2 性能对比315.2 基于三维数据集的测试335.2.1 测试数据集简介335.2.2 性能对比335.3 基于真实数据集的测试355.3.1 测试数据集简介355.3.2 性能对比355.4 基于WEB数据集的测试365.4.1 测试数据集简介365.4.2 性能对比36结 论38致 谢39参考文献40附 录41第1章 绪论1.1 引言面对日益庞大的数据资源，人们迫切需要强有力的工具来“挖掘”其中的有用信息，数据挖掘就是针对这一需求而发展起来的一门汇集统计学、机器学习、数据库、人工智能等学科内容的新兴的交叉学科。数据挖掘正在各行各业的决策活动中扮演着越来越重要的角色。目前，在很多重要的领域，数据挖掘都可以发挥积极促进的作用，尤其是在银行、电信、保险、交通、零售等商业应用领域。数据挖掘能够帮助解决很多典型的商业问题，包括：数据库营销、客户群体划分、背景分析、交叉销售等市场分析行为，以及客户流失性分析、客户信用评分、欺诈发现等。1.2 数据挖掘研究现状与发展趋势近年来，数据挖掘引起了信息产业界的极大关注。国内外各研究机构纷纷开展了对数据挖掘技术的研究和探索工作。总体上来说，数据挖掘领域已趋于成熟，出现了许多新的和改进的算法；该领域已经拓宽，融入了更多的数据类型：流、序列、图、时间序列、地理空间、音频、图像和视频。数据挖掘的黄金时代不仅尚未结束，实际上，数据挖掘的研究和商业兴趣正在继续增长。数据挖掘领域需要更多的新力军的加入。1.2.1 数据挖掘研究现状数据挖掘从一开始产生就和应用紧密相关，而深入地研究和开发使得这项技术得以实现。1993年，国际电气电子工程师学会（IEEE）的知识和数据工程会刊就出版了知识发现（KDD）的技术专刊。随着数据挖掘的逐步深入人心，第一本专门研究数据挖掘和知识发现的国际学术杂志Data Mining and Knowledge Discovery于1997年3月创刊，充分体现了数据挖掘的重要性，网络上的电子刊物和讨论区更多。不仅在数据库领域，很多和计算技术、信息系统、决策支持和人工智能相关的学术期刊和国际会议都把数据挖掘和知识发现列为重要的专题和专刊进行讨论，如并行计算、计算机网络、运筹与优化、信息系统与信息工程等领域的学术会议及期刊。不同领域的研究者都对数据挖掘显示了极大的兴趣，在因特网上已有不少关于数据挖掘的主页，许多公司也把它作为提高利润的重要途径。IBM、INFORMIX和Oracle等以数据库为重要产品的大规模信息技术公司都在数据挖掘领域投入巨资进行研究，开发了不少产品。而SPSS、SAS等以统计为主要技术核心的软件公司也推出了自己的数据挖掘产品。数据挖掘的方法得到优化，数据挖掘的软件也越来越多，数据挖掘已经深入到人们生活和工作的方方面面。目前，该领域已经成为数据库、信息管理系统、人工智能及决策支持等相关领域的研究课题。1.2.2 数据挖掘发展趋势 当前，数据挖掘和知识发现的研究方兴未艾，其研究与开发的总体水平相当于数据库技术在70年代所处的地位，迫切需要类似于关系模式、DBMS系统和SQL查询语言等理论和方法的指导。而且最近有国内大型网站评比未来十大热门技术，数据挖掘占有一席之地。鉴于数据、数据挖掘任务和数据挖掘方法的多样性，研究的焦点可能会集中在以下几个方面：1) 数据挖掘语言的设计；2) 研究解决大型应用问题的数据挖掘技术；3) 开发有效的数据挖掘方法和系统；4) 构造交互的和集成的数据挖掘环境；5) 数据挖掘与软件工程；6) Web挖掘，隐私保护和信息安全等；7) 可视数据挖掘；8) 基于群体智能的数据挖掘方法；9) 与数据库系统、数据仓库系统和Web数据库系统的集成；10) 生物数据、实时数据挖掘。1.3 本文的主要内容和组织1.3.1 本文的主要内容本文的目标就是在数据挖掘的背景下，在I-Miner环境下实现聚类分析算法，且比较各种聚类算法的优劣。主要内容有： 1 在I-Miner中嵌入三种聚类分析算法。用S语言实现DBSCAN、FCM和CABOSFV三种聚类分析算法，嵌入到I-Miner中，建立数据挖掘模型。 2 对比三种挖掘模型。通过三种挖掘模型，对实例进行挖掘，对比分析，得到三种聚类算法的优劣。1.3.2 本文的组织 全文分五章。第1章是绪论，概括地描述了数据挖掘的应用领域，简单地介绍了数据挖掘的研究现状及其未来的发展趋势。第2章是数据挖掘简介，讨论了数据挖掘的概念、分类、方法、任务以及聚类分析的概念、常用算法，分析了数据挖掘技术应用现状及各种聚类分析算法的性能问题。 第3章介绍了数据挖掘软件I-Miner（Insightful Miner）以及编程语言S语言。分析了在I-Miner环境下建立数据挖掘模型，进行数据的挖掘。第4章主要分析了基于I-Miner环境下嵌入用户编写的三种聚类算法，建立聚类分析的挖掘模型，并用不同的数据集进行了测试。第5章主要分析了DBSCAN、FCM和CABOSFV三种聚类分析算法的特点，对比讨论了三种聚类算法的性能。第2章 数据挖掘简介2.1 数据挖掘2.1.1数据挖掘的概念数据挖掘是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则。简单地说，数据挖掘是指从大量数据中提取或“挖掘”知识。数据挖掘可以看作是信息技术自然演化的结果。由于存在可以广泛使用的大量数据，并且迫切需要将这些数据转换成有用的信息和知识，数据挖掘引起了信息产业界和整个社会的极大关注。获取的信息和知识可以广泛用于各种应用，包括市场分析、欺诈检测、顾客保有、产品控制和科学探索等。数据挖掘作为KDD的核心，可以用图2-1来表示。图2-1 KDD的过程2.1.2 数据挖掘的分类从不同的角度出发，可以对数据挖掘进行不同的分类：1. 按挖掘的数据库类型分类(1) 面向对象数据挖掘。面向对象数据库的数据挖掘可用于发现基于对象层次的知识。事实上，面向对象数据库的类层次结构对描述知识发现的背景知识提供了自然的支持，其继承和封装机制也能支持数据挖掘的模块化、可重用性和多态性。(2) 事务数据库的数据挖掘。事务数据库由一个文件组成，其中每一个记录代表一个事务或交易，具有唯一的标识。事务数据库的数据挖掘经常应用在货篮数据分析中，可以回答这样的问题：“商场里哪些商品适合摆放在一起进行销售？”。(3) 多媒体数据库的挖掘。多媒体数据库存储的不仅仅是文字和数据，还包括图像、音频和视频等信息。例如，将数据挖掘技术应用于语音信号处理可以解决部分现阶段较难解决的语音技术难题。(4) 空间数据库的数据挖掘。空间数据挖掘是指从空间数据库中提取用户感兴趣的空间模式与特征、空间与非空间数据的普遍关系及其他一些隐含在数据库中的普遍的空间数据特征。它包括空间分布规律、空间关联规则、空间分类规则、空间特征规则、空间区分规则和空间演变规则。(5) 因特网上的数据挖掘。因特网上的数据挖掘有时也可称之为Web挖掘，挖掘的目的可以是筛选因特网上的新闻、屏蔽垃圾电子邮件、发现用户的浏览偏好及加快网络速度等。(6) 演绎数据库的数据挖掘。演绎数据库中的数据挖掘包括在演绎规则所定义的数据上发现知识和在已开采的知识上进一步发现新的知识，逐步求精。(7) 时间/时间序列数据库的数据挖掘。序列模式挖掘可以发现数据库中形如“某段时间内，顾客购买商品A，接着购买商品B，而后购买商品C，即序列ABC出现的频度较高”之类的知识。(8) 数据仓库的数据挖掘。数据挖掘技术已经成为数据仓库应用中极为重要和相对独立的工具。数据挖掘和数据仓库是融合与互动发展的。2. 按发现的知识类型分类(1) 关联对则挖掘。关联规则是数据挖掘中最先研究的对象之一，挖掘的目的是发现不同类型的关联关系。(2) 特征规则挖掘。特征规则挖掘在商业中有着广泛的应用。例如，将客户分成不同的类后，再进一步分析各类客户的特征。(3) 分类规则挖掘。分类是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。(4) 时序规则挖掘。时序规则指的是和时间有关的规则，有时也可以称为序列模式。(5) 偏差规则挖掘。偏差包括分类中的反常实例、例外模式、观测结对期望值的偏离及量值随时间的变化等。3. 按采用的技术类型分类它包括查询驱动挖掘、发现驱动的交互式数据挖掘、数据挖掘驱动、基于归纳的挖掘和集成挖掘。4. 按挖掘的深度分类在较浅的层次上，利用现有数据库管理系统的查询/检索和报表功能与多维分析及统计分析方法相结合，进行联机分析处理，从而得出可供决策参考的统计分析数据；在深层次上，从数据库中发现前所未知的、隐含的知识。5. 按挖掘的应用领域根据数据挖掘的应用行业，数据挖掘分为电信行业的数据挖掘、金融业的数据挖掘、保险业的数据挖掘、商业的数据挖掘、制造业的数据挖掘、体育界的数据挖掘、天文学领域的数据挖掘等1。2.1.3 数据挖掘的方法数据的挖掘离不开方法的支持，一个好的数据挖掘更需要一种准确的数据挖掘方法。一般地，数据挖掘的方法包括：l 统计分析方法：统计分析方法是利用统计学、概率论的原理对关系中各属性进行统计分析，从而找出它们之间的关系和规律。l 遗传算法：遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，具有计算简单、优化效果好的特点，它在处理组合优化问题方面也有一定的优势，可用于聚类分析等。l 粗糙集方法：粗糙集理论是波兰Pawlak Z教授在 1982年提出的一种智能决策分析工具，它是一种刻划不完整性和不确定性的数学工具，它能有效地分析不精确、不一致、不完整等各种不完备的信息。粗糙集方法被广泛应用干不精确、不确定、不完全的信息的分类和知识获取。l 决策树方法：决策树方法就是利用训练集生成一个测试函数，根据不同取值建立树的分支；在每个分支子集中重复建立下层结点和分支。这样便生成一棵决策树，然后对决策树进行剪枝处理，最后把决策树转化为规则，决策树方法主要用于分类挖掘。l 神经网络方法：它模拟人脑神经元结构，以MP模型和Hebb规则为基础，建立了三大类多种神经网络模型。 1. 前馈式网络 它以感知机、反向传播模型、函数网络为代表，可用于预测、模式识别等方面。 2. 反馈式网络 它以Hopfield的离散模型和连续模型为代表,分别用于联想和优化计算。 3自组织网络 它以ART模型、Koholon模型为代表，用于聚类。l 模糊逻辑：模糊数学研究的是“亦此亦彼”的模糊性。模糊数学是继经典数学、统计数学之后，在数学上的又一新的发展。在数据挖掘领域，模糊逻辑可以进行模糊综合判别、模糊聚类分析等。l 聚类分析：聚类分析是根据事物的特征对其进行聚类或分类，即所谓物以类聚。以期从中发现规律和典型模式。通过聚类以后，数据集就转化为类集，同一类的数据具有相似的变量值，不同类的数据的变量值不具有相似性。这类技术是数据挖掘的最重要技术之一。除传统的基于多元统计分析的聚类方法外，近年来模糊聚类和神经网络聚类方法也有了长足的发展。l 最近邻技术：通过k个与之最相近的历史记录的组合来辨别新记录。这种技术可用作聚类、偏差分析等数据挖掘任务。l 可视化技术：这是一类辅助方法。它采用比较直观的图形图表方式将挖掘出来的模式表现出来。数据可视化大大扩展了数据的表达能力从而易于为人们所理解。这在数据挖掘中非常重要，可视化技术正受到日益广泛的重视。 2.1.4 数据挖掘的任务根据数据分析工作者的不同目标，可以将数据挖掘任务划分为以下几类：l 探索性数据分析：正像名字所暗示的，这种方法的宗旨就是对数据进行探索，在探索时对要找什么并不需要明确的想法。对于低维数据，可以用一些技术直接以图形的方式显示出来，而对于高维的数据，可以采用数据低维投影进行探索。l 描述建模：描述模型的目标是面熟数据的所有特征。例如为数据的总体概率分布建模（密度估计）；把P维空间划分成组（聚类分析和区隔）；以及描述变量间的关系。描述建模已经被应用到很多领域。如市场营销、疾病分类和气候观测等。l 预测建模：预测建模的目标是建立一个模型，这个模型允许我们根据已知的变量值来预测其他某个变量值。在分类中，被预测的变量是范畴型的，而在回归中被预测的变量是数量型的。在统计和机器学习中人们已近开发出了大量的方法来解决预测建模问题，而且这已领域的工作已经取得了重大理论进展。l 寻找模式和规则：数据挖掘不久致力于建立模型，而且应用于模式探测。如欺诈探测，寻找明显不同于其他点的数据点，并查出这些数据点所属的不同类型，然后通过探测这些包含特殊类型点的区域来查出欺诈行为。数据挖掘工作者已经采用基于关联对则的算法技术来解决这方面的问题。l 根据内容检索：这种情况下，用户有一种感兴趣的模式并且希望在数据集中找到相似的模式。这种任务对于文本和图像数据集合应用最普遍。对于文本，模式可能是一系列关键字，用户希望在啪嗒的可能相关的文档集合中（例如网页）寻找相关的文档。对于图像，用户希望从庞大的图像集合中发现类似的图像。例如IBM开发的QBIC（根据图像内容查询）的系统3。2.1.5 数据挖掘的应用现状数据挖掘从理论研究到产品开发只用了短短数年，目前在国内外已经进入应用阶段。数据挖掘技术的应用十分广泛，从政府决策、商业经营、科学研究到工业决策支持等各个领域都可以找到数据挖掘技术的用武之地。基于客户数据库的市场营销、风险投资和欺诈检测以及在体育领域，数据挖掘都起到了至观重要的作用。一般地，在那些存在着海量数据的领域，数据挖掘技术都可以一显身手。数据挖掘已经被广泛应用于股票、制造业、司法、交通、科学研究、政府管理、计算机硬件和软件、教育、军事、医药和生物、传媒以及因特网等行业或领域。随着信息技术的发展，数据挖掘的应用会越来越深入和细化。2.2 聚类分析2.2.1 聚类分析概述聚类是将数据对象分成类或簇的过程，使同一簇中的对象之间具有很高的相似度，而不同簇中的对象高度相异。聚类源于许多研究领域，包括数据挖掘、统计学、生物学和机器学习。通过自动聚类能够识别对象空间中稠密和稀疏区域，从而发现全局分布模式和数据属性之间有趣的相关。聚类分析已经广泛地应用于许多领域，包括市场研究、模式识别、数据分析和图像处理。聚类还可以用于离群点检测，如信用卡欺诈检测和监控电子商务中的犯罪活动。聚类分析是一种寻求数据的自然聚集结构的重要方法，是概念描述和偏差分析的先决条件。聚类是一种处理大量的、繁杂的、属性众多的且没有类标志数据的有效方法；在知识发现的过程中，聚类经常被作为其他数据挖掘任务的前奏。分析成为数据挖掘和知识发现领域中的最重要的课题之一，迄今为止，人们已经提出了许多数据聚类的算法，解决各种领域的聚类问题，如传统的聚类方法，空间数据的聚类方法和统计学中的聚类算法等。对象间的相似性是聚类的核心，而对相似性进行度量是用以区别对象的主要基础，相似性的度量方法主要有两类，即距离和相似系数。距离通常用于数值型数据，距离越接近0，相似性越大；相似系数通常用于分类型数据，相似系数越接近1，相似性越大。聚类分析通常是基于距离的，通过构造一个 m 维空间的距离函数，利用这个距离函数来进行聚类。令为维空间中一组对象，、，是和之间的距离。距离的定义通常应满足以下四条性质：1)2) ，03) ，=4) ，在聚类分析中，一般只要求距离函数满足前三条性质。常用的距离公式如下： 1) 闵科夫斯基(Minkowski)距离，是距离的最通常的形式，如式2-1： （2-1） 2) 曼哈顿（Manhattan）距离，即各属性之差的绝对值的和，如式2-2： （2-2） 3) 欧式（Euclidean）距离，即各属性之差的平方和的平方根，如式2-3： （2-3） 4) 切比雪夫（Chebyshev）距离，即各属性之差的最大值，如式2-4： （2-4）2.2.2 常用聚类分析算法大体上,主要的聚类算法可以划分为如下几类:1. 划分聚类算法划分聚类也叫分割聚类， 给定一个 n个数据对象或元组的数据库，一个划分方法构建数据的 k 个划分，每个划分表示一个聚簇， 并且k n。即它将数据划分为 k 个组， 同时满足如下的要求：(1)每个组至少包含一个对象；(2) 每个对象必须属于且只属于一个组。目前两个比较流行的启发式划分方法是k均值算法和k中心点算法。2. 层次聚类算法层次聚类算法是对数据库分成多个层次，然后对不同层次的数据采用划分聚类，输出的是一棵层次化的分类树。层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，首先将每个对象作为一个簇，然后合并相近的原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。分裂的方法，也称为自顶向下的方法，首先将所有对象置于一个簇中，逐渐细分为越来越小的簇，直到每个对象自成一个簇，或者达到了某个终结条件。3. 基于密度的聚类算法基于密度的聚类算法的思想是：只要临近区域的密度 （对象或数据点的数目） 超过某个阀值， 就把它加到与之相近的聚类中。也就是说， 对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。一般在一个数据空间中， 高密度的对象区域被低密度 （稀疏） 的对象区域 （通常认为是噪声数据） 所分割。因此，这样的方法可以用来过滤 “噪声” 孤立点数据， 发现任意形状的聚类结果。其代表算法有：DBSCAN 算法、OPTICS算法。4. 基于网格的聚类算法基于网格的方法是采用一个多分辨率的网格数据结构。把数据空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。这种方法的主要优点是它的处理速度很快， 其处理时间独立于数据对象的数目， 只与量化空间中分成多少个单元有关。代表算法有：STING算法（统计信息网络）、CLIQUE 算法（聚类高纬空间）、WAVE-CLUSTER 算法（采用小波变换聚类） 。5. 基于模型的聚类算法基于模型的方法为每一个聚类假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。也可能基于标准的统计数字决定聚类数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。该方法试图优化给定的数据和某些数学模型之间的适应性。这样的方法常基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方法主要有两类： 统计学方法和神经网络方法。6. 模糊聚类方法模糊聚类中，每个样本不再仅属于某一类，而是以一定的隶属度属于每一类，也即通过模糊聚类分析，得到了的样本属于各个类别的不确定性程度，即建立起了样本对于类别的不确定性的描述， 这样更能准确地反映现实世界。模糊聚类不需要训练样本，可直接通过机器学习达到自动分类的目的。模糊聚类不但可以从原始数据中直接提取特征，还能对已经得到的特征进行优选和降维操作，以免造成“维数灾难” 。常用模糊聚类算法有：模糊 C-均值FCM(Fuzzy C-Means) 算法。该算法是在传统 C均值算法中应用了模糊技术。基于上述的分析，下面对上述常用聚类算法的性能从可伸缩性、 发现聚类的形状、 对 “噪声” 的敏感性、 对数据输入顺序的敏感性、高维性和算法效率六个方面进行比较，如表2-1所示。表2-1 聚类算法性能对比类别算法可伸缩性发现聚类的形状对“噪声”敏感新对数据输入顺序敏感性高维性数据类型算法效率基于划分K-means好任意形状敏感不太敏感一般数值一般基于层次CURE较差任意形状不敏感不太敏感好数值较高BIRCH较差凸形或球状一般不太敏感好数值较高基于网格WAVE-CLUSTER好任意不敏感不敏感好数值一般CLIQUE较好凸形或球形不敏感不敏感好数值较低STING好任意形状不敏感不敏感好数值高基于密度DBSCAN较好任意形状不敏感敏感一般数值一般基于模型COBWEB较好任意形状一般敏感好分类较低模糊聚类FCM好任意形状敏感不敏感好数值较高第3章 数据挖掘软件I-Miner3.1 I-Miner概述I-Miner(Insightful Miner的简称)是一个全面的具有完整分析流程、企业级的数据挖掘工具。它将S-PLUS弹性的统计分析功能和世界一流的互动式数据挖掘技术整合在一起，直观、流程清晰地对模型进行评估和预测，研究人员可以非常方便、快速地对数据进行挖掘。I-Miner界面包含一系列用于进行数据挖掘的节点面板，外加一个用来设计一个可视化挖掘网络的工作簿。当用户载入一个新的工作簿开始数据挖掘时，界面如图3-1所示。图3-1 I-Miner图形用户界面通过从左边的探索器框中拖拽组件到右边桌面框的工作薄来创建挖掘网络节点。在节点间建立连接并设置节点的属性。 在桌面框下面是信息框，显示节点运行时的状态。I-Miner 的警告和错误提示在这个框中显示。当用户运行网络时，I-Miner 通过I-Miner管道架构传递数据、进行节点计算；它是一个节点接着一个节点来处理数据。为了加快处理进程， I-Miner可以通过临时文件对每个节点以二进制形式建立缓存。在默认情况下，数据一次通过管道10000行，但是也可以用全局的或单个节点调整这个数据值。用户可以对很多数据源进行导入及导出，包括如： l Excel和Lotus等电子表格； l Access类的数据库；l SAS 和SPSS 类的统计软件； l Oracle/DB2/SQLServer等流行的关系型数据库