浦慧忠

(無錫城市職業(yè)技術(shù)學(xué)院 無錫 214153)

?

基于數(shù)據(jù)挖掘的一種聚類分析方法在PDM系統(tǒng)中的應(yīng)用研究*

浦慧忠

(無錫城市職業(yè)技術(shù)學(xué)院 無錫 214153)

從企業(yè)產(chǎn)品數(shù)據(jù)管理需求的現(xiàn)狀出發(fā)，針對數(shù)據(jù)挖掘中經(jīng)典的k-means算法中存在的不足并考慮到PDM系統(tǒng)中存在的數(shù)據(jù)量相當(dāng)大、數(shù)據(jù)類型復(fù)雜等現(xiàn)實(shí)問題，參考采用多次取樣一次聚類尋找最優(yōu)解的改進(jìn)算法，并通過模擬系統(tǒng)實(shí)驗(yàn)驗(yàn)證該算法的穩(wěn)定性及效果有顯著的改善。

產(chǎn)品數(shù)據(jù)管理; 數(shù)據(jù)挖掘; 聚類分析; k-means 算法

Class Number TP393

1 引言

近年來，制造業(yè)信息化在很多企業(yè)得以應(yīng)用，取得了明顯效果。PDM的中文名稱為產(chǎn)品數(shù)據(jù)管理(Product Data Management)是一門用來管理所有與產(chǎn)品相關(guān)信息(包括零件信息、配置、文檔、CAD文件、結(jié)構(gòu)、權(quán)限信息等)和所有與產(chǎn)品相關(guān)過程(包括過程定義和管理)的技術(shù)[1]。它可以提高生產(chǎn)效率，有利于對產(chǎn)品的全生命周期進(jìn)行管理，加強(qiáng)對文檔、圖紙、數(shù)據(jù)的高效利用，使工作流程規(guī)范化。然而在這當(dāng)中也暴露出諸多問題和困難，PDM 的迅猛發(fā)展需要企業(yè)采用分布式存儲、異地協(xié)同設(shè)計(jì)、數(shù)據(jù)共享等先進(jìn)技術(shù)，從而帶來所存儲的數(shù)據(jù)呈指數(shù)級別的增長，但這些龐大的數(shù)據(jù)背后所隱藏的知識并沒有得到充分的挖掘利用，形成“數(shù)據(jù)豐富，知識貧乏”。如何能在企業(yè)積累的大量信息中及時(shí)發(fā)現(xiàn)有價(jià)值的信息或知識并為管理者的決策提供支持是一個(gè)亟待解決的問題。

數(shù)據(jù)挖掘是指從數(shù)據(jù)庫中發(fā)現(xiàn)隱含的、新穎的、對決策有潛在價(jià)值的知識和規(guī)則的過程，已廣泛地應(yīng)用于制造業(yè)信息化中。聚類分析是數(shù)據(jù)挖掘領(lǐng)域中最重要的技術(shù)之一，面向制造企業(yè)的PDM系統(tǒng)開展聚類分析已經(jīng)成為企業(yè)信息化中一個(gè)非?；钴S的研究課題。

2 國內(nèi)外研究現(xiàn)狀及趨勢

“物以類聚，人以群分”將物理或抽象對象的集合分成由類似的對象組成的多個(gè)類的過程被稱為聚類。聚類分析又稱群分析，指將物理或抽象對象的集合分組為由類似的對象組成的多個(gè)類的分析過程。聚類分析的目標(biāo)就是在相似的基礎(chǔ)上收集數(shù)據(jù)來分類[2]，在機(jī)器學(xué)習(xí)[3～4]、數(shù)據(jù)挖掘[5～6]、模式識別[7]、生物學(xué)[8]、統(tǒng)計(jì)學(xué)[9]和化學(xué)[10]等許多領(lǐng)域都得到了廣泛的研究和應(yīng)用。聚類分析的核心是選擇合適的聚類算法，目前許多聚類算法在小于200個(gè)數(shù)據(jù)對象的小數(shù)據(jù)集合上工作得很好，但是一個(gè)大規(guī)模數(shù)據(jù)庫可能包含幾百萬個(gè)對象，在這樣的大數(shù)據(jù)集合樣本上進(jìn)行聚類可能會導(dǎo)致有偏的結(jié)果。我們更需要具有高度可伸縮性的聚類算法。

