浦慧忠
(無錫城市職業(yè)技術(shù)學(xué)院,江蘇 無錫 214153)
互聯(lián)網(wǎng)+環(huán)境下基于數(shù)據(jù)挖掘的個性化PDM系統(tǒng)的應(yīng)用研究
浦慧忠
(無錫城市職業(yè)技術(shù)學(xué)院,江蘇 無錫 214153)
從互聯(lián)網(wǎng)+時代對企業(yè)產(chǎn)品數(shù)據(jù)管理需求不斷升級的現(xiàn)狀出發(fā),針對數(shù)據(jù)挖掘中經(jīng)典的關(guān)聯(lián)規(guī)則算法-Apriori算法中存在的不足并考慮到不同企業(yè)PDM系統(tǒng)中存在的企業(yè)文化、操作習(xí)慣不同等個性化需求問題,參考相關(guān)文獻(xiàn)改進(jìn)算法,并通過模擬系統(tǒng)來實(shí)驗(yàn)驗(yàn)證,該P(yáng)DM系統(tǒng)的穩(wěn)定性及效率較之前有很大的提升。
產(chǎn)品數(shù)據(jù)管理;數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;Apriori算法
目前 Internet技術(shù)已經(jīng)被廣泛地用于制造業(yè)企業(yè)中的各個領(lǐng)域,使得人們在任何時候都可以用一致的、簡單的方式查詢各種信息,從而提高員工的工作效率。而以“互聯(lián)網(wǎng)+”為代表的新經(jīng)濟(jì)形態(tài)通過互聯(lián)網(wǎng)信息技術(shù)和傳統(tǒng)產(chǎn)業(yè)的聯(lián)合,優(yōu)化生產(chǎn)要素、更新業(yè)務(wù)體系、重構(gòu)商業(yè)模式等途徑來實(shí)現(xiàn)經(jīng)濟(jì)轉(zhuǎn)型升級發(fā)展。對制造業(yè)來講,網(wǎng)絡(luò)化制造為PDM帶來了機(jī)遇和挑戰(zhàn)。另外每個企業(yè)都有區(qū)別于其它企業(yè)的PDM系統(tǒng),建立有生命的PDM系統(tǒng),將 PDM 融于企業(yè)文化中,通過神經(jīng)網(wǎng)絡(luò)等不斷學(xué)習(xí)、改進(jìn)、創(chuàng)新、完善,能夠快速獲取和利用互聯(lián)網(wǎng)上豐富的專業(yè)資源和交流平臺。相同的核心模塊、相同的網(wǎng)絡(luò)層接口和不同的用戶風(fēng)格界面模塊、不同企業(yè)各部門操作模塊安裝來實(shí)現(xiàn)整個基于網(wǎng)絡(luò)化的PDM系統(tǒng),使其具有模塊化、個性化。
PDM 系統(tǒng)中往往存在著與產(chǎn)品相關(guān)的海量數(shù)據(jù),而這些數(shù)據(jù)中隱藏了大量有用的知識,要把他們發(fā)現(xiàn)和挖掘出來就必須通過數(shù)據(jù)挖掘功能,將這些知識轉(zhuǎn)換成有用的信息,如人工神經(jīng)網(wǎng)絡(luò),決策樹,遺傳算法等等[1]。面向制造企業(yè)的PDM系統(tǒng)應(yīng)用數(shù)據(jù)挖掘相關(guān)技術(shù)從而實(shí)現(xiàn)個性化知識管理和創(chuàng)新已成為企業(yè)信息化建設(shè)中一個非常活躍的研究方向。
關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)涵式,最初是針對購物籃分析(Market Basket Analysis)問題提出的[2]。通過關(guān)聯(lián)規(guī)則挖掘能夠發(fā)現(xiàn)顧客購物車中的各種不同商品之間的聯(lián)系,猜測顧客的消費(fèi)習(xí)慣。沃爾瑪在各門店的詳細(xì)原始交易數(shù)據(jù)的基礎(chǔ)上,對這些數(shù)據(jù)進(jìn)行分析和挖掘,誕生了經(jīng)典的“尿布與啤酒”的故事。一開始由關(guān)聯(lián)規(guī)則概念給出相應(yīng)的挖掘算法 AIS,但是性能較差,后建立了項目集格空間理論,并依據(jù)上述兩個定理,提出了著名的Apriori算法,作為關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法被廣泛使用,研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。
Product Data Management是以產(chǎn)品為核心,以軟件技術(shù)為依托,實(shí)現(xiàn)對產(chǎn)品相關(guān)數(shù)據(jù)(如 CAD/CAPP/CAM/CAE的文件、材料清單(BOM)、產(chǎn)品配置等)、過程(包括有關(guān)的加工工序、有關(guān)批準(zhǔn)權(quán)、使用權(quán)、工作流程過程程序)、資源一體化集成管理技術(shù)[3]。PDM進(jìn)行信息管理主要依托靜態(tài)的產(chǎn)品結(jié)構(gòu)和動態(tài)的產(chǎn)品開發(fā)流程。當(dāng)今的制造業(yè)企業(yè)相互間的競爭愈演愈烈,最顯著的就是產(chǎn)品的生命周期越來越短、產(chǎn)品個性化的需求越來越多、整個供應(yīng)鏈中產(chǎn)品信息的重復(fù)利用需求也越來越強(qiáng)。綜上,使PDM具有自我學(xué)習(xí)、改進(jìn)和完善是可能的,開展在PDM系統(tǒng)中的關(guān)聯(lián)挖掘也是切實(shí)可行的。
Apriori算法是一個經(jīng)典的數(shù)據(jù)挖掘算法,經(jīng)典的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法 Apriori 算法廣泛應(yīng)用于各種領(lǐng)域,通過對數(shù)據(jù)的關(guān)聯(lián)性進(jìn)行了分析和挖掘,挖掘出的這些信息在決策制定過程中具有重要的參考價值[4]。
2.1 Apriori算法的原理
Apriori是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法,它的基本思想是:首先找出所有的頻集,這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則,這些規(guī)則必須滿足最小支持度和最小可信度。再使用第1步找到的頻集產(chǎn)生期望的規(guī)則,產(chǎn)生只包含集合的項的所有規(guī)則,其中每一條規(guī)則的右部只有一項,這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成,那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來[5]。為了生成所有頻集,使用了遞歸的方法。
Apriori算法要求:頻繁項集的所有非空子集也必須是頻繁的,意味著模式不可能比A更頻繁的出現(xiàn)。它是反單調(diào)的,即一個集合如果不能通過測試,則該集合的所有超集也不能通過相同的測試。簡單的說,它通過減少搜索空間,來提高頻繁項集逐層產(chǎn)生的效率。
2.2 Apiori算法的實(shí)現(xiàn)
Apriori算法利用頻繁項集性質(zhì)的先驗(yàn)知識(prior knowledge),通過逐層搜索的迭代方法,即將 k-項集用于探察(k+1)-項集,來窮盡數(shù)據(jù)集中的所有頻繁項集[6]。具體說就是:先找到頻繁 1-項集集合L1,然后用L1找到頻繁2-項集集合L2,接著用L2找L3,直到找不到頻繁k-項集,找每個Lk需要一次數(shù)據(jù)庫掃描。
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性質(zhì)剪枝:頻繁項集的所有子集必須是頻繁的,對候選項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算法的缺點(diǎn)
Apriori算法簡單易于實(shí)現(xiàn),應(yīng)用非常廣泛。但有難以克服的缺點(diǎn):(1)在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多,沒有排除不應(yīng)該參與組合的元素;(2)每次計算項集的支持度時,都對數(shù)據(jù)庫D中的全部記錄進(jìn)行了一遍掃描比較,如果是一個大型的數(shù)據(jù)庫的話,這種掃描比較會大大增加計算機(jī)系統(tǒng)的 I/O開銷。而這種代價是隨著數(shù)據(jù)庫的記錄的增加呈現(xiàn)出幾何級數(shù)的增加[7]。
Apriori算法的最大缺點(diǎn)在于:它在運(yùn)算的過程中會產(chǎn)生大量的侯選集,而且在匹配的時候要進(jìn)行整個數(shù)據(jù)庫的掃描,因?yàn)橐鲋С侄扔嫈?shù)的統(tǒng)計操作,在小規(guī)模的數(shù)據(jù)上操作還不會有大問題,如果是大型的數(shù)據(jù)庫上呢,他的效率還是有待提高的[8]。
目前關(guān)于 Apriori算法的優(yōu)化方法有很多種主要集中的是1基于劃分的方法;2基于hash表的項集計數(shù)的方法;3基于采樣的方法(在給定數(shù)據(jù)的一個子集挖掘);4事務(wù)壓縮(壓縮進(jìn)一步迭代的事務(wù)數(shù));5動態(tài)項集計數(shù)[9-12]。借鑒一些資料,采用相對簡潔適合系統(tǒng)特點(diǎn)的算法是關(guān)鍵。
3.1 基本思路
在 Apriori算法中,尋找最大項目集的基本思路是:
第一步:簡單統(tǒng)計所有含一個元素的項目出現(xiàn)的頻率,并找出那些大于或等于最小支持度的項目集,產(chǎn)生一維頻繁項目集Lt。
第二步:循環(huán)處理直到未能再產(chǎn)生維數(shù)更高的頻繁項目集。循環(huán)過程是:在第k步中,根據(jù)k-1步生成的k-1維頻繁項目集來產(chǎn)生k維候選項目集,由于在產(chǎn)生 k-1維頻繁項目集時,我們可以實(shí)現(xiàn)對該集中出現(xiàn)元素的個數(shù)進(jìn)行計數(shù)處理,因此對某元素而言,若它的計數(shù)個數(shù)不到k-1的話,可以事先刪除該元素,從而排除由該元素將引起的大規(guī)格所有組合。
第三步:按Apriori算法再檢驗(yàn)新的K 維頻繁項目集的所有 k-1維項目集是否已經(jīng)包含在已經(jīng)求出的K-1維頻繁項目集。若其中有一個沒有包含,則也可刪去該組合,這樣得到一個真正有用的K維頻繁項目集選項目集。
第四步:得到了這個候選項目集后,可以對數(shù)據(jù)庫D的每一個事務(wù)tid進(jìn)行掃描,若該事務(wù)中至少含有候選項目集CK中的一員,則保留該項事務(wù),否則把該事物記錄與數(shù)據(jù)庫末端沒有作刪除標(biāo)記的事務(wù)記錄對換,并對移到數(shù)據(jù)庫末端的事務(wù)記錄作刪除標(biāo)一記,整個數(shù)據(jù)庫掃描完畢后為新的事務(wù)數(shù)據(jù)庫 D’ 中。
3.2 算法示例
我們可以看到改進(jìn)后的算法思路基本上與Apriori算法保持一致,但是又有不同之處。

