教学课件-数据挖掘原理、算法及应用(李爱国)

第1章绪论

1.1数据挖掘的概念和定义1.2数据挖掘的历史及发展1.3数据挖掘的研究内容及功能1.4数据挖掘的常用技术及工具1.5数据挖掘的应用热点1.1数据挖掘的概念和定义

数据挖掘（DateMining）是近年来随着人工智能和数据库技术的发展而出现的一门新兴技术。它是从大量的数据中筛选出有效的、可信的以及隐含信息的高级处理过程。数据挖掘包含丰富的内涵，是一个多学科交叉的研究领域。仅从从事研究和开发的人员来说，其涉及范围之广是其他领域所难以企及的，既有大学里的专门研究人员，也有商业公司的专家和技术人员。研究背景的不同会使他们从不同的角度来看待数据挖掘的概念。因此，理解数据挖掘的概念不是简单地下个定义就能解决的问题。

1.1.1从商业角度看数据挖掘技术

数据挖掘是一种新的商业信息处理技术。数据挖掘技术把人们对数据的应用从低层次的联机查询操作提高到决策支持、分析预测等更高级的应用上。通过对特定数据进行微观、中观乃至宏观的统计、分析、综合和推理，发现数据间的关联性、未来趋势以及一般性的概括知识等，这些知识性的信息可以用来指导高级商务活动，如顾客分析、定向营销、工作流管理、商店分布和欺诈监测等。原始数据只是未被开采的矿山，需要挖掘和提炼才能获得对商业目的有用的规律性知识。这正是数据挖掘这个名字的由来。因此，从商业角度看，数据挖掘就是按企业的业务目标，对大量的企业数据进行深层次分析，以揭示隐藏的、未知的规律并将其模型化，从而支持商业决策活动的技术。从商业应用角度刻画数据挖掘，可以使人们更全面地了解数据挖掘的真正含义。1.1.2数据挖掘的技术含义谈到数据挖掘，必须提到另外一个名词：数据库中的知识发现(KnowledgeDiscoveryinDatabases,KDD)，即将未加工的数据转换为有用信息的整个过程。KDD这个术语首次出现在1989年8月在美国底特律召开的第十一届国际人工智能联合会议的专题讨论会上。随后，在近十年的发展过程中，KDD专题讨论会逐渐发展壮大。1999年在美国圣地亚哥举行的第五届KDD国际学术大会，参加人数近千人，投稿280多篇。近年来的国际会议涉及的范围更广，如数据挖掘与知识发现(DataMiningandKnowledgeDiscovery,DMKD)的基础理论、新的发现算法、数据挖掘与数据仓库及OLAP的结合、可视化技术、知识表示方法、Web中的数据挖掘等。此外，IEEE、ACM、IFIS、VLDB、SIGMOD等其他学会、学刊也纷纷把DMKD列为会议议题或出版专刊，成为当前国际上的一个研究热点。关于KDD和DataMining的关系，有许多不同的看法。我们可以从这些不同的观点中了解数据挖掘的技术含义。

1)将KDD看成数据挖掘的例子之一这一观点在数据挖掘发展的早期比较流行，并且可以在许多文献中看到这种说法。其主要观点是数据库中的知识发现仅是数据挖掘的一个方面，因为数据挖掘系统可以在关系数据库(RelationalDatabase)、事务数据库(TransactionalDatabase)、数据仓库(DataWarehouses)、空间数据库(SpatialDatabase)、文本数据(TextData)以及诸如Web等多种数据组织形式中挖掘知识。从这个意义上来说，数据挖掘就是从数据库、数据仓库以及其他数据存储方式中挖掘有用知识的过程。

2)数据挖掘是KDD不可缺少的一部分为了统一认识，Fayyd、PiatetskyShapiro和Smyth在1996年出版的权威论文集《知识发现与数据进展》中给出了KDD和数据挖掘的最新定义：KDD是从数据中辨别有效的、新颖的、潜在有用的、最终可理解的模式的过程；数据挖掘是KDD中通过特定的算法在可接受的计算效率限制内生成特定模式的一个步骤。

这种观点得到了大多数学者的认同。它将KDD看做是一个广义的范畴，包括数据清理、数据集成、数据选择、数据转换、数据挖掘、模式生成及评估等一系列步骤。这样，我们可以把KDD看做是由一些基本功能构件组成的系统化协同工作系统，而数据挖掘则是这个系统中的一个关键的部分。源数据经过清理和转换等步骤成为适合挖掘的数据集，数据挖掘在这种具有固定形式的数据集上完成知识的提炼，最后以合适的知识模式用于进一步的分析决策工作。将数据挖掘作为KDD的一个重要步骤看待，可以使我们更容易聚焦研究重点，有效解决问题。目前，人们对于数据挖掘算法的研究基本属于这样的范畴。

3)KDD与DataMining的含义相同有些人认为，KDD与DataMining只是对同一个概念的不同叫法。事实上，现今的许多文献(如技术综述等)中，这两个术语仍然不加区分地使用着。有人说，KDD在人工智能界更流行，而DataMining在数据库界使用更多。也有人说，一般在研究领域称之为KDD，在工程领域则称之为数据挖掘。实际上，数据挖掘的概念有广义和狭义之分。广义的定义是，数据挖掘是从大型数据集(可能是不完全的、有噪声的、不确定性的、各种存储形式的)中，挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程。狭义的定义是，数据挖掘是从特定形式的数据集中提炼知识的过程。综上所述，数据挖掘概念可以从不同的技术层面上来理解，但是其核心仍然是从数据中挖掘知识。所以，有人说叫知识挖掘更合适。本书也在不同的章节使用数据挖掘的广义或狭义概念，读者要注意根据上下文加以区分。当然，在可能混淆的地方，我们将明确说明。1.2数据挖掘的历史及发展

数据挖掘可以看做是信息技术自然演化的结果。像其他新技术的发展历程一样，数据挖掘也必须经过概念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段。一方面，数据挖掘的概念已经被广泛接受；另一方面，数据挖掘的广泛应用还有待时日，需要深入的理论研究和丰富的工程实践做积累。经过十几年的研究和实践，数据挖掘技术已经吸收了许多学科的最新成果而形成独具特色的研究。毋庸置疑，数据挖掘的研究和应用具有很大的挑战性。随着KDD在学术界和商业界的影响越来越大，数据挖掘的研究向着更深入和实用技术两个方向发展。从事数据挖掘研究的人员主要集中在大学、研究机构，也有部分在企业和公司。所涉及的研究领域很多，主要集中在学习算法的研究、数据挖掘的实际应用以及数据挖掘理论等方面。大多数基础研究项目是由政府资助进行的，而司的研究则更注重和实际商业问题的结合。数据挖掘的概念从20世纪80年代被提出后，其经济价值也逐步显现出来，而且被众多商业厂家所推崇，形成初步的市场。另一方面，目前的数据挖掘系统研制也绝不是像一些商家为了宣传自己商品所说的那样神奇，而是仍有许多问题亟待研究和探索。把目前数据挖掘的研究现状描述为鸿沟(Chasm)阶段是比较准确的。所谓Chasm阶段，是说数据挖掘技术在广泛被应用之前仍有许多“鸿沟”需要跨越。例如，就目前商家推出的数据挖掘系统而言，它们都是一些通用的辅助开发工具，这些工具只能给那些熟悉数据挖掘技术的专家或高级技术人员使用，仅对应用起到加速作用，或称之为横向解决方案(HorizontalSolution)。但是，数据挖掘来自于商业应用，而商业应用又会由于领域的不同而存在很大差异。大多数学者赞成这样的观点：数据挖掘在商业上的成功不能期望于通用的辅助开发工具，而应该是数据挖掘概念与特定领域的商业逻辑相结合的纵向解决方案(VerticalSolution)。分析目前的研究和应用现状，数据挖掘需要在如下几个方面重点开展工作。

