KDD 是一个以知识使用者为中心，人机交互的探索过程，包括了在指定的数据库中用数据挖掘算法提取模型，以及围绕数据挖掘所进行的预处理和结果表达等一系列的步骤。

数据挖掘作为KDD的一个步骤。尽管数据挖掘是整个过程的中心，但它通常只占KDD 过程15%~25%的工作量。

KDD步骤：

ps：虽然数据挖掘作为KDD的一部分，但出国签证时KDD职业通过率远比数据挖掘职业的通过率高。

数据挖掘的特点：

第一，数据挖掘的数据源必须是真实的。

数据挖掘所处理的数据通常是已经存在的真实数据（如超市业务数据），而不是为了进行数据分析而专门收集的数据。因此，数据收集本身不属于数据挖掘所关注的焦点，这是数据挖掘区别于大多数统计任务的特征之一。

第二，数据挖掘所处理的数据必须是海量的。

如果数据集很小的话，采用单纯的统计分析方法就可以了。但是，当数据集很大时，会面临许多新的问题，诸如，数据的有效存储、快速访问、合理表示等。

第三，查询一般是决策制定者（用户）提出的随机查询。

查询要求灵活，往往不能形成精确的查询要求，要靠数据挖掘技术来寻找可能的查询结果。

第四，挖掘出来的知识一般是不能预知的，数据挖掘发现的是潜在的、新颖的知识。

这些知识在特定环境下是可以接受、可以理解、可以运用的，但不是放之四海皆准的。

数据挖掘基本概括为：Techniques（技术） Applications（应用）Principles（原理）

数据挖掘的分类 ：

（1）根据挖掘的数据库类型分类

数据库系统本身可以根据不同的标准分类，例如,按照数据模型或处理的数据所涉及的应用类型分类。每一类可能需要不同的数据挖掘技术。例如，根据数据模型分类，可以有关系的、面向对象的、对象-关系的、或数据仓库的数据挖掘。

如果根据所处理的数据的特定类型分类，有空间的、时间序列的、文本的、多媒体、或Web数据等数据挖掘。

（2）根据挖掘的知识类型分类

例如特征分析、关联分析、分类分析、聚类分析、异常点分析、趋势和演化分析、偏差分析、类似性分析等。

此外，数据挖掘也可以根据所挖掘的知识的粒度或抽象级别进行区分，包括泛化知识（在高抽象层），原始层知识（在原始数据层），或多层知识（考虑若干抽象层）。

（3）根据所用的技术分类

这些技术可以根据用户交互程度（例如，自动系统、交互探查系统、查询驱动系统）

或所用的数据分析方法（例如，面向数据库或数据仓库的技术、机器学习、统计、可视化、模式识别、神经网络等等）描述。

复杂的数据挖掘通常采用多种数据挖掘技术，或采用有效的、集成的技术，以综合若干不同方法的优点。

（4）根据数据挖掘的应用领域分类

例如，可能有些数据挖掘方法特别适合财政、电讯，有些数据挖掘方法特别适合DNA、股票市场等。

不同的应用有适合该应用不同的数据挖掘方法。而通用的、全面的数据挖掘可能并不适合特定领域的挖掘任务。

数据挖掘的应用：生物信息学、Web搜索、入侵检测、汽车自动驾驶、火星机器人、决策助手、古文献修复等。

数据挖掘算法的组件化思想

聚类分析：聚类指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别

基于划分的算法（K-Means、K-Medoids、K-Modes、K-Prototypes、CLARA、CLARANS、focused CLARANS）基于层次、密度、方格、模型的算法

分类分析：根据一些给定的已知类别标号的样本，训练某种学习机器（即得到某种目标函数），使它能够对未知类别的样本进行分类。这属于supervised learning（监督学习）

决策树算法（ID3、C4.5、EC4.5、PC4.5、CHAID、CART、Elisee、SIPINA、QR-MDL等近20种）、贝叶斯算法、支持向量机、人工神经网络

数据挖掘算法的组件化思想：许多著名的数据挖掘算法都是由五个“标准组件”构成的，即：

（1）模型或模式结构：通过数据挖掘过程所得到的知识通常被称为模型（model）或模式(pattern)。例如:线性回归模型、层次聚类模型、频繁序列模式。

模型是对整个数据集的高层次、全局性的描述或总结。例如，模型可以将数据集中的每一个对象分配到某个聚类中。模型是对现实世界的抽象描述，例如，Y=aX+b就是一个简单的模型，其中X和Y是变量，a和c是模型的参数。

