互联网+环境下基于数据挖掘的个性化PDM系统的应用研究

浦慧忠

（无锡城市职业技术学院，江苏 无锡 214153）

互联网+环境下基于数据挖掘的个性化PDM系统的应用研究

浦慧忠

（无锡城市职业技术学院，江苏 无锡 214153）

从互联网+时代对企业产品数据管理需求不断升级的现状出发，针对数据挖掘中经典的关联规则算法-Apriori算法中存在的不足并考虑到不同企业PDM系统中存在的企业文化、操作习惯不同等个性化需求问题，参考相关文献改进算法，并通过模拟系统来实验验证，该PDM系统的稳定性及效率较之前有很大的提升。

产品数据管理；数据挖掘；关联规则；Apriori算法

0 引言

目前 Internet技术已经被广泛地用于制造业企业中的各个领域，使得人们在任何时候都可以用一致的、简单的方式查询各种信息，从而提高员工的工作效率。而以“互联网+”为代表的新经济形态通过互联网信息技术和传统产业的联合，优化生产要素、更新业务体系、重构商业模式等途径来实现经济转型升级发展。对制造业来讲，网络化制造为PDM带来了机遇和挑战。另外每个企业都有区别于其它企业的PDM系统，建立有生命的PDM系统，将 PDM 融于企业文化中，通过神经网络等不断学习、改进、创新、完善，能够快速获取和利用互联网上丰富的专业资源和交流平台。相同的核心模块、相同的网络层接口和不同的用户风格界面模块、不同企业各部门操作模块安装来实现整个基于网络化的PDM系统，使其具有模块化、个性化。

PDM 系统中往往存在着与产品相关的海量数据，而这些数据中隐藏了大量有用的知识，要把他们发现和挖掘出来就必须通过数据挖掘功能，将这些知识转换成有用的信息，如人工神经网络，决策树，遗传算法等等[1]。面向制造企业的PDM系统应用数据挖掘相关技术从而实现个性化知识管理和创新已成为企业信息化建设中一个非常活跃的研究方向。

1 国内外研究现状

关联规则是形如X→Y的蕴涵式，最初是针对购物篮分析(Market Basket Analysis)问题提出的[2]。通过关联规则挖掘能够发现顾客购物车中的各种不同商品之间的联系，猜测顾客的消费习惯。沃尔玛在各门店的详细原始交易数据的基础上，对这些数据进行分析和挖掘，诞生了经典的“尿布与啤酒”的故事。一开始由关联规则概念给出相应的挖掘算法 AIS，但是性能较差，后建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori算法，作为关联规则挖掘的经典算法被广泛使用，研究人员对关联规则的挖掘问题进行了大量的研究。

Product Data Management是以产品为核心，以软件技术为依托，实现对产品相关数据(如 CAD/CAPP/CAM/CAE的文件、材料清单(BOM)、产品配置等)、过程(包括有关的加工工序、有关批准权、使用权、工作流程过程程序)、资源一体化集成管理技术[3]。PDM进行信息管理主要依托静态的产品结构和动态的产品开发流程。当今的制造业企业相互间的竞争愈演愈烈，最显著的就是产品的生命周期越来越短、产品个性化的需求越来越多、整个供应链中产品信息的重复利用需求也越来越强。综上，使PDM具有自我学习、改进和完善是可能的，开展在PDM系统中的关联挖掘也是切实可行的。

2 存在的问题

Apriori算法是一个经典的数据挖掘算法，经典的关联规则数据挖掘算法 Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值[4]。

2.1 Apriori算法的原理

Apriori是挖掘布尔关联规则频繁项集的算法，它的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。再使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来[5]。为了生成所有频集，使用了递归的方法。

Apriori算法要求：频繁项集的所有非空子集也必须是频繁的，意味着模式不可能比A更频繁的出现。它是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。简单的说，它通过减少搜索空间，来提高频繁项集逐层产生的效率。

2.2 Apiori算法的实现

Apriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将 k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集[6]。具体说就是：先找到频繁 1-项集集合L1，然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。

Apriori算法由连接和剪枝两个步骤组成。为了减少计算量，可以使用它的特性，即如果一个k-项集的(k-1)-子集不在 Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。

