CN104537010A - 基于决策树的网构软件中的构件分类方法 - Google Patents

Abstract

本发明公开了一种基于决策树的网构软件中的构件分类方法。在网构软件的构件库中新加入构件，对于新加入构件的分类使用数据挖掘中的决策树技术；使用基于信息增益的ID3算法对新加入构件的推荐度进行分析，建立决策树，完成构件分类。本方法将决策树技术应用于网构软件中的构件分类中，利用信息增益用来衡量构件属性的值为整个分类所能提供的信息量，分类规则直观，易于理解实现，且分类效率高。

Description

基于决策树的网构软件中的构件分类方法

技术领域

本发明涉及一种对网构软件的构件库中的构件分类方法，尤其涉及一种基于决策树的网构软件中的构件分类方法。

背景技术

大量的非结构化的信息分散在整个Internet中，在给人们带来方便的同时也带来了许多问题：信息过量，难以消化；信息真假难以辨识；信息安全难以保证；信息形式不一致，难以统一处理。建立在Internet上的网构软件的构件库也存在同样的困惑，所以在构件的提供者与构件的消费者之间应有一个中间环节，通过这个环节，需要对构件信息进行一些预处理，使得构件消费者能够快捷方便地得到想要的构件。

数据挖掘技术能够满足这一需求。数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。它包括问题定义，数据准备，挖掘操作和结果解释几个主要的部分。对一个数据挖掘系统而言，问题定义和数据准备很重要，是系统能否达到预期目的的关键。挖掘算法的选择和挖掘模型的建立是一个数据挖掘系统的核心部分。算法的合理选择和组织是建立良好的挖掘模型的基础。

发明内容

本发明的目的是克服现有技术的不足，提供一种基于决策树的网构软件中的构件分类方法。

本发明的技术方案如下：

一种基于决策树的网构软件中的构件分类方法包括如下：

1)在网构软件的构件库中新加入构件，对于新加入构件的分类使用数据挖掘中的决策树技术；

2)使用基于信息增益的ID3算法对新加入构件的推荐度进行分析，建立决策树，完成构件分类。

所述的决策树技术为：决策树技术是用于分类和预测的技术，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则，它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，然后进行剪枝，最后在决策树的叶节点得到结论；决策树的根节点是整个数据集合空间，即网构软件构件库中所有的构件，每个分节点是对一个单一属性的测试，该测试将数据集合空间分割成两个或更多块，每个叶节点是属于单一类别的记录。

所述的基于信息增益的ID3算法具体为：在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息，实现方法为：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它用来对新的样本进行分类。

所述的基于信息增益的ID3算法的信息增益，具体为：信息增益用来衡量某个属性中的值为整个分类所能提供的信息量，在决策树算法中，信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，在信息增益计算方面，使用3个公式；信息增益需要使用到熵的概念，熵的概念如公式(1)所示：

$\mathrm{Entropy}\left(S\right)=-\underset{i=1}{\overset{k}{\mathrm{\Σ}}}P\left(i\right)*{\log }_{2}P\left(i\right)---\left(1\right)$

在公式(1)中，S表示样本集合，k是样本数量，P(i)是属于分类i的样本与整个样本集合的比例,熵的取值范围是0～1，如果所有S属于相同的类，则熵为0，即数据分类完毕；如果熵取值为1，则代表S中样本是完全随机的选自不同的类；

Entropy(S,A)＝Σ(|S_v|/|S|)*Entropy(S_v)  (2)

Entropy(S,A)是属性A在集合S上的熵，S_v是属性A对应的有v值的子集，公式(2)是把属性A的所有可能的值都分别作了运算，并把结果相加，|Sv|指集合Sv中的元素个数，|S|指集合S中的元素个数；

Gain(S,A)是属性A在集合S上的信息增益，Gain(S,A)的值越大，说明选择测试属性A对分类提供的信息越多，如公式(3)所示：

Gain(S,A)＝Entropy(S)-Entropy(S,A)  (3)。

