基于聚類方法的CAPP動態零件庫構建報告人：金輝主要內容CAPP信息管理智能化的需要已有的零件分類方案分析問題和解決方法聚類技術概述距離等參數設置聚類過程劃分子簇聚類樹構建聚類樹的優化和壓縮CAPP的知識信息智能化需要工藝知識的復雜性工藝知識總結工作量大，高層次的總結難度較大，這是CAPP應用的關鍵難點之一工藝設計的復雜性在制造業向計算機集成制造系統(CIMS)的發展轉變中，隨著CAD/CAM/CAPP集成與并行化的發展，工藝設計變得越來越復雜，尋找一種有效的CAPP推理策略，成為CAPP研究的重點.自動工藝流程圖編碼分類專業工藝生成專業工藝審查工藝生成流工藝路線生成工藝路線審查工藝路線批準專業工藝批準工藝生成信息反饋工藝生成流合理分類的前提零件特征知識的合理表達零件特征知識的充分獲取已有的零件分類方法視檢法生產流程分析法順序分枝法聚類分析法編碼分類法零件信息管理中遇到的問題（1）零件本身包含大量的難以精確表述的特征零件之間的相似性不能充分表達，因此不能利用已有的相似零件的工藝信息以往傳統的零件數據組織形式已逐漸不能滿足要求：不能反映零件之間的特征關系；零件數據庫一般只有數據而沒有內在規則。零件信息管理中遇到的問題（2）對于多品種生產企業，利用計算機輔助制造時需要收集、分析和處理大量的信息，若按照單一零件來存貯它們的工藝，生產信息，會造成信息的重復和檢索的困難。CAPP的系統運行在一個處于持久變化著的應用環境中，這包括所需制造數據的動態性，各決策機制所需知識的動態性，一個不能適應動態數據變化的數據庫系統只能導致經驗性的決策方式，而阻礙推理過程的智能化。提出的解決方案利用編碼輸入法的零件信息輸入和生產流程的聚類分析方法，克服二者的缺點，著重解決以下問題：

1）確定合理的數據結構或零件模型對零件信息進行描述，能讓提高計算機辨識零件聚類的準確度，并協助完成聚類工作；2）尋找一種有效的零件在數據庫的組織形式和智能聚類策略，在此基礎上建立合理的工藝推理過程；3）構造一種有著自學習自適應能力的零件數據庫。使得零件在數據庫中的排列位置更為合理，反映特征、功能上的內在聯系；4）數據庫能及時反映零件信息的動態更新零件聚類的特點零件的分簇數事先是未知的零件的編碼雖然是用數值表示的，但大部分位并非真正意義上的數值，比如，第五位編碼表示零件的基本形狀，0表示無軸線孔，1表示非加工孔，2表示光滑單向臺階，等等，第十三、十四、十五位的數字大小有數值意義上，但是又不完全就是數值意義，如第十三位表示直徑或長度，0表示小于或等于14mm，1表示在14mm到20mm之間，2表示20mm到58mm之間，等等。聚類結果不一定是多維空間中的一個規則的超球體。但是，它們所屬于的簇應該是相似度與自身最高的簇。零件聚類中不存在某些聚類問題中需要特別處理的噪音或逃離點問題，因為輸入的每條零件信息都是實際存在的零件。Highintra-classsimilarityLowinter-classsimilarity聚類方法的質量還可以由該算法發現隱含模式的能力度量聚類概述動植物的分類證券市場中的投資客戶行為規律WWW-有相同論題的文檔

-聚類的Web日志數據以發現類似的訪問模式圖象處理聚類的應用（1）

A B DC E

聚類的應用（2）土地使用：在土地測量數據庫中，識別相似土地使用的區域市場：

在客戶菜籃中幫助商人發現不同的顧客群，以便他們利用這個知識開發有目的的市場計劃地震研究：

觀察的地震中心應該聚集在大陸斷層周圍聚類技術概述聚類分層聚類分割聚類單鏈接完全鏈接基于連接的算法核心密度估計法模式選擇K-Means算法最大期望算法平方錯誤分割算法給定K值，找到優化所選的分區標準的K個簇k-means(MacQueen’67):每個簇由簇的中心代表k-medoidsorPAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每個簇由簇中的某個點代表

K-Means算法的改進算法K-Modes(Huang’98)：處理非數值型數據K-Prototype:處理非數值型數值型的混合數據EM(Expectationmaximization)PAM(PartitioningAroundMedoids,1987)CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):Randomizedsampling分層算法Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)BIRCHCUREROCKCHAMELEON基于密度的算法基本思想

對于每個簇中的每個對象，給定的半徑ε中的鄰域（稱為ε鄰域）內必須包含至少(MinPts)個對象。 只要鄰域中的數據對象的密度超過某個閾值，這個簇就會加入新的點，不斷的增長。DBSCANOPTICSDENCLUECLIQUE基于模型的方法基于模型的方法假設對于每個簇都有一個適用的模型，并且找到該模型的適當參數基于統計的方法基于神經網絡的方法代表算法COBWEBCLASSITCOMPETITIVELEARNINGAUTOCLASSSOM零件聚類過程零件信息特征選擇或加權相關特征

聚類引擎 處理后分簇結果 的數據

數據預處理聚類聚類優化工藝人員的知識或經驗結果抽象或解釋零件的分層聚類將零件分成單個的簇并不是我們最終的目的。我們而是要通過從粗到細的零件類別的多層次的劃分為零件工藝的制作提供必要的信息。分層聚類方法能對聚類的數目有一個很好的接近因為所構造樹的情況反映了數據的結構。零件相似距離的表示距離一般用來度量兩個物體之間的相似性或不相似性常用的距離有：Minkowski

