英语原文共 18 页，剩余内容已隐藏，支付完成后下载完整资料
数据挖掘：从数据库角度的概述
摘要：在数据库系统和机器学习领域，从大型数据库挖掘知识和信息已经被很多研究者认为是一个关键的研究课题，同时也被很多业界公司看做一个主要经济收入机会的重要领域。在很多不同领域的研究人员对数据挖掘都有十分浓厚的兴趣。一些提供信息服务的新兴应用，比如数据库存和网上在线服务，为了更好的理解用户行为、改善所提供的服务和增加商业机会，同样需要各种各样的数据挖掘技术。为了响应这样的需求，这篇论文从数据库研究人员的角度提供最近数据挖掘技术发展的概况。文中提供了可用的数据挖掘技术的分类，并展示了这些技术的对比研究。
索引词：数据挖掘，知识发现，关联规则，分类，数据聚类，模式匹配算法，数据泛化与特征化，多维数据集，多维度数据库
1 引言
最近，我们生成数据和采集数据的能力都已经飞速的提高了。大多数商品使用的条形码、许多商业和政府事务的计算机化与数据收集工具的发展已经为我们提供了大量的数据。数以百万计的数据库已经在商业管理、政府行政、科学与工程数据管理和许多其他应用中被使用到。值得注意的是，由于功能强大、价格实惠的数据库系统的可用性，这些数据库的数量仍然保持着飞速的增长。这种在数据和数据库方面的爆炸性增长已经对智能化和自动化将需要被处理的数据转化为有用的知识信息的新技术工具产生了急切的需求。因此，数据挖掘成为了一个日益重要的研究领域。
数据挖掘也就指的是在数据库中发现知识，是一个在数据库的数据中对固有的以前未知但潜在有用的信息(比如知识规则、限制和规律)进行非平凡提取的过程。有些论文和文档中还出现了许多其他具有类似或稍有不同含义的术语，比如从数据库中的知识挖掘、知识抽取、数据考古、数据捕捞、数据分析等等。通过数据库中的知识发现，可以从数据库中的相关数据集提取并从不同角度研究有趣的知识、规律或高级信息，因此大型数据库可以作为可靠的知识生成和验证来源。从大型数据库中挖掘信息和知识已经被许多研究者认为在数据库系统和机器学习方面是一个关键的研究课题，同时也被很多业界公司视为一个主要经济收入机会的重要领域。被发现的知识可以应用于信息管理、查询处理、决策制定、过程控制以及其他许多应用。许多不同领域的研究人员，包括数据库系统、知识库系统、人工智能、机器学习、知识获取、统计学、空间数据库和数据可视化领域，都表现了对数据挖掘的浓厚兴趣。此外，一些提供信息服务的新兴应用，比如在线服务和万维网，为了更好的理解用户行为、改善所提供的服务和增加商业机会，同样需要各种各样的数据挖掘技术。
为了响应这样的需求，这篇论文提供了数据挖掘技术在一些研究社区发展的概况，强调了面向数据库的技术和已经在应用数据挖掘系统中实现的技术。文中也提供了可用的数据挖掘技术分类，分类基于所挖掘的数据库种类、所发现的知识种类和所采用的技术种类。这个概况依照一个分类方案进行组织，即被挖掘的知识种类。
1.1 数据挖掘的需求和挑战
为了进行有效的数据挖掘，首先需要调查一个应用的知识发现系统期望拥有何种特征和在数据挖掘技术开发过程中可能会面临的挑战。
1）处理不同类型的数据
因为在不同的应用中有许多种使用的数据和数据库，人们可能期望一个知识发现系统应该能够在不同种数据上进行有效的数据挖掘。因为多数可获得的数据库是关系型的，一个数据挖掘系统在关系型数据上进行高效且有效的知识发现是十分关键的。此外，许多可应用的数据库包含复杂的数据类型，比如结构化数据和复杂数据对象，超文本和多媒体数据，空间和时间数据，事务数据，遗留数据等等。一个强大的系统应该也能够在这样复杂的数据类型上执行有效的数据挖掘。然而，数据类型的多样性和数据挖掘目标的不同使得期望一个数据挖掘系统处理所有类型的数据不现实。具体的数据挖掘系统应该为挖掘具体类型数的知识而构建，比如有专门用于挖掘关系数据库、事务数据库、空间数据库、多媒体数据库等的系统。
2）数据挖掘算法的效率和可扩展性
为了从数据库的大量数据中有效地提取信息，知识发现算法必须对大型数据库高效且可扩展。也就是说，用于大型数据库的数据挖掘算法的运行时间必须可以预测且可以接受。指数级甚至中阶多项式级复杂度的算法在实践中并不可取。
3）数据挖掘结果的有用性、确定性和表达性
发现的知识应该准确地描述数据库的内容并对某些应用有用，其不完美性应该以近似规则或定量规则的形式用不确定性度量表达。噪音与异常数据应该在数据挖掘系统中被合理处理，这也激发了测量发现知识质量的系统学习，包括通过构建统计、分析、模拟模型和工具的趣味性和可靠性。
4）多种数据挖掘要求和结果的表示
从大量的数据中可以发现不同种类的知识，同样，人们有时也喜欢从不同角度检查发现的知识并以不同形式展示它们。这要求我们将数据挖掘需求和发现的知识都表示为高级语言或图形化用户界面，这样数据挖掘任务才能被非专家制定，发现的知识才能被用户理解并直接使用。这也要求知识发现系统采用表达性知识表示技术。
5）多个抽象层次的交互式挖掘知识
由于从一个数据库中预测可以发现什么十分困难，高级的数据挖掘询问应该被视为一项探究，这可能透露一些用于深入探索的有趣迹象。应该提倡交互式数据挖掘，这可以使用户交互式地改善数据挖掘需求，动态地调整数据的关注点，逐步深化数据挖掘过程，从多个抽象层次和不同角度弹性地观察数据和数据挖掘结果。
6）从不同数据源挖掘信息
广泛可用的计算机局域网和广域网，包括因特网，连接了许多数据源并形成了巨大的分布式异构数据库。从不同的含有多样化语义的格式化或非格式化数据源挖掘知识为数据挖掘带来了新的挑战。另一方面，数据挖掘可能会帮助揭示异构数据库中一些难以通过简单查询系统发现的高级数据规律。此外，海量的数据库、广泛分布的数据和一些数据挖掘方法的计算复杂性激励了并行与分布式数据挖掘算法的发展。
7）隐私保护和数据安全
当数据可以从许多不同角度和不同抽象层次查看时，会威胁到保护数据安全和防止侵犯隐私的目标。当知识发现可能会导致侵犯隐私时，研究开发用于保护泄露敏感信息的安全措施十分重要。
注意到这些需求中的一些可能会存在冲突，比如，保护数据安全的目标可能会与从不同角度交互式挖掘多层级知识的要求冲突。此外，这篇概述只涉及上述需求中的一部分，主要强调数据挖掘算法的效率和可扩展性。例如，不同类型数据的处理局限于关系数据和事务数据，保护隐私和数据安全的方法则没有涉及（有关的讨论可以在其他文献中找到，比如参考文献[22],[63]）。尽管如此，我们觉得展现数据挖掘需求的总体情况依然十分重要。
2 数据挖掘技术综述
因为数据挖掘提出了许多具有挑战性的研究问题，方法的直接应用和与机器学习、统计学、数据库系统领域相关研究中开发的技术不能解决这些问题，为了创造新的数据挖掘方法或为高效可用的数据挖掘开发集成技术进行专门的研究十分有必要。在此意义上，数据挖掘本身已经成为了一个独立的新领域。
2.1 数据挖掘技术分类
数据挖掘的研究与发展已经有了很多进展，许多数据挖掘技术和系统已经被开发出来了。不同的分类体系可用于数据挖掘方法和系统的归类，如下所示，其分类体系基于研究的数据库种类、发现的知识种类和利用的技术种类。
- 处理的数据库类型
一个数据挖掘系统可以依据处理的数据库类型进行分类。比如，如果一个系统在关系数据库中发现知识，那么它就是关系数据挖掘器；如果一个系统在面向对象数据库中发现知识，那么它就是面向对象数据挖掘器。一般而言，一个数据挖掘器可以依照从以下不同种类的数据库中挖掘知识来分类：关系数据库、事务数据库、面向对象数据库、演绎数据库、空间数据库、时间数据库、多媒体数据库、异构数据库、活动数据库、遗留数据库和互联网信息库。
- 挖掘的知识类型
数据挖掘器可以发现几种典型的知识，包括关联规则、特征规则、分类规则、判别规则、聚类、演变和偏差分析，在下一小节将会详细讨论它们。此外，数据挖掘器也可以根据发现知识的抽象级别进行分类，可以分为广义知识、初级知识和多层次知识。一个灵活的数据挖掘系统可以发现多个抽象级别的知识。
- 使用的技术类型
数据挖掘器也可以根据底层的数据挖掘技术来分类。比如，根据驱动方法可以将数据挖掘器分为自主知识挖掘器、数据驱动挖掘器、询问驱动挖掘器和交互式数据挖掘器；也可以根据底层的数据挖掘方法将数据挖掘器分为基于泛化挖掘、基于模式挖掘、基于统计或数学理论挖掘和集成方法等。
在许多不同的分类体系中，这篇概述主要遵照了一个分类体系：挖掘的知识类型，因为这种分类对不同数据挖掘需求和技术进行清楚的描述。挖掘不同种类知识的方法，包括关联规则、特征、分类、聚类等会进行深入讨论。对于挖掘特定种类知识，不同方法之间会进比较，比如机器学习方法、统计学方法和面向大型数据库方法，着重强调数据库问题，比如效率和可扩展性。
2.2 从数据库中挖掘不同类型的知识
数据挖掘是一个应用程序相关问题，不同的应用程序可能要求使用不同的数据挖掘技术。一般而言，在数据库中可以发现的知识种类可以进行如下分类。
在事务或关系数据库中挖掘关联规则最近在数据库社区引起了大量关注，它的任务是从数据库的相关数据集中导出一个强关联规则，其形式为，其中和表示属性值集。比如，从大量的事务数据中可以发现这样的一个关联规则，一个顾客如果买了牛奶，那么在同一单交易中也会买面包。由于挖掘关联规则可能需要重复扫描巨大的事务数据库以找到不同的关联模式，运算的总量会十分庞大，性能的提升就成为了一个基本问题。挖掘关联规则的高效算法和进一步提高性能的一些方法将会在第3节讨论。
与数据库系统关联的使用最广泛的数据挖掘和数据分析工具是数据归纳总结工具，它有几个别称，比如在线分析处理(OLAP)、多维数据库、多维数据集、数据抽象、归纳、总结、表征等。数据归纳总结展示了数据库中以一组用户指定数据的一般特征或概括的高层观点，比如，一个公司里技术员工的一般特征可以描述为一组特征规则或一组通用汇总表。此外，从多种抽象层次展示数据的广义视图通常是可取的。多级数据归纳、总结与表征的概述将在第4节展示。
数据挖掘另一个重要应用是在巨量的数据中做分类，这被称为挖掘分类规则。数据分类指的是将一组数据基于某些属性的值进行分类，例如，汽车经销商把顾客依照他们对汽车的偏好进行分类是可取的，这样销售人员将会知道该接近谁，并且新型号目录可以被直接寄给那些具有指定特征的用户，从而使商业机会最大化。一些关于分类规则的研究将在第5节回顾。
第6节中，我们会讨论数据聚类的技术。总的说来，数据聚类就是把一组数据(没有预定一定类属性)分组，其基于概念聚类原理：最大化同类间的相似度并最小化不同类间的相似度。例如，一组商品对象可以首先聚集到一组类中，然后根据此分类派生出一组规则。这种聚类可能有助于分类法的形成，这意味着观察结果组织成一个将类似事件分组在一起的类的层次结构。
时间或时空数据占据了电脑数据存储的很大比例。这类数据库的例子包括：用于股价指数的金融数据库、医药数据库和多媒体数据库等。在许多数据挖掘操作中，为了发现并预测与特定模式相关的风险、因果关系和趋势，从时间或时空数据库中搜索相似模式十分必要。此类型数据库的典型查询包括识别具有相似增长模式的公司、具有相似销售模式的产品、具有相似价格变动的股票、具有相似气候模式的图片、地质特征、环境污染或天体物理模式。这些查询总是需要相似性匹配，而不是精准匹配。第7节会回顾基于模式的相似性搜索方法。
在分布式信息提供环境中，文档或对象通常链接在一起以便于交互访问。在这种环境下理解用户访问模式不仅会改善系统设计，还能引导做出市场决策。在这种环境下捕获用户访问模式指的是挖掘路径遍历模式。但是，请注意，由于用户是沿着提供服务的信息来搜索所需信息的，一些对象是因为它的位置而不是它的内容被访问的，这表现了遍历模式问题和其他主要基于用户事务的问题之间的差别。第8节将会讨论挖掘路径遍历模式的性能。
除了上述问题外，数据挖掘中当然还有很多其他值得研究的方面。使用数据挖掘查询语言或图形化用户界面来指定感兴趣的数据子集、相关属性集和想发现的规则类型，这经常是必须的。此外运行交互式数据挖掘经常也是必须的，用来检查、转换和操作数据挖掘中间结果，关注不同的概念层次，或检测不同种类的阈值。数据和知识的视觉呈现可能对数据库中的交互式知识挖掘很有帮助。
3 挖掘关联规则
考虑一个销售交易或数据库，发现项目之间的重要性关联是可取的，这样交易中某些商品的存在将意味着同一交易中其他商品的存在。在[4]中提出了一种数学模型用来解决挖掘关联规则的问题。令，是一组字面量，叫做项目。令D为一组事务，其中每个事务T是一组项目，于是有。注意这里不考虑事务中所购买的项目的数量，也就是说每个项目用一个二进制变量表示是否购买了该项目。每个事务与一个标识符关联，叫做TID。令X为一组项目，当且仅当X时称事务T包含X。一个关系规则的含义为形式，其中。规则保存在事务集D中，并带有置信度c，表示D中c%的事务包含X并且也包含Y。如果事务集D中有s%的事务包含，那么规则在事务集D中拥有支持度s。
置信度表示含义的强度，支持度表示规则中出现模式的频率。通常只需要注意那些有相当大支持度的规则，在[4],[68]中拥有高置信度和强支持度的规则被称为强规则。挖掘关联规则的任务基本是在大型数据库中发现强关联规则。在[4],[7],[66]中，挖掘关联规则的问题被分解为以下两步：
1）发现大的项目集，即拥有事务支持度超过预定义最小支持度s的项目集的集合
2）使用大的项目集为数据库产生关联规则。
值得注意的是挖掘关联规则的整体性能由第一步决定。在大型项目集确定以后，对应的关联规则可以直接推导出来。因此，大项目集的有效计数是大多数前期工作的重点。这里介绍一下分别在[7]和[66]中开发的算法Apriori和
全文共9843字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[795]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