所述的建立决策树的方法具体为：首先寻找初始分裂，整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的，决定哪个属性域作为目前最好的分类指标，做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂；建决策树，就是根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复建立下层结点和分支，建决策树的关键在于建立分支时对记录字段不同取值的选择，选择不同的字段值，会使划分出来的记录子集不同，影响决策树生长的快慢以及决策树结构的好坏，从而导致找到的规则信息的优劣,构件检索使用的决策树算法具体为：

1)初始化决策树T为只含一个树根(X，Q)，其中X是全体样本集，Q为全体属性集；

2)如果T中所有叶结点(X’，Q’)都满足X’属于同一类或Q’为空，那么算法停止；否则执行步骤3)；

3)计算Q中每个属性的信息增益，选择信息增益最高的属性作为节点的测试属性，记该属性为A；

4)从信息增益最高的属性所对应的节点出发，在X’中求得属性A的值等于给定值的子集，并生成相应的叶结点；

5)重复步骤2)～步骤4)，直到T中所有叶结点(X’，Q’)都满足X’属于同一类或Q’为空。

所述的穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂，具体为：

1)利用公式(1)，计算决策属性的熵，

2)计算条件属性的熵，样本集共有多个条件属性，使用公式(2)分别计算条件属性的熵，计算分两个过程，首先利用公式(1)计算属性值的熵，然后再用公式(2)计算属性的熵；

3)使用公式(3)分别计算条件属性的信息增益：

选择信息增益最大的条件属性作为决策树的根节点，进行支节点的选取。

所述的进行支节点的选取，具体为：使用样本所有条件属性中信息增益最大的条件属性为根节点，用剩余的条件属性重复权利要求6中步骤1)～步骤3)的操作，选取增益最大的条件属性作为支节点；并对选取支节点后的剩余条件属性重复权利要求6中步骤1)～步骤3)的操作，直到剩余的属性数量为1为止。

数据挖掘是指从大量的不完全的，有噪声的，模糊的数据中提取隐含的、未知的、非平凡的及有潜在应用价值的信息或模式。决策树是一种简单的数据挖掘方法，本发明把决策树技术用于网构软件的构件库中，使用了基于信息增益的ID3算法对已有构件的推荐度进行分析，建立决策树，进而为新加入构件库的构件进行分类。

本方法将决策树技术应用于网构软件中的构件分类中，利用信息增益用来衡量构件属性的值为整个分类所能提供的信息量，分类规则直观，易于理解实现，且分类效率高。

附图说明

图1为网构软件构件库中构件的主要属性；

图2为四个条件属性的熵；

图3构件检索使用的决策树算法；

图4构件的条件属性以及属性值。

具体实施方式

把整个构件库的所有已知构件作为训练集，通过决策树来决定新加入的构件的推荐分类(用是/否来标志是否是系统推荐的构件)。网构软件构件库中的构件主要属性如图1所示。可见，并非所有的属性都对建立决策树有用，因此我们选取了4个属性：ComType(构件类型)、ValidTime(有效时间)、EntityType(实体类型)以及RepCount(复本个数)来描述构件，目的是找出这4个属性和推荐度(推荐/不推荐)的关系。

决策树技术是用于分类和预测的主要技术，决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，然后进行剪枝，最后在决策树的叶节点得到结论。决策树作为一棵树，树的根节点是整个数据集合空间(即网构软件构件库中所有的构件)，每个分节点是对一个单一变量的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于单一类别的记录。构造决策树的过程为：首先寻找初始分裂。整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的。决定哪个属性域作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。建决策树，就是根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复建立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值，会使划分出来的记录子集不同，影响决策树生长的快慢以及决策树结构的好坏，从而导致找到的规则信息的优劣。图3说明了构造决策树算法。

对决策树决策结果的好坏有三种评价或比较尺度：

(1)预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。

(2)计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。

(3)模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就更有用。

本发明利用ID3算法构造决策树，ID3算法的核心是：在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

算法中涉及信息增益的计算。信息增益(Information Gain，简称IG)用来衡量某个属性中的值为整个分类所能提供的信息量，在决策树算法中，信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁。

本发明在信息增益计算方面，主要使用了3个公式。由于信息增益需要使用到“熵”(Entropy)，因此首先来定义熵的概念，如公式(1)所示。

