基于聚类-决策树的玉米良种选育方法

摘要

本发明公开了一种基于聚类-决策树的玉米良种选育方法，包括数据预处理、建立决策树、根据形成的决策树，系统判断所输入的属性值属于哪个分类，并通过计算这个三维点和所属分类中其他点的距离，得到一个距离最小的点，这个点所具有的属性就是最接近于输入玉米品种的玉米属性，从子女表中查询出这个玉米品种的父类和母类，即完成玉米选育的功能。本发明结合聚类和决策树算法，可根据要求对玉米的生育信息、生长信息和收获信息等进行玉米良种的优选，可达到降低劳动强度，提高决策效率的目的。

说明书

技术领域：

本发明涉及一种玉米良种选育方法。

背景技术：

聚类是一种常见的数据分析工具，是指用数学的方法研究和处理给定对象，是多元统计分析的一种。基于“物以类聚”的思想，它把大量数据点的集合分成若干类或簇，使得每个类中的数据之间最大程度地相似，而不同类中的数据最大程度地不同，从而发现全局的分布模式以及数据属性之间的相互关系。聚类分析的一个突出特点是处理巨大、复杂的数据集，而且还可作为其他算法的预处理步骤。目前常用的聚类算法还有k-平均、k-模、k-中心点、DIANA、AGNES、STING、COBWEB等。

这些经典的聚类算法只能处理简单的、一般的数据，对于大型的、复杂的数据集效果欠佳，于是很多改进的和新的算法不断被提出。比如，有文献提出了一种进化的基于多中心的动态聚类算法，其中簇的数目不用预先制定，对于不同的簇可选择多个中心点，且由两个目标函数进行评估，提高了算法对于具有特殊特性和特殊分布的数据集的应用；CUZ算法改进了代表点的计算，不仅能有效地鉴别非圆形、非矩形形状的数据，还可以处理表面非凸起形状的簇；GriDBSCAN算法通过在数据空间构造网格，先局部采用密度算法，后聚合产生真正的簇，大大提高了DBSCAN的效率，降低了复杂度。还有一些新的算法，比如Yu Wei等人提出的凝聚层次聚类算法，采用了84维的空间序列来表示对象，通过对由两两对象间的皮尔森系数构成的矩阵进行凝聚，最终可获得较有效的系统树图；在种群算法和智能体的基础上提出的较新颖的蚂蚁算法，不必事先规定簇的数目，并且可通过计算局部的对象而非全部对象的方法来减少算法整个的计算量，能够发现任意形状的簇。

决策树方法是分类方法中应用较广泛的逻辑方法之一，它从一组无次序、无规则的实例中推理出决策树表示形式的分类规则，它采用自顶向下的递归方式，利用信息论中的互相信息(信息增益)寻找数据库中具有最大信息量的字段，建立决策树的一个结点，再根据字段的不同取值检查树的分支，在每一个分支子集中，重复建立树的下层结点和分支的过程。从决策树的根到叶节点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式。常用的方法有C4.5、ID3、CLS等。

目前已经提出了很多改进的决策树算法，比如Ding Rongtao等人在计算信息熵以鉴别属性的相关度时引入了用户的兴趣参数以减少属性间的冗余，加快了信息熵减少的速度；Fadila Bentayeb等人提出一种新的基于决策树的数据挖掘算法，通过在数据挖掘处理之前对数据进行的预处理，建立一张可能性表，并对此实施新的ID3算法和信息增益公式，简化了算法的复杂度，最终达到决策树分类的目的；关系分类方法RDC算法，使用ID数组传播来更新多关系决策树，可防止建立过大冗余的关系表，有效地防止了信息的丢失，优化了树结构，增强了算法的正确性。

信息技术已经在我国农业生产中得到广泛的应用，它大大推进了我国农业生产的发展，成为发展现代农业生产的重要支撑力量。在玉米良种的选育方面，存储着大量信息，如株高、穗高、全生育期、小区产量等，若能从中挖掘出正确的、可靠的、有用的规则，将对农业的发展与改革产生指导性的作用。

发明内容：