由于在PDM的數(shù)據(jù)庫中保存著所有產(chǎn)品整個(gè)生命周期中的每一個(gè)環(huán)節(jié)的數(shù)據(jù)，在PDM的數(shù)據(jù)庫中應(yīng)用聚類分析，可以從數(shù)據(jù)中得到更深層次的信息。例如：根據(jù)產(chǎn)品的銷售記錄可以聚類分析結(jié)果，調(diào)整該產(chǎn)品的生產(chǎn)周期，減少庫存降低成本；在開發(fā)設(shè)計(jì)新的工件時(shí)，可以將原來存儲于數(shù)據(jù)庫中已經(jīng)開發(fā)設(shè)計(jì)過的相似工件進(jìn)行聚類，根據(jù)結(jié)果和新工件的要求做比較得出哪些設(shè)計(jì)數(shù)據(jù)、產(chǎn)品模型、工程圖紙、技術(shù)規(guī)范、工藝資料等是可以重復(fù)利用的，這樣可以進(jìn)一步降低設(shè)計(jì)開發(fā)時(shí)間，提高生產(chǎn)效率。綜上，面向PDM系統(tǒng)這類具有高維度和大型數(shù)據(jù)的情況采用基于數(shù)據(jù)挖掘的聚類分析研究是切實(shí)可行的。

3 存在的問題

文獻(xiàn)[11]中作者介紹和研究了幾種比較經(jīng)典和常用的聚類方法，分析和比較了各種方法的優(yōu)缺點(diǎn)。k-means算法是一種經(jīng)典的基于劃分的方法，它的優(yōu)點(diǎn)是簡單易行、效率高，所以被廣泛應(yīng)用于大規(guī)模數(shù)據(jù)的聚類分析。目前，大多數(shù)聚類分析的研究均圍繞著該算法進(jìn)行擴(kuò)展和改進(jìn)。

3.1 K-means 算法的原理

K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)[12]。

算法的主要工作過程如下：首先從n個(gè)數(shù)據(jù)對象任意選擇 k 個(gè)對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心(該聚類中所有對象的均值)；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止。

3.2 K-means 算法的優(yōu)缺點(diǎn)

K-means算法的特點(diǎn)-采用兩階段反復(fù)循環(huán)過程算法，結(jié)束的條件是不再有數(shù)據(jù)元素被重新分配：即指定數(shù)據(jù)到某一個(gè)聚類，使得它與這個(gè)聚類中心的距離比它到其它聚類中心的距離要近。

K-means算法的優(yōu)點(diǎn)主要集中在： 1) 算法快速、簡單； 2) 對大數(shù)據(jù)集有較高的效率并且是可伸縮性的； 3) 時(shí)間復(fù)雜度近于線性，而且適合大規(guī)模數(shù)據(jù)集挖掘[13]。

而它的缺點(diǎn)主要表現(xiàn)在： 1) 運(yùn)行速度慢。雖然通常情況下，K-means執(zhí)行的循環(huán)次數(shù)要少于數(shù)據(jù)對象的個(gè)數(shù)。但是對于最壞的情況下，其執(zhí)行的時(shí)間復(fù)雜度將是超多項(xiàng)式的。 2) K值的選取。在執(zhí)行程序前，需要給定K值的大小。然而對于不同的K值，劃分的結(jié)果當(dāng)然不同，因此確定最合適的K值非常關(guān)鍵。 3) 初始化K個(gè)形心。形心的初始選取對于劃分結(jié)果亦非常關(guān)鍵。 4) K-means對于數(shù)據(jù)不同的維度”一視同仁”，缺乏輕重之分[14]。

4 改進(jìn)的方法

