２Ｏ１Ｏ年８月 电 脑 学 习 第４期 数据挖掘算法综述 张君枫’ 摘 要：本文主要对数据挖掘的常用算法进行综合研究和比较。分析各个算法的利弊与适用情况 关键词：数据挖掘 中图分类号：ＴＰ３０１ 分类 预测 聚类 文献标识码： Ａ 文章编号：１００２—２４２２（２０１０）０４—０１２０—０３ Ｓｕｍｍａｒｙ ｏｆ Ｄａｔａ Ｍｉｎｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｚｈａｎｇ Ｊｕｎｆｅｎｇ Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｍａｋｅｓ ｔｈｅ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｓｔｕｄｙ ｏｆ ｃｏｎｌ￣ｏｎ ｄａｔａ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ，ａｎｄ ａｎａｌｙｚｅｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓ－ ａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍｓ ａ８ ｗｅｌｌ ａｓ ａｐｐｌｉｃａｂｌｅ ｓｉｔｕａｔｉｏｎｓ． Ｋｅｙｗｏｒｄ：Ｄａｔａ Ｍｉｎｉｎｇ Ｃｌａｓｓｉｉｆｃａｔｉｏｎ Ｐｒｅｄｉｃｔｉｏｎ Ｃｌｕｓｔｅｒｉｎｇ １数据挖掘的主要研究内容 数据挖掘的任务是发现隐藏在数据中的模式，可以发 现的模式分为两大类：描述型模式和预测型模式［２１。描述型 模式是对当前数据中存在的事实做规范描述，刻画当前数 据的一般特性：而预测型模式则是以时间为关键参数，对于 时间序列型数据，根据其历史和当前的值预测未来的值。 关联模式是反映一个事件和其他事件之间依赖或关联 联规则挖掘算法的核心，也是计算量最大的部分［３１。 关联规则中最典型的是购物篮分析，在关联规则的分 析中有助于发现交易数据库中不同商品之间的联系，找出 顾客购买的行为模式。 分类就是通过构造一个分类函数，把具有某些特征的 数据项划分到某个给定的类别上。分类由模型创建和模型 使用两步组成，模型创建是指通过对训练数据集的学习来 建立分类模型：模型使用是指使用分类模型对测试数据和 的知识，其目的是为了生成部分数据的概要，寻找数据子集 之间关联关系与数据之间的派生关系，即在同一事件中出 现的不同项之问的相关性。如果两项或多项属性之间存在 关联，那么就可以依据已知的属性值预测某一项的属性值。 新的数据进行分类。训练数据集中的数据带有类标号，通过 训练集的训练，使得使用分类函数可以把标号未知的数据 正确的分类到其相应的标号中１４１。 关联规则的挖掘可分为两步，首先是通过迭代识别所有的 频繁项目集，然后再从频繁项目集中构造可信度不低于用 户设定的最低值的规则。识别和挖掘所有频繁项目集是关 聚类就是将数据项分组成多个类或簇，类之间的数据 差别应尽可能大，类内的数据差别应尽可能小，即为“最小 化类间的相似性，最大化类内的相似性”原则。与分类模式 于场景的元数据的ＲＤＦ文件会自动转换，并通过ＲＤＦ编 辑器显示。这样，用户可以存储结果，将来还可以进一步编 辑，从用户的视野在ＲＤＦ文件里增加新的类和属性，从而 为现今Ｗｅｂ上可用的多媒体元数据做出贡献。 数据可组成全局网络信息的部分，任何人都有给任何资源 添加元数据的能力。 参考文献 ［１］吴波，王保保．几种基于内容的图像检索的方法【Ｊ】＿西安：计算 机技术与发展，２００６，１６（６）：１９１—１９５． ５结束语 语义Ｗｅｂ里不断增长的研究和应用意味着需要大容 量的元数据，还有合理的ＲＤＦ存储和查询结构。目前，在创 建大容量音乐元数据库已进行了一些研究，但由于Ｗｅｂ上 可用乐曲数量的不断增加，这些研究的范围是局限的。元数 据是在不断更新修改中发展的信息。描述的竞争应该是受 鼓励的，而在线团体用户的角色是决定性的。应用ＲＤＦ查 询体系结构，根据可用的在线资源设计出一种在线检索和 转换音乐元数据的应用程序。应用在基于上下文的元数据 方向上，以ＲＤＦ格式的结果提供给终端用户，从而强化语 义Ｗｅｂ标准和思想的使用。为了这个目的，需要理解基于 本体的框架。系统得益于ＲＤＦ特定上下文的元数据的简单 结构和灵活性，能够由用户自行添加元数据，任何ＲＤＦ元 收稿日期：２０１０－－０７—０６ ｝张君枫辽宁对外经贸学院信息技术系讲师（辽宁，大连１１６０５２）。 ・１２０・ 【２】张海玲．多媒体元数据的语义集成和检索【Ｊ】．北京：情报科学， ２ｏ０７，２５（７）：１０５２—１０９８． 【３】左琼，王元珍，曹忠升，等．基于ＭＰＥＧ一７的通用多媒体数据库 模型Ｇ３Ｍ［Ｊ］．武汉：华中科技大学学报（自然科学版），２００９， ３７（１）：６５—６８． ［４］Ｃｅｌｍａ，Ｏ．，ｅｔ ａ１．Ｔｏｏｌｓ ｆｏｒ ｃｏｎｔｅｎｔ—ｂａｓｅｄ ｒｅｔｉｒｅｖａｌ ａｎｄ ｔｒａｎｓ ｆｏｒｍａｔｉｏｎ ｏｆ ａｕｄｉｏ ｕｓｉｎｇ ＭＰＥＧ・・７：Ｔｈｅ ＳＰＯｆｆｌｉｎｅ ａｎｄ ｔｈｅ ＭＤ・。 Ｔｏｏｌｓ［Ｃ］．Ｐｒｏｃ．ｏｆ ２５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ ＡＥＳ Ｃｏｎｆｅｒｅｎｃｅ Ｌｏｎｄｏｎ， ＵＫ．，２００４． ［５］Ｄ．Ｏｂｅｒｌｅ，ｅｔ ａ１．Ｓｕｐｐｏｒｔｉｎｇ ａｐｐｌｉｃａｔｉｏｎ ｄｅｖｅｌｏｐｍｅｎｔ ｉｎ ｔｈｅ Ｓｅ— ｍａｎｔｉｃ Ｗｅｂ［Ｊ］．ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｒｎｅｔ Ｔｅｃｈｎｏｌｏｇｙ，２０一 Ｏ５。５（２）：３２８－３５８． 不同的是，聚类中要划分的类别是未知的，是一种不依赖于 着一组析取表达式规则。 预先定义的类和带类标号的训练数据集的非监督学习，无 决策树算法中最著名的是ＩＤ３和Ｃ４．５两个算法。ＩＤ３ 需背景知识，其中类的数量由系统按照某种性能指标自动 算法用信息论的知识作为基础，来计算具有最大信息增益 确定。聚类分析作为数据挖掘中的一个模块，既可以作为一 的属性字段，然后建立一个决策树结点，再根据该属性字段 个单独的工具以发现数据库中数据分布的一些深入的信 的不同取值来建立分支。该方法描述简单且分类速度快，但 息，概括出每一类的特点，又可以把注意力放在某一个特定 是只对较小的数据集有效，而且抗噪性差。Ｃ４．５算法在继承 的类上以作进一步的分析，还可以作为数据挖掘算法中其 ＩＤ３算法的优点的基础上对其进行了改进，用信息增益率 他分析算法的一个预处理步骤。 代替信息增益来选择属性，同时在树的构造过程中对树进 ２关联分析算法 行剪枝避免了过拟合问题，还能够处理属性值缺少的样本， 常用的经典频繁项集挖掘算法有下面几种阁。 提高了抗噪能力。Ｃ４．５算法产生的分类规则仍然易于理解， ２．１ Ａｐｆｉｏｆｉ算法 准确率较高，但是在构造树的过程中，对数据集进行多次的 在关联分析中经典算法是Ｒ．Ａｇｒａｗａｌ等人提出的Ａｐｆｉ— 顺序扫描和排序，导致算法的效率降低，而且Ｃ４．５仍然不 ｏｒｉ算法，这是一种很有影响力的挖掘关联规则频繁项集的 适合大训练集数据。 算法，探查逐级挖掘Ａｐｒｉｏｒｉ性质：频繁项集的所有非空子 ３．２人工神经网络 集都必须是频繁的。根据频繁ｋ一项集，形成频繁（ｋ＋１）一项 人工神经网络是多个神经元按一定规则连接构成的网 集候选，并扫描数据库１次，完成第ｋ次迭代（ｋ＞１），找出 络系统，通过模拟人类大脑的结构和功能完成对外部输入 完整的频繁（ｋ＋１）一项集 。。 信息的动态响应，并将获取的知识存储在网络单元之问的 Ａｐｆｉｏｒｉ算法是最早用于解决关联规则问题的算法，也 连接权系数中，使网络具有很强的容错性和鲁棒性。 是目前数据挖掘领域里应用最广泛的算法之一。该算法的 反向传播算法是人工神经网络中采用最多的训练方 优点是简单易懂并且能够有效地产生所有关联规则，在频 法。该算法通过对训练样本集的学习，将每次的处理结果与 繁项目不多时表现出了明显优势：但是，当最小支持度低 该样本已知类别进行比较，用所得的误差帮助完成学习，并 时，该算法会生成大量的候选频繁项集，可能会遇到组合爆 且对每个训练样本动态的修改权值从而让网络的输出值与 炸的问题，另外，在判定每个候选项集支持度的时候，Ａｐｒｉ— 实际的类别的均方差最小。 ｏ 算法需要反复多次的遍历事务数据库，导致系统的输入 神经网络的优点就是并行分布处理能力强，分类的准 输出代价过高。 确度高，对噪声数据有较强的鲁棒性和容错能力，具备联想 ２．２ Ａｐｒｉｏｒｉ—Ｔｉｄ算法 记忆的功能等。但是该方法获取的模式隐含在网络结构中， 为了提高Ａｐｒｉｏｒｉ算法的有效性，目前已经提出了许多 导致分类结果较难理解，网络的训练时间较长，不适于大数 Ａｐｒｉｏｒｉ变形，旨在提高原算法的效率，ＡＤｆｉｏｆｉ—Ｔｉｄ算法就 据量的学习。 是一种Ａｐｆｉｏｒｉ变形算法。 ３．３贝叶斯分类 Ａｐｒｉｏｒｉ－Ｔｉｄ算法仅在第１次扫描时用事务数据库Ｄ计 贝叶斯分类以统计学中的贝叶斯定理为理论基础，通 算候选频繁项集的支持度，其它各次扫描用其上一次扫描 过贝叶斯定理得到的后验概率来预测类成员关系的可能 生成的候选事务数据库Ｄ 来计算候选频繁项集的支持度。 性，是一种具有最小错误率的概率分类方法。在计算过程 该做法可以减少对数据库的扫描次数，在一定情况下能迅 中，如果假设所有变量都是条件的，则可以使用朴素贝 速削减候选频繁项集。虽然Ａｐｆｉｏｆｉ－Ｔｉｄ算法进行了改进，但 叶斯分类方法，但所有变量都是条件的情况非常少。贝 是仍然无法克服Ａｐｒｉｏｒｉ算法的固有缺陷，仍然存在下面的 叶斯网络可以综合先验信息和样本信息，减少了定义全联 问题：可能产生大量的候选集；可能需要重复扫描数据库， 合概率分布的概率数目，又避免了朴素贝叶斯分类器要求 通过模式匹配检查一个很大的候选集；无法对稀有信息进 所有变量都是条件的不足，成为近年的主要研究方向。 行分析。 ４结束语 ３分类算法 数据挖掘是当今计算机学领域研究的一个主要热门课 常用的分类算法有下面的几种旧。 题，在各个领域都有广泛的应用，数据挖掘的算法对数据挖 ３．１决策树方法 掘技术的实现起到关键的作用，也直接影响到能否把数据 决策树是一种以实例为基础的归纳学习算法，在其树 挖掘应用到具体的实践中。本文综合研究了数据挖掘的各 型结构中，每个结点表示对一个属性值的测试，其分支表示 种算法的优劣，为算法的改进和创新提供了基础。 测试的结果，而树的叶结点表示类别，从决策树的根结点到 参考文献 叶结点的一条路径对应着一条合取规则，整个决策树对应 【ｌ】王光宏，蒋平．数据挖掘综述［Ｊ］．上海．同济大学学报，２００４，３２ ・ １２１ ・ ２Ｏ１０年８月 电 脑 学 习 第４期 从锐捷ＲＧ—ＳＡＭ认证系统的应用认识８０２．１ｘ技术 高俊 摘 要：本文从实际出发．结合学生的应用。参与学生认证上网的全部过程和用户使用过程中遇到的问题进行讲解。这样更能 加深用户的理解。 关键词：８０２．１ｘ 认证 锐捷 Ｒｅｃｏｇｎｉｔｉｏｎ ｏｆ ８０２．１ｘ Ｔｅｃｈｎｏｌｏｇｙ Ｂａｓｅｄ ｏｎ 中图分类号：ＴＰ２９ 文献标识码： Ａ 文章编号：１００２—２４２２（２０１０）０４—０１２２—０２ ｔｈｅ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｒｕｉｊｉｅ ＲＧ—ＳＡＭ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｓｙｓｔｅｍ Ｇａｏ Ｊｕｎ Ａｂｓｔｒａｃｔ：Ｓｔａｒｔｉｎｇ ｆｒｏｍ ｔｈｅ ｐｒａｃｔｉｃｅ ａｎｄ ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｔｈｅ ｓｔｕｄｅｎｔｓｔｈｅ ｐａｐｅｒ ｓｈｏｗｓ ｔｈｅ ｗｈｏｌｅ ｐｒｏｃｅａｓ ｏｆ ，ｔａｋｉｎｇ ｐａｒｔ ｉｎ ｓｔｕｄｅｎｔｓ ｃｅｒｔｉｉｆｃａｔｉｏｎ Ｉｎｔｅｍｅｔ，ａｎｄ ｓｏｌｖｅｓ ｔｈｅ ｐｒｏｂｌｅｍｓ ｅｎｃｏｕｎｔｅｒｅｄ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ａｔ ｔｈｅ ｓａｌｎｅ ｔｉｍｅ， ｗｈｉｃｈ ｃｏｎｔｒｉｂｕｔｅｓ ｔｏ Ｕ￥ＣｌＸ３ ｄｅｅｐ ｃｏｎｍｐｒｅｈｅｎｓｉｏｎ． Ｋｅｙｗｏｒｄ：８０２１ｘ ．Ａｕｔｈｅｎｔｉｃａｔｉ０ｎ Ｒｕｉｊｉｅ １锐捷ＲＧ—ＳＡＭ认证系统的应用 锐捷ＲＧ—ＳＡＭ认证系统的应用，并不是该系统的部署 情况，而是从最终用户（学生）角度所接触的认证系统的直 观感受出发。学生所认识的锐捷ＲＧ—ＳＡＭ认证系统可化分 为以下几个部分： （１）用户开户。用户要开通网络要带身份证、学生证、 饭卡和所对应墙上端口的标签号，到网络中心填写开户申 请表，申请开通网络。 （２）配置网络地址。在互联网中，每一台接入网络的计 序，客户端程序有操作系统自带，也有像锐捷ＲＧ—ＳＡＭ客 户端一样开发商定制的。然后输入之前申请时授予的用户 名、密码，发起连接请求。认证客户端发出认证请求报文给 交换机，开始启动一次认证过程。 第二步，交换机接收到认证客户端发出的认证请求数 据帧后，将发送一个请求帧给客户端，要求客户端把用户名 发过来。 第三步，认证客户端响应交换机发出的请求，将用户名 通过数据帧发送给交换机。交换机将该数据帧经过封包处 理后发送给ＲＡＤＩＵＳ认证服务器进行处理。 算机或终端设备都需要有一个唯一的Ｉ】）地址。在开户后， 用户会得到一张回执，有管理员分配给用户计算机的一个 第四步，ＲＡＤＩＵＳ认证服务器收到交换机转发过来的用 户名信息数据包后，经过解包，将该信息与数据库中的用户 名相比对，然后找到该用户名相对应的口令信息，用随机生 成的一个加密字对口令进行加密处理，同时把这个加密字 口地址等网络地址。把其配置到电脑的网卡属性中。 （３）安装锐捷认证软件。用户在自己计算机中安装管 理员提供的锐捷客户端的软件。需根据不同的操作系统类 型分别安装和设置。 发送给交换机，由交换机传送给客户端。 第五步，客户端收到由交换机传过来的加密字后，用该 （４）使用锐捷客户端认证上网。客户端安装设置完毕 后，双击锐捷图标，打开客户端对话框，输入用户名、密码，点 “连接”，客户端自动完成认证后，用户就可无上网了。 加密字对用户所输入的密码进行加密处理，然后将加密过 的口令信息再上传给交换机发给ＲＡＤＩＵＳ认证服务器． 第六步，ＲＡＤＩＵＳ认证服务器将收到的客户端加密后的 再加上一些对锐捷客户端出现问题的处理，这就是用 户所认识的基于８０２．１ｘ技术的锐捷ＲＧ—ＳＡＭ认证系统。 口令信息和自己经过加密后的口令信息相比较，如果相同， 说明用户名、密码一致，该用户为合法用户，反馈认证通过 消息，并向交换机发出打开端口的指令，允许用户的业务流 ｖ－ 、 ～ ～ ａ‘ Ｙ ２ ８０２．１ｘ的工作过程 第一步，当用户需要上网时打开８０２．１ｘ认证客户端程 …一ｖ－ｖ－… ……ｖ－ ……ｖ－ …ｖ Ｗｖ－ｖ．ｖ—Ｗｖ－ ｖ－ （２）：２４６—２５２． Ｏ１． 【２】Ｆａｙｙａｄ Ｕ．Ｋｎｏｗｌｄｇｅ Ｄｉｅｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ ｔｏｗａｒｄｓ ａ Ｕ－ ｊｎｊ ｎｇ Ｆｒａｍｅｗｏｒｋ．ＫＤＤ ６ Ｐｒｏｃ．２ｎｄ Ｉｎｆ１．Ｃｏｎｆ．ｏｎ Ｋｎｏｗｌｅｄ－ ｇｅ Ｄｉｃｏｖｅｒｓｙ＆Ｄａｔａ Ｍｉｎｉｎｇ，１９９６． 【５】Ｒ．Ａｇｒａｗａｌ，Ｔ．Ｉｍｉｅｌｉｎｓｋｉ，Ａ．Ｎ．Ｓｗａｍｙ．Ｍｉｎｉｎｇ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ ｂｅｔｗｅｅｎ ｓｅｔｓ ０ｆ ｉｔｅｍｓ ｉｎ ｌａｒｇｅ ｄａｔａｂａｓｅｓ［Ａ】．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ １９９３ ＡＣＭ ＳＩＧＭＯＤ ｌｎｔｅｍａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｎａｇｅｍ－ ｅｎｔ ｏｆ Ｄａｔａ，Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．ＵＳＡ，１９９３：２０７—２１６． 【３】邹志文，朱金伟．数据挖掘算法研究与综述［Ｊ］．北京．计算机工 程与设计，２００５，２６（９）：２３０４—２３０７． ［６】胡可云．数据挖掘理论与应用［Ｍ】．北京：清华大学出版社，２ｏ－ ０８． ［４】韩家炜．数据挖掘：概念与技术【Ｍ】．北京：机械工业出版社，２Ｏ一 收稿日期：２０１０－０６－０１ ・高俊南京财经大学现代教育中心网络中心助理工程师（江苏，南京２１００２９）。 ・１２２・