1.数据挖掘技术与特定商业逻辑的平滑集成问题

谈到数据挖掘和知识发现技术，人们大多引用“啤酒与尿布”的例子。事实上，目前在数据挖掘领域的确很难再找到其他类似的经典例子。数据挖掘和知识发现技术的广阔应用前景需要有效的应用实例来证明。数据挖掘与知识发现技术研究与应用的重要方向包括领域知识对行业或企业知识挖掘的约束与指导、商业逻辑有机潜入数据挖掘过程等关键课题。

2.数据挖掘技术与特定数据存储类型的适应问题数据的存储方式会影响数据挖掘的目标定位、具体实现机制、技术有效性等问题。指望一种能够在所有数据存储方式下发现有效知识的应用模式是不现实的。因此，针对不同的数据存储类型进行挖掘研究是目前的趋势，而且也是未来研究所必须面对的问题。

3.大型数据的选择和规格化问题

数据挖掘技术是面向大型且动态变化的数据集的，这些数据集往往存在噪声、不确定性、信息丢失、信息冗余、数据分布稀疏等问题，挖掘前必须对数据进行预处理。另外，数据挖掘技术又是面向特定商业目标的，数据需要选择性地利用，因此，针对特定挖掘问题进行数据选择、针对特定挖掘方法进行数据规格化是数据挖掘技术无法回避的问题。

4.数据挖掘系统的构架与交互式挖掘技术

虽然经过多年的探索，数据挖掘系统的基本构架和过程已经趋于明朗，但是在应用领域、数据类型以及知识表达模式等因素的影响下，其具体的实现机制、技术路线以及各阶段(如数据清理、知识形成、模式评估等)功能定位等方面仍需细化和深入的研究。另外，由于数据挖掘是在大量的源数据中发现潜在的、事先并不知道的知识，因此和提供源数据的用户进行交互式探索挖掘是必然的。这种交互可能发生在数据挖掘的各个阶段，从不同角度或不同粒度进行交互。所以,良好的交互式挖掘(InteractionMining)也是数据挖掘系统成功的前提。

5.数据挖掘语言与系统可视化问题对于OLTP应用来说，结构化查询语言SQL已经得到充分发展，并成为支持数据库应用的重要基石。相比OLTP应用而言，数据挖掘技术诞生较晚，应用更复杂，因此开发相应的数据挖掘操作语言仍然是一件极富挑战性的工作。可视化已经成为目前信息处理系统必不可少的要求，对于一个数据挖掘系统来说更是尤为重要。可视化挖掘除了要和良好的交互式技术相结合外，还必须在挖掘结果或知识模式的可视化、挖掘过程的可视化以及可视化指导用户挖掘等方面进行探索和实践。数据的可视化在某种程度上推动了人们进行知识发现，因此它可以被认为是人们从对KDD的神秘感变成可以直观理解知识和形象的过程。

6.数据挖掘理论与算法研究

经过几十年的研究，数据挖掘已经在继承和发展相关基础学科(如机器学习、统计学等)方面取得了可喜的进步，并探索出了许多独具特色的理论体系。但这并不意味着挖掘理论的探索已经结束，恰恰相反，它留给研究者更多丰富的理论课题。这些研究课题一方面着眼于探索和创新面向实际应用目标的挖掘理论，另一方面的重点在于发展新的挖掘理论和算法。这些算法可能在挖掘的有效性、挖掘的精度或效率以及融合特定的应用目标等方面做出贡献。因此，对数据挖掘理论和算法的探讨将是长期而艰巨的任务。特别是，像定性定量转换、不确定性推理等一些根本性的问题还没有得到很好的解决，同时需要针对大容量数据集研究有效和高效算法。从上面的叙述可以看出，数据挖掘研究和探索的内容是极其丰富和具有挑战性的。1.3数据挖掘的研究内容及功能

1.3.1数据挖掘的研究内容目前，数据挖掘的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘。数据挖掘所发现的知识最常见的有以下五类。

1.广义知识(Eneralization)

广义知识指类别特征的概括性描述知识，是根据数据的微观特性发现其表征的、带有普遍性的、高层次概念的、中观或宏观的知识。反映同类事物的共同性质，是对数据的概括、精炼和抽象。广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约等。数据立方体还有其他一些别名，如“多维数据库”、“实现视图”、“OLAP”等。该方法的基本思想是计算某些常用的代价较高的聚集函数，诸如计数、求和、平均、最大值等，并将这些实现视图储存在多维数据库中。既然很多聚集函数需经常重复计算，那么在多维数据立方体中存放预先计算好的结果将能保证快速响应，并可灵活地提供不同角度和不同抽象层次上的数据视图。另一种广义知识发现方法是加拿大SimonFraser大学提出的面向属性的归约方法。这种方法以类SQL语言表示数据挖掘查询，收集数据库中的相关数据集，然后在相关数据集上应用一系列数据推广技术进行数据推广，包括属性删除、概念树提升、属性阈值控制、计数及其他聚集函数传播等。

2.关联知识(Association)关联知识是反映一个事件和其他事件之间依赖或关联的知识，又称依赖(Dependency)关系。这类知识可用于数据库中的归一化、查询优化等。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名的关联规则发现方法是R.Agrawal提出的Apriori算法。关联规则的发现挖掘可分为两步：第一步是找出所有的频繁项集，要求频繁项集出现的频繁性不低于用户设定的最小支持度阈值（支持度反映了所发现规则的有用性）；第二步是从频繁项集中产生强关联规则，这些规则必须满足用户设定的最小置信度阈值（置信度反应了所发现规则的确定性）。识别或发现所有挖掘频繁项集是关联规则发现算法的核心，也是计算量最大的部分。

3.分类知识(Classification＆Clustering)分类知识反映同类事物共同性质的特征型知识和不同事物之间差异的特征型知识，用于反映数据的汇聚模式或根据对象的属性区分其所属类别。最为典型的分类方法是基于决策树的分类方法。它从实例集中构造决策树，是一种有指导性的学习方法。该方法先根据训练子集(称为窗口)构造决策树。如果该树不能对所有对象进行正确的分类，那么选择一些例外加入到窗口中，重复该过程一直到形成正确的决策集。其最终结果是一棵树，叶结点是类名，中间结点是带有分枝的属性，该分枝对应该属性的某一可能值。最为典型的决策树分类系统是ID3，它采用自顶向下不回溯策略，能保证找到一个简单的树。算法C4.5和C5.0都是ID3的扩展，它们将分类领域从类别属性扩展到数值型属性。数据分类还有统计、粗糙集(RoughSet)等方法。线性回归和线性辨别分析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。

