分类算法

数据分类的基本过程

对一个类别已经确定的数据集创建模型。用于创建模型的数据集称为训练集；训练集中的那个元祖称为训练样本，训练集中每一个元祖都数据一个确定的类别；类别用类标号标识
使用创建的模型将类别未知的元祖归于某个或某个类中，使用模型进行分类需要评估分类模型的预测准确率

数据分类需要对数据进行数据准备。包括数据清洗、属性选择、数据转换等处理过程。
数据清洗的任务是对数据进行预处理、消除或者减少噪声、处理空缺值
属性选择的任务是通过相关性分析，找出和分类任务相关的属性，去掉那些不相干或者冗余的属性。已提高分类的速度、防止分类过程被误导。
数据转换任务是对数据进行标准化或者对数据进行泛化

评估分类模型可以根据下列标准来进行：
预测准确率
模型的创建速度和使用速度
强壮性
伸缩性
可解释性

决策树分类概述

基本组成部分：决策结点、分支和叶，树种每个内部节点表示一个属性上的测试。每个叶结点表示一个类。决策树种最上面的结点称为根节点。是整个决策树的开始。决策树的每个结点的子结点的个数和决策树使用的算法相关。

决策树的基本算法是贪心算法。它采用自上而下分而治之的方法。开始时，所有的数据都在根节点，然后用所选属性递归的对元组集合进行分裂。每个结点上的数据都是同一个类别。没有属性可以在用于对数据的分裂时停止分裂。对每个分裂的要求分成的组的差异最大。各种决策树算法之间的主要区别就是对这个差异衡量方式的区别。属性的选择是基于一个启发式规则或者一个统计的度量。

决策树的特点

在为一个结点选择怎样进行分裂时采用贪心算法。这种算法在决定结点的分裂时根本不考虑此次选择会对将来的分裂造成什么样的影响。
通常的分裂算法在决定怎么在一个结点进行分裂时，都只考察一个预测变量。这样生成的决策树使得有些很明确的情况变得复杂而且意义不清
由于递归的分裂，一些数据子集可能变得太小。使得进一步分裂它们就失去了统计意义
决策树每个结点对应分裂的定义必须非常明确，但在实际生活中，这种明确是不合理的

二叉决策树算法与分类规则的生成

决策树一般都是自上而下生成的，建立决策树的过程，即树的生长过程。是不断吧数据按照一定规则进行分裂的结果。在每个结点分裂使用一个相应的特征，使分裂后某种准侧函数达到最优，不同的准则对应不同的分裂分方法和不同的决策树。

基本过程

开始吧训练数据归入某单个结点
选择训练数据最佳分类的一个检验特征值进行数据分裂，然后进入下一个结点。
在每个结点处，用同样的办法递归的形成下一个分裂。分类过的特征以后不在考虑
当下列条件之一满足时，递归分裂停止：a. 不在有进一步分裂的特征。2.已没有样本分裂某个检验特征

决策树属性的选取

处理数值型决策树问题的常用方式是对数据值进行排序并考虑没对值之间的二元分裂，然后对每个可能的分裂点计算优度值，这样，每个分裂点看成是由2个值得分裂属性，对每个选择点进行此计算，找出优度值最大的分裂点作为最好的数据分裂点。

设S是训练样本的集合，其中每个样本的类标号都是已知的。假定有m个类。集合S中类别 $C_i$ 的记录个数为 $s_i$ 个，i=1,2,3,4,...,一个给定的样本分类所需的期望信息是

$EA = \sum^{v}_{j=1} \frac{s_1j + ... + s_mj}{S}Is_1j, ... ,_mj$

设属性A具有值 ${a_1, ..., a_v}$ 。属性A可以用来对S进行分组，将S分为子集 $S_1,...,S_v$ ,其中 $S_j$ 包含S中值为 $a_j$ 的哪些样本。设 $S_j$ 包含类 $C_i$ 的 $S_ij$ 个样本。根据A的这种分裂的期望信息称为属性A的熵为

$Is_1j, ... ,_mj = - \sum^{m}_{i=1}\frac{S_i}{S}\log{2}{\frac{S_i}{S}}$

A的信息增益为
$GainA=Is_1j, ... ,_mj - EA$

改进决策树性能的方法

作为分类结果的决策树，没有必要让其生长的太“枝繁叶茂”，否则，既降低了树的可理解性和可作用性。同时也使决策树本身对训练集数据的依赖性增大
为了使决策树蕴含的规则具有普遍意义，必须防止以上过分拟合现象。需要使用剪枝方法，解决该过拟合现象，常用的方法有

增加限制条件
对树进行剪枝，一般用统计量度来去掉不可靠的分支。改进预报能力和分类速度；可以根据剪的时机分为先剪和后剪

泛化规则算法

概念层次结构是所有数据挖掘的基础，而面向属性的方法经过改进和扩充后可用于关系数据库的数据挖掘，称之为面向属性的泛化方法,该方法吧机器学习，特别是示例学习技术，与面向集合的数据库操作结合起来。大大的提高了数据挖掘的功能和效率。

概念层次

基本概念

概念层次结构表示吧一组较低级概念映射到与他们相对应得较高级概念的次序。这种映射关系可以按照偏序关系来组织概念集
偏序关系反映了概念之间的特殊--- 一一对应关系，可以用树、格或有向无循环图等来表示，统称为层次结构。

类型

模式层次

模式层次是在模式级上通过定义反应数据库属性之间联系的偏序关系而形成的。如门牌号码街道城市省份国家形成模式上的偏序关系。它指明沿模式自左向右是泛化，自右而左是特化。

集合分组层次