本发明的目的在于提供一种可根据要求对玉米的生育信息、生长信息和收获信息等进行玉米良种的优选，可达到降低劳动强度，提高决策效率的基于聚类-决策树的玉米良种选育方法。

本发明的技术解决方案是：

一种基于聚类-决策树的玉米良种选育方法，其特征是：包括下列步骤：

(1)数据预处理：将选择的三个属性对应成空间中的三维点，利用聚类算法中的k-平均算法，计算子女表中所有的记录点和重心之间的距离，比较大小，最终将所有的记录聚为两个簇，并使每个簇内的记录有较大的相似度，而不同的簇有较大的相异度；

(2)建立决策树：先离散化所选的三个属性的属性值，将它们分区成三类，并将千粒重作为分类属性，划分类别标记为低产、中产、高产，在输入全生育期、千粒重和小区产量这三个属性之后，根据欧氏距离公式：

$d(x_i,y_j)={\left(\underset{k=1}{\overset{m}{\Sigma }}{(x_{\mathrm{ik}}-x_{\mathrm{jk}})}^2\right)}^{\frac{1}{2}}$

即可判断这个三维点属于哪个聚类簇，得出结论后，对这个簇进行ID3算法的数据挖掘，计算出全生育期属性和小区产量属性的信息增益值，并将具有较大增益的属性作为测试属性，在测试属性分段的子节点处，引出分支，划分整个记录集，再依次进行即可形成一个精简的决策树，其中属性S_k的信息增益公式为：

$G\left(S_K\right)=h_s\left(s_j\right)-\underset{k=1}{\overset{K}{\Sigma }}(\frac{n_k}{n_j}\times (-\underset{i=1}{\overset{c}{\Sigma }}\frac{n_{\mathrm{ik}}}{n_k}\times {\log }_2\left(\frac{n_{\mathrm{ik}}}{n_k}\right)))$

其中n_j是总节点的出现次数，n_k是预测属性值为V_k的子节点的出现次数，n_ik是分类属性为C_i的预测属性值为V_k的子节点的出现次数；

(3)根据形成的决策树，系统判断所输入的属性值属于哪个分类，并通过计算这个三维点和所属分类中其他点的距离，得到一个距离最小的点，这个点所具有的属性就是最接近于输入玉米品种的玉米属性，从子女表中查询出这个玉米品种的父类和母类，即完成玉米选育的功能。

本发明结合聚类和决策树算法，可根据要求对玉米的生育信息、生长信息和收获信息等进行玉米良种的优选，可达到降低劳动强度，提高决策效率的目的。

基于聚类-决策树的玉米良种选育方法是根据所输入的玉米属性要求，利用数据挖掘中聚类和决策树的算法，找出与该属性最相似相近的玉米品种，然后再从子女表中找出这该玉米品种的父类和母类，并将父类和母类的基本信息进行输出，从而获得输入的玉米属性要求的父类和母类的良种。

本玉米良种选育方法是基于计算机软件辅助实现，极大的减少了人工良种选育中劳动强度，提高了玉米良种选育的决策效率和准确性。

下面结合附图和实施例对本发明作进一步说明。

图1是实施例的最终决策图。

图2是聚类算法描述图。

图3是决策树算法描述图。

具体实施方式：

①选择样本集；

原有样本集来自于某农业信息组2006年所选品种实验年终汇总(Y组)数据表。由于原有样本集数据信息量大，玉米品种较多，为方便说明描述，现只选Y1-Y8这八条记录进行讨论，所列举的选取样本集如下表1所示。表1选择样本集

  次   数   平均值   (簇1)   平均值   (簇2)   产生的新   簇   新平均   值   (簇1)   新平均   值   (簇2)   1   (100，   200.8，   6.73)   (101，   269.8，   7.83)  {Y1，Y7}，{  Y2，Y3，Y4，  Y5，Y6，Y8}   (100，   213.9，   6.555)   (100.33，   275.23，   7.67)   2   (100，   213.9，   6.555)   (100.33，   275.23，   7.67)  {Y1，Y6，Y7  }，{Y2，Y3，Y  4，Y5，Y8}   (100，   212.87，   6.75)   (100.4，   288.12，7   .782)   3   (100，   213.9，   6.555)   (100.33，   275.23，   7.67)  {Y1，Y6，Y7  }，{Y2，Y3，Y  4，Y5，Y8}   (100，   212.87，   6.75)   (100.4，   288.12，7   .782)