4.预测型知识(Prediction)预测型知识是指由历史的和当前的时间序列型数据去推测未来的数据，它实际上是一种以时间为关键属性的关联知识。目前，时间序列预测的经典方法有统计方法、神经网络和机器学习等。1968年，Box和Jenkins提出了一套比较完善的时间序列建模理论和分析方法，通过经典的数学方法建立随机模型，如自回归模型、自回归滑动平均模型、求和自回归滑动平均模型和季节调整模型，并在此基础上进行时间序列的预测。大量的时间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化，仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的预测任务，为此，人们提出了统计学和基于精确性的再训练方法，当发现现存预测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。此外，有许多系统借助并行算法的计算优势对时间序列进行预测。

5.偏差型知识(Deviation)偏差型知识是指通过分析标准类以外的特例、数据聚类外的离群值、实际观测值和系统预测值间的显著差别，对差异和极端特例进行描述。所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观到中观、到宏观，满足不同用户不同层次决策的需要。1.3.2数据挖掘的功能数据挖掘用于在指定数据挖掘任务中找到模式类型。数据挖掘任务一般可以分两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性；预测性挖掘任务在当前数据上进行推测和预测。用户有时不知道他们的数据中什么类型的模式是有趣的，因此数据挖掘系统要能够并行地挖掘多种类型的模式，以适应不同的用户需要或不同的应用。此外，数据挖掘系统应当能够发现各种粒度(即不同的抽象层次)的模式。数据挖掘系统应当允许用户给出提示，指导或聚焦有趣模式的搜索。由于有些模式并非对数据库中的所有数据都成立，通常每个被发现的模式需要带上一个确定性或“可信性”度量。数据挖掘的功能主要体现在以下六个方面。

1.类/概念描述：特征化和区分

数据可以与类或概念相关联。一个概念常常是对一个包含大量数据的数据集合总体情况的概述。对含有大量数据的数据集合进行描述性的总结并获得简明、准确的描述，这种描述就称为类/概念描述(Class/ConceptDescription)。这种描述可以通过下述方法得到：

(1)数据特征化，一般地汇总所研究类(称为目标类(ArgetClass))的数据。

(2)数据区分，将目标类与一个或多个比较类(常称为对比类(OntrastingClass))比较。

(3)数据特征化和比较。数据特征化(DataCharacterization)是目标类数据的一般特征或特性的汇总。通常，用户指定类的数据通过数据库查询收集。例如，为研究上一年销售增加10%的软件产品的特征，可以通过执行一个SQL查询收集关于这些产品的数据。有许多有效的方法可以将数据特征化和汇总。例如，基于数据立方体的OLAP上卷操作可以用来执行用户控制的、沿着指定维的数据汇总。一种面向属性的归纳技术可以用来进行数据的概化和特征化，而不必一步步地与用户进行交互。

数据特征可以通过多种形式输出，包括饼图、条图、曲线、多维数据立方体和包括交叉表在内的多维表。结果描述也可以由概化关系(GeneralizedRelation)或规则形式(称作特征规则)提供。数据区分(DataDiscrimination)是将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。目标类和对比类由用户指定，而对应的数据通过数据库查询检索。例如，用户可能希望将上一年销售增加10%的软件产品与同一时期销售至少下降30%的那些产品进行比较。用于数据区分的方法与用于数据特征化的方法类似。区分描述的输出形式类似于特征描述，但区分描述应当包括比较度量，帮助区分目标类和对比类。用规则表示的区分描述称为区分规则(DiscriminantRule)。用户应当能够对特征和区分描述的输出进行操作。

2.关联分析

关联分析(AssociationAnalysis)就是从给定的数据集中发现频繁出现的项集模式知识,又称为关联规则AssociationRules。关联分析广泛应用于市场营销、事务分析等领域。通常关联规则具有X

Y形式即“A1∧…∧Am

B1∧…∧Bn”的规则，其中，Ai(i∈{1,…,m}),Bj(j∈{1,…，n})均为属性—值(属性=值)形式。关联规则XY

表示“数据库中的满足X中条件的记录(tuples)也一定满足Y中的条件”。

3.分类和预测

分类(Classification)就是找出一组能够描述数据集合典型特征的模型（或函数），以便能够分类识别未知数据的归属或类别(Class)，即将未知事例映射到某种离散类别之一。分类模型（或函数）可以通过分类挖掘算法从一组训练样本数据（其类别归属已知）中学习获得。

分类挖掘所获得的分类模型可以采用多种形式加以描述输出。其中主要的表示方法有：分类规则(IFTHEN)、决策树(DecisionTrees)、数学公式(MathematicalFormulae)和神经网络。分类规则容易由判定树转换而成。决策树是一个类似于流程图的树结构，每个节点代表一个属性值上的测试，每个分支代表测试的一个输出，树叶代表类和类分布。神经网络在用于分类时是一组类似于神经元的处理单元，单元之间加权连接。分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望预测某些空缺或未知的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预测(Prediction)。尽管预测可以涉及数据值预测和类标记预测，但预测通常是指值预测，并因此不同于分类。预测同时也包含基于可用数据的分布趋势识别。相关分析(RelevanceAnalysis)可能需要在分类和预测之前进行，它试图识别对于分类和预测无用的属性。这些属性应当排除。

4.聚类分析

聚类分析(ClusteringAnalysis)与分类预测方法的明显不同之处在于，后者所学习获取分类预测模型所使用的数据是已知类别属性(ClasslabeledData)，属于有监督学习方法，而聚类分析(无论是在学习还是在归类预测时)所分析处理的数据均是无(事先确定)类别归属的。类别归属标志在聚类分析处理的数据集中是不存在的。聚类也便于将观察到的内容分类编制(TaxonomyFormation)成类分层结构，把类似的事件组织在一起。

5.孤立点分析数据库中可能包含一些与数据的一般行为或模型不一致的数据对象。这些数据对象被称为孤立点(Outlier)。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃,然而在一些应用场合，如各种商业欺诈行为的自动检测中，小概率发生的事件(数据)往往比经常发生的事件(数据)更有挖掘价值。孤立点数据分析通常称做孤立点挖掘(OutlierMining)。孤立点可以使用统计试验检测。它假定一个数据分布或概率模型，并使用距离进行度量，到其他聚类的距离很大的对象被视为孤立点。基于偏差的方法通过考察一群对象主要特征上的差别来识别孤立点，而不是使用统计或距离度量。

6.演变分析数据演变分析(EvolutionAnalysis)就是对随时间变化的数据对象的变化规律和趋势进行建模描述。这一建模手段包括概念描述、对比概念描述、关联分析、分类分析、时间相关数据(TimeRelated)分析,时间相关数据分析又包括时序数据分析，序列或周期模式匹配，以及基于相似性的数据分析等。1.4数据挖掘的常用技术及工具