模式是局部的，它仅对一小部分数据做出描述。例如，购买商品A和B的人也可能经常购买C，就是一个模式。模式有可能只支持几个对象或对象的几个属性。

全局的模型和局部的模式是相互联系的，就好比一个硬币的两个面。例如，为了检测出数据集内的异常对象（局部模式），需要一种对数据集内正常对象的描述（全局模型）。

模式（如果X>c，则Y>d的概率为p）的参数为c，d和p。

通常把参数不确定的模型叫做模型的结构。把参数不确定的模式叫做模式的结构。（一般形式）

（2）数据挖掘任务

根据数据分析者的目标，可以将数据挖掘任务分为：1、模式挖掘：频繁模式、异常模式…2、模型挖掘：预测建模(有监督)：描述建模(无监督)

模式挖掘：致力于从数据中寻找模式，比如寻找频繁模式，异常模式等。

频繁模式指在某个数据集中频繁出现的模式，这些模式可以是一个项集、一个子序列或者一个子结构(子图)。例如，在交易数据集中，牛奶和面包经常在一起出现，称之为频繁的项集。人们经常在购买了个人电脑之后，就会购买打印机，称之为频繁的子序列。在某些图、树或格结构中频繁出现的一些子图、子树或子格则被称为频繁的子结构

预测建模：根据现有数据先建立一个模型，然后应用这个模型来对未来的数据进行预测。

当被预测的变量是范畴型(category)时，称之为分类。分类模型有时也称作分类函数或分类器。分类的典型应用如，信用卡系统中的信用分级、市场调查、疗效诊断、寻找店址等。因为分类的过程中，用到了训练集，进行了学习，所以分类是一个有监督的学习过程。

当被预测的变量是数量型(quantitative)时，称之为预测（回归）。回归的典型应用如性能评测、概率估计等。

分类：构造、使用模型来对某个样本的类别进行判别。主要用于对离散的数据进行预测。典型应用：信誉评估、医学诊断

回归（预测）：构造、使用模型来对某个样本的值进行估计，例如预测某个不知道的值或者缺失值。主要用于对连续或有序的数据进行预测。典型应用：性能预测

聚类：根据数据特征找出数据间的相似性，将相似的数据聚成一个类。作为一个独立的工具对数据分布进行分析，可以作为其他算法（如分类等）的预处理步骤，模式识别、空间数据分析、图像处理、经济科学(尤其是市场研究)、WWW

描述建模：目标是描述数据的全局特征。描述建模的典型例子是聚类分析。

描述和预测的关键区别是：预测的目标是唯一的变量，如信用等级、疾病种类等，而描述并不以单一的变量为中心。

第一步，建立模型阶段：用来构造模型的数据集被称为训练集。模型一般表示为：分类规则, 决策树或者数学公式

第二步，使用模型阶段：首先测试模型的准确性，用测试集和由模型进行分类的结果进行比较，两个结果相同所占的比率称为准确率。测试集和训练集必须不相关。如果准确性可以接受的话, 使用模型对新数据进行分类

由于模型（模式）代表的是函数的一般形式，它的参数空间非常大，可选的参数值有很多。那么什么样的参数值比较好呢，需要一个评价指标，这个评价指标就是评分函数。

（3）评分函数

评分函数用来对数据集与模型（模式）的拟合程度进行评估。

如果没有评分函数，就无法说出一个特定的已拟合的模型是否比另一个要好。或者说，就没有办法为模型（模式）选择出一套好的参数值来。

常用的评分函数有：似然（likelihood）函数、误差平方和、准确率等。

在为模型（模式）选择一个评分函数时，既要能够很好地拟合现有数据，又要避免过度拟合（对极端值过于敏感），同时还要使拟合后的模型（模式）尽量简洁。

不存在绝对“正确”的模型（模式），所有模型（模式）都是对现有数据的一种近似。从这个角度来讲，如果模型（模式）没有随着现有数据的变化而剧烈变化，这个模型（模式）就是能够接受的了。换句话说，对数据的微小变化不太敏感的模型（模式）才是一个好的模型（模式）。

（4）搜索和优化方法

评分函数衡量了提出的模型（模式）与现有数据集的拟合程度，搜索和优化的目标是确定模型（模式）的结构及其参数值，以使评分函数达到最小值（或最大值）。如：平方差最小、准确率最高，等等。

如果模型（模式）的结构已经确定，则搜索将在参数空间内进行，目的是针对这个固定的模型（模式）结构，优化评分函数。