表2  聚类全过程

  玉米   品种代   码   Period   (周期)   Weight   (重   量)   Yield   (产   量)   Y1   100   200.8   6.73   Y2   101   269.8   7.83   Y3   99   287.3   6.70   Y4   101   303.5   7.54   Y5   100   255.5   7.56

  玉米   品种代   码   Period   (周期)   Weight   (重   量)   Yield   (产   量)   Y6   100   210.8   7.13   Y7   100   227.0   6.38   Y8   101   324.5   9.28

②对样本集进行聚类，作为决策树算法的预处理步骤。表2给出了整个过程中平均值计算和簇生成的过程和结果；

第一次迭代：假定随机选择的两个对象，如Y1和Y2当作初始点，分别找到离两点最近的对象，并产生两个簇{Y1，Y7}和{Y2，Y3，Y4，Y5，Y6，Y8}。对于产生的簇分别计算平均值，得到平均值点。对于{Y1，Y7}，平均值点为(100，213.9，6.555)；对于{Y2，Y3，Y4，Y5，Y6，Y8}，平均值点为(100.33，275.23，7.67)。

第二次迭代：通过平均值调整对象所在簇，重新聚类，即将所有点按平均值点(100，213.9，6.555)，(100.33，275.23，7.67)最近的原则重新分配。得到两个新的簇：{Y1，Y6，Y7}和{Y2，Y3，Y4，Y5，Y8}。重新计算簇平均值点，得到新的平均值点为(100，212.87，6.75)和(100.4，288.12，7.782)。

第三次迭代：将所有点按离平均值点(100，212.87，6.75)和(100.4，288.12，7.782)最近的原则重新分配，调整对象，簇仍然为{Y1，Y6，Y7}和{Y1，Y6，Y7}，发现没有出现重新分配，而且准则函数收敛，程序结束。

经过三次迭代，可得到最终的两个聚类C1、C2类。其中，C1包括Y1，Y6，Y7，C2包括Y2，Y3，Y4，Y5，Y8。

③输入选择条件，判断所属类别；

随机输入一组选择条件，假设Period＝101，Weight＝290，Yield＝7.2，则可对应为空间中的一个三维点P(101，290，7.2)，根据欧氏距离公式计算P点到两个簇中心的距离，得到d1＝77.14，d2＝2.06(d1为P到类C1重心的距离，d2为P到类C2重心的距离)，由于d1＞d2，可判断将点P归入类C2中。

④对选择的聚类实施ID3算法，选出良种；首先确定分类属性为Weight(Weight＜＝300的样本为低产，Weight＞300的样本为高产)，然后对属性Period和Yield进行分段(Period＜＝100，Period＞100；Yield＜＝7.6，Yield＞7.6)。如表3所示。表3样本的属性值表

  Y2   ＞100   ＞7.6   低产   Y3   ＜100   ＜7.6   低产   Y4   ＞100   ＜7.6   高产   Y5   ＜100   ＜7.6   低产   Y8   ＞100   ＞7.6   高产

计算分类属性Weight的期望信息为：$I\left(\mathrm{Weight}\right)=-\frac{3}{5}{\log }_2\left(\frac{3}{5}\right)-\frac{2}{5}{\log }_2\left(\frac{2}{5}\right)=0.97;$

再计算属性Period的熵： $E\left(\mathrm{Period}\right)=0-\frac{3}{5}(\frac{1}{3}{\log }_2\left(\frac{1}{3}\right)+\frac{2}{3}{\log }_2\left(\frac{2}{3}\right))=0.55;$

属性Yield的熵：

$E\left(\mathrm{Yield}\right)=-\frac{3}{5}(\frac{1}{3}{\log }_2\left(\frac{1}{3}\right)+\frac{2}{3}{\log }_2\left(\frac{2}{3}\right))-\frac{2}{5}(\frac{1}{2}{\log }_2\left(\frac{1}{2}\right)+\frac{1}{2}{\log }_2\left(\frac{1}{2}\right))=0.95;$