Science雜志上Alex Rodriguez，Alessandro Laio[15]的文章Clustering by fast search and find of density peak中提出了一種很簡潔優(yōu)美的聚類算法，可以識別各種形狀的類簇，并且其參數(shù)很容易確定。

4.1 算法思想

首先，基于這樣的假設(shè)：類簇中心被具有較低局部密度的鄰居點(diǎn)包圍，且與具有更高密度的任何點(diǎn)有相對較大的距離。對于每一個(gè)數(shù)據(jù)點(diǎn)i，要計(jì)算兩個(gè)量：點(diǎn)的局部密度ρi和該點(diǎn)到具有更高局部密度的點(diǎn)的距離δi，而這兩個(gè)值都取決于數(shù)據(jù)點(diǎn)間的距離dij。

數(shù)據(jù)點(diǎn)i的局部密度ρi定義為式(1)：

(1)

其中，如果x<0，那么χ(χ)=1；否則χ(χ)=0，dc是一個(gè)截?cái)嗑嚯x?；旧希裪等于與點(diǎn)i的距離小于dc的點(diǎn)的個(gè)數(shù)。算法只對不同點(diǎn)的ρi的相對大小敏感，這意味著對于大數(shù)據(jù)集，分析結(jié)果對于dc的選擇有很好魯棒性。

數(shù)據(jù)點(diǎn)i的δi是點(diǎn)到任何比其密度大的點(diǎn)的距離的最小值為式(2)：

δi=minj:pj>pi(dij)

(2)

對于密度最大的點(diǎn)，可以得到δi=maxj(dij)。

圖1中的簡單示例展示了算法的核心思想。圖1(a)展示了二維空間中的28個(gè)點(diǎn)?？梢园l(fā)現(xiàn)點(diǎn)1和點(diǎn)10的密度最大，故將其作為類簇中心。圖1(b)展示了對于每一個(gè)點(diǎn)的δi作為ρi的函數(shù)的圖示，稱其為決策圖。點(diǎn)9和點(diǎn)10的ρ相似，但δ值卻有很大差別：點(diǎn)9屬于點(diǎn)1的類簇，其它幾個(gè)有更高的ρ的點(diǎn)距其很近，然而點(diǎn)10有更高密度的最近鄰屬于其它的類簇。所以，正如預(yù)期的那樣，只有具有高δ和相對較高的ρ的點(diǎn)才是類簇中心。因?yàn)辄c(diǎn)26、27、28是孤立的，所以有相對較高的δ值和低ρ值，它們可以被看作是由單個(gè)點(diǎn)做成的類簇，也就是異常點(diǎn)。

類簇中心找到后，剩余的每個(gè)點(diǎn)被歸屬到它的有更高密度的最近鄰所屬類簇。類簇分配只需一步即可完成，不像其它算法要對目標(biāo)函數(shù)進(jìn)行迭代優(yōu)化。

4.2 聚類分析

在聚類分析中，定量的衡量分配的可信度是很重要的。在該算法中，首先為每個(gè)類簇定義一個(gè)邊界區(qū)域(即分配到該類簇但于其它類簇的點(diǎn)的距離小于dc的點(diǎn)的集合)，然后為每個(gè)類簇的找到其邊界區(qū)域中密度最高的點(diǎn)，并以ρb來表示該點(diǎn)的密度。類簇中局部密度值比ρb大的點(diǎn)被看作是類簇的核心部分(即分配到該類簇的可靠性較高)，其他點(diǎn)被看作是類簇的光暈部分(亦可以被看作是噪聲)。

圖1 算法在二維空間的展示

圖2 合成點(diǎn)分布的結(jié)果

其中圖2(a)為繪制的點(diǎn)分布的概率分布。圖2(b)和圖2(c)分別為4000和1000樣本點(diǎn)的點(diǎn)分布。每個(gè)點(diǎn)以其顏色表示所屬類簇，黑色點(diǎn)屬于光暈類簇。圖2(d)和(e)相應(yīng)的決策圖，彩色的點(diǎn)表示類簇中心。圖2(f)被歸屬到錯(cuò)誤的類簇的點(diǎn)的比例作為樣本維度的函數(shù)。誤差線表明均值的標(biāo)準(zhǔn)差。