这种概念层级是通过定义一组概念值得子集之间的关系而形成的。反应应用领域的语义联系特点，它可用于详细说说明模式层次或者其他集合分组层次

导出操作层次

通过定义数据上的一组操作形成导出层次。常用与描述数字型属性

基于规则的层次

基于规则的概念层次将概念层次的无条件泛化扩展到有条件的泛化，进一步完善了面向属性的方法。
若一个概念层次的各条路径具有相应的泛化规则，则称之为基于规则的概念层次。通常用格结构描述，一般来说，他有三种类型

概念泛化和演绎规则有关
概念泛化和计算规则有关
混合型

作用

概念层次可用于各种数据挖掘，可把原始数据泛化到某个较高抽象层，多层规则挖掘等

面向属性泛化的策略和特点

策略

面向属性泛化：属性是关系的原子单位，泛化时一个属性一个属性地进行。通过移去不可泛化的属性和概念树来提升，对属性进行泛化
移去不可泛化的属性：若属性尽管有多个不同的值，但没有更一般意义上的高层次概念来归纳它，则认为该属性在泛化过程中是没有意义的，可以将他移去
概念树提升：对于某一个元组的属性值，若概念树种存在一个更高层次的概念，就用该概念替换属性值，从而吧元组泛化。泛化没提升一层，以控制泛化速度，避免过泛化
累计覆盖度：当一个元组被泛化时，应将该元组的覆盖度值带到他的泛化元组中；当合并相同元组或者去掉冗余元组时，应该覆盖度累计起来
指定泛化阈值、控制概念提升：用户指定的泛化阈值，其实就是把知识基表进一步浓缩，最后得到的宏元组的最大数量，对于知识基表中的某个属性，如果他的不同值得个数大于用户指定的泛化阈值，就要把这个属性进一步泛化
指定阈值、控制已泛化关系：如果已泛化关系的元组个数仍大于用户指定的泛化阈值，则应对该关系继续泛化
规则转化：吧泛化关系中的一个宏元组转换成一条合取规则，多个宏元组可以转化为多条规则的析取

特点

面向属性的
学习效率高
功能强

相关分析

相关关系是指事物之间的关系数值存在着一定的依存关系。即某一个现象在其发展变化中，当数量上为某一个确定值是，与之有联系的其他现象可以有若干个数值与之对用，但这些值按照某种规律在一定的范围内波动。
相关关系的特定是：一个变量的取值不能有另一个变量唯一确定。也不能用函数形式予以描述。但并不是归规律可循。

两要素间的相关分析

简单相关系数的计算

两个变量之间线性相关程度的度量称为简单相关系数（单相关系数），对于2个要素x和y，如果他们的样本值分别为 $x_1, x_2i=1,2,3,4,5...,n$ 则它们之间的相关系数 $r_{xy}$ 定义为
$r_{xy}=\frac{\sum^{n}_{i=1}x_i - \bar{x}y_i - \bar{y}}{\sqrt{\sum^{n}_{i=1}{x_i - \bar{x}}^2} \sqrt{\sum^{n}_{i=1}{y_i - \bar{y}}^2}} \\\bar{x} = \frac{1}{n}\sum^{n}_{i=1}x_i \\\bar{y} = \frac{1}{n}\sum^{n}_{i=1}y_i$
$r_{xy}介于-1和1之间，若r_{xy}>0,表示正相关，若r_{xy}<0,则表示负相关，r_{xy}的绝对值越接近1，表示两要素的关系越密切$

简单相关系数的检验

当 $r>r_{\alpha}$ 即所计算的相关系数r大于给定置信水平 $\alpha$ 下的临界值 $r_{\alpha}$ 时，则认为2要素相关。

多要素之间的相关分析

在多要素所构成的地理系统中，当研究某一个要素对另外一个要素的影响或相关程度时，暂不考虑其他要素的影响，而单独研究那2个要素之间的相关关系的密切程度时，则称为偏相关。用来度量偏相关程度的统计量称为偏相关系数

偏相关系数的计算与检验

可利用单相关系数来计算偏相关系数，假设有3个要素，其两两之间的单相关系数为 $r_{ij}i,j=1,2,3$ ,在偏相关分析中，常称这些单相关系数为零级相关系数，3个要素之间的偏相关系数共有3个，即 $r_{12.3}、r_{23.1}、r_{13.2}$ ,称为一级偏相关系数维护
$r_{12.3} = \frac{r_{12}- r_{13}r_{23}}{\sqrt{1-r^2_{13}1-r^2_{23}}} \\r_{13.2} = \frac{r_{13}- r_{12}r_{23}}{\sqrt{1-r^2_{12}1-r^2_{23}}} \\r_{12.3} = \frac{r_{23}- r_{12}r_{13}}{\sqrt{1-r^2_{12}1-r^2_{13}}}$

偏相关系数

系数分布的范围在1~-1之间
系数的绝对值越大，其偏相关程度越大
系数的绝对值必小于或者等于由同一个系列资料所求得的复相关系数

复相关系数的计算和检验

实际上一个要素的变化往往受到多种要素的综合作用和影响，而单相关和偏相关分析的方法都不能反映各要素的综合影响，要解决这一问题，就必须采用研究几个要素同时对某一个要素之间的相关关系的复相关分析。

复相关系数可以利用单相关系数和偏相关系数求得，

$R_{y \cdot 12...\cdot k} = \sqrt{1- 1 - r^2_{y1} 1 - r^2_{y2 \cdot 1} ... 1 - r^2_{y k \cdot 12... \cdot k-1}}$

显著性检验
$F = \frac{R^2_{y\cdot 12...\cdot k}}{1-R^2_{y\cdot 12...\cdot k}}\times \frac{n -k - 1}{k}$