则属性Period的信息增益为：Gain(Period)＝I(Weight)-E(Period)＝0.42；

属性Yield的信息增益为：Gain(Yield)＝I(Weight)-E(Yield)＝0.02；

由于属性Period具有较大的信息增益，则将Period作为测试属性，创建决策树，得到图1。

根据之前随机输入的选择条件，可确定此品种属于Y2低产类，只需查询数据库中Y2的父类和母类，即可得到良种期望的双亲基本信息。

2算法描述

基于聚类-决策树的玉米良种选育方法概括如下：首先对所有样本进行聚类，得到所需簇类，然后根据需要判断的对象的属性，将其归入到对应的簇类中。最后针对找到的小范围簇类实施决策树算法，创建最佳的决策树，从而找到较优化的解。其中聚类和决策树算法的描述如图2和3所示。

根据基于聚类-决策树的玉米良种选育方法，运用VC++编程与ACCESS数据库技术，开发设计了基于聚类-决策树的玉米良种选育的软件系统，系统的ACCESS数据库中包含了基础数据库、知识库和推理库。其中，基础数据库包括用户信息表和玉米信息表，知识库包括了双亲表和子女表，推理库是根据玉米育种专家多年来的育种经验总结出的规则来建立的。

玉米信息管理模块包括两个部分，一是信息查询操作，一是玉米基本信息的添加、删除、修改操作。

玉米良种选育模块实现的功能是根据所输入的玉米属性，利用数据挖掘中聚类和决策树的算法，找出和这些属性最相似的玉米品种，然后再从子女表中找出这个玉米品种的父类和母类，并将它们的基本信息输出到列表框中。

所述的“玉米信息表(corn)”，用于记录玉米的基本信息，包括全生育期、株高、穗高、千粒重、小区产量、比对照等属性。

表4   玉米信息表(corn)

  字段名称   数据类型   可否为空   约束条件   说明   Corn_id   自动编号   否   主键   编号   Corn_name   文本   否   \   品种代码   Corn_period   文本   否   \   全生育期   Corn_high   文本   否   \   株高   Corn_shigh   文本   否   \   穗高   Corn_length   文本   否   \   穗长   Corn_wide   文本   否   \   穗粗   Corn_weight   文本   否   \   千粒重   Corn_yield   文本   否   \   小区产量   Corn_percent   文本   否   \   比对照

所述的“知识库-双亲表(father)”，可显示双亲标志和子女信息等，如表5所示。

表5  双亲表(father)

  字段名称   数据类型   可否为空   约束条件   说明   Pid   自动编号   否   主键   编号   Pname   文本   否   \   品种代码   Pyield   文本   否   \   小区产量   Pweight   文本   否   \   千粒重   Gperiod   文本   否   \   全生育期   Plogo   文本   否   \   双亲标志   Pnum   文本   否   \   子女数目

  字段名称   数据类型   可否为空   约束条件   说明   Pfirst   文本   否   \   起始子女代码

“知识库-子女表(son)”，可显示相应父类玉米品种代码，如表6所示。

表6  子女表(son)

  字段名称   数据类型   可否为空   约束条件   说明   Sid   自动编号   否   主键   编号   Sname   文本   否   \   品种代码   Syield   文本   否   \   小区产量   Sweight   文本   否   \   千粒重   Speriod   文本   否   \   全生育期   Fathername   文本   否   \   父类品种代码   Mothername   文本   否   \   母类品种代码

所述的“推理库”，是根据玉米育种专家多年来的育种经验总结出两个规则：◇子代的比对照＞＝0；◇子代的生育期＜父代的生育期。从双亲表中选出良种玉米的双亲。

所述的“玉米良种选育模块”，是根据所输入的玉米属性要求，利用数据挖掘中聚类和决策树的算法，找出与该属性最相似相近的玉米品种，然后再从子女表中找出这该玉米品种的父类和母类，并将父类和母类的基本信息进行输出，从而获得输入的玉米属性要求的父类和母类的良种。本玉米良种选育方法是基于计算机软件辅助实现，极大的减少了人工良种选育中劳动强度，提高了玉米良种选育的决策效率和准确性。