圖2 第二步Fig.2 S econd steps

圖3 第三、四步Fig.3 Third, fourth steps
第一,改進(jìn)的算法在考慮組合 Ck前,對將參與組合的元素進(jìn)行計數(shù)處理,根據(jù)計數(shù)結(jié)果決定排除一些不符合組合條件的元素,這就降低了組合的可能性,即降低循環(huán)判斷的次數(shù)。
第二,改進(jìn)的算法對數(shù)據(jù)庫進(jìn)行了掃描后的重新生成,雖然會在記錄重寫中浪費(fèi)時間和 I/O的開銷,但是隨著循環(huán)次數(shù)的增加,本算法對以后在‘新生成的數(shù)據(jù)庫’中的掃描比較次數(shù)很快減少將逐漸體現(xiàn)出來。
4.1 算法實(shí)例對比
問題:假設(shè) 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}}。
改進(jìn)算法:首先從Lk-1中取元素{1,2,3},掃描Ck中的元素,看{1,2,3}是不是Ck元中元素的子集,{1,2,3}是{1,2,3,4}的子集,{1,2,3,4}的計數(shù)加 1,{1,2,3}不是{2,3,4,5}的子集,計數(shù)不變,是{1,2,3,5}的子集,計數(shù)加 1,經(jīng)過對{1,2,3}處理后得到計數(shù){1,0,1};然后看{1,2,4},{1,2,4}是{1,2,3,4}的子集,而不是 {2,3,4,5}的子集,也不是{1,2,3,5}的子集,計數(shù)不變,計數(shù)變?yōu)閧2,0,1};考察{2,3,4},{2,3,4}是{1,2,3,4}的子集,也是{2,3,4,5}的子集,不是{1,2,3,5}的子集,計數(shù)變?yōu)閧3,1,1};{2,3,5}不是{1,2,3,4}的子集,是{2,3,4,5}的子集,也是{1,2,3,5}的子集,計數(shù)變?yōu)閧3,2,2};{1,3,4}是{1,2,3,4}的子集,不是{2,3,4,5}的子集,也不是{1,2,3,5}的子集,計數(shù)變?yōu)閧4,2,2}。對數(shù)據(jù)掃描完畢。此時 K=4,只有第一個元素的計數(shù)為 4,為高頻數(shù)據(jù)項集。得到C’k={{1,2,3,4}}。
復(fù)雜度對比
下面對原算法和改進(jìn)算法的性能進(jìn)行比較。Lk-1中的數(shù)據(jù)項集的個數(shù)記為|Lk-1|,Ck中的數(shù)據(jù)項集的個數(shù)記為|Ck|,Ck中元素的子集個數(shù)設(shè)為ni,其中i=1~|Ck|。這里只分析從Ck~C’k的處理。原算法從 AprioriCk中取元素,然后求該元素的子集,判斷該子集是否在|Ck|中。需要進(jìn)行的計算為1<=|L’k-1|<=|L’k-1|,1< = n’i <=n i。而改進(jìn)算法是從Lk-1中選取元素,看是不是Ck中元素的子集,對 Ck中數(shù)據(jù)項集的子集個數(shù)進(jìn)行統(tǒng)計。需要進(jìn)行的計算是(|Lk-1|+1)*|Ck| 次。如果 n’i =1,就是每次只取 Ck中數(shù)據(jù)項集的一個子集就可以判斷該數(shù)據(jù)項集,則兩個算法的效率基本相同,但是這種情況很少出現(xiàn),從而大部分情況下,改進(jìn)算法的效率要高于原算法。
4.2 系統(tǒng)實(shí)現(xiàn)
PDM 系統(tǒng)采用JSP加MSSQL2000數(shù)據(jù)庫的方式,應(yīng)用平臺為B/S結(jié)構(gòu),采用模塊化方式。核心部分?jǐn)?shù)據(jù)挖掘模塊分為三層:數(shù)據(jù)存儲層、業(yè)務(wù)邏輯層、界面層,以Web頁面的方式嵌入到系統(tǒng)框架中,如圖 4。其中挖掘算法管理模塊封裝實(shí)現(xiàn)各種數(shù)據(jù)挖掘算法,如關(guān)聯(lián)規(guī)則算法可以實(shí)現(xiàn)對樣本數(shù)據(jù)源的關(guān)聯(lián)分析,并改進(jìn)經(jīng)典的 Apriori 算法,適應(yīng)制造業(yè)的多維數(shù)據(jù),如圖5。