$\mathrm{Entropy}\left(S\right)=-\underset{i=1}{\overset{k}{\mathrm{\Σ}}}P\left(i\right)*{\log }_{2}P\left(i\right)---\left(1\right)$

在公式(1)中，S表示样本集合，k是样本数量，P(i)是属于分类i的样本与整个样本集合的比例。如果所有S属于相同的类，则熵为0(数据分类完毕)。熵的取值范围是0(分类完毕)到1(完全随机)。

Entropy(S,A)＝Σ(|S_v|/|S|)*Entropy(S_v)  (2)

S_v是属性A对应的有v值的子集，公式(2)是把属性A的所有可能的值都分别作了运算，并把结果相加。|Sv|指集合Sv中的元素个数，|S|指集合S中的元素个数。

Gain(S,A)是属性A在集合S上的信息增益，Gain(S,A)的值越大，说明选择测试属性A对分类提供的信息越多，如公式(3)所示。

Gain(S,A)＝Entropy(S)-Entropy(S,A)  (3)

当一个构件加入构件库的时候，构件库便根据现有的样本数据生成决策树，为新加入的构件分类。之后系统会进一步根据实际使用情况调整推荐度的具体数值，因此，决策树仅仅在对构件初始化的时候使用。

实例中，构件库中已有构件100个，当一个新的构件请求加入构件库时，决策树程序启动，目标是“新加入的构件是系统推荐的构件吗？”。它有两种选择，是或者否。构件用四个属性来刻画，它们的属性值如图4所示。

注意，有效时间和复本个数在构件库的数据库中存放的都是具体的数值，而这里却需要一个定性的值，因此在构造决策树之前需要转换这里的值，例如，有效时间是1000小时之内的认为有效时间的值为“短”，否则有效时间的值为“长”。接下来，进行根节点的选择。

第一步，利用公式(1)，计算决策属性的熵。实例中，样本集有100个构件的记录，其中65个记录的推荐属性为“是”，35个为“否”，则：Entropy(推荐)＝‐(65/100)*log2(65/100)‐(35/100)*log2(35/100)＝0.934。

第二步，计算条件属性的熵。样本集共有四个条件属性，使用公式(2)分别计算条件属性的熵。计算分两个过程，首先利用公式(1)计算属性值的熵，然后再用公式(2)计算属性的熵。计算结果见图2。样本集合中，在线构件25个，其中推荐的有10个，离线构件75个，其中推荐的有55个；有效时间长的构件81个，其中推荐的有60个，有效时间短的构件19个，推荐的5个；实体类型为文件实体的构件69个，推荐的为45个，实体类型为逻辑服务的构件31个，推荐的为20个；复本个数多的构件60个，推荐的为45个，复本个数少的构件个数是40个，推荐的为20个。

第三步，使用公式(3)分别计算条件属性的信息增益：

Gain(S,构件类型)＝Entropy(推荐)‐Entropy(S,构件类型)＝0.934‐0.871＝0.063

Gain(S,有效时间)＝Entropy(推荐)‐Entropy(S,有效时间)＝0.934‐0.827＝0.107

Gain(S,实体类型)＝Entropy(推荐)‐Entropy(S,实体类型)＝0.934‐0.934＝0

Gain(S,复本个数)＝Entropy(推荐)‐Entropy(S,复本个数)＝0.934‐0.887＝0.047

可以发现，条件属性“有效时间”有最大的增益，所以它用于决策树的根节点。接着，进行支节点的选取。因为有效时间有两种类型，因此根节点就有两个分支(长，短)，接下来的问题是“在有效时间长的支节点处应该检验什么属性？”，“在有效时间短的支节点处又应该检验什么属性？”。因为已经使用了有效时间为根节点，只能用剩余的三个变量：构件类型，实体类型或复本个数。算法和选取根节点类似，这里就不再赘述了。

Claims (7)

1.一种基于决策树的网构软件中的构件分类方法，其特征在于包括如下：

1)在网构软件的构件库中新加入构件，对于新加入构件的分类使用数据挖掘中的决策树技术；

2)使用基于信息增益的ID3算法对新加入构件的推荐度进行分析，建立决策树，完成构件分类。

