基于聚類方法地CAPP動態(tài)零件庫構(gòu)建

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

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

-聚類的Web日志數(shù)據(jù)以發(fā)現(xiàn)類似的訪問模式圖象處理聚類的應(yīng)用（1）

A B DC E

聚類的應(yīng)用（2）土地使用：在土地測量數(shù)據(jù)庫中，識別相似土地使用的區(qū)域市場：

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

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

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

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

聚類引擎 處理后分簇結(jié)果 的數(shù)據(jù)

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

距離性質(zhì)：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屬于不同的概念。概念上的相似度量可作為最一般的相似度量?；诟拍畹木嚯x定義屬性Aj的值域取自有限個可以互相區(qū)別的符號(稱為概念)組成的域。用Dom(Aj)={a1,a2,...,am}表示屬性Aj的值域。Dl表示有序概念域，表示屬性值取自有序概念集合。如精度分類Dl={‘低精度’、‘中等精度’、‘高精度’、‘超高精度’}；Dc表示無序概念域，表示屬性值取自無序概念集合。如零件的各種細(xì)分類別Dc={‘盤、蓋’、‘墊圈片’、‘短圓柱’、‘外齒輪’、‘異形盤套’……}；基于概念的距離定義(2)Dh

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

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

0aik=ajk

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

i≠j.有序?qū)傩灾档恼Z義距離

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

①ai1≠aj1

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

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

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

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

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

…

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

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

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

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