基于數據挖掘的一種聚類分析方法在PDM系統中的應用研究*

浦慧忠

(無錫城市職業技術學院 無錫 214153)

?

基于數據挖掘的一種聚類分析方法在PDM系統中的應用研究*

浦慧忠

(無錫城市職業技術學院 無錫 214153)

從企業產品數據管理需求的現狀出發，針對數據挖掘中經典的k-means算法中存在的不足并考慮到PDM系統中存在的數據量相當大、數據類型復雜等現實問題，參考采用多次取樣一次聚類尋找最優解的改進算法，并通過模擬系統實驗驗證該算法的穩定性及效果有顯著的改善。

產品數據管理; 數據挖掘; 聚類分析; k-means 算法

Class Number TP393

1 引言

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

數據挖掘是指從數據庫中發現隱含的、新穎的、對決策有潛在價值的知識和規則的過程，已廣泛地應用于制造業信息化中。聚類分析是數據挖掘領域中最重要的技術之一，面向制造企業的PDM系統開展聚類分析已經成為企業信息化中一個非常活躍的研究課題。

2 國內外研究現狀及趨勢

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

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

3 存在的問題

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

3.1 K-means 算法的原理

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

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

3.2 K-means 算法的優缺點

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

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

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

4 改進的方法

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

4.1 算法思想

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

數據點i的局部密度ρi定義為式(1)：

(1)

其中，如果x<0，那么χ(χ)=1；否則χ(χ)=0，dc是一個截斷距離。基本上，ρi等于與點i的距離小于dc的點的個數。算法只對不同點的ρi的相對大小敏感，這意味著對于大數據集，分析結果對于dc的選擇有很好魯棒性。

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

δi=minj:pj>pi(dij)

(2)

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

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

類簇中心找到后，剩余的每個點被歸屬到它的有更高密度的最近鄰所屬類簇。類簇分配只需一步即可完成，不像其它算法要對目標函數進行迭代優化。

4.2 聚類分析

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

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

圖2 合成點分布的結果

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

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

圖3 應用于各種數據分布后的聚類效果

算法對于不嚴重影響dc以下的距離，也就是保持式(1)的密度估計量不變的度量標準的變化有很好的魯棒性。很明顯，式(2)中的距離將會被這種度量標準的改變所影響，但很容易意識到決策圖的結構(尤其是有較大的值δ的點的個數)是一個按密度值排序的結果，并不是距離較遠的點的真實距離。

5 實驗結果驗證及分析

5.1 系統實現

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

5.2 聚類分析

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

圖4 數據挖掘分析系統登錄界面

圖5 數據挖掘分析系統讀取PDM數據庫中的表

圖6 數據挖掘分析系統對PDM數據庫表聚類的散列點圖

圖7 對應圖6的三維聚類結果圖

應用本系統對制造類企業PDM數據庫的進行分析，以某種銑床夾具零件的數據為例，說明本系統在實際應用中的價值。圖8顯示了某企業PDM數據庫中零件表與其它各個表之間的關系，通過其中一張表或是某個屬性進行聚類，結果用來指導其它的相關零件的生產和加工工具的使用等等。

圖8 PDM數據庫中零件表與其它各個表之間的關系

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

圖9 聚類分析前某零件數據庫和數據表的選擇

圖10 系統聚類分析后某零件數據庫和數據表的選擇

6 結語

隨著PDM系統在企業信息化中的不斷深入，各種數據源大量涌現，應用數據挖掘中的聚類分析方法在企業PDM系統中開展相關研究應用有很大的前景，本文從數據挖掘中的經典K-means算法出發，探索尋找一種效率更高、穩定性更強的聚類分析方法，并在某企業PDM系統中進行實踐，取得了不錯的應用效果，也為今后后續研究積累了相關經驗。

[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.范明,孟小峰,等譯.數據挖掘概念與技術(第一版)[M].北京:機械工業出版社,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] 姜園,張朝陽,仇佩亮,等.用于數據挖掘的聚類算法[J].電子與信息學報,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] 袁方,周志勇,宋鑫.初始聚類中心優化的k-means算法[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值優化問題研究[J].系統工程理論與實踐,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日

無錫市教育科學“十二五”規劃立項課題《非標企業PDM管理系統的實踐與研究》(編號：J/D/2014/025)資助。

浦慧忠，男，碩士，講師，研究方向：數據挖掘。

TP392

10.3969/j.issn.1672-9722.2016.11.024