数据挖掘学习报告
一、引言
数据挖掘是通过分析每个数据， 从大量数据中寻找其规律的技术， 主要有数据准备、
规律寻找和规律表示 3 个步骤。数据挖掘的任务有关联分析、聚类分析、分类分析、异
常分析、特异群组分析和演变分析等。
二、基本概念
数据挖掘，在人工智能领域，习惯上又称为数据库中的知识发现也有人把数据挖掘
视为数据库中知识发现过程的一个基本步骤。知识发现过程由以下三个阶段组成： （ 1）数据准备，（2）数据挖掘，（3）结果表达和解释。数据挖掘可以与用户或知识库交互。
数据挖掘是通过分析每个数据，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示 3 个步骤。数据准备是从相关的数据源中选取所需的数据并整合成用于数据挖掘的数据集；规律寻找是用某种方法将数据集所含的规律找出来；规律表示是尽可能以用户可理解的方式（如可视化）将找出的规律表示出来。
数据挖掘的任务有关联分析、聚类分析、分类分析、异常分析、特异群组分析和演变分析，等等。并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系
统查找个别的记录，或通过因特网的搜索引擎查找特定的 Web 页面，则是信息检索领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主
要依赖传统的计算机科学技术和数据的明显特征来创建索引结构， 从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。
1、数据挖掘的基本步骤
数据挖掘的步骤会随不同领域的应用而有所变化，每一种数据挖掘技术也会有各自
的特性和使用步骤，针对不同问题和需求所制定的数据挖掘过程也会存在差异。此外，
数据的完整程度、专业人员支持的程度等都会对建立数据挖掘过程有所影响。这些因素
造成了数据挖掘在各不同领域中的运用、规划，以及流程的差异性，即使同一产业，也
会因为分析技术和专业知识的涉入程度不同而不同，因此对于数据挖掘过程的系统化、
标准化就显得格外重要。如此一来，不仅可以较容易地跨领域应用，也可以结合不同的
专业知识，发挥数据挖掘的真正精神。
数据挖掘完整的步骤如下：
① 理解数据和数据的来源（ understanding）。
② 获取相关知识与技术（ acquisition）。
③ 整合与检查数据（ integration and checking）。
④ 去除错误或不一致的数据（ data cleaning）。
⑤ 建立模型和假设（ model and hypothesis development）。
⑥ 实际数据挖掘工作（ data mining）。
⑦ 测试和验证挖掘结果（ testing and verification）。
⑧ 解释和应用（ interpretation and use）。
由上述步骤可看出，数据挖掘牵涉了大量的准备工作与规划工作，事实上许多专家
都认为整套数据挖掘的过程中， 有 80%的时间和精力是花费在数据预处理阶段， 其中包
括数据的净化、数据格式转换、变量整合，以及数据表的链接。可见，在进行数据挖掘
技术的分析之前，还有许多准备工作要完成。
2、数据挖掘十大经典算法
1．C4.5：是机器学习算法中的一种分类决策树算法，其核心算法是 ID3 算法。
K-means算法：是一种聚类算法。
3.SVM ：一种监督式学习的方法，广泛运用于统计分类以及回归分析中
4.Apriori ：是一种最有影响的挖掘布尔关联规则频繁项集的算法。
5.EM ：最大期望值法。
6.pagerank：是 google 算法的重要内容。
Adaboost:是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器然后把弱分类器集合起来，构成一个更强的最终分类器。
8.KNN: 是一个理论上比较成熟的的方法，也是最简单的机器学习方法之一。
9.Naive Bayes：在众多分类方法中，应用最广泛的有决策树模型和朴素贝叶斯 （Naive
Bayes）
10.Cart：分类与回归树，在分类树下面有两个关键的思想，第一个是关于递归地划
分自变量空间的想法，第二个是用验证数据进行减枝。
下面我们着重研究一下动态规划法。
三、动态规划法
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。
20世纪 50年
代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程 (multistep decision process)的优
化问题时，提出了著名的最优化原理 (principle of optimality) ，把多阶段过程转化为一系
列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新
方法——动态规划。
（一）基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许
多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与
分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后
从这些子问题的解得到原问题的解。 与分治法不同的是， 适合于用动态规划求解的问题，
经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问
题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答
案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我
们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要
它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算
法多种多样，但它们具有相同的填表格式。
（二）基本结构
多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于
当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故
有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。
动态规划程序设计是对解最优化问题的一种途径、 一种方法，而不是一种特殊算法。
不象前面所述的那些搜索或数值计算那样， 具有一个标准的数学表达式和明确清晰的解
题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确
定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解
题方法，而不存在一种万能的动态规划，可以解决各类最优化问题。因此在学习时，除
了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建
立模型，用创造性的技巧去求解。
（三）基本模型
根据上例分析和动态规划的基本概念，可以得到动态规划的基本模型如下：
(1)确定问题的决策对象。
(2)对决策过程划分阶段。
(3)对各阶段确定状态变量。
(4)根据状态变量确定费用函数和目标函数。
(5)建立各阶段状态变量的转移过程，确定状态转移方程。
四、应用举例
用动态规划实现导弹拦截。
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统
有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高
于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以
只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数），计算
这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。
SAMPLE INPUT:
389 207 155 300 299 170 158 65
SAMPLE OUTPUT:
6
389 300 299 170 158 65
因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以
后的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的 高
度组成一个非递增序列。题目要求我们计算这套系统最多能拦截的导弹数，并依次输出
被拦截导弹的高度，实际上就是要求我们在导弹依次飞来的高度序列中寻找 一个最长
非递增子序列。
设 X={x 1 ,x 2 , ?,x n 为}依次飞来的导弹序列， Y={y 1 ,y 2 , ?,y k 为}问题的最优解（即 X 的最长非递增子序列），s 为问题的状态（表示导弹拦截系统当前发送炮弹能够到达的最大高度， 初值为 s=∞—— 第一发炮弹能够到达任意的高度） 。如果 y 1 =x
1 ，即飞来的第一枚导弹被成功拦截。那么，根据题意 “每一发炮弹都不能高于前一发
的高度 ”，问题的状态将由 s=∞ 变成 s≤x 1（ x 1 为第一枚导弹的高度）；在当前状态
下，序列 Y 1 ={y 2 , ?,y k }也应该是序列 X 1 ={x 2 , ?,x n }的最长非递增子序列 （大
家用反证法很容易证明） 。也就是说，在当前状态 s≤x1 下，问题的最优解 Y 所包含
的子问题（序列 X 1 ）的解（序列 Y 1 ）也是最优的。这就是拦截导弹问题的最优子
结构性质。
设 D(i) 为第 i 枚导弹被拦截之后，这套系统最多还能拦截的导弹数（包含被拦截
的第
i 枚）。我们可以设想，当系统拦截了第
k 枚导弹
x k
，而
x k
又是序列
X={x 1 ,x
2 ,
? ,x n } 中的最小值，即第
k 枚导弹为所有飞来的导弹中高度最低的， 则有
D(k)=1
；
当系统拦截了最后一枚导弹 x n ，那么，系统最多也只能拦截这一枚导弹了，即
D(n)=1；其它情况下，也应该有 D(i) ≥ 1。
假设系统最多能拦截的导弹数为 dmax（即问题的最优值），则 dmax = max(D(i)) 所以，要计算问题的最优值 dmax ，需要分别计算出 D(1) 、 D(2) 、 D(n) 的
值，然后将它们进行比较，找出其中的最大值。根据上面分析出来的递归方程，我们完
全可以设计一个递归函数， 采用自顶向下的方法计算 D(i) 的值。然后，对 i 从 1 到 n
分别调用这个递归函数，就可以计算出 D(1) 、 D(2) 、 D(n) 。但这样将会有大
量的子问题被重复计算。
比如在调用递归函数计算 D(1) 的时候，可能需要先计算 D(5)
的值；之后在分别调用递归函数计算 D(2) 、 D(3) 、 D(4) 的时候，都有可能需要先
计算 D(5) 的值。如此一来，在整个问题的求解过程中， D(5) 可能会被重复计算很多
次，从而造成了冗余，降低了程序的效率。
其实，通过以上分析， 我们已经知道： D(n)=1 。如果将 n 作为阶段对问题进行划分，
根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出 D(n-1) 、
D(n-2) 、 D(1) 的值。这样，每个 D(i) 的值只计算一次，并在计算的同时把计算
结果保存下来，从而避免了有些子问题被重复计算的情况发生，提高了程序的效率。算
法代码如下：
for(i=n-2;i>=0;i--){ // 从后往前计算 d[i] 值
for(j=i+1;j<n;j++){
if((array[j]<=array[i])&&(d[i]<d[j]+1)){
d[i]=d[j]+1;
}
}
}
dmax = 0;
xh = 1;
for(i=0;i<n;i++){
//求出
dmax
if(d[i]>dmax){
dmax = d[i];
xh = i;
}
}
cout<<dmax<<endl; //输出结果
cout<<array[xh]);
int temp = xh;
for(i=xh+1;i<n;i++){
if(d[i]==d[temp]-1){
temp = i;
cout<<array[i];
}
}
cout<<endl;
五、结论
动态规划程序设计是对解最优化问题的一种途径、 一种方法，而不是一种特殊算法。
动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解
的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，
而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此在学习时，除了要
对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模
型，用创造性的技巧去求解。