龙珠

From Data Mining to Knowledge Discovery in Databases

Usama Fayyad, Gregory Piatetsky-Shapiro, and Padhraic Smyth

“基于数据库的从数据挖掘到知识发现”，本周的Paper。

这篇文章，我自己看完的时候，觉得只是一篇overview，没有什么具体的算法，虽然讲了KDD和DM的关系，但觉得没什么用。但后来李师兄讲这篇文章的时候，有些像是醍醐灌顶一样。

师兄说，这只是篇概论，没有什么算法。文章的特点就是很客观、很理性、很全面。它其实解决了数据挖掘（DM）“从哪里来到那里去”的问题，说明了我们为什么要进行数据挖掘。强迫去运用一个技术是一种很二的表现，最牛逼的不是说会编程，而是能对潜在的应用领域提供一个解决方案（前两天看的文章中也提到，skilled和problem solving的不同。会编程、会写DM算法只能算是skilled，能提供解决方案才算是problem solving）。而数据挖掘存在的意义是什么呢？是说，无论我们每个人有多么不同，多么特立独行，在许多的人集合在一起的时候，总会有一种不可抗拒的总体的趋势和模式，比如二八原则、黄金比例、高斯分布等。而我们进行数据挖掘，就是为了发现这些规律，而这，就是知识发现（KDD）的过程。

师兄和我站的角度不一样。我还处在怎么去用的过程，想把自己变成skilled的阶段，师兄已经站得有高度了，开始讨论为什么要去用和怎么去用的问题了，已经是problem solving的阶段。自己当时看完还觉得文章没有什么大用，有些失望，其实只是自己眼界不够，一叶障目，不见泰山。师兄说，经典的，一般都是简单的。这篇文章解决了我们对为什么要进行DM的困惑，不让我们再为了DM而DM，这就是经典。我还需要慢慢体会。

——写在前面    Arthur   2011.12.01

文章简介：an overview of this emerging field, clarifying how data mining and knowledge discovery in databases are related both to each other and to related fields, such as maching learning, statistics, and databases.

这是个关于该领域的概论，阐明了在数据库中，数据挖掘和知识发现的相互关系，以及他们和相关领域的关系，例如机器学习、统计学和数据库。

一、为什么需要KDD？

传统：从数据中获取知识需要人工分析和理解

缺点：慢、昂贵、高度主观性

数据库快速增长包括：

1.记录/物体的数目N

2.物体的属性数目d

KDD试图解决的问题：数据过载（data overload）

二、现实世界中的数据挖掘和知识发现

科学领域：

• 天文学：SKICAT，图像分析，分类。可处理TB级数据。

金融领域：

• Marketing: database maketing system, market-basket analysis systems
  
• Investment: LBS Capital Management
• Fraud Detection: HNC Falcon and Nestor PRISM system, FAIS system
• Manufacturing: CASSIOPEE troubleshooting system
• Telecommunications: telecommunication alarm-sequence analyzer(TASA)
• Data Cleaning: MERGE-PURGE system

其他领域：

• IBM's ADVANCED SCOUT: NBA球员评价系统

（新）通过智能应用从富信息环境中获得有用信息：FIREELY, 音乐推荐

三、数据挖掘和知识发现

二者不同。

本文中，KDD指的是从数据中发现有用知识的整个过程，而数据挖掘是指该过程中特殊的一步。数据挖掘是应用特殊的算法，从数据中提取出特征。

KDD中不只包括DM，还包括：data preparation, data selection, data cleaning, incorporation of appropriate prior knowledge, proper interpretation of the results of mining.

I) KDD的跨学科特性（The interdisciplinary nature of KDD）

KDD设计的研究领域：maching learning, pattern recognition, databases, statistics, AI, knowledge acquisition for expert systems, data visualization, high-performance computing.

统一目标（unifying goal）：从大规模数据库的低等级的数据之中提取出高等级的知识。

• KDD中的数据库挖掘部分倚重的学科：maching learning, pattern recognition, statistics。以从数据中发现特征。

A natural question is: How is KDD different from pattern recognition or machine learning(and related fields)?

Answer: 这些领域为整个KDD过程中的数据挖掘步骤提供了一些数据挖掘方法。KDD关注与从数据中进行知识发现的整个过程。包括：how the data are stored and accessed, how algorithms can be scaled to massive data sets and still run efficiently, how results can be interpreted and visualized, how the overall man-machine interaction can usefully be modeled and supported.

• 相关的AI领域，包括machine discovery(targets the discovery of empirical laws from observation and experimentation), and causal modeling(for the inference of causal models from data).
  
• 统计学(Statistics)

统计学和KDD有很多相同点。

从数据中进行知识发现，其实也是一种统计探索。

当试图从一个特殊样本中得到一般特征时，统计学提供了一种语言和框架，来判别结果的不确定性。

一个关心(a concern)是：如果对任意数据（哪怕是随机数据）进行长时间的探索，总能从统计上找到一些看起来像但其实不是的所谓“特征”。

不同：KDD, be viewed as encompassing a broader view of modeling than statistics. aims to provide tools to automate(to the degree possible) the entire process of data analysis and the statistician's "art" of hypothesis selection.

• Driving force behind KDD：数据库领域
• 数据库的相关领域：数据仓库

1. Data cleaning: 处理丢失数据，尽可能处理早上和错误数据

2. Data access

当所有部分模块都搞定了，我们该如何处理这些数据呢？

这就是：KDD。

II) 基本定义

KDD: is the nontrivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data.

Data: a set of facts(for example, cases in a databases)

Pattern: an expression in some language describing a subset of the data or a model applicable to the subset. it will be knowledge if it exceeds some interesting threshold, which is by no means an attempt to define knowledge in the philosophical or even the popular view.

