数据挖掘中分类的目的是学会一个分类函数或分类模型(也常常被称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个。分类可描述如下:输入数据,或称训练集(Training Set),是由一条条数据库记录(Record)组成的。每一条记录包含若干个属性(Attribute),组成一个特征向量。训练集的每条记录还有一个特定的类标签(Class Label)与之对应。该类标签是系统的输入,通常是以往的一些经验数据。一个具体样本的形式可谓样本向量:(v1,v2,...,vn;c),在这里vi表示字段值,c表示类别。分类的目的是:分析输入数据,通过在训练集中的数据表现出来的特征,为每一个类找到一种准确的描述或模型。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的,我们仍可以由此预测这些新数据所属的类。注意是预测,而不能肯定,因为分类的准确率不能达到百分之百。我们也可以由此对数据中的每一个类有更好的理解。也就是说:我们获得了对这个类的知识。
所以分类(Classification)也可以定义为:对现有的数据进行学习,得到一个目标函数或规则,把每个属性集x映射到一个预先定义的类标号y。目标函数或规则也叫分类模型(Classification Model),它有两个主要作用:一是描述性建模,即作为解释性的工具,用于区分不同类的对象;二是预测性建模,即用于预测未知记录的类标号。
分类方法是一种根据输入数据建立分类模型的系统方法,这些方法都是使用一种学习算法(Learning Algorithm)确定分类模型,使该模型能够很好地拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好地拟合输入数据,还要能够正确地预测未知样本的类标号。因此,训练算法的主要目标就是建立具有很好泛化能力的模型,即建立能够准确预测未知样本类标号的模型。图1展示了解决分类问题的一般方法。首先,需要一个训练集,它由类标号已知的记录组成。使用训练集建立分类模型,该模型随后将运用于检验集(Test Set),检验集由类标号未知的记录组成。
图1
通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学公式形式。例如,给定一个顾客信用信息数据库,通过学习所获得的分类规则可用于识别顾客是否具有良好的信用等级或一般的信用等级。分类规则也可用于对今后未知所属类别的数据进行识别判断,同时也可以帮助了解数据库中的内容。
构造模型的过程一般分为训练和测试两个阶段。在构造模型之前,要求将数据集随机地分为训练数据集合测试数据集。在训练阶段,使用训练数据集,通过分析由属性描述的数据库元组来构造模型,假定每个元组属于一个预定义的类,有一个叫做类标号的属性来确定。由于提供了每个训练样本的类标号,该阶段也被称为有指导的学习。在测试阶段,使用测试数据集来评估模型的分类准确率,如果认为模型的准确率可以接受,就可以用该模型对其它数据元组进行分类。一般来说,测试阶段的代价远远低于训练阶段。
为了提高分类的准确性、有效性和可伸缩性,在进行分类之前,通常要对数据进行预处理,包括:
决策树(Decision Tree)又叫分类树(Classification Tree),是使用最为广泛的归纳推理算法之一,处理类别型或连续型变量的分类预测问题,可以用图形或if-then的规则表示模型,可读性较高。决策树模型通过不断地划分数据,使因变量的差别最大,最终目的是将数据分类到不同的组织或不同的分枝,在因变量的值上建立最强的归类。
决策树是一种监督式的学习方法,产生一种类似流程图的树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。
决策树构建的主要步骤有三个:第一是选择适当的算法训练样本构建决策树,第二是适当的修剪决策树,第三则是从决策树中萃取知识规则。
(1)决策树的分割
决策树是通过递归分割(Recursive Partitioning)建立而成,递归分割是一种把数据分割成不同小的部分的迭代过程。构建决策树的归纳算法如下:
如果有以下情况发生,决策树将停止分割:
(2)决策树的剪枝
在实际构造决策树时,通常要进行剪枝,这是为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造;后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。
(3)决策树算法
决策树算法基本上是一种贪心算法,是由上至下的逐次搜索方式,渐次产生决策树模型结构。划分数据集的最大原则是:使无序的数据变的有序。如果一个训练数据中有20个特征,那么选取哪个做划分依据?这就必须采用量化的方法来判断,常用的量化划分方法是“信息论度量信息分类”。基于信息论的决策树算法有ID3、C4.5和CART等算法,其中C4.5和CART两种算法从ID3算法中衍生而来。
C4.5和CART支持数据特征为连续分布时的处理,主要通过使用二元切分来处理连续型变量,即求一个特定的值-分裂值:特征值大于分裂值就走左子树,或者就走右子树。这个分裂值的选取原则是使得划分后的子树中的“混乱程度”降低,具体到C4.5和CART算法则有不同的定义方式。
ID3算法由Ross Quinlan发明,建立在“奥卡姆剃刀”的基础上:越是小型的决策树越优于大的决策树(be simple简单理论)。ID3算法中根据信息论的信息增益评估和选择特征,每次选择信息增益最大的特征做判断属性。ID3算法可用于划分标称型数据集,没有剪枝的过程,为了去除过度数据匹配的问题,可通过裁剪合并相邻的无法产生大量信息增益的叶子节点(例如设置信息增益阀值)。使用信息增益有一个缺点,那就是它偏向于具有大量值的属性,就是说在训练集中,某个属性所取的不同值的个数越多,那么越有可能拿它来作为分裂属性,而这样做有时候是没有意义的,另外ID3不能处理连续分布的数据特征,于是就有了C4.5算法。CART算法也支持连续分布的数据特征。
C4.5是ID3的一个改进算法,继承了ID3算法的优点。C4.5算法用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足,在树构造过程中进行剪枝;能够完成对连续属性的离散化处理;能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高;但效率低,因树构造过程中,需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描,C4.5只适合于能够驻留于内存的数据集。
CART算法的全称是Classification And Regression Tree,采用的是Gini指数(选Gini指数最小的特征s)作为分裂标准,同时它也包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息,但其生成的决策树分支较大,规模较大。为了简化决策树的规模,提高生成决策树的效率,就出现了根据GINI系数来选择测试属性的决策树算法CART。
Madlib中有三个决策树函数,分别为训练函数、预测函数和显示函数。训练函数接收输入的训练数据进行学习,生成决策树模型。预测函数用训练函数生成的决策树模型预测数据的所属分类。显示函数用来显示决策树模型。
MADlib中的决策树训练函数使用的是CART算法。
(1)语法
tree_train(
training_table_name,
output_table_name,
id_col_name,
dependent_variable,
list_of_features,
list_of_features_to_exclude,
split_criterion,
grouping_cols,
weights,
max_depth,
min_split,
min_bucket,
num_splits,
pruning_params,
surrogate_params,
verbosity
)
(2)参数
training_table_name:TEXT类型,训练数据输入表名。
output_table_name:TEXT类型,包含决策树模型的输出表名,如果表已经存在则报错。由训练函数生成的模型表具有以下列:
<...>当提供了grouping_cols入参时,该列存储分组列,依赖于grouping_cols入参的值,可能有多列,类型与训练表相同。
treeBYTEA8类型,二进制格式存储的决策树模型。
cat_levels_in_textTEXT[]类型,分类变量的层次。
cat_n_levelsINTEGER[]类型,每个分类变量的层号。
tree_depthINTEGER类型,剪枝前的决策树最大深度(根的深度为0)。
pruning_cpDOUBLE PRECISION类型,用于剪枝决策树的复杂性成本参数。如果使用交叉验证,该值应与‘input_cp’入参的值不同。
生成模型表的同时还会生成一个名为<model_table>_summary的概要表,具有以下列:
methodTEXT类型,值为‘tree_train’。
is_classificationBOOLEAN类型,用于分类时为TRUE,用于回归时为FALSE。
source_tableTEXT类型,源表名。
model_tableTEXT类型,模型表名。
id_col_nameTEXT类型,ID列名。
dependent_varnameTEXT类型,因变量。
independent_varnameTEXT类型,自变量。
cat_featuresTEXT类型,逗号分隔字符串,分类特征名称列表。
con_featuresTEXT类型,逗号分隔字符串,连续特征名称列表。
grouping_colTEXT类型,分组列名。
num_all_groupsINTEGER类型,训练决策树时的总分组数。
num_failed_groupsINTEGER类型,训练决策树时失败的分组数。
total_rows_processedBIGINT类型,所有分组处理的总行数。
total_rows_skippedBIGINT类型,所有分组中因为缺少值或失败而跳过的总行数。
dependent_var_levelsTEXT类型,对于分类,因变量的不同取值。
dependent_var_typeTEXT类型,因变量类型。
input_cpDOUBLE PRECISION类型,交叉验证前,用于剪枝决策树的复杂度参数。与pruning_params入参输入的值相同。
independent_var_typesTEXT类型,逗号分隔字符串,自变量类型。
id_col_name:TEXT类型,训练数据中,含有ID信息的列名。这是一个强制参数,用于预测和交叉验证。每行的ID值应该是唯一的。
dependent_variable:TEXT类型,包含用于训练的输出列名。分类的输出列是Boolean、integer或text类型,回归的输出列是double precision类型。决策树的因变量可以为多个,但是训练函数的时间和空间复杂度, 会随着因变量数量的增加呈线性增长。
list_of_features:TEXT类型,逗号分隔字符串,用于预测的特征列名,也可以用‘*’表示所有列都用于预测(除下一个参数中的列名外)。特征列的类型可以是boolean、integer、text或double precision。
list_of_features_to_exclude:TEXT类型,逗号分隔字符串,不用于预测的列名。如果自变量是一个表达式(包括列的类型转换),那么这个列表中应该包括用于自变量表达式的所有列名,否则那些列将被包含在特征中。
split_criterion:TEXT类型,缺省值为‘gini’,用于分类,而‘mse’用于回归。不纯度函数计算用于分裂的特征值。分类树支持的标准有‘gini’、‘entropy’或‘misclassification’,回归树的分裂标准总是使用‘mse’。
grouping_cols(可选):TEXT类型,缺省值为NULL,逗号分隔字符串,分组的列名。将为每个分组产生一棵决策树。
weights(可选):TEXT类型,权重列名。
max_depth(可选):INTEGER类型,缺省值为10。最终决策树的最大深度,根的深度为0。
min_split(可选):INTEGER类型,缺省值为20。一个试图被分裂的节点中,必须存在的元组的最小数量。此参数的最佳值取决于数据集的元组数目。
min_bucket(可选):INTEGER类型,缺省值为min_split/3。任何叶节点对应的最小元组数量。如果min_split和min_bucket只指定一个,那么min_split设置成min_bucket*3,或者min_bucket设置成min_split/3。
num_splits(可选):INTEGER类型,缺省值为100。为计算分割边界,需要将连续特征值分成离散型分位点。此全局参数用于计算连续特征的分割点,值越大预测越准,处理时间也越长。
pruning_params(可选):TEXT类型,逗号分隔的键-值对,用于决策树剪枝,当前接受的值为:
cp缺省值为0。cp全称为complexity parameter,指某个点的复杂度,对每一步拆分,模型的拟合优度必须提高的程度。试图分裂一个节点时,分裂增加的精确度必须提高cp,才进行分裂,否则剪枝该节点。该参数值用于在运行检查验证前,创建一棵初始树。
n_folds缺省值为0。用于计算cp最佳值的交叉验证褶皱数。为执行交叉验证,n_folds的值应该大于2。执行交叉验证时,会产生一个名为<model_table>_cv的输出表,其中包含估计的cp值和交叉验证错误。输出表中返回的决策树对应具有最少交叉错误的cp(如果多个cp值有相同的错误数,取最大的cp)。
surrogate_params:TEXT类型,逗号分隔的键值对,控制替代分裂点的行为。替代变量是与主预测变量相关的另一种预测变量,当主预测变量的值为NULL时使用替代变量。此参数当前接受的值为:
max_surrogates缺省值为0,每个节点的替代变量数。
verbosity(可选):BOOLEAN类型,缺省值为FALSE,提供训练结果的详细输出。
提示:
预测函数估计条件均值给出了新的预测。
(1)语法
tree_predict(tree_model,
new_data_table,
output_table,
type)
(2)参数
tree_model:TEXT类型,包含决策树模型的表名,应该是决策树训练函数的输出表。
new_data_table:TEXT类型,包含被预测数据的表名。该表应该和训练表具有相同的特征,也应该包含用于标识每行的id_col_name。
output_table:TEXT类型,预测结果的输出表名,如果表已经存在则报错。表中包含标识每个预测的id_col_name列,以及每个因变量的预测列。
如果type = 'response',表有单一预测列。此列的类型依赖于训练时使用的因变量的类型。
如果type = 'prob',每个因变量对应多列,每列表示因变量的一个可能值。列标识为‘estimated_prob_dep_value’,其中dep_value表示对应的因变量值。
type(可选):TEXT类型,缺省值为‘response’。对于回归树,输出总是因变量的预测值。对于分类树,变量类型可以是‘response’或‘prob’。
显示函数输出一个决策树的格式化表示。输出可以是dot格式,或者是一个简单的文本格式。dot格式可以使用GraphViz等程序进行可视化。
(1)语法
tree_display(tree_model, dot_format, verbosity)
还有一个显示函数输出为每个内部节点选择的替代分裂点:
tree_surr_display(tree_model)
(2)参数
tree_model:TEXT类型,含有决策树模型的表名。
dot_format:BOOLEAN类型,缺省值为TRUE,使用dot格式,否则输出文本格式。
verbosity:BOOLEAN类型,缺省值为FALSE。如果设置为TRUE,dot格式输出中包含附加信息,如不纯度、样本大小、每个因变量的权重行数、被剪枝的分类或预测。输出总是返回文本形式,对于dot格式,可以重定向输出到客户端文件,然后使用可视化程序处理。
本示例取自维基百科中的“决策树”条目,问题描述如下:
小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都來玩高尔夫,以至于所有员工都忙的团团转还是应付不过来,而有些天不知道什么原因却一个人也不来,俱乐部为雇员数量浪费了不少资金。小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫,以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。在2周时间内我们得到以下记录:天气状况有晴、云和雨;气温用华氏温度表示;相对湿度用百分比;还有有无风。当然还有顾客是不是在这些日子光顾俱乐部。最终他得到了14行5列的数据表格。
我们利用Madlib的决策树函数来解决此问题。
创建dt_golf表,将14条数据插入dt_golf表中。
drop table if exists dt_golf;
create table dt_golf (
id integer not null,
"outlook" text,
temperature double precision,
humidity double precision,
windy text,
class text
);
copy dt_golf (id,"outlook",temperature,humidity,windy,class) from stdin with delimiter '|';
1|sunny|85|85|'false'|'Don't Play'
2|sunny|80|90|'true'|'Don't Play'
3|overcast|83|78|'false'|'Play'
4|rain|70|96|'false'|'Play'
5|rain|68|80|'false'|'Play'
6|rain|65|70|'true'|'Don't Play'
7|overcast|64|65|'true'|'Play'
8|sunny|72|95|'false'|'Don't Play'
9|sunny|69|70|'false'|'Play'
10|rain|75|80|'false'|'Play'
11|sunny|75|70|'true'|'Play'
12|overcast|72|90|'true'|'Play'
13|overcast|81|75|'false'|'Play'
14|rain|71|80|'true'|'Don't Play'
\.
drop table if exists train_output, train_output_summary, train_output_cv;
select madlib.tree_train('dt_golf', -- 训练数据表
'train_output', -- 输出模型表
'id', -- id列
'class', -- 因变量是分类
'"outlook", temperature, humidity, windy', -- 四个属性是特征,注意加了双引号的outlook,要区分大小写
null::text, -- 没有排除列
'gini', -- 分裂标准使用gini
null::text, -- 无分组
null::text, -- 无权重
5, -- 因为只有4个特征,设置最大深度为5,防止过拟合
3, -- 最小分裂元组数
1, -- 最小桶数,min_split/3
10, -- 每个连续性变量的离散型分位点数量
'cp=0,n_folds=6' -- 初始cp=0,6折验证
);
(1)查询概要表
\x
select * from train_output_summary;
结果:
-[ RECORD 1 ]---------+-----------------------------------------------
method | tree_train
is_classification | t
source_table | dt_golf
model_table | train_output
id_col_name | id
dependent_varname | class
independent_varnames | "outlook", windy, temperature, humidity
cat_features | "outlook",windy
con_features | temperature,humidity
grouping_cols |
num_all_groups | 1
num_failed_groups | 0
total_rows_processed | 14
total_rows_skipped | 0
dependent_var_levels | "'Don't Play'","'Play'"
dependent_var_type | text
input_cp | 0
independent_var_types | text, text, double precision, double precision
说明:
(2)查询决策树表
\x
select madlib.tree_display('train_output', false);
结果:
tree_display
-----------------------------------------------------------------------------------
-------------------------------------
- Each node represented by 'id' inside ().
- Each internal nodes has the split condition at the end, while each
leaf node has a * at the end.
- For each internal node (i), its child nodes are indented by 1 level
with ids (2i+1) for True node and (2i+2) for False node.
- Number of (weighted) rows for each response variable inside [].'
The response label order is given as ['"\'Don\'t Play\'"', '"\'Play\'"'].
For each leaf, the prediction is given after the '-->'
-------------------------------------
(0)[5 9] "outlook" in {overcast}
(1)[0 4] * --> "'Play'"
(2)[5 5] temperature <= 75
(5)[3 5] temperature <= 65
(11)[1 0] * --> "'Don't Play'"
(12)[2 5] temperature <= 70
(25)[0 3] * --> "'Play'"
(26)[2 2] temperature <= 72
(53)[2 0] * --> "'Don't Play'"
(54)[0 2] * --> "'Play'"
(6)[2 0] * --> "'Don't Play'"
-------------------------------------
(1 row)
说明:
(3)以dot格式显示决策树
\t -- 不显示表头
\o test.dot -- 将查询结果输出到文件
select madlib.tree_display('train_output', true, true); -- 查询决策树,输出详细信息
\o
\t
生成dot文件后,使用第三发图形软件画出决策树,执行以下shell命令:
# 安装GraphViz
yum -y install graphviz
# 将dot文件转成jpg文件输出
dot -Tjpg test.dot -o test.jpg
生成的决策树如图2所示
图2
图中显示的决策树与文本的输出一致,矩形为叶子节点,椭圆形为内部测试节点。除了文本输出的信息外,图中还多了一个impurity,代表不纯度,是指将来自集合中的某种结果随机应用在集合中,某一数据项的预期误差率。不纯度越小,纯度越高,集合的有序程度越高,分类的效果越好。叶子节点的不纯度为0。
(4)查询交叉验证结果表
select * from train_output_cv;
结果:
cp | cv_error_avg | cv_error_stddev
-----+------------------------+--------------------------------------------
0 | 0.54861111111111111111 | 0.1827757821265895499515345089798222389039
0.2 | 0.58333333333333333333 | 0.2297341458681703628002325108823829393492
(2 rows)
可以看到,随着cp值的增大,剪枝增多,精度降低。
分类树算法可以通过特征,找出最好地解释因变量class(是否打高尔夫球)的方法。
(1)变量outlook的范畴被划分为两组:多云天和其它。我们得出第一个结论:如果天气是多云,人们总是选择玩高尔夫。
(2)在不是多云天气时,以气温划分,当气温高于华氏75度或低于华氏65度时,没人打高尔夫;65到70度之间人们选择玩高尔夫,70到72度之间没人打;72到75度会打。
这就通过分类树给出了一个解决方案。小王在晴天、雨天并且气温过高或过低时解雇了大部分员工,因为这种天气不会有人打高尔夫。而其他的天气会有很多人打高尔夫,因此可以雇用一些临时员工来工作。
从交叉验证结果来看,即便是初始cp=0,得到的标准差仍然较大,这和我们的样本数据过少有关。从本示例的分析中就可以看到,65到70度、72到75度会打高尔夫,而70到72度之间没人打,这个预测显然有悖常理。现在就用此模型预测一下原始数据,再和实际情况对比一下。这里只是演示一下如何用模型进行预测,实践中训练数据集与预测数据集相同意义不大。
drop table if exists prediction_results;
select madlib.tree_predict('train_output', -- 决策树模型
'dt_golf', -- 被预测的数据表
'prediction_results', -- 预测结果表
'response'); -- 预测结果
select t1.*,t2.class
from prediction_results t1, dt_golf t2
where t1.id=t2.id order by id;
结果:
id | estimated_class | class
----+-----------------+--------------
1 | 'Don't Play' | 'Don't Play'
2 | 'Don't Play' | 'Don't Play'
3 | 'Play' | 'Play'
4 | 'Play' | 'Play'
5 | 'Play' | 'Play'
6 | 'Don't Play' | 'Don't Play'
7 | 'Play' | 'Play'
8 | 'Don't Play' | 'Don't Play'
9 | 'Play' | 'Play'
10 | 'Play' | 'Play'
11 | 'Play' | 'Play'
12 | 'Play' | 'Play'
13 | 'Play' | 'Play'
14 | 'Don't Play' | 'Don't Play'
(14 rows)