数据挖掘是从人工智能领域的一个分支——机器学习发展而来的，因此机器学习、模式识别、人工智能领域的常规技术，如聚类、决策树、统计等方法经过改进，大都可以应用于数据挖掘。数据挖掘的常用技术有决策树、规则发现、神经网络、贝叶斯网络、关联规则、聚类、可视化、文本/Web挖掘等。近年来，神经网络、贝叶斯网络、关联规则等技术在数据挖掘中的应用发展很快；可视化技术受到越来越多的重视；文本和Web数据的挖掘成为一个新兴的研究方向。1.4.1数据挖掘的常用技术数据挖掘的常用技术有：

(1)人工神经网络：仿照生理神经网络结构的非线性预测模型，通过学习进行模式识别。

(2)决策树：代表着决策集的树形结构。

(3)遗传算法：基于进化理论，并采用遗传结合、遗传变异以及自然选择等设计方法的优化技术。

(4)近邻算法：将数据集合中每一个记录进行分类的方法。

(5)规则推导：从统计意义上对数据中的“如果—那么”规则进行寻找和推导。采用上述技术的某些专门的分析工具已经发展了大约十年的时间，不过这些工具所能处理的数据量通常较小。现在，这些技术已经被直接集成到许多大型的符合工业标准的数据仓库和联机分析系统中了。1.4.2数据挖掘的工具

1.基于神经网络的工具神经网络用于分类、特征挖掘、预测和模式识别。人工神经网络仿真生物神经网络，本质上是一个分散型或矩阵结构，它通过训练数据的挖掘，逐步计算网络连接的加权值。由于对非线性数据具有快速建模能力，基于神经网络的数据挖掘工具现在越来越流行。其开采过程基本上是将数据聚类，然后分类计算权值。神经网络很适合分析非线性数据和含噪声数据，所以在市场数据库的分析和建模方面应用广泛。

2.基于规则和决策树的工具

大部分数据挖掘工具采用规则发现或决策树分类技术来发现数据模式和规则，其核心是某种归纳算法。这类工具通常是对数据库的数据进行开采，产生规则和决策树，然后对新数据进行分析和预测。其主要优点是：规则和决策树都是可读的。

3.基于模糊逻辑的工具该方法应用模糊逻辑进行数据查询、排序等。它使用模糊概念和“最近”搜索技术的数据查询工具，可以让用户指定目标，然后对数据库进行搜索，找出接近目标的所有记录，并对结果进行评估。

4.综合多方法的工具

不少数据挖掘工具采用了多种开采方法，这类工具一般规模较大，适用于大型数据库(包括并行数据库)。这类工具开采能力很强，但价格昂贵，并要花很长时间进行学习。1.5数据挖掘的应用热点

就目前来看，数据挖掘未来的几个应用热点包括网站的数据挖掘、生物数据挖掘、文本的数据挖掘、实时数据挖掘以及数据挖掘中的隐私保护和信息安全。

1.网站的数据挖掘随着互联网的发展，各类电子商务网站层出不穷。电子商务网站在进行数据挖掘时，所需要的数据主要来自于两个方面：一部分数据是客户的背景信息，此部分信息主要来自于客户的登记信息；另外一部分数据主要来自浏览者的点击流(ClickStream)，此部分数据主要用于考察客户的行为表现。但有的时候，客户不肯把背景信息填写在登记表上，这就会给数据分析和挖掘带来不便。此时，就不得不从浏览者的点击流数据中来推测客户的背景信息，进而再加以分析。就分析和建立模型的技术和算法而言，网站的数据挖掘和传统的数据挖掘差别并不是特别大，很多方法和分析思想都可以运用。所不同的是网站的数据格式有很大一部分来自于点击流，这与传统的数据库格式有区别。因而对电子商务网站进行数据挖掘所做的主要工作是数据准备。目前，有很多厂商正在致力于开发专门用于网站挖掘的软件。

2.生物数据挖掘

生物数据具有复杂性、丰富性、重要性等特点。这些都需要在进行数据挖掘时重点关注。挖掘DNA和蛋白序列、挖掘高维微阵列数据、生物路径和网络分析、异构生物数据的链接分析，以及通过数据挖掘集成生物数据等都是生物数据挖掘研究的有趣课题。生物数据挖掘和通常的数据挖掘相比，无论是数据的复杂程度、数据量还是分析和建立模型的算法，都要复杂得多。从分析算法上讲，更需要一些新的和好的算法。现在很多厂商正在致力于这方面的研究。

3.文本的数据挖掘随着文本数据的快速猛增，传统信息检索技术已无法满足实际的需要。文档都包含有用信息，但只有一小部分是与特定用户的需求密切相关的，在不知道文档中究竟会有哪些内容时，要想给出准确精致的查询是较为困难的。在处理大量文档时，需要对文档进行比较，评估文档的重要性和相关性，或发现多文档的模式和趋势。也可以将互联网看成是一个巨大的、动态的文本数据库。显然，随着互联网的飞速发展，文本挖掘将在数据挖掘中扮演越来越重要的角色。

4.实时数据挖掘

许多包括流数据(比如电子商务、Web挖掘、股票分析、入侵检测和移动数据挖掘)的应用要求能实时地建立动态数据挖掘模型。该领域还需要进一步发展。

5.数据挖掘中的隐私保护和信息安全

Web上有大量电子形式的个人信息，随着网上攻击能力的不断增强，对我们的隐私和数据安全造成了威胁。隐私的保护越来越得到了重视。这需要技术专家、社会科学家、法律专家和公司协作，提出隐私的严格定义和形式机制，以证明数据挖掘中的隐私保护性。随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、越来越复杂，数据挖掘将发挥出越来越大的作用。第2章数据预处理

2.1数据预处理的目的2.2数据清理2.3数据集成和数据变换2.4数据归约2.5数据离散化和概念分层2.6特征选择与提取2.1数据预处理的目的

数据源中的数据可能不完整(如某些属性值的空缺)、含噪声(具有不正确的属性值)和不一致(如同一属性的不同名称)。不完整数据的出现可能有多种原因：某些数据被认为是不必要的，如销售事务数据中顾客的信息并非总是可用的；其他数据没有包含在内，可能只是因为输入时认为是不重要的；由于理解错误，或者因为设备故障相关数据没有记录；某些记录与其他记录的内容不一致而被删除；记录历史或修改的数据可能被忽略。

空缺的数据，特别是某些属性上缺少值的元组可能需要推导。数据含噪声可能有多种原因：数据采集设备可能出故障；在数据录入过程中发生了人为的或计算机导致的错误；可能由于技术的限制，数据传输过程中出现错误；不正确的数据也可能是由命名或所用的数据代码不一致而导致的。重复元组有时也需要进行数据清理。数据清理(DataCleaning)例程通过填补空缺数据平滑噪声数据，识别、删除孤立点，并纠正不一致的数据。异常数据可能使挖掘过程陷入混乱，导致不可靠的输出。数据集成(DataIntegration)指将来自不同数据源的数据合成一致的数据存储。数据变换(DataTransformation)操作，如规格化和聚集，是将数据转换成适于挖掘的形式的预处理过程。数据归约策略有助于从原有的庞大的数据集中获得一个精简的数据集合，并使这一精简数据集保持原有数据集的完整性。在精简数据集上进行的数据挖掘显然效率更高，并且挖掘结果与使用原有数据集的结果基本相同。概化也可以“归约”数据。概化用较高层的概念替换较低层的概念。图2-1对上述数据预处理进行了图解。以上的数据预处理并不互斥，例如，冗余数据的删除既是数据清理，也是数据归约。图2-1数据预处理的形式总之，数据源中的数据一般是含噪声的、不完整的和不一致的。数据预处理技术可以改进数据的质量，从而改善挖掘过程的性能，提高挖掘结果的质量。高质量的决策必然依赖于高质量的数据，因此数据预处理是知识发现过程的重要步骤。2.2数据清理

