大学生体育训练决策支持系统中ID3算法的改进研究
2014-06-16王建伟等
王建伟等
摘 要：引入ID3算法的大学生体育训练决策支持系统可以根据学生的特征对其分类。而传统的决策树ID3算法存在多值倾向的问题，选择分裂属性不符合客观事实。本文运用了一种基于灰色关联度的修正因子属性选择方法予以改进，克服了传统ID3算法的不足，改进的ID3算法可使分类更加精确，更好的为大学生体育训练提供决策支持。
关键词：ID3算法 决策支持系统 数据挖掘 灰色关联度
中图分类号：G434 文献标识码：A 文章编号：1674-098X（2014）02（a）-0019-01
大学生体育训练决策支持系统是随着人工智能理论与数据挖掘技术的发展而不断发展的，通过对大学生身体素质和训练等数据来进行有效的挖掘，产生用于辅助决策的规则，进而为大学生体育训练制定相应的训练方案[1]。系统中应用了数据挖掘的决策树ID3算法对不同特征的学生进行分类，但传统的ID3算法存在多值倾向的问题，选择分裂属性不符合客观事实，同时，在构造树的过程中，需要多次自上而下对数据集的排序和扫描，因而导致算法的处理效率较低[2]，如何改进算法从而使分类更加精确是我们亟需解决的问题。
1 ID3算法的改进
灰色关联分析是指对一个系统发展变化态势的定量描述和比较的方法，分析考虑了各因素之间的相关性，比系统分析中常用的因素两两对比法要更合理，更科学[3]。同时考虑到正弦函数的曲线变化比较缓和，对信息增益因子修正不会出现过度的问题。因此，本文引入灰色关联度的正弦值作为ID3算法的修正因子进行改进。改进的ID3算法的具体流程是：
（1）计算各特征属性与类别属性之间的灰色关联度，并将它们排序；
（2）对取值较多的属性通过灰色关联度来判断是否最优，从而确定是否降低它的信息增益；
（3）对取值较多但灰色关联度低的属性，在计算其信息增益时通过灰色关联度的正弦值作为修正因子，而其它属性计算信息增益时修正因子设为0。
改进的ID3算法的描述如下：
算法：GBID（Sample_set，Attribute_set）
输入：由多个属性描述的训练样本集Sample_set；候选属性集Attribute_set。
输出：一棵决策树。
Begin
如果 Sample_set为空
则返回null；创建结点L；
如果结点L中的所有样本均属于同一类C
则返回L作为叶结点，并以类C为标记；
如果Attribute_set为空
则返回L作为叶结点，并以Sample_set中最普通的类标记；
计算出Attribute_set中每个属性的信息增益，并选择出信息增益最大的属性A和取值个数最多的属性B
如果 A=B，该条件成立说明选择信息增益最大和取值个数最多的属性作为测试属性易产生多值偏向问题，需要用修正因子降低该属性的信息增益
则根据公式
属性A具有多值倾向是其它来计算该属性的修正因子；
再根据公式重新计算该属性的信息增益；
否则该属性的修正系数为0，信息增益最大的属性不是取值个数最多属性，选择该属性作为分裂属性不会产生多值偏向问题，不需要用修正系数降低该属信息增益
从Attribute_set中选择出信息增益最大的属性Splitting_Attribute作为分裂属性；
标记结点L为Splitting _Attribute；
For Each Splitting_Attribute中的已知；
m为Splitting_Attribute的取值个数∥根据Splitting_Attribute的取值划分Sample_set
根据Splitting_Attribute=，从结点L产生相应分支表示测试条件；
设为Splitting_Attribute=所获得的样本集；
如果为空
则加上一个叶结点，并标记为Sample_set中最普通的类；
否则加上GBID（Attribute_set，Splitting _Attribute）返回的结点；
End。
2 改进后的ID3算法的应用
我们选取十个学生的篮球训练样本集作说明，每个学生有四个属性，分别为力量、身高、灵活性、速度。每条学生记录为（学号 力量 身高 灵活性 速度 评价），十条学生记录为（20100001强高好慢Y），（20100002强高好块Y），（20100003强矮好慢Y），（20100004强中一般慢N），（20100005弱中差慢N），（20100006弱中差块N），（20100007弱矮差快N），（20100008强高一般慢Y），（20100009弱高差慢N），（20100010弱中一般慢N）。力量为强、弱，量化为{0，1}；身高为高、中、矮分别量化为{0，1，2}；灵活性为好、一般、差分别量化为{0，1，2}；速度为快、慢量化为{0，1}。根据训练集样本数据，依次根据公式计算各特征属性与分类属性的灰色关联度，结果为r（力量）=0.52，r（身高）=0.72，r（灵活性）=0.78，r（速度）=0.56，然后计算上述属性信息增益，可得Gain（力量）=0.4816，Gain（身高）=0.0275，Gain（灵活性）=0.0588，Gain（速度）=0.0368，因为力量的信息增益最大、取值个数最多但灰色关联度最低，所以需要用修正因子降低其信息增益，设定修正因子CF（力量）为sin（0.52）=0.4968，而其它属性的信息增益设定为0，则改进的ID3算法算得的Gain（力量）=-0.2196。因而会选择信息增益最大的灵活性作为分裂属性。
从上面实例可知，ID3算法确定决策树的根节点时，选择信息增益最大的力量作为分裂属性，显然这与客观事实不符。而改进的ID3算法在确定根节点时，选择灵活性作为分裂属性，符合客观事实，避免了多值但非最优属性的力量成为分裂属性。
3 结语
改进的ID3算法避免了传统算法的多值倾向问题，使分类更加精确。首先，通过训练集总结出学生分类模型，通过上述模型我们可以对新加入的学生进行预测，然后再将不同的学生根据模型添加到不同的类型中。把不同学生的特征存入了相应的用户库之后，教师可以通过它及时地了解学生的信息，并以此为依据为不同的学生提供不同的教学策略的决策支持。
参考文献
[1] 王鑫，王建伟，钟玉峰，等.个性化远程教学平台中数据挖掘技术的应用[J].黑龙江工程学院学报（自然科学版），2010（24）：72-74.
[2] 孙卫强.决策树方法在远程教育辅助教学中的应用研究[D].中山大学，2010：22-25.
[3] 叶明全，胡学钢.一种基于灰色关联度的决策树改进算法[J].2007，43（32）：171-173.
摘 要：引入ID3算法的大学生体育训练决策支持系统可以根据学生的特征对其分类。而传统的决策树ID3算法存在多值倾向的问题，选择分裂属性不符合客观事实。本文运用了一种基于灰色关联度的修正因子属性选择方法予以改进，克服了传统ID3算法的不足，改进的ID3算法可使分类更加精确，更好的为大学生体育训练提供决策支持。
关键词：ID3算法 决策支持系统 数据挖掘 灰色关联度
中图分类号：G434 文献标识码：A 文章编号：1674-098X（2014）02（a）-0019-01
大学生体育训练决策支持系统是随着人工智能理论与数据挖掘技术的发展而不断发展的，通过对大学生身体素质和训练等数据来进行有效的挖掘，产生用于辅助决策的规则，进而为大学生体育训练制定相应的训练方案[1]。系统中应用了数据挖掘的决策树ID3算法对不同特征的学生进行分类，但传统的ID3算法存在多值倾向的问题，选择分裂属性不符合客观事实，同时，在构造树的过程中，需要多次自上而下对数据集的排序和扫描，因而导致算法的处理效率较低[2]，如何改进算法从而使分类更加精确是我们亟需解决的问题。
1 ID3算法的改进
灰色关联分析是指对一个系统发展变化态势的定量描述和比较的方法，分析考虑了各因素之间的相关性，比系统分析中常用的因素两两对比法要更合理，更科学[3]。同时考虑到正弦函数的曲线变化比较缓和，对信息增益因子修正不会出现过度的问题。因此，本文引入灰色关联度的正弦值作为ID3算法的修正因子进行改进。改进的ID3算法的具体流程是：
（1）计算各特征属性与类别属性之间的灰色关联度，并将它们排序；
（2）对取值较多的属性通过灰色关联度来判断是否最优，从而确定是否降低它的信息增益；
（3）对取值较多但灰色关联度低的属性，在计算其信息增益时通过灰色关联度的正弦值作为修正因子，而其它属性计算信息增益时修正因子设为0。
改进的ID3算法的描述如下：
算法：GBID（Sample_set，Attribute_set）
输入：由多个属性描述的训练样本集Sample_set；候选属性集Attribute_set。
输出：一棵决策树。
Begin
如果 Sample_set为空
则返回null；创建结点L；
如果结点L中的所有样本均属于同一类C
则返回L作为叶结点，并以类C为标记；
如果Attribute_set为空
则返回L作为叶结点，并以Sample_set中最普通的类标记；
计算出Attribute_set中每个属性的信息增益，并选择出信息增益最大的属性A和取值个数最多的属性B
如果 A=B，该条件成立说明选择信息增益最大和取值个数最多的属性作为测试属性易产生多值偏向问题，需要用修正因子降低该属性的信息增益
则根据公式
属性A具有多值倾向是其它来计算该属性的修正因子；
再根据公式重新计算该属性的信息增益；
否则该属性的修正系数为0，信息增益最大的属性不是取值个数最多属性，选择该属性作为分裂属性不会产生多值偏向问题，不需要用修正系数降低该属信息增益
从Attribute_set中选择出信息增益最大的属性Splitting_Attribute作为分裂属性；
标记结点L为Splitting _Attribute；
For Each Splitting_Attribute中的已知；
m为Splitting_Attribute的取值个数∥根据Splitting_Attribute的取值划分Sample_set
根据Splitting_Attribute=，从结点L产生相应分支表示测试条件；
设为Splitting_Attribute=所获得的样本集；
如果为空
则加上一个叶结点，并标记为Sample_set中最普通的类；
否则加上GBID（Attribute_set，Splitting _Attribute）返回的结点；
End。
2 改进后的ID3算法的应用
我们选取十个学生的篮球训练样本集作说明，每个学生有四个属性，分别为力量、身高、灵活性、速度。每条学生记录为（学号 力量 身高 灵活性 速度 评价），十条学生记录为（20100001强高好慢Y），（20100002强高好块Y），（20100003强矮好慢Y），（20100004强中一般慢N），（20100005弱中差慢N），（20100006弱中差块N），（20100007弱矮差快N），（20100008强高一般慢Y），（20100009弱高差慢N），（20100010弱中一般慢N）。力量为强、弱，量化为{0，1}；身高为高、中、矮分别量化为{0，1，2}；灵活性为好、一般、差分别量化为{0，1，2}；速度为快、慢量化为{0，1}。根据训练集样本数据，依次根据公式计算各特征属性与分类属性的灰色关联度，结果为r（力量）=0.52，r（身高）=0.72，r（灵活性）=0.78，r（速度）=0.56，然后计算上述属性信息增益，可得Gain（力量）=0.4816，Gain（身高）=0.0275，Gain（灵活性）=0.0588，Gain（速度）=0.0368，因为力量的信息增益最大、取值个数最多但灰色关联度最低，所以需要用修正因子降低其信息增益，设定修正因子CF（力量）为sin（0.52）=0.4968，而其它属性的信息增益设定为0，则改进的ID3算法算得的Gain（力量）=-0.2196。因而会选择信息增益最大的灵活性作为分裂属性。
从上面实例可知，ID3算法确定决策树的根节点时，选择信息增益最大的力量作为分裂属性，显然这与客观事实不符。而改进的ID3算法在确定根节点时，选择灵活性作为分裂属性，符合客观事实，避免了多值但非最优属性的力量成为分裂属性。
3 结语
改进的ID3算法避免了传统算法的多值倾向问题，使分类更加精确。首先，通过训练集总结出学生分类模型，通过上述模型我们可以对新加入的学生进行预测，然后再将不同的学生根据模型添加到不同的类型中。把不同学生的特征存入了相应的用户库之后，教师可以通过它及时地了解学生的信息，并以此为依据为不同的学生提供不同的教学策略的决策支持。
参考文献
[1] 王鑫，王建伟，钟玉峰，等.个性化远程教学平台中数据挖掘技术的应用[J].黑龙江工程学院学报（自然科学版），2010（24）：72-74.
[2] 孙卫强.决策树方法在远程教育辅助教学中的应用研究[D].中山大学，2010：22-25.
[3] 叶明全，胡学钢.一种基于灰色关联度的决策树改进算法[J].2007，43（32）：171-173.
摘 要：引入ID3算法的大学生体育训练决策支持系统可以根据学生的特征对其分类。而传统的决策树ID3算法存在多值倾向的问题，选择分裂属性不符合客观事实。本文运用了一种基于灰色关联度的修正因子属性选择方法予以改进，克服了传统ID3算法的不足，改进的ID3算法可使分类更加精确，更好的为大学生体育训练提供决策支持。
关键词：ID3算法 决策支持系统 数据挖掘 灰色关联度
中图分类号：G434 文献标识码：A 文章编号：1674-098X（2014）02（a）-0019-01
大学生体育训练决策支持系统是随着人工智能理论与数据挖掘技术的发展而不断发展的，通过对大学生身体素质和训练等数据来进行有效的挖掘，产生用于辅助决策的规则，进而为大学生体育训练制定相应的训练方案[1]。系统中应用了数据挖掘的决策树ID3算法对不同特征的学生进行分类，但传统的ID3算法存在多值倾向的问题，选择分裂属性不符合客观事实，同时，在构造树的过程中，需要多次自上而下对数据集的排序和扫描，因而导致算法的处理效率较低[2]，如何改进算法从而使分类更加精确是我们亟需解决的问题。
1 ID3算法的改进
灰色关联分析是指对一个系统发展变化态势的定量描述和比较的方法，分析考虑了各因素之间的相关性，比系统分析中常用的因素两两对比法要更合理，更科学[3]。同时考虑到正弦函数的曲线变化比较缓和，对信息增益因子修正不会出现过度的问题。因此，本文引入灰色关联度的正弦值作为ID3算法的修正因子进行改进。改进的ID3算法的具体流程是：
（1）计算各特征属性与类别属性之间的灰色关联度，并将它们排序；
（2）对取值较多的属性通过灰色关联度来判断是否最优，从而确定是否降低它的信息增益；
（3）对取值较多但灰色关联度低的属性，在计算其信息增益时通过灰色关联度的正弦值作为修正因子，而其它属性计算信息增益时修正因子设为0。
改进的ID3算法的描述如下：
算法：GBID（Sample_set，Attribute_set）
输入：由多个属性描述的训练样本集Sample_set；候选属性集Attribute_set。
输出：一棵决策树。
Begin
如果 Sample_set为空
则返回null；创建结点L；
如果结点L中的所有样本均属于同一类C
则返回L作为叶结点，并以类C为标记；
如果Attribute_set为空
则返回L作为叶结点，并以Sample_set中最普通的类标记；
计算出Attribute_set中每个属性的信息增益，并选择出信息增益最大的属性A和取值个数最多的属性B
如果 A=B，该条件成立说明选择信息增益最大和取值个数最多的属性作为测试属性易产生多值偏向问题，需要用修正因子降低该属性的信息增益
则根据公式
属性A具有多值倾向是其它来计算该属性的修正因子；
再根据公式重新计算该属性的信息增益；
否则该属性的修正系数为0，信息增益最大的属性不是取值个数最多属性，选择该属性作为分裂属性不会产生多值偏向问题，不需要用修正系数降低该属信息增益
从Attribute_set中选择出信息增益最大的属性Splitting_Attribute作为分裂属性；
标记结点L为Splitting _Attribute；
For Each Splitting_Attribute中的已知；
m为Splitting_Attribute的取值个数∥根据Splitting_Attribute的取值划分Sample_set
根据Splitting_Attribute=，从结点L产生相应分支表示测试条件；
设为Splitting_Attribute=所获得的样本集；
如果为空
则加上一个叶结点，并标记为Sample_set中最普通的类；
否则加上GBID（Attribute_set，Splitting _Attribute）返回的结点；
End。
2 改进后的ID3算法的应用
我们选取十个学生的篮球训练样本集作说明，每个学生有四个属性，分别为力量、身高、灵活性、速度。每条学生记录为（学号 力量 身高 灵活性 速度 评价），十条学生记录为（20100001强高好慢Y），（20100002强高好块Y），（20100003强矮好慢Y），（20100004强中一般慢N），（20100005弱中差慢N），（20100006弱中差块N），（20100007弱矮差快N），（20100008强高一般慢Y），（20100009弱高差慢N），（20100010弱中一般慢N）。力量为强、弱，量化为{0，1}；身高为高、中、矮分别量化为{0，1，2}；灵活性为好、一般、差分别量化为{0，1，2}；速度为快、慢量化为{0，1}。根据训练集样本数据，依次根据公式计算各特征属性与分类属性的灰色关联度，结果为r（力量）=0.52，r（身高）=0.72，r（灵活性）=0.78，r（速度）=0.56，然后计算上述属性信息增益，可得Gain（力量）=0.4816，Gain（身高）=0.0275，Gain（灵活性）=0.0588，Gain（速度）=0.0368，因为力量的信息增益最大、取值个数最多但灰色关联度最低，所以需要用修正因子降低其信息增益，设定修正因子CF（力量）为sin（0.52）=0.4968，而其它属性的信息增益设定为0，则改进的ID3算法算得的Gain（力量）=-0.2196。因而会选择信息增益最大的灵活性作为分裂属性。
从上面实例可知，ID3算法确定决策树的根节点时，选择信息增益最大的力量作为分裂属性，显然这与客观事实不符。而改进的ID3算法在确定根节点时，选择灵活性作为分裂属性，符合客观事实，避免了多值但非最优属性的力量成为分裂属性。
3 结语
改进的ID3算法避免了传统算法的多值倾向问题，使分类更加精确。首先，通过训练集总结出学生分类模型，通过上述模型我们可以对新加入的学生进行预测，然后再将不同的学生根据模型添加到不同的类型中。把不同学生的特征存入了相应的用户库之后，教师可以通过它及时地了解学生的信息，并以此为依据为不同的学生提供不同的教学策略的决策支持。
参考文献
[1] 王鑫，王建伟，钟玉峰，等.个性化远程教学平台中数据挖掘技术的应用[J].黑龙江工程学院学报（自然科学版），2010（24）：72-74.
[2] 孙卫强.决策树方法在远程教育辅助教学中的应用研究[D].中山大学，2010：22-25.
[3] 叶明全，胡学钢.一种基于灰色关联度的决策树改进算法[J].2007，43（32）：171-173.
