Some Knownledge of Data Mining

26 Sep 2015 DM

---

What is Data Mining?

Data mining (knowledge discovery from data): Extraction of interesting (non-trivial, implicit, previously, unknown and potentially useful) patterns or knowledge from huge amount of data.

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

大部分数据挖掘算法都是有五个标准组件构成：

• 模型或模式结构
• 数据挖掘任务
• 评分函数
• 搜索和优化方法
• 数据管理策略

每一种组件都有一些通用的系统原理，掌握每一种组件的基本原理后，再来理解不同组件组装的算法就变得相对简单，不同算法之间的比较也更加容易。

模型或模式结构

模型（model）/ 模式（pattern）：通过数据挖掘过程所得到的知识。eg: 线性回归模型、层次聚类模型、频繁序列模式…… 模型是对整个数据集的高层次、全局性的描述或总结，是对现实世界的抽象描述；模式是局部的，仅对一小部分数据做出描述，它可能只支持几个对象或对象的几个属性。

数据挖掘任务

• 模式挖掘（关联分析、异常检测）
• 预测建模（分类，回归）
• 描述建模（聚类分析）

评分函数

模型（模式）代表的是函数的一般形式，它的参数空间非常大，可选的参数值很多，需要评分函数来确定什么样的参数值比较好。评分函数用来对数据集与模型的拟合程度进行评估；选择的评分函数要能很好的拟合现有数据，同时要避免过拟合并使拟合后的模型尽量简洁。常见的评分函数有似然函数、误差平方和、准确率等。

搜索和优化方法

搜索和优化的目标是确定模型的结构及其参数值，使得评分函数达到极值（eg: 平方差最小、准确率最高……）。如果模型的结构已经确定，则搜索将在参数空间内进行，目的是针对这个固定的模型结构，优化评分函数。如果模型的结构还没有确定的话（例如，存在一族不同的模型（模式）结构），那么搜索既要针对结构空间又要针对和这些结构相联系的参数空间进行。

优化问题：针对特定的模型，发现其最佳参数值的过程 常用的优化方法：爬山(Hill-Climing)、最陡峭下降(Steepest-Descend)、期望最大化(Expectation-Maximization)……

搜索问题：从潜在的模型族中发现最佳模型结构的过程 常用的搜索方法：贪婪搜索、分支界定、宽度（深度）优先遍历……

数据管理策略

传统的统计和机器学习算法都假定数据是可以全部放入内存的，所以不太关心数据管理技术。但在大数据环境下，GB甚至TB数量级的数据是常见的。由于外存的访问速度要慢的多，直接将传统的内存算法应用于这些外存数据，性能将变得非常差。因此，针对海量数据，应该设计有效的数据组织和索引技术，或者通过采样、近似等手段，来减少数据的扫描次数，从而提高数据挖掘算法的效率。