互聯網+環境下基于數據挖掘的個性化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-)，男，碩士，講師，江蘇無錫人，主要研究方向：數據挖掘。