文档介绍：数据挖掘算法
Wang Ye
一、概念和术语
数据挖掘 / 知识发现
（1）数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的过程。
（2）数据挖掘，又称为数据库中知识发现（Knowledge Di近似、下近似、边界等概念见下图。
-2 粗糙集归约（续）
（3）令Q代表属性的集合。q∈Q是一个属性，如果IND(Q−q) = IND(Q)，则q在S中不是独立的；否则称q在S中是独立的。
（4）若集合满足IND(R) = IND(Q)且R中的每一个属性都是独立的，则R被称为Q的一个“约简”，记作R = RED(Q)。
（5）约简可以通过删除冗余的（不独立的）属性而获得，约简包含的属性即为“对分类有帮助”的属性。
数据变换
-1 归一化与模糊化
有限区间的归一化：
无限区间的归一化：
模糊隶属度：
-2 核函数
（1）核函数的基本思想是将在低维特征向量线性不可分的数据映射到线性可分的高维特征空间中去。
（2）映射可以是显式的，也可以是隐式的。显式映射即找到一个映射关系f，使高维空间的特征向量f (x)可以被直接计算出来。
（3）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求f (x)的计算困难。核函数即某高维特征空间中向量的内积，是核矩阵中的一个元素。
（4）并不是所有的实值函数f (x)都可以作为空间映射的核函数，只有f (x)是某一特征空间的内积时，即符合Mercer条件，它才能成为核函数。
-2 核函数（续）
多项式函数：

高斯（RBF）函数：

多层感知机函数：
低维空间向量映射到高维空间向量举例：
数据压缩
-1 离散化
离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。
离散化的方法包括几下几种。
（1）等距分割；
（2）聚类分割；
（3）直方图分割；
（4）基于熵的分割；
（5）基于自然属性的分割。
-2 回归
回归和对数线性模型可以用来近似给定的数据。
在线性回归中，用一条直线来模拟数据的生成规则。
多元回归是线性回归的扩展，涉及多个预测变量。
在多项式回归中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。
-2 回归（续）
利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建模。
在广义线性模型中，因变量Y 的变化速率是Y 均值的一个函数；这一点与线性回归不同。常见的广义线性模型有：对数回归和泊松回归。
对数回归模型是利用一些事件发生的概率作为自变量所建立的线性回归模型。
泊松回归模型主要是描述数据出现次数的模型，因为它们常常表现为泊松分布。
-3 主成分分析（PCA）
PCA算法搜索c个最能代表数据的k-维正交向量；这里c  k。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤如下：
（1）对输入数据归一化，使得每个属性都落入相同的区间。
（2）PCA计算c个规范正交向量，作为归一化输入数据的基。这些是单位向量，每一个都垂直于另一个：称为主成分。输入数据是主要成分的线性组合。
（3）对主成分按“意义”或强度降序排列，选择部分主成分充当数据的一组新坐标轴。
-4 离散小波变换（DWT）
离散小波变换是一种线性信号处理技术。该技术方法可以将一个数据向量转换为另一个数据向量（为小波相关系数）；且两个向量具有相同长度。
可以舍弃转换后的数据向量中的一些小波相关系数。保留所有大于用户指定阈值的小波系数，而将其它小波系数置为0，以帮助提高数据处理的运算效率。
这一技术方法可以在保留数据主要特征情况下除去数据中的噪声，因此该方法可以有效地进行数据清洗。
给定一组小波相关系数，利用离散小波变换的逆运算还可以近似恢复原来的数据。
-4 离散小波变换（续）
常用的小波函数包括Haar系列, Daubechies系列，Moret系列，Sym系列，Meyer系列，Coif系列。
-5 潜在语义分析
潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系。
（1）构造“特征-样本”矩阵，“特征-样本”矩阵中的每一列是对应于第i个样本特征向量；
（2）对该矩阵进行奇异值分解(SVD)；
（3）用最大的k个奇异值所对应的“特征-语义”矩阵Uk和“样本-语义”矩阵Vk以及最大的k个奇异值重构“特征-样本”矩阵。
下面两式分别代表在语义空间特征与特征之间的距离和在语义空间样本与样本之间的距离
-6