圖4 PDM 中數(shù)據(jù)挖掘分析系統(tǒng)登錄界面Fig.4 Data mining analysis system login interface in PDM

圖5 PDM 中數(shù)據(jù)挖掘分析系統(tǒng)模塊化管理界面Fig.5 Modular management interface of data mining analysis system in PDM
交互模塊允許用戶自定義關(guān)聯(lián)項數(shù)、支持度和置信度,并依據(jù)產(chǎn)生的規(guī)則和用戶的需求對結(jié)果進(jìn)行過濾,以自然語言的方式來表示規(guī)則,提取規(guī)則,保存規(guī)則。
4.3 挖掘結(jié)果分析
應(yīng)用本系統(tǒng)對制造類企業(yè) PDM 數(shù)據(jù)庫的進(jìn)行分析,以某種銑床夾具零件的數(shù)據(jù)為例,圖6是某企業(yè)PDM數(shù)據(jù)庫中零件表與其它各表之間的關(guān)系。系統(tǒng)對其中一張表或是某個屬性進(jìn)行關(guān)聯(lián)分析,產(chǎn)生的挖掘結(jié)果對其它相關(guān)零件的生產(chǎn)和加工工具的使用有指導(dǎo)作用。

圖6 PDM 數(shù)據(jù)庫中零件表與其它各個表之間的關(guān)系Fig.6 BOM relations between tables and other PDM database
隨著互聯(lián)網(wǎng)+在各行各業(yè)的深入推廣和大數(shù)據(jù)涌現(xiàn),PDM系統(tǒng)在企業(yè)信息化中大有作為,應(yīng)用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則分析在制造類企業(yè) PDM 系統(tǒng)中開展相關(guān)研究有很大的前景。本文依據(jù)數(shù)據(jù)挖掘中的經(jīng)典算法 Apriori并進(jìn)行適當(dāng)改進(jìn),結(jié)合企業(yè)PDM系統(tǒng)的相關(guān)個性應(yīng)用需求,試圖探索尋找一種效率更高、穩(wěn)定性更強(qiáng)的關(guān)聯(lián)規(guī)則挖掘分析方法,并在模擬系統(tǒng)中進(jìn)行實(shí)踐,取得了一定的效果,為今后的后續(xù)研究積累了經(jīng)驗(yàn)。
[1] 約瑟夫·蕭塔納著,祁國寧譯. 制造企業(yè)的產(chǎn)品數(shù)據(jù)管理[M]. 機(jī)械工業(yè)出版社,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. 范明, 孟小峰, 等譯. 數(shù)據(jù)挖掘概念與技術(shù)(第一版)[M]. 北京: 機(jī)械工業(yè)出版社, 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] 童秉樞, 李建明. 產(chǎn)品數(shù)據(jù)管理(PDM)技術(shù)[M]. 清華大學(xué)出版社, 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] 王銳, 李晶, 熊海蘊(yùn), 繩鵬. 基于關(guān)聯(lián)規(guī)則的Apriori算法的可視化實(shí)現(xiàn)方法[J]. 計算機(jī)工程與設(shè)計, 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] 黃進(jìn), 尹治本. 關(guān)聯(lián)規(guī)則挖掘的Apriori算法的改進(jìn)[J]. 電子科技大學(xué)學(xué)報, 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] 陸麗娜, 陳亞萍. 挖掘關(guān)聯(lián)規(guī)則中Apriori算法的研究[J].小型微型計算機(jī)系統(tǒng), 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] 蔡偉杰, 張曉輝, 朱建秋, 朱揚(yáng)勇. 關(guān)聯(lián)規(guī)則挖掘綜述[J].計算機(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] 李緒成, 王保保. 挖掘關(guān)聯(lián)規(guī)則中Apriori算法的一種改進(jìn)[J]. 計算機(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] 楊澤民. 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[J]. 軟件, 2013,34(11): 71-72.Yang Zemin. Research on association rules algorithm in data mining[J]. software, 2013, 34(11): 71-72.
[12] 孫文靜, 傅濤. 基于改進(jìn)Apriori 算法的入侵檢測數(shù)據(jù)挖掘模型研究[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
本文著錄格式:浦慧忠. 互聯(lián)網(wǎng)+環(huán)境下基于數(shù)據(jù)挖掘的個性化PDM系統(tǒng)的應(yīng)用研究[J]. 軟件,2017,38(11):202-207
浦慧忠(1980-),男,碩士,講師,江蘇無錫人,主要研究方向:數(shù)據(jù)挖掘。