图1 Apiori算法示例Fig.1 Example of apiori algorithm

1、连接

C3=L2

L2= {{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}} ={{A,B,C},{A,C,E},{B,C,E}}

2、使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项。

{A,B,C}的 2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以删除这个选项；{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E} 不是L2的元素，所以删除这个选项；{B,C,E}的 2项子集是{B,C},{B,E},{C,E}，它的所有 2－项子集都是L2的元素，因此保留这个选项。

3、这样，剪枝后得到C3={{B,C,E}}

2.3 Apiori算法的缺点

Apriori算法简单易于实现，应用非常广泛。但有难以克服的缺点：（1）在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素；（2）每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的 I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加[7]。

Apriori算法的最大缺点在于：它在运算的过程中会产生大量的侯选集，而且在匹配的时候要进行整个数据库的扫描，因为要做支持度计数的统计操作，在小规模的数据上操作还不会有大问题，如果是大型的数据库上呢，他的效率还是有待提高的[8]。

3 改进的方法

目前关于 Apriori算法的优化方法有很多种主要集中的是1基于划分的方法；2基于hash表的项集计数的方法；3基于采样的方法（在给定数据的一个子集挖掘）；4事务压缩（压缩进一步迭代的事务数）；5动态项集计数[9-12]。借鉴一些资料，采用相对简洁适合系统特点的算法是关键。

3.1 基本思路

在 Apriori算法中，寻找最大项目集的基本思路是：

第一步:简单统计所有含一个元素的项目出现的频率，并找出那些大于或等于最小支持度的项目集，产生一维频繁项目集Lt。

第二步:循环处理直到未能再产生维数更高的频繁项目集。循环过程是:在第k步中，根据k-1步生成的k-1维频繁项目集来产生k维候选项目集，由于在产生 k-1维频繁项目集时，我们可以实现对该集中出现元素的个数进行计数处理，因此对某元素而言，若它的计数个数不到k-1的话，可以事先删除该元素，从而排除由该元素将引起的大规格所有组合。

第三步：按Apriori算法再检验新的K 维频繁项目集的所有 k-1维项目集是否已经包含在已经求出的K-1维频繁项目集。若其中有一个没有包含，则也可删去该组合，这样得到一个真正有用的K维频繁项目集选项目集。

第四步：得到了这个候选项目集后，可以对数据库D的每一个事务tid进行扫描，若该事务中至少含有候选项目集CK中的一员，则保留该项事务，否则把该事物记录与数据库末端没有作删除标记的事务记录对换，并对移到数据库末端的事务记录作删除标一记，整个数据库扫描完毕后为新的事务数据库 D’ 中。

3.2 算法示例

我们可以看到改进后的算法思路基本上与Apriori算法保持一致，但是又有不同之处。

图2 第二步Fig.2 S econd steps

图3 第三、四步Fig.3 Third, fourth steps

第一，改进的算法在考虑组合 Ck前，对将参与组合的元素进行计数处理，根据计数结果决定排除一些不符合组合条件的元素，这就降低了组合的可能性，即降低循环判断的次数。

第二，改进的算法对数据库进行了扫描后的重新生成，虽然会在记录重写中浪费时间和 I/O的开销，但是随着循环次数的增加，本算法对以后在‘新生成的数据库’中的扫描比较次数很快减少将逐渐体现出来。

4 实验结果验证及分析

4.1 算法实例对比

问题：假设 Lk-1={{1,2,3},{1,2,4},{2,3,4},{2,3,5},{1,3,4}}，求Lk。

由Lk-1得到Ck={{1,2,3,4},{2,3,4,5},{1,2,3,5}}。

原算法：首先得到{1,2,3,4}的子集{1,2,3}，{1,2,4}，{2,3,4}，{1,3,4}。然后判断这些子集是不是 Lk-1的元素。如果都是则保留，否则删除。这里保留，{2,3,4,5}和{1,2,3,5}则删除。得到 C’k={{1,2,3,4}}。