2.2.1空缺值空缺值是指所关心的某些属性对应的部分属性值是空缺的。在数据挖掘过程中，这些空缺值会对挖掘结果带来影响，因此需要进行相应的处理。主要方法如下：

(1)忽略元组，即不选择有空缺值的元组。此方法不是很有效，除非元组有多个属性缺少值时。

(2)人工填写空缺值。通常数据挖掘所涉及的数据量较大，如果空缺值很多，这种方法比较费时，几乎行不通。

(3)使用一个全局常量填充空缺值，即对一个属性的所有空缺值都使用一个事先确定好的值(如“OK”或-∞)来填补。虽然此方法比较简单，但并非总是正确的，例如空缺值都用“OK”替换，挖掘程序可能误以为它们形成了一个有趣的模式。

(4)使用属性的平均值填充空缺值。例如，若一个顾客的平均收入(income)为16000元，则用此值填补income属性中的所有空缺值。

(5)使用与给定元组属同一类的所有样本的平均值。例如，在分类挖掘中，使用与给定样本属于同一类的其他样本的平均值来填充空缺值。

(6)使用最可能的值填充空缺值：可以用回归、贝叶斯形式化方法的工具或判定树归纳确定最有可能的值。当有空缺值的数据不是孤立点时，此方法有较高的准确性。2.2.2噪声数据

噪声(Noise)是一个测量变量中的随机错误或偏差。下面介绍四种数据平滑技术。

1.分箱(Binning)分箱方法通过考察“邻居”(即周围的值)来平滑存储数据的值。存储的值被划分到若干个箱或桶中。由于仅考察被平滑点邻近的数据，因此分箱方法进行的是局部平滑。例2.1展示了一些分箱技术。在该例中，score数据首先被划分并存入等深(每个箱中的数据个数相等)的箱中。平均值平滑是指将同一箱中的数据全部用该箱中数据的平均值替换。例如，箱1中的值60,65,67的平均值是64，那么该箱中的每一个值被替换为64。类似地，可以使用按箱中值平滑，此时，箱中的每一个值被箱中的中值替换；按箱边界平滑，箱中的最大和最小值被视为箱边界，箱中的每一个值被最近的边界值替换。分箱技术可以采用等深和等宽的分布规则对数据进行平滑，等深指每个箱中的数据个数相同，等宽指每个箱的取值范围相同。分箱也可以作为一种离散化技术使用。【例2.1】[ST][HT]

score排序后的数据(分):60,65,67,72,76,77,84,87,90划分为(等深，深度为3)箱(桶)：箱1:60,65,67箱2:72,76,77箱3:84,87,90采用分箱平滑技术后，用平均值平滑得：箱1:64,64,64箱2:75,75,75箱3:87,87,87用边界值平滑得：箱1:60,67,67箱2:72,77,77箱3:84,84,90

2.聚类(Clustering)孤立点可以被聚类检测。通过聚类可以发现异常数据(Outliters)，相似或相邻近的数据聚合在一起形成了各个聚类集合，而那些位于聚类集合之外的数据，自然被认为是异常数据(孤立点)。直观地看，落在聚类集合之外的值被视为孤立点，如图2-2所示。孤立点将被视为噪声数据而消除。图2-2孤立点可以被聚类分析检测

3.计算机检查和人工检查结合

通过人与计算机相结合的检查方法，可以帮助识别孤立点。例如，利用机遇信息论方法可以帮助识别用于手写符号库中的异常模式，所识别出的异常模式可以输出到一个列表中，然后由人对这一列表中的各异常模式进行检查，并最终确认无用的模式。这种人机结合检查的方法比单纯利用手工方法手写符号库进行检查要快得多。

4.回归(Regression)可以利用拟合函数对数据进行平滑。例如，线性回归需要找出适合两个变量的“最佳”直线，使得一个变量能够预测另一个。多线性回归是线性回归的扩展，它涉及多于两个变量。利用回归分析方法获得的拟合函数，能够帮助平滑数据并除去其中的噪声。

许多数据平滑的方法也是离散化的数据归约方法。例如，上面介绍的分箱技术减少了每个属性的不同值的数量。概念分层是一种数据离散化形式，也可以用于数据平滑。例如，score的概念分层可以把score的值映射到优、良、中、及格和不及格，从而减少了挖掘过程所处理的值的数量。有些分类方法有内置的数据平滑机制，如神经网络。2.2.3不一致数据现实世界的数据可能常出现数据记录内容的不一致。有些数据不一致可以用其与外部的关联手工加以解决。例如，数据输入时的错误可以与原稿进行对比来加以纠正。知识工程工具也可以用来检测违反限制的数据。例如，知道属性间的函数依赖，可以查找违反函数依赖的值。由于同一属性在不同数据库中的取名不规范，常常使得在进行数据集成时，不一致的情况发生，也可能存在冗余。2.3数据集成和数据变换

2.3.1数据集成数据分析任务多半涉及数据集成。数据集成将多个数据源中的数据结合起来存放在一个一致的数据存储(如数据仓库)中。数据源可能涉及多个数据库、数据立方体或一般文件。在数据集成时，需要解决以下几个问题：

(1)模式集成的过程中涉及到的实体识别问题。这类问题主要是来自多个信息源的现实世界的实体如何才能“匹配”的问题。例如，确信一个数据库中的customer_id和另一个数据库中的cust_number指的是同一实体。通常，数据库和数据仓库中的元数据(关于数据的数据)可以帮助避免模式集成中的错误。

(2)冗余问题。冗余是数据集成中的另一个重要问题。如果一个属性可以从其他属性中推演出来，该属性就是冗余的，如年薪。属性或维命名的不一致也可能导致数据集中的冗余。利用相关分析可以帮助发现一些数据冗余情况。例如，给定两个属性，根据可用的数据，这种分析可以度量一个属性能在多大程度上蕴涵另一个属性。属性A和B之间的相关性可用下式度量：其中，n是元组个数；σA和σB分别为属性A和B的标准差。如果(2.1)式的值大于0，则A和B是正相关的，意味着A的值随B的值增加而增加。该值越大，说明A、B正相关关系越密切。因此，一个很大的值表明A(或B)可以作为冗余而被去掉。如果结果值等于0，则A和B是独立的，两者之间没有关系。如果结果值小于0，则A和B是负相关的，一个值随另一个值减少而增加，这表明每一个属性都阻止另一个属性出现。(2.1)式可以用来检测（1）中的customer_id和cust_number的相关性。除了检测属性间的冗余外，还应当检测元组级的“重复”。重复是指对于同一数据，存在两个或多个相同的元组。