距離性質：d(i,j)

0d(i,i)

=0d(i,j)

=d(j,i)d(i,j)

d(i,k)

+d(k,j)概念距離A和B之間的歐拉距離明顯小于B和C之間的歐拉距離但是，B、C可以看作比A和B之間更相似。因為B和C屬于同一概念（橢圓）而A（矩形）和B屬于不同的概念。概念上的相似度量可作為最一般的相似度量。基于概念的距離定義屬性Aj的值域取自有限個可以互相區別的符號(稱為概念)組成的域。用Dom(Aj)={a1,a2,...,am}表示屬性Aj的值域。Dl表示有序概念域，表示屬性值取自有序概念集合。如精度分類Dl={‘低精度’、‘中等精度’、‘高精度’、‘超高精度’}；Dc表示無序概念域，表示屬性值取自無序概念集合。如零件的各種細分類別Dc={‘盤、蓋’、‘墊圈片’、‘短圓柱’、‘外齒輪’、‘異形盤套’……}；基于概念的距離定義(2)Dh

表示結構化的概念域，屬性一般是樹狀層次的。父結點的概念是對其子結點概念的歸納和概括。對于每一個概念層，屬性也可以分為有序的和無序的兩種。零件總類回轉體非回轉體輪盤類桿條類環套類板塊類齒輪類座架類數據的規格化處理為統一性和易于處理規格化數值=例如，如果在所有數據中長度的最大值為5000mm，最小值為0mm，那么長度值3000mm一般化表示為

基于概念的距離定義(3)符號屬性的語義距離：

0aik=ajk

dc(aik,ajk)=1aik≠ajk,

i≠j.有序屬性值的語義距離

dl(aik,ajk)=|aik-ajk|零件距離的計算直接利用零件第一位編碼對零件粗分類，語義距離的計算可以在此基礎上計算其他編碼綜合的語義距離定義

①ai1≠aj1

dist(Ci,Cj)=+∞ ②ai1=ai2

dist(Ci,Cj)=1/14dc(ai2,aj2)+…+1/14|ai13–aj13|+1/14|ai14–aj14|

簇的表示人們需要易于理解的簇的直觀描述。數據集合的模糊簇可以獲得模糊規則。這些規則可以用來構造模糊分類器和模糊控制器。在許多涉及到決策的應用場合中，最終的聚類結果必須以簡要的聚類形式表示或描述已達到數據的抽象。可以產生數據壓縮以便以后使用。簇的表示提高了任務決策的效率。比如說，要檢索相關于某一特征的某些零件，查詢結果最終會和簇的中心匹配而不是對應于所有零件的葉結點。這將有助于高效的檢索相關的零件。尤其是在大型的數據庫中，聚類可用來索引。零件總類零件某粗分類別零件某細分類別零件的分層聚類兩種解決方案：分而治之的方法（DivideandConquer）數據被劃分為多個子集，每個子集被分別聚類。接下來是產生整個模式集合聚類的合并步驟。我們將這個方法稱為分而治之的方法。增量聚類方法(IncrementalClustering)

每次只考慮一個零件信息并且將它們分配給已有的簇。這里，一個新的數據項分配給一個簇時不會大幅度的影響已有的簇。聚類過程第一階段：劃分子簇第三階段：動態插入新零件（增量聚類）…第四階段：聚類優化…第二階段：對每個子簇分別建立聚類樹劃分子簇定義：聚類中心，聚類中心、之間的距離Dij，聚類半徑作如下定義：

Dij=||Ci,Cj||(||||使用歐拉距離)子簇劃分流程否則當n的數目大于N的2倍，或兩個聚類中心之間的距離比小于平均聚類中心距離的一半，則產生簇的合并當n的數目小于N的一半，或某個簇的半徑Rk大于平均半徑的2倍，則產生簇的分裂Sk插入最近的簇中

…

…否則……結束建立動態模糊樹確定n個樣本X=（x1,x2,…,xn）上的模糊相似關系；將R按下面計算改造為一個等價矩陣RR=R2R2R2=R4……

直到存在一個k，滿足。//在R是相似矩陣的假設下，已證明必有這樣的k存在，滿足k≤logn

。按聚類水平的大小構造模糊聚類樹停止聚類樹的動態生長（1）添加新零件（1）為防止新結點的半徑影響閾值，選擇和最接近的結點同一個父結點和最相鄰葉結點合并后，新結點的半徑不影響閾值聚類樹的動態生長（2）添加新零件（2）回溯修改各層結點的值某一層的結點分裂聚類樹的動態生長（3）刪除舊零件

舊結點的刪除聚類樹的壓縮和優化最近鄰鏈怎樣找到距離最近的結點？怎樣判定每個子類所屬父類是距其最近的上層結點？……最近鄰鏈第i條結點鏈第1條結點鏈N13N12N11d12d13d11…………d1k-1N1k-1N1kNi3Ni2Ni1di2di3dik-1di1Nik-1Nik…………聚類樹的壓縮…………D>Ti?…………合并后的結點插入最近鄰鏈…………斷裂的結點鏈插入最近鄰鏈1）最近鄰鏈的拆分2）3）聚類樹的優化…………對類中的聚類損失貢獻最大的結點定義：測試各層中對聚類損失貢獻最大的點是否可以屬于其他結點的子結點零件分類樹結論零件的相似性得以充分表達,每個子結點都繼承父結點的特征工藝人員根據樹上每一層的分類編制工藝路線，父層的工藝路線可適用于子層工藝知識存儲于零件樹的各個結點上，已有的經驗得