数据挖掘综述

数据挖掘中聚类算法的综述数据挖掘中聚类算法的综述 摘要 摘要 数据挖掘技术在当前研究领域中算是比较热门的一项技术 从国外发展到中国 具有广阔的商业应用前景 本文主要概述了当前数据挖掘的七大方法 分类 回归分析 聚类 关联规则 特征 变化和偏差分析 Web 页挖掘 和十大经典算法 C4 5 K Means SVM Apriori EM PageRank AdaBoost kNN Naive Bayes CART 以及数据 挖掘的发展趋势 关键词 关键词 数据挖掘 常用方法 经典算法 1 1 引言引言 在当今信息爆炸的时代 伴随着社会事件和自然活动的大量产生 数据的海量增长 人类正 面临着 被信息所淹没 但却饥渴于知识 的困境 随着计算机软硬件技术的快速发展 企业信息 化水平的不断提高和数据库技术的日臻完善 人类积累的数据量正以指数方式增长 面对海量的 杂乱无序的数据 人们迫切需要一种将传统的数据分析方法与处理海量数据的复杂算法有机结合的 技术 数据挖掘技术就是在这样的背景下产生的 它可以从大量的数据中去伪存真 提取有用的信 息 并将其转换成知识 数据挖掘是一个多学科领域 它融合了数据库技术 人工智能 机器学习 模式识别 模糊数 学和数理统计等最新技术的研究成果 可以用来支持商业智能应用和决策分析 例如顾客细分 交 叉销售 欺诈检测 顾客流失分析 商品销量预测等等 目前广泛应用于银行 金融 医疗 工业 零售和电信等行业 数据挖掘技术的发展对于各行各业来说 都具有重要的现实意义 2 2 数据挖掘的概念数据挖掘的概念 2 1 什么是数据挖掘 数据挖掘 Data Mining 也叫数据开采 数据采掘等 是按照既定的业务目标从海量数据中 提取出潜在 有效并能被人理解的模式的高级处理过程 在较浅的层次上 它利用现有数据库管理 系统的查询 检索及报表功能 与多维分析 统计分析方法相结合 进行联机分析处理 O 乙心 从而得出可供决策参考的统计分析数据 在深层次上 则从数据库中发现前所未有的 隐含的知 识 OLAF 的出现早于数据挖掘 它们都是从数据库中抽取有用信息的方法 就决策支持的需要而 言两者是相辅相成的 OLAP 可以看作一种广义的数据挖掘方法 它旨在简化和支持联机分析 而数据挖掘的目的是便 这一过程尽可能自动化 数据挖掘基于的数据库类型主要有 关系型数据库 面向对象数据库 事务数据库 演绎数 据库 时态数据库 多媒体数据库 主动数据库 空间数据库 遗留数据库 异质数据库 文本型 Internet 信息库以及新兴的数据仓库 而挖掘后获得的知识包括关联规则 特征规则 区分规则 分类规则 总结规则 偏差规则 聚类规则 模式分析及趋势分析等 2 2 数据挖掘的特点 数据挖掘技术具有以下特点 1 处理的数据规模十分庞大 达到 GB TB 数量级 甚至更大 2 查询一般是决策制定者 用户 提出的即时随机查询 往往不能形成精确的查询要求 需要 靠系统本身寻找其可能感兴趣的东西 3 在一些应用 如商业投资等 中 由于数据变化迅速 因此要求数据挖掘能快速做出相应反 应以随时提供决策支持 4 数据挖掘中 规则的发现基于统计规律 因此 所发现的规则不必适用于所有数据 而是 当达到某一临界值时 即认为有效 因此 利用数据挖掘技术可能会发现大量的规则 5 数据挖掘所发现的规则是动态的 它只反映了当前状态的数据库具有的规则 随着不断地 向数据库中加入新数据 需要随时对其进行更新 2 3 数据挖掘的应用基础 数据挖掘是一种获得知识的技术 它的基础是数据 手段是各种算法 目的是获得数据中蕴含 的知识 发现知识并非易事 人们总是受到各种各样的局限 目前数据缺乏仍然是发现知识的瓶颈 随着数据采集和存储技术的发展 对大量数据的分析和使用成为一个新的难题 对数据挖掘应用而 言 知识的发现存在两个极限 一个是数据极限 即数据要么非常庞大 要么数据量足够小 或者 数据量小但维度非常大 另一个是算法极限 即针对很多数据 不同的性质 不同的形式 和很多 需求 目前所有的算法尚不能很好地解决某些问题 因此 数据挖掘应用具有三个要素 数据 算 法 知识 数据挖掘应用是一个多层次 流程化的工程任务 开展数据挖掘应用也需要从每个层面加以 处理 才能保证整个数据挖掘的成功运行 数据挖掘 应用从上到下可分为三个大层面 具体结构 如下图 1 所示 图图 1 1 数据挖掘应用的三大层面数据挖掘应用的三大层面 应用层 把数据挖掘结果应用于实践 算法层 提供算法 引擎和界面 数据层 提供数据源 数据探索 数据准备 3 3 数据挖掘的常用方法数据挖掘的常用方法 数据挖掘从一个新的视角将数据库技术 统计学 机器学习 信息检索技术 数据可视化和 模式识别与人工智能等领域有机结合起来 它能组合各个领域的优点 从而能从数据中挖掘到其他 传统方法不能发现的有用知识 利用数据挖掘进行数据分析常用的方法主要有分类 回归分析 聚 类 关联规则 特征 变化和偏差分析 Web 页挖掘等 它们分别从不同的角度对数据进行挖掘 1 分类 分类就是应用已知的一些属性数据去推测一个未知的离散型属性数据 而这个被推测的属性数 据的可取值是预先定义的 要很好地实现这种推测 就需要事先在已知的一些属性和未知的离散型 属性之间建立一个有效的模型 即分类模型 它可以应用到客户的分类 客户的属性和特征分析 客户满意度分析 客户的购买趋势预测等 如一个汽车零售商将客户按照对汽车的喜好划分成不同的类 这样营销人员就可以将新型汽车的广 告手册直接邮寄到有这种喜好的客户手中 从而大大增加了商业机会 2 回归分析 回归分析方法反映的是事务数据库中属性值在时间上的特征 产生一个将数据项映射到一个实 值预测变量的函数 发现变量或属性间的依赖关系 其主要研究问题包括数据序列的趋势特征 数 据序列的预测以及数据间的相关关系等 它可以应用到市场营销的各个方面 如客户寻求 保持和预防客户流失活动 产品生命周期分 析 销售趋势预测及有针对性的促销活动等 3 聚类 聚类是将数据划分为簇的过程 根据数据本身的自然分布性质 数据变量之间存在的程度不 同的相似性 亲属关系 按一定的准则将最相似的数据聚集成簇 使得属于同一类别的数据间的 相似性尽可能大 不同类别中的数据间的相似性尽可能小 它可以应用到客户群体的分类 客户背景分析 客户购买趋势预测 市场的细分等 4 关联规则 关联规则是描述数据库中数据项之间所存在的关系的规则 即根据一个事务中某些项的出现可 导出另一些项在同一事务中也出现 即隐藏在数据间的关联或相互关系 在客户关系管理中 通过对企业的客户数据库里的大量数据进行挖掘 可以从大量的记录中发 现有趣的关联关系 找出影响市场营销效果的关键因素 为产品定位 定价与定制客户群 客户寻 求 细分与保持 市场营销与推销 营销风险评估和诈骗预测等决策支持提供参考依据 5 特征分析 特征分析是从数据库中的一组数据中提取出关于这些数据的特征式 这些特征式表达了该数 据集的总体特征 如营销人员通过对客户流失因素的特征提取 可以得到导致客户流失的一系列原 因和主要特征 利用这些特征可以有效地预防客户的流失 6 变化和偏差分析 偏差包括很大一类潜在有趣的知识 如分类中的反常实例 模式的例外 观察结果对期望的 偏差等 其目的是寻找观察结果与参照量之间有意义的差别 在企业危机管理及其预警中 管理者 更感兴趣的是那些意外规则 意外规则的挖掘可以应用到各种异常信息的发现 分析 识别 评价 和预警等方面 7 Web 页挖掘 随着 Internet 的迅速发展及 Web 的全球普及 使得 Web 上的信息量无比丰富 通过对 Web 的挖掘 可以利用 Web 的海量数据进行分析 收集政治 经济 政策 科技 金融 各种市场 竞 争对手 供求信息 客户等有关的信息 集中精力分析和处理那些对企业有重大或潜在重大影响的 外部环境信息和内部经营信息 并根据分析结果找出企业管理过程中出现的各种问题和可能引起危 机的先兆 对这些信息进行分析和处理 以便识别 分析 评价和管理危机 数据挖掘是一种决策支持过程 它通过高度自动化地分析企业的数据 做出归纳性的推理 从 中挖掘出潜在的模式 帮助决策者调整市场策略 减少风险 做出正确的决策 这对于一个企业的 发展十分重要 4 4 数据挖掘的算法数据挖掘的算法 1 C4 5 算法 C4 5 算法是机器学习算法中的一种分类决策树算法 其核心算法是 ID3 算法 C4 5 算法继承了 ID3 算法的优点 并在以下几方面对 ID3 算法进行了改进 1 用信息增益率来选择属性 克服了用信息增益选择属性时偏向选择取值多的属性的不足 2 在树构造过程中进行剪枝 3 能够完成对连续属性的离散化处理 4 能够对不完整数据进行处理 C4 5 算法有如下优点 产生的分类规则易于理解 准确率较高 其缺点是 在构造树的过程中 需要对数据集进行多次的顺序扫描和排序 因而导致算法的低效 2 K Means 算法 k means 算法是一个聚类算法 给定一个含有 N 个数据点的数据集 以及要生成的簇的数目 K 每一个分组就代表一个聚类 K N 而 N 得数量不能过少 否则聚类的效果就会大打折扣 一 般实践中 N 最好大于 K 10 K 个分组满足每一个分组至少包含一条数据记录 每一个数据记录属于 且仅属于一个分组 对于给定的 K 算法首先得任务就是将数据构建成 K 个划分 以后通过反复迭 代以改变分组的重定位技术 使得每一次改进之后的分组方案都较前一次的好 一个好的划分准则 是同一簇中数据点尽可能 相似 不同数据点中的数据尽可能 相异 3 支持向量机 支持向量机简称 SVM 它是一种监督式学习的方法 它广泛的应用于统计分类以及回归分析中 支持向量机将向量映射到一个更高维的空间里 在这个空间里建立有一个最大间隔超平面 在分开 数据的超平面的两边建有两个互相平行的超平面 分隔超平面使两个平行超平面的距离最大化 平 行超平面间的距离或差距越大 分类器的总误差越小 支持向量机可以很好地解决小样本 非线性 及高维数据识别分类问题 在实践应用中与其他算法比较时 总能表现出表现出更好的性能和效果 4 Apriori 算法 Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法 Apriori 算法基于先验原理 它反映了子集与超集之间的关系 即频繁项集的所有非空子集都必须是频繁的 非频繁项集的所有 超集都必须是非频繁的 如果项集 I 不满最小支持度阈值 s 则 I 不是频繁的 即 P I s 如果 A 添 加到 I 则结果项集 不可能比 I 更频繁出现 因此 I A 也不是频繁的 即 P AI AI s 因此 Apriori 算法的性质主要是用于搜索频繁项集的时候对候选式的筛选过程 利用 Apriori 性质 能够比较好的避免盲目的搜索 提高频繁项集的查找效率 5 最大期望 EM 算法 在统计计算中 最大期望 EM 算法是在概率模型中寻找参数最大似然估计的算法 其中概 率模型依赖于无法观测的隐藏变量 最大期望算法经过两个步骤交替进行计算 第一步是计算期望 E 利用对隐藏变量的现有估计值 计算其最大似然估计值 第二步是最大化 M 最大化 在 E 步上求得的最大似然值来计算参数的值 M 步上找到的参数估计值被用于下一个 E 步计算 中 这个过程不断交替进行 最大期望经常用在机器学习和计算机视觉的数据集聚领域 6 PageRank 算法 如果网页 T 存在一个指向网页 A 的连接 则表明 T 的所有者认为 A 比较重要 从而把 T 的一 部分重要性得分赋予 A 这个重要性得分值为 PR T C T 其中 PR T 为 T 的 PageRank 值 C T 为 T 的出链数 则 A 的 PageRank 值为一系列类似于 T 的页面重要性得分值的累加 算 法的优点是该算法是一个与查询无关的静态算法 所有网页的 PageRank 值通过离线计算获得 有 效减少在线查询时的计算量 极大降低了查询响应时间 算法的缺点是人们的查询具有主题特征 PageRank 忽略了主题相关性 导致结果的相关性和主题性降低 另外 PageRank 有很严重的对 新网页的歧视 7 AdaBoost 算法 AdaBoostt 是一种迭代算法 其核心思想是针对同一个训练集训练不同的分类器 弱分类器 然后把这些弱分类器集合起来 构成一个更强的最终分类器 强分类器 其算法本身是通过改变数 据分布来实现的 它根据每次训练集之中每个样本的分类是否正确 以及上次的总体分类的准确率 来确定每个样本的权 值 将修改过权值的新数据集送给下层分类器进行训练 最后将每次训练得 到的分类器最后融合起来 作为最后的决策分类器 8 KNN 算法 K 最近邻 KNN 分类算法 是一个理论上比较成熟的方法 也是最简单的机器学习算法之一 该方法的思路是 如果一个样本在特征空间中的 k 个最相似 即特征空间中最邻近 的样本中的大多 数属于某一个类别 则该样本也属于这个类别 9 朴素贝叶斯分类算法 朴素贝叶斯模型发源于古典数学理论 有着坚实的数学基础 以及稳定的分类效率 同时 其 模型所需估计的参数很少 对缺失数据不太敏感 算法也比较简单 理论上 该模型与其他分类方 法相比具有最小的误差率 但是实际上并非总是如此 这是因为该模型假设属性之间相互独立 这 个假设在实际应用中往往是不成立的 这给模型的正确分类带来了一定影响 朴素贝叶斯分类算法 思想是 对于给定的待分类项 求解在此项出现的条件下各个类别出想的概率 哪个概率最大就认 为此待分类项属于哪个类别 10 CART 算法 分类与回归树 CART 也属于一种决策树 在分类树下面有两个关键的思想 第一个是关于 递归地划分自变量空间的想法 第二个想法是用验证数据进行剪枝 分类回归树是一棵二叉树 且每个非叶子节点都有两个孩子 所以对于第一棵子树其叶子节点数比非叶子节点数多 1 CART 中用于选择变量的不纯性度量是 Gini 指数 如果目标变量是标称的 并且是具有两个以上的类别 则 CART 可能考虑将目标类别合并成两个超类别 双化 如果目标变量是连续的 则 CART 算法 找出一组基于树的回归方程来预测目标变量 5 5 数据挖掘发展趋势数据挖掘发展趋势 现今 数据挖掘的发展趋势主要在以下几个方面 数据挖掘语言的标准化 语言的标准化对于数据挖掘系统的开发和数据挖掘技术的普遍使用是 至关重要的 其可改进多个数据挖掘系统和功能间的互操作 促进其在企业和社会中的使用 数据挖掘的可视化 可视化要求已经成为数据挖掘系统中必不可少的技术 可以在发现知识的 过程中进行很好的人机交互 数据的可视化起到了推动人们主动进行知识发现的作用 分布式数据挖掘 分布式技术的到来为日益增长的数据提供了有力支持 而分布式数据挖掘中 将分布式技术和数据挖掘技术的结合 也使对分离数据库的可协作数据挖掘工作开发了一个重要领 域 数据挖掘与数据库系统和 Web 数据库系统的集成 数据库系统和 Web 数据库已经成为信息处 理系统的主流 数据挖掘系统的理想体系结构是与数据库和数据仓库系统的紧耦合 挖掘复杂数据类型的新方法 挖掘复杂数据类型是数据挖掘的重要前沿研究课题 也有人称复 杂类型的数据挖掘是 下一代数据挖掘 伴随着数据的增多 需要处理的数据类型也变得越来越 复杂 例如数据流 时间序列 时间空间 多媒体和文本数据 虽然现在在很多复杂数据类型的挖 掘方面取得了一些进展 但是在应用需求和可用技术之间仍然存在较大的距离 数据挖掘中的隐私保护和信息安全 随着信息技术的发展 越来越多的数据涌入了网络 其中 包括大量电子形式的个人信息 而挖掘技术的发展和科技的更新 在相反的一面上也使大量的个人 信息受到了威胁 因此保护隐私的数据挖掘方法愈显重要 参考文献 1 张银奎 廖丽 宋俊等译 数据挖掘原理 机械工业出版社 2003 2 杨杰 姚莉秀 数据挖掘技术及其应用 上海交通大学出版社 2011 3 闪四清 陈茵 程雁等译 数据挖掘 概念 模型 方法和算法 清华大学出版社 2003 4 洪松林 庄映辉 李堃 数据挖掘技术与工程实践 机械工业出版社 2014 5 吕纪荣 王士虎 数据中聚类算法研究综述 理论广角 2014 1 下 6 胡庆林 叶念渝 朱明富 数据挖掘中聚类算法的综述 计算机与数字工程 2007 第 2 期 7 应劭霖 数据挖掘中的聚类算综述 2014 6 8 方媛 车启凤 数据挖掘之聚类算法综述 河西学院学报 2012 第 5 期 9 蔡伟杰 张晓辉 朱建秋 朱扬勇