(3)数据集成过程中的数据值冲突的检测与处理问题。例如，对于同一实体，不同数据源的属性值可能不一致。这可能是因为表示的差异、比例尺度或编码不同造成的。例如，长度属性可能在一个系统中以公制单位存放，而在另一个系统中以英制单位存放；价格属性不同地点采用不同的货币单位。数据在语义上的差异，是数据集成的巨大挑战。2.3.2数据变换数据变换将数据转换成适合于挖掘的形式。常用的数据变换方法如下：

(1)平滑(smoothing)：帮助去除数据中的噪声。这种技术包括分箱、聚类和回归。

(2)聚集：对数据进行汇总和聚集操作。例如，可以聚集日销售数据，计算月和年销售额。通常，这一步用来为多粒度数据分析构造数据立方体。

(3)数据概化：用更抽象的概念来取代低层次或数据层的数据对象。例如，分类的属性，如price，可以概化为较高层的概念，如cheap、moderatelypriced或expensive。类似地，数值属性，如age，可以映射到较高层概念，如young、middleage和senior。

(4)规范化：将有关属性数据按比例投射到特定的小范围内，如-1.0~1.0或0.0~1.0。规范化可以消除数值型属性因大小不一而造成的挖掘结果偏差。对于分类算法，如涉及神经网络的算法或诸如最临近分类和聚类的距离度量分类算法，规范化特别有用。如果使用神经网络后向传播算法进行分类挖掘，训练样本的规范化能够提高学习的速度。有许多数据规范化的方法，此处介绍三种：最小—最大规范化、z-score规范化和按小数定标规范化。最小—最大规范化方法是对初始数据进行一种线性变换。假定，minA和maxA分别为属性A的最小值和最大值。最小—最大规范化方法通过下式(2.2)将A的值v映射到区间［new_minA,new_maxA］中的v′。最小—最大规范化保留了原始数据中存在的关系。如果将来遇到目前属性A取值范围之外的数据，则该方法将面临“越界”错误。

【例2.2】假定某属性的最小与最大值分别为$8000和$14000。要将其映射到区间［0.0，1.0］。按照最小-最大规范化方法对属性值进行缩放，则属性值$12600将变换为

z-score(零—均值)规范化方法根据属性A的平均值和标准差对A进行规范化。A的值v被规范化为v′，由下式计算：(2.3)其中，和σA分别为属性A的平均值和标准差。该方法常用于属性A最大值和最小值未知的情况，或孤立点左右了最大—最小规范化的情况。

【例2.3】若属性income的平均值和标准差分别为$32000和$17000,则使用z-score规范化后，值$65600被转换为按小数定标规范化方法通过移动属性A的小数点位置进行规范化。小数点的移动位数依赖于A的最大绝对值。

A的值v被规范化为v′，由下式计算：(2.4)其中，j是使得max(|v′|)<1的最小整数。【例2.4】假定A的值为-859~653。A的最大绝对值为859。使用按小数定标规范化方法，用1000(即j=3)除每个值。这样，-859被规范化为-0.859。注意，规范化使得原始数据改变了很多，必须保留规范化参数(如平均值和标准差，如果使用z-score规范化)，以便将来的数据可以用一致的方式规范化。

(5)属性构造(或特征构造)：由已有的属性构造和添加新的属性，以帮助挖掘更深层次的模式知识，提高挖掘结果的准确性。例如，可根据属性height和width添加属性area。属性构造可以减少使用判定树算法分类的分裂问题。通过组合属性，可以帮助发现所遗漏的属性间的相互关系，而这对于数据挖掘是十分重要的。2.4数据归约

数据归约技术可以用来得到数据集的归约表示，它比源数据集小得多，但仍接近于保持原数据的完整性。在归约后的数据集上挖掘将更高效，并能产生相同(或几乎相同)的分析结果。数据归约的策略如下：

(1)数据立方体聚集：主要用于构造数据立方体。

(2)维归约：可以检测并删除不相关、弱相关或冗余的属性或维(数据仓库中的属性)。

(3)数据压缩：利用编码技术压缩数据集的大小。

(4)数值压缩：用较小的数据表示数据或估计数据，如用参数模型(只需要存放模型参数，而不是实际数据)或非参数方法，如聚类、抽样和使用直方图。

(5)离散化和概念分层产生：利用取值范围或更高层次的概念来代替原始数据。概念分层允许挖掘多个抽象层上的模式知识，是数据挖掘的一种强有力的工具。下面详细地介绍几种常用的数据规约策略。2.4.1维归约数据集可能包含成百上千的属性，但大部分属性与挖掘任务不相关，属于冗余属性。例如，分析银行顾客的信用度时，诸如顾客的电话号码、地址等属性与任务不相关。维归约通过减少或删除不相关的属性(或维)减少数据集的规模。通常使用属性子集选择方法。属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能地接近原属性集的概率分布。在规约后的属性集上进行挖掘，不仅减少了出现在发现模式上的属性的数目，而且使得模式更易于理解。对于属性子集选择，通常使用压缩搜索空间的启发式算法。属性子集选择的基本启发式方法包括以下几种：

(1)逐步向前选择。方法从空属性集开始，每次从原来属性集合中选择一个当前最优的属性添加到当前属性子集中。直到无法选择出最优属性或满足一定阈值为止。

(2)逐步向后删除。该方法从一个全属性集开始，每次从当前属性集中选择一个当前最差的属性并将其从当前属性集中消去，直到无法选择出最差的属性为止或满足一定阈值为止。

(3)向前选择和向后删除的结合。向前选择和向后删除方法可以结合在一起，每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。方法(1)~(3)的结束条件可以有多种。可以用一个阈值来确定是否停止属性选择过程。

(4)判定树归纳：通常用于分类的决策树算法也可以用于构造属性子集，如ID3和C4.5。判定树归纳构造对原数据进行分类归纳学习，获得一个初始判定树，没有出现在树中的属性均被认为是不相关的属性，出现在树中的属性就可以得到一个较优的属性集。2.4.2数据压缩数据压缩就是利用数据编码或数据转换将原始数据集合压缩为一个较小规模的数据集合。可以不丢失任何信息地还原数据的压缩称为无损压缩；构造原始数据的近似表示称为有损压缩。本小节介绍两种流行的和有效的有损数据压缩方法：小波变换和主要成分分析。

1.小波变换离散小波变换(DWT)是一种线性信号处理技术，该技术可以将一个数据向量D转换为另一个数据向量D′(小波相关系数)。两个向量具有相同的长度。小波变换后的数据可以裁减。仅存放一小部分最强的小波系数，就能保留近似的压缩数据。例如，保留大于用户设定的某个阈值的小波系数，其他系数置为0。这样，结果数据表示非常稀疏，若在小波基础上进行的话，利用数据稀疏特点的操作使得计算效率得到大大提高。该技术也能用于消除噪声，并且不会平滑掉数据的主要特性，使得它们也能有效地用于数据清理。给定一组系数，使用所用的DWT的逆，可以还原源数据的近似。流行的小波变换包括Haar_2、Daubechies_4和Daubechies_6变换。应用离散小波变换的一般过程使用一种分层的算法，它在每次迭代时将数据减半，从而获得更快的计算速度。该方法步骤如下：

(1)输入数据向量的长度L，它必须是2的整数幂。必要时，需要在数据向量后添加0，以满足上述条件。