Data mining: a step in the KDD process that consists of applying data analysis and discovery algorithms that, under acceptable computational efficiency limitations, produce a particular enumeration of patterns(or models) over the data.

四、知识发现过程(KDD process)

交互的和循环迭代的。

基本步骤：

1. 理解应用领域及相关知识，确定目标
   
2. 创建目标数据库
3. 数据清洗和预处理
4. 数据精简和突出
5. 找到与目标匹配的数据挖掘算法
6. 探索分析和模型、假设的选择
7. 数据挖掘
8. 解释挖掘到的特征（可能会重复1~7步骤）
9. 发现的知识的使用

五、KDD过程中的数据挖掘

主要讲数据挖掘的主要目标、达到目标的方法和与这些方法相关的数据挖掘算法。

KDD的目标有两种类型：

1. 验证(Verification): verify the user's hypothesis

2. 发现(discovery): 包括：

• 预测(prediction): system find the patterns for predicting the future behavior of some entities.
• 描述(description): 系统发现特征，并以人类可以理解的方式展现出来。
  

数据挖掘涉及到从观察到的数据中建立合适的模型和提取特征。

模型建立的两种主要数学方法：

• 统计学(Statistical)
  
• 逻辑学(Logical)

1、数据挖掘方法

1. 分类(Classification)：将数据归入已定义的几类之一。
   
2. 回归(Regression)：将一个数据映射到一个实数值预测变量
3. 聚类(Clustering)：通过有限的类或簇来描述数据。与此相关的是概率密度估计（probability density estimation）
4. 概要(Summarization)：为数据的子集找到一种简介的描述
5. 依赖模型(Dependency Modeling)：建立模型，描述变量之间的依赖性。包括结构层面和量的层面。
6. 变化监测(Change and Deviation detection)：检测数据最重要的变化

2、数据挖掘算法的模块

1. 模型描述(Model representation)：描述发现的特征
   
2. 模型评价(Model evaluation)：评价一个特征如何满足KDD的目标
3. 搜索(Search)：包括参数搜索(parameter search)和模型搜索(model search)

六、一些数据挖掘方法

方法很多，本文只挑了几个流行的技术。

1. 决策树和规划（Decision Tree and Rules）
2. 非线性回归和分类方法（Nonlinear Regression and Classification Methods）
3. 基于例子的方法（Example-Based Methods）：用数据库中有代表性的例子进行模拟接近，形成一个模型。但有潜在的缺点是：还缺少一个优良的计算数据点间距的算法。
4. 概率图形依赖模型（Probabilistic Graphic Dependency Models）：专注于通过图形结构显示概率依赖关系
5. 相关学习模型（Relational Learning Models）：Although decision tree and rules have a representation restricted to prepositional logic, relational learning(also known as inductive logic programming) use the more flexible pattern language of first-order logic.

七、讨论

每种技术都有其使用的问题，使其在该问题中的表现比其他方法好。

没有一种通用的数据挖掘算法。对一个特殊的应用选择一种合适的算法是一种艺术(art)。

本文中对数据挖掘的讨论比较简短，再次需要申明一下两点：

1. our overview of automated search focused mainly on automated methods for extracting patterns or models from data
   
2. beware the hype: the state of the art in automated methods in data mining is still in a fairly early stage of development

八、应用问题

技术标准要考虑到：

• 充足的数据
  
• 属性间的相关性
• 低噪声
• 面向时间变化的数据
• 先验知识

1、研究和应用的挑战

目前在研究和应用领域，KDD面对的主要挑战包括(均提供了可能的解决方案)：

1. 更大的数据库
   
2. 高维度
3. 过适/过度拟合（overfitting）
4. 评价统计意义（accessing of statistical significance）
5. 变化的数据和知识
6. 丢失数据和噪声
7. 领域间复杂关系
8. 特征的易理解性
9. 与用户交互以及先验知识
10. 和其他系统的整合

九、总结评论：人工智能在KDD中的潜在角色

出了机器学习，其他的人工智能（AI）领域也有可能会对KDD的各方面产生较大的影响。

1. 自然语言（Natural Language）
   
2. 计划（Planning）
3. 智能主体（Intelligent Agent）
4. 人工智能的不确定性（Uncertainty in AI）
5. 知识表示（Knowledge Representation）

其他领域，包括人机交互、知识获取技术、机器推理等，也会对KDD有所贡献。

结语：本文中，我们主要的目的是澄清知识获取（KDD）和数据挖掘（DM）的关系。

我们对KDD的过程进行了概览介绍，并简介了数据挖掘的方法。

后记：

看国外的Paper的时候，头总是晕晕乎乎的，脑子不够使，很容易理不清逻辑关系。但在做框架的时候，由于需要对原文进行概括，所以还是很需要明白文章的逻辑关系的。昨晚之后，发现，文中也有很多处重复的地方（例如数据挖掘方法的三个模块，文章出现两次），也有一些逻辑上稍微欠妥的地方。但是，虽有瑕疵，瑕不掩瑜。文章整体还是很严谨，逻辑也很清晰，这也是以后要学习的地方。以后可以考虑给自己的文章做一个框架，更容易看出来自己逻辑上有没有什么漏洞和缺陷。

看一篇文章，里面讲读文献，开头的十几篇，二十几篇要认真读、细细的读，经典的甚至要背诵。我想，这应该是一个建立知识体系框架的过程，所以需要细细的读。等知识体系建立起来，以后读文献就是往里面填充了，重复的文献快速浏览，了解不同，不重复的文献只要建立新的旁支就可以了，这样以后读文献的速度就能快起来。做文献的框架很费力，那我也以15篇文献为目标吧，看看能否把自己的知识体系建立起来。

算上上一篇HTML5的，这算是第二篇。

——Arthur