2.1 知识发现与数据挖掘
2.1.1 数据库知识发现过程
数据库知识发现（knowledge discovery of database，KDD）［2］是从大量原始数据中挖掘出隐含的、有用的、尚未发现的信息和知识，其不仅被许多研究人员看作数据库系统和机器学习方面一个重要的研究课题，同时也被许多工商界人士看作一个能带来巨大回报的重要领域。
数据库中的知识发现技术［7］是1989年8月在美国底特律市召开的第一届知识发现与数据挖掘（knowledge discovery and data mining）国际会议上首次提出的，是从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的处理过程，是一种高级数据处理过程，是人工智能技术与数据库技术的结合，也是从数据库中提取有价值知识的过程。其研究的问题有定量知识和定性知识的描述、数据库知识发现的方法和知识发现的应用。
数据库知识发现过程如图2-1所示，整个过程可以粗略地理解为三个阶段［2］，即数据准备（data preparation）、数据挖掘、挖掘结果的解释与评估（interpretation and evaluation）。
图2-1 数据库知识发现的过程图
1.数据准备
从完成的功能角度划分，数据准备阶段主要包括四个方面，即数据的净化［8，9］、数据的集成［10］、数据的应用变换和数据的精简［11～13］。
数据的净化是数据准备阶段的基础部分。这部分的功能是找出数据源中不正确的、不完整或其他方面不能达到数据挖掘质量要求的数据并清除，如删除重复记录等。数据净化能提高数据的质量，从而有助于提高数据挖掘结果的准确性。
数据的集成解决的是数据的异构问题，即将来自多个不同数据源的数据合并后存储，并消除其中的不一致性。
数据的应用变换功能是根据数据挖掘运算的需要完成数据相应的转换，这种转换的原因可以有很多，如金融工程中的数据需要考虑地域性，不同类型的变量进行聚类分析差异度的计算，等等。
数据的精简是运用某种方法减小参与运算的数据量，或者通过选维技术从初始数据中找出对数据挖掘贡献比较大的维，提高数据挖掘方法的效率与质量。
2.数据挖掘
在经过数据预处理的数据集上，结合数据挖掘的目的，确定将要进行的数据挖掘功能，并选择相应的方法进行数据挖掘。这一阶段的工作一般是通过计算机编程实现的。
在数据挖掘过程中，首先根据数据挖掘的目的确定挖掘任务，然后结合实际对象的特点，考虑合适的数据挖掘方法。因为不同的数据有不同的特点，如高维数据相比低维数据有很大不同，正如前所说，通常，低维的数据挖掘方法直接应用于高维数据进行数据挖掘时，其挖掘的结果很难令人满意；同时，不同的用户对数据挖掘有着不同的要求，如有的用户可能希望获取描述型的、容易理解的知识，而有的用户的目的是获取预测准确度尽可能高的预测型知识。
因为数据库知识发现的核心是数据挖掘方法，所以，一直以来，该领域的研究重点和难点都是数据挖掘相关问题。但是，成功的数据挖掘的前提是方法使用得当，即对各种挖掘方法的要求或前提假设有充分的理解，或者说，选择一个真正适合解决问题的方法模型是数据挖掘成功的关键。
3.挖掘结果的解释与评估
这个阶段的功能是完成数据挖掘结果的解释、分析和评价，并能根据用户的需求转换成为他们能够理解的知识。在实际应用问题中，还需要将得到的知识和相关专业知识相结合，集成到业务信息系统的组织结构中，使数据挖掘的结果在实际应用中发挥真正的作用。
数据挖掘阶段发现的知识，还需要通过用户或机器的评估找出并剔除其中的冗余模式；同时，如果得到的模式不能满足用户要求，这时则需要重新开始整个发现过程，包括数据源的重选、更换数据转换方法、数据挖掘方法参数的重设等，直到获得用户满意的数据挖掘结果。
数据挖掘定义为，“在数据中发现有效的、新颖的、潜在有用的、可理解的模式的非平凡过程”［2］。在一开始，数据挖掘被看作数据库中知识发现的一个基本步骤［14］。后来，数据挖掘成为KDD的代名词。一般来说，KDD这一名词多用于人工智能和机器学习领域；而统计、数据分析、数据库和管理信息系统领域的研究人员则更加愿意使用数据挖掘这一名词。
随着数据挖掘相关研究的不断深入，研究者取得了一些研究成果，如Journal of Intelligent Information Systems、EEE Transaction on Knowledge and Data Engineering、International Journal of Intelligent Systems等。第一本专门的关于数据挖掘的期刊Data Mining and Knowledge Discovery由Usama Fayyad博士于1996年创办，早在1997年就开始面向全球正式发行，目前该刊物已经被公认为数据挖掘领域的顶级刊物。另外，后来出现的刊物，如美国计算机协会（Association for Computing Machinery，ACM）创办的SIGKDD Explorations、Knowledge and Information Systems、International Journal of Business Intelligence and Data Mining和International Journal of Data Warehousing and Mining等，在数据挖掘领域也同样具有重要的影响力。
回顾数据挖掘发展历史，从1996年只有一个专门的数据挖掘会议——KDD 1996，到2005年关于数据挖掘的专题会议的数量超过20个，而全年发表的相关文章数翻了百倍，在亚洲尤其是在中国，数据挖掘的研究与应用发展的速度更为迅猛［15］。
数据挖掘是一门具有广泛应用背景的学科，从某种角度来看，正是实际应用的需要推动了数据挖掘的产生和发展。商业智能（business intelligence，BI）就是其中一个典型的应用。1996年，Gartner Group提出了BI［16，17］，并给出了其定义：“一类由数据仓库（数据集市）、查询报表、数据分析、数据挖掘等部分组成的，以帮助企业决策为目的的技术及其应用。”事实上，数据挖掘是实现商业智能的一项关键技术，因为它把先进的信息技术应用到整个企业，为企业提供信息获取能力，更重要的是，通过对信息的开发将其转变为企业的竞争优势。
随着互联网（Internet）的发展，数据在实际应用中遇到的各种类型的高维数据呈爆炸式增长。对这类数据进行分析、组织和总结，提取各种文档中所隐含的联系、规则和模式，是数据挖掘在“Internet时代”的另一个重要应用。目前国内外数据挖掘领域对高维数据挖掘的研究已经成为热点，相关研究包括高维稀疏数据挖掘［2，18］、复杂数据对象的高维分析［19］、多媒体数据库的数据挖掘［20］、时间序列的挖掘［21］、文本数据库挖掘［22］、Web挖掘［23］及数据流挖掘［24］等。
2.1.2 数据挖掘任务
数据挖掘主要有两类模式：一类为描述型（descriptive）模式，另一类为预测型（predictive）模式［25］。
描述性挖掘任务是对数据库中数据进行一般特性刻画，或者根据数据间的差异度将其分组。但是，描述型模式不能直接用来进行预测。
预测性挖掘任务［25］则是根据数据项的值推理出某种模式，然后根据这种模式预测未知某种结果的模式。例如，根据血象检查的数据，有这样的模式：白细胞比例在6～12范围属于正常，超出12则表示病毒感染，需要用抗生素治疗。当有人感冒感觉不舒服时，医生就根据这个模式判断这个病人是否需要用抗生素治疗。
按照功能或者可以发现的不同模式，数据挖掘主要分类如下。
1.关联规则发现
Agrawal等首先提出了关联规则（association rule）挖掘问题［26，27］，最初用于挖掘顾客交易数据库中数据集间的关系，后来用于查找不同数值域或者数据属性之间的关联，以发现多个数值域之间有趣的、有价值的联系。
关联规则的目标是在数据库中寻找数据对象间的关联模式。实际上，关联性是一种统计意义上的关系，并以置信度因子衡量关联的程度。因此，关联规则给出的是一个概率事件，如“因为某些事件的发生而导致其他一些事件的发生的概率”等；又如著名的“啤酒与尿布”关联：通过分析超市的购物数据，发现2/3的顾客在购买啤酒的同时也会购买尿布。关联模式主要用于零售业交易数据分析，为物品的合理摆放位置（营销策略）提供决策支持，刺激产品的销售。当前，在购物篮或事务数据分析以及金融等领域中已经广泛采用关联规则进行规则分析。
2.分类和预测
分类（categorization or classification），简单地说，就是按照某种标准给对象贴标签，然后根据该标签来区分归类，即对数据集中的数据进行数据挖掘获得有关该类数据的描述或模型，然后再根据这种描述或者模型进行分类。
预测是根据历史数据找出其中的规律，建立相应的模型，并根据此模型来预测未来数据的种类和模式等。其使用的主要方法有分类和回归两种。
不论是分类还是预测，都能导出多种规则，如分类（if-then）规则、决策树或神经网络等。数据对象的类标记通常是分类预测的结果。而在实际应用中，缺失或者未知的值则需要通过预测来获得。
3.离群点分析
数据库中可能包含一些与数据的一般行为或模型不一致的数据对象，这部分数据对象称为离群点（outlier）［28］。离群点在大部分数据挖掘方法中被当作噪声或异常值处理。但是，在一些特殊应用中如恶意交通肇事案、金融行业的恶意欠款等，则往往对这种小概率或异常事件更感兴趣。离群点数据分析称作离群点挖掘（outlier mining）。离群点的挖掘方法分为以下几类。
（1）基于统计方法的离群点检测。对给定的数据集合利用统计的方法得到一个概率分布模型，孤立点的确定则可以在参照模型的基础上采用不一致性方法来检验。检验的条件是已知分布参数、数据集参数和预期的孤立点的数目。
（2）基于距离的离群点检测。对于给定的数据对象集合S，对象O中存在至少与P部分的距离大于d，则对象O称为基于P和d参数距离的离群点。这种方法与统计检验无关，而仅仅考虑距离，将没有“足够多”邻居的对象称为“基于距离的离群点”［29］，这里的邻居的数目是根据给定对象间的距离来判断的。
基于距离的离群点检测以距离作为判断的依据，该方法有效解决了统计方法中存在的多个标准分布的不一致性检验的问题。
（3）基于偏移的离群点检测。离群点的判定是通过检验一组对象的主要特征来完成的，这一点类似于模式识别［30］。在给定的一组特征描述的基础上，当被考察对象与特征描述相差超过给定的阈值时，则被认为是离群点。
4.数据演变分析
数据演变分析（evolution analysis）是指对象变化的规律或趋势随时间的变化而变化。分析包括与时间相关的数据的特征化、关联、区分、聚类或分类等操作，其方法包括序列或周期模式、匹配时间序列数据分析和基于相似性的数据分析［31，32］。
5.聚类分析
聚类（clustering）是数据挖掘领域最为常见的技术之一，用于发现在数据库中未知的对象类。聚类也可应用于分类操作，同一类数据形成一个聚类，不同的聚类形成分类。由于聚类的有关知识是本书的基础。因此，下面综述聚类分析。