從圖2(f)中可以看到，錯(cuò)分點(diǎn)的比例即使在只有1000個(gè)點(diǎn)的小樣本中仍保持在1%以下，說明算法有很好的魯棒性。為圖2(b)中數(shù)據(jù)賦予不同的dc值，卻得到幾乎一樣的結(jié)果。一般來說，可以選擇dc使得點(diǎn)的平均鄰居數(shù)大概是數(shù)據(jù)集中點(diǎn)的總數(shù)的1%～2%。對于較小的數(shù)據(jù)集，ρi可能會被大的統(tǒng)計(jì)誤差影響，在這種情況下，需要通過更準(zhǔn)確的方法估計(jì)密度(例如可以采取文章中提到的指數(shù)核的方法)。如圖3所示，該算法對于各種數(shù)據(jù)級都能達(dá)到很好的聚類效果。

圖3 應(yīng)用于各種數(shù)據(jù)分布后的聚類效果

算法對于不嚴(yán)重影響dc以下的距離，也就是保持式(1)的密度估計(jì)量不變的度量標(biāo)準(zhǔn)的變化有很好的魯棒性。很明顯，式(2)中的距離將會被這種度量標(biāo)準(zhǔn)的改變所影響，但很容易意識到?jīng)Q策圖的結(jié)構(gòu)(尤其是有較大的值δ的點(diǎn)的個(gè)數(shù))是一個(gè)按密度值排序的結(jié)果，并不是距離較遠(yuǎn)的點(diǎn)的真實(shí)距離。

5 實(shí)驗(yàn)結(jié)果驗(yàn)證及分析

5.1 系統(tǒng)實(shí)現(xiàn)

在實(shí)際的開發(fā)中，為了實(shí)現(xiàn)系統(tǒng)的可視化，采用Matlab與Java混合編程，在核心聚類算法的選擇方面借鑒Alex Rodriguez,Alessandro Laio的相關(guān)算法，主要最大限度的保證系統(tǒng)的穩(wěn)定性，主要界面見圖4～圖7。

5.2 聚類分析

將作者M(jìn)atlab下實(shí)現(xiàn)的代碼轉(zhuǎn)化成Java語言，并得到一定實(shí)驗(yàn)效果。作者使用Matlab做的實(shí)驗(yàn)數(shù)據(jù)集使用的是(點(diǎn)序號、點(diǎn)序號、兩點(diǎn)間的距離)的矩陣形式，本文使用的數(shù)據(jù)集形式是空間坐標(biāo)點(diǎn)。對于實(shí)驗(yàn)中的重要幾個(gè)參數(shù)：局部密度rho，點(diǎn)到高局部密度點(diǎn)的最近距離delta，dc等。首先，關(guān)于dc的取值問題，作者簡單提到選擇dc使得平均每個(gè)點(diǎn)的鄰居數(shù)為所有點(diǎn)的1%～2%。但是在實(shí)際實(shí)驗(yàn)中，不同的數(shù)據(jù)集需要的dc值在使得平均每個(gè)點(diǎn)的鄰居數(shù)為所有點(diǎn)的1%～2%之間的某個(gè)范圍，而這個(gè)范圍并不是確定得到的，需要經(jīng)過大量實(shí)驗(yàn)測試才能取到一個(gè)相對比較適合的范圍。第二，關(guān)于離群點(diǎn)的問題，作者M(jìn)atlab實(shí)現(xiàn)的源碼中沒有實(shí)現(xiàn)如何分離出離群點(diǎn)，26，27，28這三個(gè)點(diǎn)雖然delta值雖然很大，但是rho很小，所以這三個(gè)點(diǎn)可以作為離群點(diǎn)。

圖4 數(shù)據(jù)挖掘分析系統(tǒng)登錄界面

圖5 數(shù)據(jù)挖掘分析系統(tǒng)讀取PDM數(shù)據(jù)庫中的表