(2)每次变换涉及两个函数。第一个对数据进行平滑，如求和或加权平均；第二个进行带权差分，以获得数据的主要特征。该步将数据一分为二，产生两个长度为L/2的数据集，它们分别代表输入数据平滑后的低频部分和高频部分。

(3)循环使用两个函数作用于数据集，直到结果数据集的长度为2。由以上步骤处理得到的结果即为数据变换的小波系数。类似地，可以使用矩阵乘法对输入数据进行处理，以得到小波系数。所用的矩阵依赖于具体的DWT。矩阵必须是标准正交的，即它们的列是单位向量并相互正交，使得矩阵的逆是它的转置。

小波变换还可以用于多维数据，如数据立方体。具体操作方法为：先对第一维数据进行变换，然后对第二维进行变换，如此下去。计算的复杂性与立方体的单元个数呈线性关系。对于稀疏或倾斜数据和具有有序属性的数据，小波变换能够得到很好的结果。小波变换有许多实际应用，包括指纹图像压缩、计算机视觉、时间序列、数据分析和数据清理。

2.主要成分分析

假定待压缩的数据由N个元组或数据向量组成，取自k个维。主要成分分析(PCA，又称Karhunen－Loeve或K－L方法)从k维数据中寻找出c个正交向量，这里c≤k。通过该方法，原数据被投影到一个较小的空间，实现数据的压缩。PCA可以作为一种维归约形式使用。然而，不同于属性子集选择保留原属性集的一个子集来减少属性集的大小，PCA方法通过创建一个替换的、较小的变量集来“组合”属性的精华。原数据可以投影到此较小的集合中。主要处理步骤如下：

(1)对输入数据规范化，使得每个属性的数据值都落在相同的数值范围内。

(2)计算c个规范正交向量，作为规范化输入数据的基。这些向量是单位向量，两两间相互垂直。这些向量被称为主要成分。输入数据都可以表示为主要成分的线性组合。(3)对c个主要成分按照“重要性”进行递减排序。

(4)根据给定的用户阈值，消去“意义”较低的主要成分。使用最强的主要成分，应当可能重构原数据的很好的近似值。

PCA方法的计算量不大，并且可以用于有序和无序的属性，还可以处理稀疏和倾斜数据。高维数据可以通过将问题归约为2维来处理。与数据压缩的小波变换相比，PCA能较好地处理稀疏数据，而小波变换更适合高维数据的处理变换。2.4.3数值归约

数值规约通过选择替代的、较小的数据表示形式来减少数据量。主要包括有参数与非参数两种基本方法。所谓有参数方法，就是利用一个模型来评估数据，因此只需要存储模型参数即可，而不是实际数据(孤立点也可能被存放)。例如数线性模型，它可以估计离散的多维概率分布。无参方法用于存储利用直方图、聚类和选样归约后的数据集。

1.回归和对数线性模型

回归和对数线性模型可以用来近似给定数据。线性回归方法利用一条直线对数据进行拟合。例如，将随机变量Y(称做响应变量)表示为另一随机变量X(称为预测变量)的线性函数：

Y=α+βX

(2.5)这里，假定Y的方差是常量，系数α和β(称为回归系数)分别为直线的截距和斜率。系数可以用最小二乘法求得，使得分离数据的实际直线与该直线间的误差最小。多元回归是线性回归的扩展，响应变量是多维特征向量的线性函数。对数线性模型(loglinearmodel)近似离散的多维概率分布。该方法能够根据构成数据立方的较小数据块，对其一组属性的基本单元分布概率进行估计，并且可以由较低阶的数据立方体构造较高阶的数据立方体。这样，对数线性还可以进行数据压缩(因为较小阶的方体总共占用的空间小于基本方体占用的空间)，同时具有一定的数据平滑效果(因为与用基本方体进行估计相比，用较小阶的方体对单元进行估计选样变化小一些)。回归和对数线性模型都可以用于稀疏数据和异常数据处理。虽然两种方法都可以用于异常数据，但回归模型的效果好于对数线性模型。回归模型处理高维数据时计算复杂度较大，而对数线性模型具有好的可伸缩性，可以扩展到10维左右。

2.直方图直方图使用分箱方法近似数据分布，是一种常用的数据归约方法。属性A的直方图(histogram)将A的数据分布划分为若干个不相交的子集，或称桶。子集(桶)沿水平轴显示，而高度(和面积)表示值的平均频率。如果每个桶只代表单个属性值/频率对，则该桶称为单桶。通常，桶表示给定属性的一个连续区间。

【例2.5】下面是某商场销售的商品的价格清单(按照递增的顺序排列，括号中的数字表示改价格产品销售的数目)：2(3)，5(6)，8(2)，10(6)，13(9)，15(5)，18(4)，20(7)，21(10)，23(4)，26(8)，28(7)，29(3)，30(8)图2-3使用单桶显示了这些数据的直方图。为进一步压缩数据，通常让一个桶代表给定属性的一个连续值域。在图2-4中每个桶代表商品价格的一个不同的$10区间。

图2-3使用单桶的商品价格直方图—每个桶代表一个商品价格/频率对图2-4商品价格的等宽直方图，值被聚类使得每个桶都有$10宽构造直方图的数据集划分方法有以下几种：

(1)等宽。在等宽的直方图中，每个桶的宽度区间是一个常数(如图2-4中每个桶的宽度为＄10)。

(2)等深(或等高)。在等深的直方图中，每个桶中的数据个数为一个常数(即每个桶大致包含相同个数的临近数据样本)。

(3)V最优。给定桶个数，如果考虑所有可能的直方图，那么V最优直方图是具有最小方差的直方图。直方图的方差是每个桶代表的原数据的加权和，其中权等于桶中值的个数。

(4)MaxDiff。在MaxDiff直方图中，我们考虑每对相邻值之间的差。桶的边界是具有β-1个最大差的对，其中β是由用户指定的阈值。

V-最优和MaxDiff是更精确和实用的方法。对于近似稀疏和稠密数据以及高倾斜和一致的数据，直方图具有较高的效能。直方图可以推广到多属性数据集，多维直方图能够描述属性间的依赖。研究发现，这种直方图对于多达5个属性能够有效地近似表示数据。对于更高维、多维直方图的有效性尚需进一步研究。对于存放具有高频率的孤立点，单桶是有用的。

3.聚类

聚类技术将数据行视为对象。聚类分析所得到的组或类有下述性质：同一类或类中的对象比较相似，不同组或类中的对象彼此不相似。一般的类似性基于多维空间的距离表示，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示，直径是指一个聚类中两个任意对象的最大距离。质心距离是聚类质量的另一种度量，以组或类质心(表示“平均对象”，或聚类空间中的平均点)到每个聚类对象的平均距离。图2-5所示为某城市内的大学位置的2D图，每个聚类的质心用“＋”显示，两个数据聚类如图所示。图2-5某城市的大学位置2D图在数据归约时，用数据的聚类替换原始数据。该技术的有效性依赖于数据的性质。如果数据能够组织成不同的聚类，该方法将是有效的。

4.选样