改进算法：首先从Lk-1中取元素{1,2,3}，扫描Ck中的元素，看{1,2,3}是不是Ck元中元素的子集，{1,2,3}是{1,2,3,4}的子集，{1,2,3,4}的计数加 1，{1,2,3}不是{2,3,4,5}的子集，计数不变，是{1,2,3,5}的子集，计数加 1，经过对{1,2,3}处理后得到计数{1，0，1}；然后看{1,2,4}，{1,2,4}是{1,2,3,4}的子集，而不是 {2,3,4,5}的子集，也不是{1,2,3,5}的子集，计数不变，计数变为{2,0，1}；考察{2,3,4}，{2,3,4}是{1,2,3,4}的子集，也是{2,3,4,5}的子集，不是{1,2,3,5}的子集，计数变为{3,1,1}；{2,3,5}不是{1,2,3,4}的子集，是{2,3,4,5}的子集，也是{1,2,3,5}的子集，计数变为{3,2,2}；{1,3,4}是{1,2,3,4}的子集，不是{2,3,4,5}的子集，也不是{1,2,3,5}的子集，计数变为{4,2,2}。对数据扫描完毕。此时 K=4，只有第一个元素的计数为 4，为高频数据项集。得到C’k={{1,2,3,4}}。

复杂度对比

下面对原算法和改进算法的性能进行比较。Lk-1中的数据项集的个数记为|Lk-1|，Ck中的数据项集的个数记为|Ck|，Ck中元素的子集个数设为ni，其中i=1～|Ck|。这里只分析从Ck～C’k的处理。原算法从 AprioriCk中取元素，然后求该元素的子集，判断该子集是否在|Ck|中。需要进行的计算为1<=|L’k-1|<=|L’k-1|,1< = n’i <=n i。而改进算法是从Lk-1中选取元素，看是不是Ck中元素的子集，对 Ck中数据项集的子集个数进行统计。需要进行的计算是(|Lk-1|+1)*|Ck| 次。如果 n’i =1，就是每次只取 Ck中数据项集的一个子集就可以判断该数据项集，则两个算法的效率基本相同，但是这种情况很少出现，从而大部分情况下，改进算法的效率要高于原算法。

4.2 系统实现

PDM 系统采用JSP加MSSQL2000数据库的方式，应用平台为B/S结构，采用模块化方式。核心部分数据挖掘模块分为三层：数据存储层、业务逻辑层、界面层，以Web页面的方式嵌入到系统框架中，如图 4。其中挖掘算法管理模块封装实现各种数据挖掘算法，如关联规则算法可以实现对样本数据源的关联分析，并改进经典的 Apriori 算法，适应制造业的多维数据，如图5。

图4 PDM 中数据挖掘分析系统登录界面Fig.4 Data mining analysis system login interface in PDM

图5 PDM 中数据挖掘分析系统模块化管理界面Fig.5 Modular management interface of data mining analysis system in PDM

交互模块允许用户自定义关联项数、支持度和置信度，并依据产生的规则和用户的需求对结果进行过滤，以自然语言的方式来表示规则，提取规则，保存规则。

4.3 挖掘结果分析

应用本系统对制造类企业 PDM 数据库的进行分析，以某种铣床夹具零件的数据为例，图6是某企业PDM数据库中零件表与其它各表之间的关系。系统对其中一张表或是某个属性进行关联分析，产生的挖掘结果对其它相关零件的生产和加工工具的使用有指导作用。

图6 PDM 数据库中零件表与其它各个表之间的关系Fig.6 BOM relations between tables and other PDM database

5 结语

随着互联网+在各行各业的深入推广和大数据涌现，PDM系统在企业信息化中大有作为，应用数据挖掘中的关联规则分析在制造类企业 PDM 系统中开展相关研究有很大的前景。本文依据数据挖掘中的经典算法 Apriori并进行适当改进，结合企业PDM系统的相关个性应用需求，试图探索寻找一种效率更高、稳定性更强的关联规则挖掘分析方法，并在模拟系统中进行实践，取得了一定的效果，为今后的后续研究积累了经验。

[1] 约瑟夫·萧塔纳著,祁国宁译. 制造企业的产品数据管理[M]. 机械工业出版社,2000（12）.Joseph, Xiao Yan, Qi Guoning. Product data management of manufacturing enterprises [M]. Mechanical Industry Press,2000 (12).