圖6 數(shù)據(jù)挖掘分析系統(tǒng)對PDM數(shù)據(jù)庫表聚類的散列點(diǎn)圖

圖7 對應(yīng)圖6的三維聚類結(jié)果圖

應(yīng)用本系統(tǒng)對制造類企業(yè)PDM數(shù)據(jù)庫的進(jìn)行分析，以某種銑床夾具零件的數(shù)據(jù)為例，說明本系統(tǒng)在實(shí)際應(yīng)用中的價(jià)值。圖8顯示了某企業(yè)PDM數(shù)據(jù)庫中零件表與其它各個(gè)表之間的關(guān)系，通過其中一張表或是某個(gè)屬性進(jìn)行聚類，結(jié)果用來指導(dǎo)其它的相關(guān)零件的生產(chǎn)和加工工具的使用等等。

圖8 PDM數(shù)據(jù)庫中零件表與其它各個(gè)表之間的關(guān)系

例如，選取圖中銑床夾具上的零件的銷售情況為分析對象，圖9顯示了在聚類分析前對于此零件數(shù)據(jù)庫和數(shù)據(jù)表的選擇。在圖中的屬性選擇工作空間中列出了這個(gè)零件的數(shù)據(jù)表中的屬性，用戶可以通過添加和刪除按鈕從左邊的屬性列表中選擇要進(jìn)行聚類分析的數(shù)據(jù)屬性，為進(jìn)行數(shù)據(jù)分析做好準(zhǔn)備。一共選取了330個(gè)此零件的相關(guān)數(shù)據(jù)，用系統(tǒng)對選擇的數(shù)據(jù)屬性進(jìn)行分析可以得到圖10的結(jié)果。圖中橫坐標(biāo)表示零件銷售的天數(shù)(單位/天)，縱坐標(biāo)表示零件售出的數(shù)量(單位/千件)。從最后顯示的結(jié)果可以很直觀地看出：數(shù)據(jù)被分為四個(gè)簇A，B，C，D，其中簇A中有101個(gè)數(shù)據(jù)，簇B有97個(gè)數(shù)據(jù)，簇C有68個(gè)數(shù)據(jù)，簇D有64個(gè)數(shù)據(jù)。在簇的中心即數(shù)據(jù)點(diǎn)比較密集的地方，表示此零件在這些天銷售情況較集中，特別是C和D兩個(gè)簇還表明此時(shí)的零件銷售量較大。由此非常清晰地顯示出產(chǎn)品銷售的數(shù)據(jù)中隱藏的信息，該挖掘結(jié)果反饋給企業(yè)的管理者可以根據(jù)情況調(diào)整相應(yīng)的生產(chǎn)進(jìn)度，協(xié)調(diào)各個(gè)生產(chǎn)部門的工作，如應(yīng)改變此銑床夾具其他相關(guān)零件的生產(chǎn)；改變生產(chǎn)這些零件所需材料的選購日期和庫存周期的長短；根據(jù)挖掘出的信息重新協(xié)調(diào)生產(chǎn)車間的毛坯的使用情況等。

圖9 聚類分析前某零件數(shù)據(jù)庫和數(shù)據(jù)表的選擇

圖10 系統(tǒng)聚類分析后某零件數(shù)據(jù)庫和數(shù)據(jù)表的選擇

6 結(jié)語

隨著PDM系統(tǒng)在企業(yè)信息化中的不斷深入，各種數(shù)據(jù)源大量涌現(xiàn)，應(yīng)用數(shù)據(jù)挖掘中的聚類分析方法在企業(yè)PDM系統(tǒng)中開展相關(guān)研究應(yīng)用有很大的前景，本文從數(shù)據(jù)挖掘中的經(jīng)典K-means算法出發(fā)，探索尋找一種效率更高、穩(wěn)定性更強(qiáng)的聚類分析方法，并在某企業(yè)PDM系統(tǒng)中進(jìn)行實(shí)踐，取得了不錯(cuò)的應(yīng)用效果，也為今后后續(xù)研究積累了相關(guān)經(jīng)驗(yàn)。

