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

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

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

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

A B DC E

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

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

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

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基于密度的算法基本思想

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

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

數(shù)據(jù)預(yù)處理聚類聚類優(yōu)化工藝人員的知識(shí)或經(jīng)驗(yàn)結(jié)果抽象或解釋零件的分層聚類將零件分成單個(gè)的簇并不是我們最終的目的。我們而是要通過(guò)從粗到細(xì)的零件類別的多層次的劃分為零件工藝的制作提供必要的信息。分層聚類方法能對(duì)聚類的數(shù)目有一個(gè)很好的接近因?yàn)樗鶚?gòu)造樹的情況反映了數(shù)據(jù)的結(jié)構(gòu)。零件相似距離的表示距離一般用來(lái)度量?jī)蓚€(gè)物體之間的相似性或不相似性常用的距離有：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之間更相似。因?yàn)锽和C屬于同一概念（橢圓）而A（矩形）和B屬于不同的概念。概念上的相似度量可作為最一般的相似度量?；诟拍畹木嚯x定義屬性Aj的值域取自有限個(gè)可以互相區(qū)別的符號(hào)(稱為概念)組成的域。用Dom(Aj)={a1,a2,...,am}表示屬性Aj的值域。Dl表示有序概念域，表示屬性值取自有序概念集合。如精度分類Dl={‘低精度’、‘中等精度’、‘高精度’、‘超高精度’}；Dc表示無(wú)序概念域，表示屬性值取自無(wú)序概念集合。如零件的各種細(xì)分類別Dc={‘盤、蓋’、‘墊圈片’、‘短圓柱’、‘外齒輪’、‘異形盤套’……}；基于概念的距離定義(2)Dh

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

基于概念的距離定義(3)符號(hào)屬性的語(yǔ)義距離：

0aik=ajk

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

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

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

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

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

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

…

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

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

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

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