论文部分内容阅读
[摘要] 本文将数据挖掘技术中的关联规则算法运用于笔记本电脑BTO生产计划中，并基于BTO制造的特点，采用了分类、多最小支持度和增量挖掘的改进算法，挖掘PC配置选择的关联关系，为制造部门制定准确的生产计划提供科学的支持。
[关键词] 关联规则 多最小支持度 按订单制造 生产计划 笔记本电脑
一、应用背景
近年来笔记本电脑市场发展迅速，预计2007年全球产量将突破9000万台。为了在满足市场多样化需求的同时又能降低生产成本、提高响应速度，许多企业都在实施一种以销订产、按订单生产（Build to Order, BTO）的模式。BTO模式的成功运行强烈地依赖于原材料供应商、制造企业和销售公司之间的协作关系。然而笔记本电脑制造企业所面对的原材料供应商大多为垄断企业，它们为了自身利益要求按照企业给出的采购预测供货，这样制造企业如何制定一个尽可能准确反映用户个性化需求的生产计划变得尤为重要。但是通常这样的生产计划在现实中仅仅是少数人员根据经验制定，缺乏科学性和准确性。随着数据挖掘技术的不断成熟，在商业领域有着巨大的发展潜力。本文运用其中的关联规则经典算法并结合BTO制造的特点加以改进，挖掘出历史数据库中笔记本电脑配置关联关系，为生产计划提供科学的支持。
二、关联规则基本概念和描述
关联规则挖掘是目前数据挖掘领域最活跃的分支之一。一条关联规则是形如 XY 的蕴涵式，其中XY的支持度是事务集中包含X和Y的事务数与所有事务数之比，即Support(XY) =P(XY)；它的置信度则是事务集中包含X和Y的事务数与包含X的事务数之比，即Confidence((XY))= P(XY)/P(X);若支持度和置信度分别大于用户定义的最小支持度和最小置信度，则XY为强关联规则。实现关联规则挖掘的算法很多，以下以Apriori算法来描述：
三、关联规则应用改进
BTO制造的特殊性和难点在于无法预测到用户的具体需求，业界普遍采用的一种方案是为各机型建立一份备选组件清单，生产计划将转化为对各个组件需求数量的预测。通常，一台笔记本电脑包含了外框体以及若干自选组件，如CPU，RAM，HDD等。与传统的货篮分析相比，BTO笔记本电脑配置信息挖掘又有它不同的特点：
1.耦合性
BTO笔记本电脑的订单从内容上看更像是一份电脑组件选购清单，对于大多数组件，不可以重复选择其同类的其他组件。因此，对关联规则算法做如下改进：由频繁K-项集生成侯选K+1项集时，直接忽略同类组件间的关联。对组件进行分类，将所有项目集合I分解为n类: 且有其中表示第n类下的第m种组件。在Apriori_Cgen(Lk)过程中增加限制条件，改进为：
,且有
2.多样差异性
电脑组件的可替换性、供应商情况和库存成本等因素决定了它们的重要程度各不相同。然而传统关联规则算法仅使用单一的最小支持度，对不同组件重要程度没有区分。因此，采用多支持度关联规则挖掘方法对Apriori算法进行改进。定义各部品的最小支持度为min_sup(in)，将候选k-项集中的某一候选项的最小支持度定义为：min_sup(c)= MIN(min_sup(i1), min_sup(i2) ,..., min_sup(ik)，其中c={i1, i2, …, ik})。Apriori算法的实现基于以下前提：频繁项的任意子集必是频繁项。但是多支持度关联规则挖掘算法无法满足这一前提。为此，特别规定在1-项频繁项的挖掘过程中对所有的候选项采用所有项支持度的最小值，此后多项频繁项挖掘再采用多支持度的方法，保证算法能够继续适用。
3.动态性
企业信息系统每天都在不停地接收来自全球各地的订单，因此采用一种动态更新的关联规则挖掘算法，当数据更新时充分利用原有数据关联规则信息，仅对新增数据进行挖掘，得到新的关联规则结果。本应用将在数据库中记录所有候选项的支持度，无论其最终是否成为频繁项，这样不必重复先前的工作。假设DB为原有的订单记录，db为新增记录。若c在DBdb上频繁，则c至少在DB和db中的一个上频繁。基于以上性质，在db增量数据挖掘时采取以下策略：若c在DBdb上同为频繁项或非频繁项，那么直接定义c在DB和db上频繁或非频繁；若c仅在DB和db中的一个上频繁，则重新计算其支持度进行判定。为此对Apriori_Lgen(Ck)作了补充,比较原有关联规则信息:(1)对增量挖掘中新出现或者丢失的频繁项重新计算其支持度判定频繁属性;(2)对在DB和db中都频繁的项继续判定为频繁项。
四、应用实例
我们选取了某笔记本制造企业的一种机型为研究对象，将其组件分为16大类120多项，以下将对其中5类部件关联规则加以跟踪和描述:(1)根据用户提供的包括库存成本，供应商情况等信息对各类电脑组件设定不同的最小支持度（百分比形式），具体为CPU：2%、RAM：10%、LCD：10%、ODD：15%、HDD：8%。 (2)将所有的组件作为候选1-项频繁集，扫描数据库，得到各项支持度如表1所示。根据3.2的改进，此处最小支持度阈值统一采用2%，因此YCPUT135等3项（删除线）被定为非频繁项，而YRAM1520D等8项（带*项）虽然支持度小于本类组件设定的最小支持度，但仍然入选1-项频繁项集。(3)由性质4.1，直接忽略同类组件之间的关联，比如排除{YCPUT225,YCPUT23D}成为2-项候选项，可以减少158次计算。生成2-项频繁项时，采用新的最小支持度计算方法。以{YCPUT23E，YHDDS087}为例该项的最小支持度为2%，计算得到支持度为3.87%，因此入选频繁项集。(4)用同样的方法，得到k-项频繁项集，结果如表2所示:注意频繁2-项集中的{YCPUT23D,YHDDS065}，正是由于在1-项频繁项挖掘过程中采用了2%作为支持度阈值使YHDDS065能够入选，否则该2-项频繁项将被丢失。(5)前几步针对该机种某月前2周的3450个订单数据生成了关联规则，在第3周又发生了1473笔新的订单，因此需要更新关联规则信息。在新增数据中发现了新的9组频繁项，如：{YCPUT76D，YRAM162GD}，而原关联规则信息中的16组频繁项在新增数据中为非频繁项，如：{YCPUT23D，YHDDS065}，因此基于上一次挖掘结果重新计算支持度。以上述两项为例，原记录中SUPDB({YCPUT76D，YRAM162GD})=1.72%新增记录中的支持度为SUPDB({YCPUT76D，YRAM162GD})=4.72%，计算得到新的支持度为SUPDBdb({YCPUT76D, YRAM162GD})=,所以该项成为频繁项，而SUPDBdb({YCPUT23D，YHDDS065})=1.86%,因此从频繁项集中排除。
通过对订单数据关联规则的挖掘，使用户在制定生产计划时能够充分考虑到这些组件之间的相关性，从一定程度上改变了以往对单个组件孤立地进行预估的状况，使得对各组件产量的计划能够有比较科学的比例关系，更能准确地反映出用户偏好的变化规律，计划更加准确。
参考文献:
[1]2006～2007年中国笔记本电脑产业研究报告[R/OL]. http://www.ccidnet.com/
[2]宫雨:分组多支持度关联规则研究[J].计算机工程与设计,2007,(05):1205～1207
[3]Cheung D W:Maintenance of discovered association rules in large databases: An incremental updating technique [C]. Proceedings of the 12th International Conference on Data Engineering,1996:106～114
注：本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。
[关键词] 关联规则 多最小支持度 按订单制造 生产计划 笔记本电脑
一、应用背景
近年来笔记本电脑市场发展迅速，预计2007年全球产量将突破9000万台。为了在满足市场多样化需求的同时又能降低生产成本、提高响应速度，许多企业都在实施一种以销订产、按订单生产（Build to Order, BTO）的模式。BTO模式的成功运行强烈地依赖于原材料供应商、制造企业和销售公司之间的协作关系。然而笔记本电脑制造企业所面对的原材料供应商大多为垄断企业，它们为了自身利益要求按照企业给出的采购预测供货，这样制造企业如何制定一个尽可能准确反映用户个性化需求的生产计划变得尤为重要。但是通常这样的生产计划在现实中仅仅是少数人员根据经验制定，缺乏科学性和准确性。随着数据挖掘技术的不断成熟，在商业领域有着巨大的发展潜力。本文运用其中的关联规则经典算法并结合BTO制造的特点加以改进，挖掘出历史数据库中笔记本电脑配置关联关系，为生产计划提供科学的支持。
二、关联规则基本概念和描述
关联规则挖掘是目前数据挖掘领域最活跃的分支之一。一条关联规则是形如 XY 的蕴涵式，其中XY的支持度是事务集中包含X和Y的事务数与所有事务数之比，即Support(XY) =P(XY)；它的置信度则是事务集中包含X和Y的事务数与包含X的事务数之比，即Confidence((XY))= P(XY)/P(X);若支持度和置信度分别大于用户定义的最小支持度和最小置信度，则XY为强关联规则。实现关联规则挖掘的算法很多，以下以Apriori算法来描述：
三、关联规则应用改进
BTO制造的特殊性和难点在于无法预测到用户的具体需求，业界普遍采用的一种方案是为各机型建立一份备选组件清单，生产计划将转化为对各个组件需求数量的预测。通常，一台笔记本电脑包含了外框体以及若干自选组件，如CPU，RAM，HDD等。与传统的货篮分析相比，BTO笔记本电脑配置信息挖掘又有它不同的特点：
1.耦合性
BTO笔记本电脑的订单从内容上看更像是一份电脑组件选购清单，对于大多数组件，不可以重复选择其同类的其他组件。因此，对关联规则算法做如下改进：由频繁K-项集生成侯选K+1项集时，直接忽略同类组件间的关联。对组件进行分类，将所有项目集合I分解为n类: 且有其中表示第n类下的第m种组件。在Apriori_Cgen(Lk)过程中增加限制条件，改进为：
,且有
2.多样差异性
电脑组件的可替换性、供应商情况和库存成本等因素决定了它们的重要程度各不相同。然而传统关联规则算法仅使用单一的最小支持度，对不同组件重要程度没有区分。因此，采用多支持度关联规则挖掘方法对Apriori算法进行改进。定义各部品的最小支持度为min_sup(in)，将候选k-项集中的某一候选项的最小支持度定义为：min_sup(c)= MIN(min_sup(i1), min_sup(i2) ,..., min_sup(ik)，其中c={i1, i2, …, ik})。Apriori算法的实现基于以下前提：频繁项的任意子集必是频繁项。但是多支持度关联规则挖掘算法无法满足这一前提。为此，特别规定在1-项频繁项的挖掘过程中对所有的候选项采用所有项支持度的最小值，此后多项频繁项挖掘再采用多支持度的方法，保证算法能够继续适用。
3.动态性
企业信息系统每天都在不停地接收来自全球各地的订单，因此采用一种动态更新的关联规则挖掘算法，当数据更新时充分利用原有数据关联规则信息，仅对新增数据进行挖掘，得到新的关联规则结果。本应用将在数据库中记录所有候选项的支持度，无论其最终是否成为频繁项，这样不必重复先前的工作。假设DB为原有的订单记录，db为新增记录。若c在DBdb上频繁，则c至少在DB和db中的一个上频繁。基于以上性质，在db增量数据挖掘时采取以下策略：若c在DBdb上同为频繁项或非频繁项，那么直接定义c在DB和db上频繁或非频繁；若c仅在DB和db中的一个上频繁，则重新计算其支持度进行判定。为此对Apriori_Lgen(Ck)作了补充,比较原有关联规则信息:(1)对增量挖掘中新出现或者丢失的频繁项重新计算其支持度判定频繁属性;(2)对在DB和db中都频繁的项继续判定为频繁项。
四、应用实例
我们选取了某笔记本制造企业的一种机型为研究对象，将其组件分为16大类120多项，以下将对其中5类部件关联规则加以跟踪和描述:(1)根据用户提供的包括库存成本，供应商情况等信息对各类电脑组件设定不同的最小支持度（百分比形式），具体为CPU：2%、RAM：10%、LCD：10%、ODD：15%、HDD：8%。 (2)将所有的组件作为候选1-项频繁集，扫描数据库，得到各项支持度如表1所示。根据3.2的改进，此处最小支持度阈值统一采用2%，因此YCPUT135等3项（删除线）被定为非频繁项，而YRAM1520D等8项（带*项）虽然支持度小于本类组件设定的最小支持度，但仍然入选1-项频繁项集。(3)由性质4.1，直接忽略同类组件之间的关联，比如排除{YCPUT225,YCPUT23D}成为2-项候选项，可以减少158次计算。生成2-项频繁项时，采用新的最小支持度计算方法。以{YCPUT23E，YHDDS087}为例该项的最小支持度为2%，计算得到支持度为3.87%，因此入选频繁项集。(4)用同样的方法，得到k-项频繁项集，结果如表2所示:注意频繁2-项集中的{YCPUT23D,YHDDS065}，正是由于在1-项频繁项挖掘过程中采用了2%作为支持度阈值使YHDDS065能够入选，否则该2-项频繁项将被丢失。(5)前几步针对该机种某月前2周的3450个订单数据生成了关联规则，在第3周又发生了1473笔新的订单，因此需要更新关联规则信息。在新增数据中发现了新的9组频繁项，如：{YCPUT76D，YRAM162GD}，而原关联规则信息中的16组频繁项在新增数据中为非频繁项，如：{YCPUT23D，YHDDS065}，因此基于上一次挖掘结果重新计算支持度。以上述两项为例，原记录中SUPDB({YCPUT76D，YRAM162GD})=1.72%新增记录中的支持度为SUPDB({YCPUT76D，YRAM162GD})=4.72%，计算得到新的支持度为SUPDBdb({YCPUT76D, YRAM162GD})=,所以该项成为频繁项，而SUPDBdb({YCPUT23D，YHDDS065})=1.86%,因此从频繁项集中排除。
通过对订单数据关联规则的挖掘，使用户在制定生产计划时能够充分考虑到这些组件之间的相关性，从一定程度上改变了以往对单个组件孤立地进行预估的状况，使得对各组件产量的计划能够有比较科学的比例关系，更能准确地反映出用户偏好的变化规律，计划更加准确。
参考文献:
[1]2006～2007年中国笔记本电脑产业研究报告[R/OL]. http://www.ccidnet.com/
[2]宫雨:分组多支持度关联规则研究[J].计算机工程与设计,2007,(05):1205～1207
[3]Cheung D W:Maintenance of discovered association rules in large databases: An incremental updating technique [C]. Proceedings of the 12th International Conference on Data Engineering,1996:106～114
注：本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。