数据挖掘 分类方法

分类的目的是学会一个分类函数或分类模型（分类器），该模型能把数据库中的数据项映射到给定类别中的某一个类别。
分类可用于预测，常用的方法是回归，主要应用于医疗诊断，信用卡系统的信用分级、图像模式识别等。
分类器的构造方法有统计方法、机器学习方法、神经网络方法。

分类的基本概念与步骤

定义：给定一个数据库D = {t1，t2，……，tn }和一组类C={C1，C2，……，Cn}，分类问题是去确定一个映射f：D->C，每个元素ti被分配到一个类中。一个类Cj包含映射到该类中的所有元组，即Cj={ti|f(ti)=Cj,1<=i<=n,且ti∈D}。
数据分类分为两个步骤，建模和使用。目的是分析输入数据，为每个类找到一种准确的描述或模型。
基本步骤：建立一个模型，描述预定的数据类集或概念集，然后使用模型进行分类。
数据元组也称作样本、实例或对象，为建立模型而被分析的数据元组形成训练数据集。样本随机抽取，并独立于训练样本。

基于距离的分类算法

给定一个数据库D= {t1, t2, …, tn}和一组类C={C1，C2, …, Cm}。对于任意的元组ti = {ti1, ti2, …, tik}∈D，如果存在一个Cj属于C，使得：sim(ti, Cj) ≥ sim(ti, Cp), 任意Cp∈C， Cp ≠ Cj，则ti被分配到类Cj中，其中sim成为相似性。
在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。
简单的基于距离寻找待分类数据类表示的搜索算法：假定每个类Ci用类中心来表示，每个元组必须和各个类的中心来比较，从而可以找出最近的类中心得到确定的类别标记，复杂性一般为O(n)。
基本步骤：

dist = INF;//距离初始化
for i = 1 to m do
	if dis(ci, t)<dist then begin
		c = i;
		dist = dist(ci, t);
	end;
flag t with c
1
2
3
4
5
6
7

k-最临近分类算法（kNN）：假定每个类包含多个训练数据，且每个训练数据都有一个唯一的类别标记，k-最临近分类的主要思想就是计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的k个训练数据，k个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。复杂度为O(nq)。
具体描述：

输入：	训练数据T；
		最临近数目k；
		待分类的元组t。
输出：	输出类别c。
N = σ;
for each d∈T do begin
	if |N|≤k then
		N = N∪{d};
	else
		if 存在u∈N such that sim(t,u) < sim(t,d) then
			begin
				N = N-{u};
				N = N ∪{d};
			end
end
c = class related to such u∈N which has the most number;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

决策树分类方法

决策树：采用自顶而下的递归方式，在决策树内部结点进行属性值的比较并根据不同的属性值判断从该节点向下的分支，在决策树的叶节点得到结论。

决策树基本算法概述

决策树生成：决策树生成算法的输入是一组带有类别标记的例子，构造的结果是一棵二叉树或多叉树。

Generate_decision_tree//决策树生成算法
输入：训练样本sample，由离散值属性表示；候选属性的集合attribute_list。
输出：一棵决策树//由给定的训练数据产生一棵决策树
创建结点N
if sample 都在同一个类C then
	返回N作为叶节点，以类C标记；
if attribute_list 为空 then
	返回N作为叶节点，标记为samples中最普通的类；//多数表决
选择attribute_list中具有最高信息增益的属性test_attribute;
标记结点N为test_attribute;
for each test_attribute中的已知值ai//划分samples
	由结点N长出一个条件为test_attribute=ai的分支；
设si是samples中test_attribute=ai的样本的集合；//一个划分
if si 为空 then
	加上一个树叶，标记为samples中最普通的类；
else 加上一个由Generate_decision_tree(si,attribute_list-test_attribute)返回的结点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

决策树修剪：剪枝是一种克服噪声的基本技术，同时也能使树变得简化。
预先剪枝：子生成树的同时决定是继续对不纯的训练子集进行划分还是停机。
后剪枝：为一种拟合-化简的两阶段方法。首先生成于训练数据完全拟合的决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。如果存在某个叶子剪去后使得在测试集上的准确度或其他测度不降低，则减去该叶子；否则停机。

ID3算法

ID3：决策树中每个非叶节点对应一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。每个非叶结点都将与属性中具有最大信息量的非类别属性相关联。采用信息增益来选择出能够最好地将样本分类的属性。
信息增益基于信息论中熵的概念，ID3总是选择具有最高信息增益的属性作为当前结点的测试属性。