选样可以作为一种数据归约技术使用，它采用数据的较小随机样本(子集)表示大的数据集。假定大的数据集D包含N个元组，几种选样方法如下:

(1)简单选择n个样本，不回放(SRSWOR)。由D的N个元组中抽取n个样本(n<N)，其中D中任何元组被抽取的概率均为1/N。即所有元组是等可能的。

(2)简单选择n个样本，回放(SRSWR)。该方法类似于SRSWOR，不同在于当一个元组被抽取后，记录它，然后放回去。这样，一个元组被抽取后，它又被放回D，以便它可以再次被抽取。这样，最后的n个样本数据集中可能会出现相同的数据行。

(3)聚类选样。如果D中的元组被分组放入M个互不相交的“聚类”，则可以得到聚类的m个简单随机选样，这里m<M。

(4)分层选样。如果D被划分成互不相交的部分，称做“层”，则通过对每一层的简单随机选样就可以得到D的分层选样。特别是当数据倾斜时，这可以帮助确保样本的代表性。例如，可以得到关于顾客数据的一个分层选样，其中分层对顾客的每个年龄组创建。这样，具有最少顾客数目的年龄组肯定能够得到表示。采用选样进行数据归约的优点是，得到样本的花费正比例于样本的大小n，而不是数据的大小N。因此，选样的复杂性子线性(Sublinear)于数据的大小。其他数据归约技术至少需要完全扫描D。对于固定的样本大小，选样的复杂性仅随数据的维数d线性地增加，而其他技术，如使用直方图，复杂性随d指数增长。用于数据归约时，选样最常用来回答聚集查询。在指定的误差范围内，可以确定(使用中心极限定理)估计一个给定的函数在指定误差范围内所需的样本大小。样本的大小n相对于N可能非常小。对于归约数据集的逐步求精，选样是一种自然选择。这样的集合可以通过简单地增加样本大小而进一步提炼。2.5数据离散化和概念分层

2.5.1数值数据的离散化和概念分层生成对于数值属性，由于数据的可能取值范围的多样性和数据值的更新频繁，构造数值属性的概念分层是比较困难的。数值属性的概念分层可以根据数据分布分析自动地构造。下面介绍五种主要的数值概念分层生成方法：分箱、直方图分析、聚类分析、基于熵的离散化和通过“自然划分”的数据分段。

1.分箱前面讨论了数据平滑的分箱方法。此方法也是离散化方法。例如，通过将数据分布到箱中，并用平均值或中值替换方法对箱值进行平滑，可以将属性值离散化。递归地应用这些操作处理每次的结果，就可以产生一个概念层次树。

2.直方图分析前面讨论的直方图也可以用于离散化处理。图2-6给出了一个等宽直方图，显示某给定数据集的数值分布。例如，大部分数据分布在0~2171。例如，在等宽直方图中，将值划分成相等的部分或区间(如(0,2171)，(2171,4342)，…，(8685,10860))。直方图分析算法递归地用于每一部分，将自动地产生多级概念分层，直到到达用户指定的层次水平后结束划分。图2-6显示某数据集数值的分布直方图

3.聚类分析聚类算法可以将数据划分成若干类或组。每一个类形成概念分层的一个节点，而所有的节点在同一概念层。每一个类还可以进一步分成若干子类，形成较低的概念层。类也可以合并在一起，以形成分层结构中较高的概念层。

4.基于熵的离散化熵(Entropy)是一种基于信息的度量，可以用来递归地划分数值属性A的值，形成分层的离散化。这种离散化形成属性的数值概念分层。给定一个数据元组的集合S，基于熵对A离散化的方法如下：

(1)A的每个值都可以认为是一个潜在的区间边界或阈值T。例如，A的值v可以将样本S划分成分别满足条件A<v和A≥v的两个子集，这样就创建了一个二元离散化。

(2)对给定的数据集S,所选择的阈值是这样的值，它使其后划分得到的信息增益最大。信息增益(InformationGain)为(2.6)其中，S1和S2分别对应于S中满足条件A<T和A≥T的一个划分。对于给定的集合，它的熵函数Ent可以根据集合中样本的类分布计算获得。例如，给定m个类，S1的熵为(2.7)其中，pi是类i在S1中的概率，等于S1中类i的样本数除以S1中的样本总数。Ent(S2)的值可以类似地计算。

(3)确定阈值的过程递归地用于所得到的每个划分，直到满足某个终止条件，如Ent(S)-I(S,T)>δ

(2.8)

基于熵的离散化可以压缩数据量。与其他方法不同的是，基于熵的方法利用了类别信息，这使得区间边界定义的分类挖掘结果更加准确。这里介绍的信息增益和熵也用于判定树归纳。

5.通过自然划分分段尽管分箱、直方图、聚类和基于熵的离散化都可以帮助构造数值概念层次树，但是用户希望得到数值区域被划分为相对一致的、易于阅读的、看上去更自然直观的区间。例如，更希望将年薪划分成像($4000，$8000)的区间，而不是像由某种复杂的聚类技术得到的($4263.52，$6471.38］。利用3-4-5规则可以将数值量分解为相对统一、自然的区间。该规则一般将数值范围递归地和逐层地将给定的数据区域划分为3、4或5个等宽区间。该规则如下：

(1)若一个区间在最高有效位上包含3、6、7或9个不同的值，则将该区间划分成3个区间(对于3、6和9，划分成3个等宽区间；而对于7，按2-3-2分组，划分成3个区间)。

(2)如果它在最高有效位上包含2、4或8个不同的值，则将区间划分成4个等宽区间。

(3)如果它在最高有效位上包含1、5或10个不同的值，则将区间划分成5个等宽区间。

(4)将该规则递归地用于每个区间，就可以得到数值属性创建的概念分层树。由于在数据集中可能有特别大的正值和负值，最高层分段简单地按最小和最大值划分可能导致与实际结果背离。例如，在考试成绩中，少数人的成绩可能比较接近满分。按照最高分分段可能导致高度倾斜的分层。因此最初的区间分解需要根据包含大多数取值的区间(例如，从5%到95%之间的区域)进行。不在这个区域的特别高和特别低的值划分为单独的区间。2.5.2分类数据的概念分层生成分类数据(CategoricalData)是离散数据。一个分类属性具有有限个(但可能很多)不同值，且值之间无序。例如电话号码、家庭住址和商品类型。分类数据的概念分层主要有以下几种方法。

(1)属性的部分序由用户或专家在模式级显式地说明。通常，分类属性或维的概念分层涉及一组属性。通过在(数据库)模式定义时指定各属性的有序关系，可以很容易地构造概念分层。例如，关系数据库或数据仓库的维location可能包含一组属性：street,city,province_or_state和country。可以在模式级说明一个全序，如street<city<province_or_state<country，来定义层次结构。

(2)通过数据聚合描述层次树。这是人工地定义概念分层结构方法。在大型数据库中，显式的值穷举定义整个概念分层是不现实的。然而，对于一小部分中间层数据，可以进行显式的分组。例如，在模式级说明了province和country形成一个分层后，可以人工地添加某些中间层。

(3)定义一组不说明顺序属性集。用户可以定义一个属性集，形成概念分层，但并不显式说明它们的顺序。系统将自动地产生属性的序，以便构造有意义的