2.如权利要求1所述的网构软件中的构件分类方法，其特征在于所述的决策树技术为：决策树技术是用于分类和预测的技术，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则，它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，然后进行剪枝，最后在决策树的叶节点得到结论；决策树的根节点是整个数据集合空间，即网构软件构件库中所有的构件，每个分节点是对一个单一属性的测试，该测试将数据集合空间分割成两个或更多块，每个叶节点是属于单一类别的记录。

3.如权利要求1所述的网构软件中的构件分类方法，其特征在于所述的基于信息增益的ID3算法具体为：在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息，实现方法为：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它用来对新的样本进行分类。

4.如权利要求3所述的网构软件中的构件分类方法，其特征在于所述的基于信息增益的ID3算法的信息增益，具体为：信息增益用来衡量某个属性中的值为整个分类所能提供的信息量，在决策树算法中，信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，在信息增益计算方面，使用3个公式；信息增益需要使用到熵的概念，熵的概念如公式(1)所示：

$\mathrm{Entropy}\left(S\right)=-\underset{i=1}{\overset{k}{\mathrm{\Σ}}}P\left(i\right)*{\log }_{2}P\left(i\right)---\left(1\right)$

在公式(1)中，S表示样本集合，k是样本数量，P(i)是属于分类i的样本与整个样本集合的比例,熵的取值范围是0～1，如果所有S属于相同的类，则熵为0，即数据分类完毕；如果熵取值为1，则代表S中样本是完全随机的选自不同的类；

Entropy(S,A)＝Σ(|S_v|/|S|)*Entropy(S_v)       (2)

Entropy(S,A)是属性A在集合S上的熵，S_v是属性A对应的有v值的子集，公式(2)是把属性A的所有可能的值都分别作了运算，并把结果相加，|Sv|指集合Sv中的元素个数，|S|指集合S中的元素个数；

Gain(S,A)是属性A在集合S上的信息增益，Gain(S,A)的值越大，说明选择测试属性A对分类提供的信息越多，如公式(3)所示：

Gain(S,A)＝Entropy(S)-Entropy(S,A)        (3)。

5.如权利要求1所述的网构软件中的构件分类方法，其特征在于所述的建立决策树的方法具体为：首先寻找初始分裂，整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的，决定哪个属性域作为目前最好的分类指标，做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂；建决策树，就是根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复建立下层结点和分支，建决策树的关键在于建立分支时对记录字段不同取值的选择，选择不同的字段值，会使划分出来的记录子集不同，影响决策树生长的快慢以及决策树结构的好坏，从而导致找到的规则信息的优劣,构件检索使用的决策树算法具体为：

1)初始化决策树T为只含一个树根(X，Q)，其中X是全体样本集，Q为全体属性集；

2)如果T中所有叶结点(X’，Q’)都满足X’属于同一类或Q’为空，那么算法停止；否则执行步骤3)；

3)计算Q中每个属性的信息增益，选择信息增益最高的属性作为节点的测试属性，记该属性为A；

4)从信息增益最高的属性所对应的节点出发，在X’中求得属性A的值等于给定值的子集，并生成相应的叶结点；

5)重复步骤2)～步骤4)，直到T中所有叶结点(X’，Q’)都满足X’属于同一类或Q’为空。

6.如权利要求5所述的所述的网构软件中的构件分类方法，其特征在于所述的穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂，具体为：

1)利用公式(1)，计算决策属性的熵，

2)计算条件属性的熵，样本集共有多个条件属性，使用公式(2)分别计算条件属性的熵，计算分两个过程，首先利用公式(1)计算属性值的熵，然后再用公式(2)计算属性的熵；

3)使用公式(3)分别计算条件属性的信息增益：

选择信息增益最大的条件属性作为决策树的根节点，进行支节点的选取。

7.如权利要求6所述的所述的网构软件中的构件分类方法，其特征在于所述的进行支节点的选取，具体为：使用样本所有条件属性中信息增益最大的条件属性为根节点，用剩余的条件属性重复权利要求6中步骤1)～步骤3)的操作，选取增益最大的条件属性作为支节点；并对选取支节点后的剩余条件属性重复权利要求6中步骤1)～步骤3)的操作，直到剩余的属性数量为1为止。