[2] J Han J, Kamber M. 范明, 孟小峰, 等译. 数据挖掘概念与技术(第一版)[M]. 北京: 机械工业出版社, 2006:185-217.J Han J, Kamber M., Ming Fan, Meng Xiaofeng, et al. Data mining: concepts and techniques (First Edition) [M]. Beijing:Mechanical Industry Press, 2006:185-217.

[3] 童秉枢, 李建明. 产品数据管理(PDM)技术[M]. 清华大学出版社, 2000(11): 3-4.Tong Bingshu, Li Jianming. Product data management (PDM)technology, [M], Tsinghua University press, 2000(11): 3-4.

[4] XU Rui, Donald Wunsch 1 1. survey of clustering algorithm[J]. IEEE. Transactions on Neural Networks, 2005,16(3): 645-67 8.

[5] YI Hong, SAM K．Learning assignment order of instances for the constrained k-means clustering algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B：Cybernetics,2009, 39(2): 568-574.

[6] 王锐, 李晶, 熊海蕴, 绳鹏. 基于关联规则的Apriori算法的可视化实现方法[J]. 计算机工程与设计, 2007, 28(4):757-759.Wang Rui, Li Jing, Xiong Hai Yun, Peng Peng. Visualization method of Apriori algorithm based on association rules [J],computer engineering and design, 2007, 28(4): 757-759.

[7] 黄进, 尹治本. 关联规则挖掘的Apriori算法的改进[J]. 电子科技大学学报, 2003, 32(1): 76-79.Huang Jin, Yin Yin. Improvement of association rules mining Apriori algorithm[J] Journal of University of Electronic Science and technology of China, 2003, 32(1): 76-79.

[8] 陆丽娜, 陈亚萍. 挖掘关联规则中Apriori算法的研究[J].小型微型计算机系统, 2000, 21(9): 940-943.Lu Lina, Chen Yaping. Research on mining Apriori algorithm in association rules[J]. small and micro computer systems, 2000, 21(9): 940-943.

[9] 蔡伟杰, 张晓辉, 朱建秋, 朱扬勇. 关联规则挖掘综述[J].计算机工程, 2001, 27(5): 31-33.Cai Weijie, Zhang Xiaohui, Zhu Jianqiu, Zhu Yangyong.Summarization of association rules mining[J]. computer engineering, 2001, 27(5): 31-33.

[10] 李绪成, 王保保. 挖掘关联规则中Apriori算法的一种改进[J]. 计算机工程, 2002, 28(7): 104-105.Li Xucheng, Wang Baobao. An improved Apriori algorithm for association rules[J]. computer engineering, 2002, 28(7):104-105.

[11] 杨泽民. 数据挖掘中关联规则算法的研究[J]. 软件, 2013,34(11): 71-72.Yang Zemin. Research on association rules algorithm in data mining[J]. software, 2013, 34(11): 71-72.

[12] 孙文静, 傅涛. 基于改进Apriori 算法的入侵检测数据挖掘模型研究[J]. 软件, 2014, 35(8): 1-6.Sun Wenjing, Fu Tao. Research on data mining model of Intrusion Detection Based on improved Apriori algorithm [J].software, 2014, 35(8): 1-6.

Research and Application of Personalized PDM System Based on Data Mining Under Internet Plus Environment

PU Hui-zhong
(Wuxi city college of vocational teachnology Jiangsu Wuxi 214153)

From the current situation of the Internet era of product data management needs of enterprises continuously upgrade, aiming at the problems of -Apriori algorithm for mining association rules in the classical and taking into account the existence of different enterprises in the PDM system of enterprise culture, different operating habits such as personalized requirements, refer to the relevant literature to improve the algorithm, and through simulation experiment system validation, stability and efficiency of the PDM system is much better than before.

PDM; Data mining; Association rules; Apriori

TP392

A

10.3969/j.issn.1003-6970.2017.11.038

本文著录格式：浦慧忠. 互联网+环境下基于数据挖掘的个性化PDM系统的应用研究[J]. 软件，2017，38（11）：202-207

浦慧忠(1980-)，男，硕士，讲师，江苏无锡人，主要研究方向：数据挖掘。