[1] D.Lindeman, Brian Moore. PDM, An Enabling Technology for Integrated Product Development[C]//1994 Proceedings Annual Reliability and Maintainability Symposium,1994:320-326.

[2] J Han J,Kamber M.范明,孟小峰,等譯.數(shù)據(jù)挖掘概念與技術(shù)(第一版)[M].北京:機(jī)械工業(yè)出版社,2006:185-217. Han J,Kamber M.,&Fan Ming, & Meng Xiaofeng.(2006).The concept and technology of data mining(the first edition).185-217.Beijing:Mechanical industry press,2006:185-217.

[3] T.Kanungo,D.M Mount,N.S.Netanyahu,etal.An efficient K-means clustering algorithm:analysis and implementation[J].IEEE Transactions on Pattern Ana1ysis and Machine Intelligence,2002,24(7):881-892.

[4] M.Meila,D.Heckerman.An experimental comparison of model-based Clustering methods[J].Machine Learning,2001,42(1/2):9-29.

[5] G.sudipto,R.Rajeev,S.Kyuseok.Cure:an efficient clustering algorithm For large databases[J].Information Systems,2001,26(1):35-58.

[6] Xu,J.Jager, H.P.Kriegel. A fast Parallel clustering algorithm for large spatial dalabases[J].Data Mining and Knowiedge Discovery,1999,3(3):263-290.

[7] Marie Chavent,Yves Lechevallier,Olivier Briant.monothetic divisive hierarchical clustering method[J].Elsevier Science Publishers B.V,2007,52(2):687-701.

[8] E.Hartuv,R.Shamir. A clustering algorithm based on graph connectivity[J].Information Processing Letters,2000,76:175-181.

[9] MJ.Symons.Approximate clustering criteria and multivariate normal mixtures[J].Biometrics,1981,37:35-43.

[10]GA.Jacques, R.Roger.Clustering of a molecular dynamics trajectory with a Harnming distance[J].Computers and Chemistry,2000,24(6):693-698.

[11] 姜園,張朝陽,仇佩亮,等.用于數(shù)據(jù)挖掘的聚類算法[J].電子與信息學(xué)報(bào),2005,27(4):655- 662. JIANG Yuan, ZHAN Chaoyang, QIU Peiliang, et al. The clustering algorithm of data mining[J].Journal of Electronics & Information Technology,2005,27(4):655-662.

[12] 袁方,周志勇,宋鑫.初始聚類中心優(yōu)化的k-means算法[J].計(jì)算機(jī)工程,2007,33(3):65-66. YUAN Fang, ZHOU Zhiyong, SONG Xing. The initial clustering center optimized k - means algorithm[J].Computer Engineering,2007,33(3):65-66.

[13] 楊善林,李永森,胡笑旋,等.K-means算法中的k值優(yōu)化問題研究[J].系統(tǒng)工程理論與實(shí)踐,2006,26(2):97-101. YANG Shanlin, LI Yongsen, HU Xiaoxuan, et al. K value optimization research in K-means algorithm[J].System Engineering Theory and Practice,2006,26(2):97-101.

Application of A Cluster Analysis Based on Data Mining in the PDM System

PU Huizhong

(Wuxi City College of Vocational Teachnology, Wuxi 214153)

From the current situation of enterprise product data management needs, aiming at shortage of data mining in the classic k-means algorithm that exist and considering the amount of data that exist in the PDM system is quite large, complex data types and other practical problems, a reference to the use of multiple sampling improved clustering algorithm to find the optimal solution by simulating experiments verify the stability of the system and the algorithm is significantly improved.

PDM, data mining, cluster analysis, k-means algorithm

2016年5月3日,

2016年6月19日

無錫市教育科學(xué)“十二五”規(guī)劃立項(xiàng)課題《非標(biāo)企業(yè)PDM管理系統(tǒng)的實(shí)踐與研究》(編號：J/D/2014/025)資助。

浦慧忠，男，碩士，講師，研究方向：數(shù)據(jù)挖掘。

TP392

10.3969/j.issn.1672-9722.2016.11.024