如果模型（模式）的结构还没有确定的话（例如，存在一族不同的模型（模式）结构），那么搜索既要针对结构空间又要针对和这些结构相联系的参数空间进行。

针对特定的模型，发现其最佳参数值的过程通常被称为优化问题。

而从潜在的模型（模式）族中发现最佳模型（模式）结构的过程通常被称为搜索问题。

常用的优化方法有：爬山（Hill-Climing）、最陡峭下降（Steepest-Descend）、期望最大化（Expectation-Maximization, EM）

常用的搜索方法有：贪婪搜索、分支界定、宽度（深度）优先遍历

（5）数据管理策略

传统的统计和机器学习算法都假定数据是可以全部放入内存的，所以不太关心数据管理技术。

但是，对于数据挖掘工作者来说，GB甚至TB数量级的数据是常见的。由于外存的访问速度要慢的多，直接将传统的内存算法应用于这些外存数据，性能将变得非常差。

因此，针对海量数据，应该设计有效的数据组织和索引技术，或者通过采样、近似等手段，来减少数据的扫描次数，从而提高数据挖掘算法的效率。

组件总结：

在实践中，数据挖掘算法的组件化思想是非常有用的。它通过将算法分解成一些核心组件而阐明了算法的实现机制。更重要的是，该观点强调了算法的本质，而不仅仅是算法的罗列。

当面对一个新的应用时，数据挖掘人员应该从组件的角度，根据应用需求，考虑应该选取哪些组件，来组成一个新的算法，而不是考虑选取哪个现成的算法。

确定模型（模式）结构和评分函数的过程通常由人来完成

而优化评分函数的过程通常需要计算机辅助来实现。实践中，通常要根据前一次的计算结果来改进模型（模式）结构和评分函数，所以整个过程要重复很多次。

有趣的是，不同的研究团体将注意力放在不同的数据挖掘算法组件上。

统计学家强调推理过程，关注模型（模式）、评分函数、参数估计等，很少突出计算效率问题。

而从事数据挖掘的计算机科学家则更注重高效的空间搜索和数据管理，不太关心模型（模式）或评分函数是否合适。

实际上，一个数据挖掘算法的所有组件都是至关重要的。

对于小的数据集，模型（模式）的解释和预测能力相对于计算效率来说可能要重要的多。

但是，随着数据集的增大，计算效率将变得越来越重要。对于海量数据，必须在模型（模式）的完备性和计算效率之间进行平衡，以期对现有数据达到某种程度的拟合。

1989 IJCAI Workshop on Knowledge Discovery in Databases (Piatetsky-Shapiro)

Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley,1991)

1991-1994 Workshops on Knowledge Discovery in Databases Advances in Knowledge Discovery and Data Mining (U. Fayyad,G. Piatetsky-Shapiro,P. Smyth, and R. Uthurusamy, 1996)

1995-1998 International Conferences on Knowledge Discovery in Databases and Data Mining (KDD’95-98)

Journal of Data Mining and Knowledge Discovery (1997)

1998 ACM SIGKDD, SIGKDD’1999-2001 conferences, and SIGKDD Explorations

More conferences on data mining

PAKDD (1997), PKDD (1997), SIAM-Data Mining (2001), (IEEE) ICDM (2001), etc.

--------------------------------------------------------------------------------

Reference

周志华，机器学习导论课程PPT

http://www.cs.uiuc.edu/homes/hanj/, Jiawei han’s lecture ppt.

http://www.comp.nus.edu.sg/~atung/, Anthony Tung’s lecture ppt.

T. Dasuand T. Johnson.  Exploratory Data Mining and Data Cleaning.John Wiley & Sons, 2003 U. M.Fayyad, G. Piatetsky-Shapiro,

P. Smyth, and R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996

U.Fayyad, G. Grinstein, and A. Wierse, Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann, 2001

J. Han and M. Kamber. Data Mining: Concepts and Techniques. 2nd ed.,Morgan Kaufmann, 2005

D. J.Hand, H. Mannila, and P. Smyth, Principles of Data Mining, MIT Press, 2001

T.Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer-Verlag, 2001 

T. M.Mitchell, Machine Learning, McGraw Hill, 1997

G. Piatetsky-Shapiro and W. J. Frawley. Knowledge Discovery in Databases. AAAI/MIT Press, 1991

S. M.Weiss and N. Indurkhya, Predictive Data Mining, Morgan Kaufmann, 1998

I. H.Witten and E. Frank,  Data Mining:Practical Machine Learning Tools and Techniques with Java Implementations, 2nd ed., Morgan Kaufmann, 2005