模糊分類樹在CAPP零件分組中的應(yīng)用探討課件

基于聚類方法的CAPP動(dòng)態(tài)零件庫(kù)構(gòu)建報(bào)告人：金輝基于聚類方法的CAPP動(dòng)態(tài)零件庫(kù)構(gòu)建報(bào)告人：金輝1主要內(nèi)容CAPP信息管理智能化的需要已有的零件分類方案分析問題和解決方法聚類技術(shù)概述距離等參數(shù)設(shè)置聚類過程劃分子簇聚類樹構(gòu)建聚類樹的優(yōu)化和壓縮主要內(nèi)容CAPP信息管理智能化的需要2CAPP的知識(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).CAPP的知識(shí)信息智能化需要工藝知識(shí)的復(fù)雜性3自動(dòng)工藝流程圖編碼分類專業(yè)工藝生成專業(yè)工藝審查工藝生成流工藝路線生成工藝路線審查工藝路線批準(zhǔn)專業(yè)工藝批準(zhǔn)工藝生成信息反饋工藝生成流自動(dòng)工藝流程圖編碼專業(yè)工藝生成專業(yè)工藝審查工藝生成流工藝路線4合理分類的前提零件特征知識(shí)的合理表達(dá)零件特征知識(shí)的充分獲取合理分類的前提零件特征知識(shí)的合理表達(dá)5已有的零件分類方法視檢法生產(chǎn)流程分析法順序分枝法聚類分析法編碼分類法已有的零件分類方法視檢法6零件信息管理中遇到的問題（1）零件本身包含大量的難以精確表述的特征零件之間的相似性不能充分表達(dá)，因此不能利用已有的相似零件的工藝信息以往傳統(tǒng)的零件數(shù)據(jù)組織形式已逐漸不能滿足要求：不能反映零件之間的特征關(guān)系；零件數(shù)據(jù)庫(kù)一般只有數(shù)據(jù)而沒有內(nèi)在規(guī)則。零件信息管理中遇到的問題（1）零件本身包含大量的難以精確表述7零件信息管理中遇到的問題（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)性的決策方式，而阻礙推理過程的智能化。零件信息管理中遇到的問題（2）對(duì)于多品種生產(chǎn)企業(yè)，利用計(jì)算機(jī)8提出的解決方案利用編碼輸入法的零件信息輸入和生產(chǎn)流程的聚類分析方法，克服二者的缺點(diǎn)，著重解決以下問題：1）確定合理的數(shù)據(jù)結(jié)構(gòu)或零件模型對(duì)零件信息進(jìn)行描述，能讓提高計(jì)算機(jī)辨識(shí)零件聚類的準(zhǔn)確度，并協(xié)助完成聚類工作；2）尋找一種有效的零件在數(shù)據(jù)庫(kù)的組織形式和智能聚類策略，在此基礎(chǔ)上建立合理的工藝推理過程；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)更新提出的解決方案利用編碼輸入法的零件信息輸入和生產(chǎn)流程的聚類分9零件聚類的特點(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)該是相似度與自身最高的簇。零件聚類中不存在某些聚類問題中需要特別處理的噪音或逃離點(diǎn)問題，因?yàn)檩斎氲拿織l零件信息都是實(shí)際存在的零件。零件聚類的特點(diǎn)零件的分簇?cái)?shù)事先是未知的10Highintra-classsimilarityLowinter-classsimilarity聚類方法的質(zhì)量還可以由該算法發(fā)現(xiàn)隱含模式的能力度量聚類概述Highintra-classsimilarity聚類概11動(dòng)植物的分類證券市場(chǎng)中的投資客戶行為規(guī)律WWW-有相同論題的文檔-聚類的Web日志數(shù)據(jù)以發(fā)現(xiàn)類似的訪問模式圖象處理聚類的應(yīng)用（1）

A B DC E

動(dòng)植物的分類聚類的應(yīng)用（1） A12聚類的應(yīng)用（2）土地使用：在土地測(cè)量數(shù)據(jù)庫(kù)中，識(shí)別相似土地使用的區(qū)域市場(chǎng)：在客戶菜籃中幫助商人發(fā)現(xiàn)不同的顧客群，以便他們利用這個(gè)知識(shí)開發(fā)有目的的市場(chǎng)計(jì)劃地震研究：觀察的地震中心應(yīng)該聚集在大陸斷層周圍聚類的應(yīng)用（2）土地使用：在土地測(cè)量數(shù)據(jù)庫(kù)中，識(shí)別相似土地使13聚類技術(shù)概述聚類分層聚類分割聚類單鏈接完全鏈接基于連接的算法核心密度估計(jì)法模式選擇K-Means算法最大期望算法平方錯(cuò)誤聚類技術(shù)概述聚類分層聚類分割聚類單鏈接完全鏈接基于連接的算法14分割算法給定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值，找到優(yōu)化所選的分區(qū)標(biāo)準(zhǔn)的K個(gè)簇15K-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):RandomizedsamplingK-Means算法的改進(jìn)算法K-Modes(Huang’916分層算法Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)BIRCHCUREROCKCHAMELEON分層算法Step0Step1Step2Step3St17基于密度的算法基本思想

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

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

數(shù)據(jù)預(yù)處理聚類聚類優(yōu)化工藝人員的知識(shí)或經(jīng)驗(yàn)結(jié)果抽象或解釋零件聚類過程零件信息特征選擇或加權(quán)相關(guān)特征 20零件的分層聚類將零件分成單個(gè)的簇并不是我們最終的目的。我們而是要通過從粗到細(xì)的零件類別的多層次的劃分為零件工藝的制作提供必要的信息。分層聚類方法能對(duì)聚類的數(shù)目有一個(gè)很好的接近因?yàn)樗鶚?gòu)造樹的情況反映了數(shù)據(jù)的結(jié)構(gòu)。零件的分層聚類將零件分成單個(gè)的簇并不是我們最終的目的。我們而21零件相似距離的表示距離一般用來(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)零件相似距離的表示距離一般用來(lái)度量?jī)蓚€(gè)物體之間的相似性或不相22概念距離A和B之間的歐拉距離明顯小于B和C之間的歐拉距離但是，B、C可以看作比A和B之間更相似。因?yàn)锽和C屬于同一概念（橢圓）而A（矩形）和B屬于不同的概念。概念上的相似度量可作為最一般的相似度量。概念距離A和B之間的歐拉距離明顯小于B和C之間的歐拉距離但是23基于概念的距離定義屬性Aj的值域取自有限個(gè)可以互相區(qū)別的符號(hào)(稱為概念)組成的域。用Dom(Aj)={a1,a2,...,am}表示屬性Aj的值域。Dl表示有序概念域，表示屬性值取自有序概念集合。如精度分類Dl={‘低精度’、‘中等精度’、‘高精度’、‘超高精度’}；Dc表示無(wú)序概念域，表示屬性值取自無(wú)序概念集合。如零件的各種細(xì)分類別Dc={‘盤、蓋’、‘墊圈片’、‘短圓柱’、‘外齒輪’、‘異形盤套’……}；基于概念的距離定義屬性Aj的值域取自有限個(gè)可以互相區(qū)別的符24基于概念的距離定義(2)Dh表示結(jié)構(gòu)化的概念域，屬性一般是樹狀層次的。父結(jié)點(diǎn)的概念是對(duì)其子結(jié)點(diǎn)概念的歸納和概括。對(duì)于每一個(gè)概念層，屬性也可以分為有序的和無(wú)序的兩種。零件總類回轉(zhuǎn)體非回轉(zhuǎn)體輪盤類桿條類環(huán)套類板塊類齒輪類座架類基于概念的距離定義(2)Dh表示結(jié)構(gòu)化的概念域，屬性一般25數(shù)據(jù)的規(guī)格化處理為統(tǒng)一性和易于處理規(guī)格化數(shù)值=例如，如果在所有數(shù)據(jù)中長(zhǎng)度的最大值為5000mm，最小值為0mm，那么長(zhǎng)度值3000mm一般化表示為

數(shù)據(jù)的規(guī)格化處理為統(tǒng)一性和易于處理26基于概念的距離定義(3)符號(hào)屬性的語(yǔ)義距離： 0aik=ajkdc(aik,ajk)=1aik≠ajk,i≠j.有序?qū)傩灾档恼Z(yǔ)義距離 dl(aik,ajk)=|aik-ajk|基于概念的距離定義(3)符號(hào)屬性的語(yǔ)義距離：27零件距離的計(jì)算直接利用零件第一位編碼對(duì)零件粗分類，語(yǔ)義距離的計(jì)算可以在此基礎(chǔ)上計(jì)算其他編碼綜合的語(yǔ)義距離定義 ①ai1≠aj1dist(Ci,Cj)=+∞ ②ai1=ai2

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

零件距離的計(jì)算直接利用零件第一位編碼對(duì)零件粗分類，語(yǔ)義距離的28簇的表示人們需要易于理解的簇的直觀描述。數(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ù)壓縮以便以后使用。簇的表示人們需要易于理解的簇的直觀描述。數(shù)據(jù)集合的模糊簇可以29簇的表示提高了任務(wù)決策的效率。比如說(shuō)，要檢索相關(guān)于某一特征的某些零件，查詢結(jié)果最終會(huì)和簇的中心匹配而不是對(duì)應(yīng)于所有零件的葉結(jié)點(diǎn)。這將有助于高效的檢索相關(guān)的零件。尤其是在大型的數(shù)據(jù)庫(kù)中，聚類可用來(lái)索引。零件總類零件某粗分類別零件某細(xì)分類別簇的表示提高了任務(wù)決策的效率。比如說(shuō)，要檢索相關(guān)于某一特征的30零件的分層聚類兩種解決方案：分而治之的方法（DivideandConquer）數(shù)據(jù)被劃分為多個(gè)子集，每個(gè)子集被分別聚類。接下來(lái)是產(chǎn)生整個(gè)模式集合聚類的合并步驟。我們將這個(gè)方法稱為分而治之的方法。增量聚類方法(IncrementalClustering)每次只考慮一個(gè)零件信息并且將它們分配給已有的簇。這里，一個(gè)新的數(shù)據(jù)項(xiàng)分配給一個(gè)簇時(shí)不會(huì)大幅度的影響已有的簇。零件的分層聚類兩種解決方案：31聚類過程第一階段：劃分子簇第三階段：動(dòng)態(tài)插入新零件（增量聚類）…第四階段：聚類優(yōu)化…第二階段：對(duì)每個(gè)子簇分別建立聚類樹聚類過程第一階段：劃分子簇第三階段：動(dòng)態(tài)插入新零件（增量聚類32劃分子簇定義：聚類中心，聚類中心、之間的距離Dij，聚類半徑作如下定義： Dij=||Ci,Cj||(||||使用歐拉距離)劃分子簇定義：聚類中心，聚類中心、之33子簇劃分流程否則當(dāng)n的數(shù)目大于N的2倍，或兩個(gè)聚類中心之間的距離比小于平均聚類中心距離的一半，則產(chǎn)生簇的合并當(dāng)n的數(shù)目小于N的一半，或某個(gè)簇的半徑Rk大于平均半徑的2倍，則產(chǎn)生簇的分裂Sk插入最近的簇中

…

…否則……結(jié)束子簇劃分流程否則當(dāng)n的數(shù)目大于N的2倍，或兩個(gè)聚類中心之間的34建立動(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)模糊樹確定n個(gè)樣本X=（x1,x2,…,xn）上的模35聚類樹的動(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)（1）添加新零件為防止新結(jié)點(diǎn)的半徑影響閾值，36聚類樹的動(dòng)態(tài)生長(zhǎng)（2）添加新零件（2）回溯修改各層結(jié)點(diǎn)的值某一層的結(jié)點(diǎn)分裂聚類樹的動(dòng)態(tài)生長(zhǎng)（2）添加新零件某一層的結(jié)點(diǎn)分裂37聚類樹的動(dòng)態(tài)生長(zhǎng)（3）刪除舊零件舊結(jié)點(diǎn)的刪除聚類樹的動(dòng)態(tài)生長(zhǎng)（3）刪除舊零件舊結(jié)點(diǎn)的刪除38聚類樹的壓縮和優(yōu)化最近鄰鏈怎樣找到距離最近的結(jié)點(diǎn)？怎樣判定每個(gè)子類所屬父類是距其最近的上層結(jié)點(diǎn)？聚類樹的壓縮和優(yōu)化最近鄰鏈怎樣找到距離最近的結(jié)點(diǎn)？怎樣判定每39……最近鄰鏈第i條結(jié)點(diǎn)鏈第1條結(jié)點(diǎn)鏈N13N12N11d12d13d11…………d1k-1N1k-1N1kNi3Ni2Ni1di2di3dik-1di1Nik-1Nik………………最近鄰鏈第i條結(jié)點(diǎn)鏈第1條結(jié)點(diǎn)鏈N13N12N11d1240聚類樹的壓縮…………D>Ti?…………合并后的結(jié)點(diǎn)插入最近鄰鏈…………斷裂的結(jié)點(diǎn)鏈插入最近鄰鏈1）最近鄰鏈的拆分2）3）聚類樹的壓縮…………D>Ti?…………合并后的結(jié)點(diǎn)插入41聚類樹的優(yōu)化…………對(duì)類中的聚類損失貢獻(xiàn)最大的結(jié)點(diǎn)定義：測(cè)試各層中對(duì)聚類損失貢獻(xiàn)最大的點(diǎn)是否可以屬于其他結(jié)點(diǎn)的子結(jié)點(diǎn)聚類樹的優(yōu)化…………對(duì)類中的聚類損失貢獻(xiàn)最大的結(jié)點(diǎn)定義：測(cè)42零件分類樹零件分類樹43結(jié)論零件的相似性得以充分表達(dá),每個(gè)子結(jié)點(diǎn)都繼承父結(jié)點(diǎn)的特征工藝人員根據(jù)樹上每一層的分類編制工藝路線，父層的工藝路線可適用于子層工藝知識(shí)存儲(chǔ)于零件樹的各個(gè)結(jié)點(diǎn)上，已有的經(jīng)驗(yàn)得以很好的利用，最終隨著樹的增長(zhǎng)，能識(shí)別的零件種類不斷也增長(zhǎng)減少工藝人員的重復(fù)勞動(dòng)為零件的虛擬制造提供方便結(jié)論零件的相似性得以充分表達(dá),每個(gè)子結(jié)點(diǎn)都繼承父結(jié)點(diǎn)的特征44需要改進(jìn)的地方零件特征的提取，可以考慮直接從CAD圖的零件表示中提取特征，這樣可以減少繁瑣、費(fèi)時(shí)的零件二次輸入的過程，便于建立CAD、CAPP和CAM的統(tǒng)一模型；相似度的計(jì)算，對(duì)于不同的零件信息輸入方式，應(yīng)該有不同的相似度的計(jì)算方式；各個(gè)碼位對(duì)零件特征的刻劃程度不同,因此對(duì)零件分組的影響也不盡相同,而在模糊數(shù)學(xué)的運(yùn)算中并沒有考慮這一因素需要改進(jìn)的地方零件特征的提取，可以考慮直接從CAD圖的零件表45需要改進(jìn)的地方簇的表示聚類樹的優(yōu)化和壓縮算法二維圖形中的聚類點(diǎn)p需要改進(jìn)的地方簇的表示二維圖形中的聚類點(diǎn)p46聚類技術(shù)的發(fā)展前景聚類技術(shù)是數(shù)據(jù)挖掘技術(shù)的一種，隨著計(jì)算機(jī)應(yīng)用的越來(lái)越廣泛，每年都要積累大量的數(shù)據(jù)，運(yùn)用數(shù)據(jù)挖掘技術(shù)在這些數(shù)據(jù)當(dāng)中我們可以找出“金子”來(lái)。據(jù)國(guó)外專家預(yù)測(cè)，在今后的5—10年內(nèi)，隨著數(shù)據(jù)量的日益積累以及計(jì)算機(jī)的廣泛應(yīng)用，數(shù)據(jù)挖掘?qū)⒃谥袊?guó)形成一個(gè)產(chǎn)業(yè)。2000年7月IDC發(fā)布了關(guān)于信息存取工具市場(chǎng)的報(bào)告，其中估計(jì)1999年的數(shù)據(jù)挖掘的市場(chǎng)大概是7.5億美元，估計(jì)在下個(gè)5年內(nèi)市場(chǎng)的年增長(zhǎng)率（CompoundAnnualGrowthRate）為32.4%，其中亞太地區(qū)為26.6%，并且預(yù)測(cè)此市場(chǎng)在2002年時(shí)會(huì)達(dá)到22億美元。聚類技術(shù)的發(fā)展前景聚類技術(shù)是數(shù)據(jù)挖掘技術(shù)的一種，隨著計(jì)算機(jī)應(yīng)47Hopeyoutoenjoymyreport!Hopeyoutoenjoymyreport!48基于聚類方法的CAPP動(dòng)態(tài)零件庫(kù)構(gòu)建報(bào)告人：金輝基于聚類方法的CAPP動(dòng)態(tài)零件庫(kù)構(gòu)建報(bào)告人：金輝49主要內(nèi)容CAPP信息管理智能化的需要已有的零件分類方案分析問題和解決方法聚類技術(shù)概述距離等參數(shù)設(shè)置聚類過程劃分子簇聚類樹構(gòu)建聚類樹的優(yōu)化和壓縮主要內(nèi)容CAPP信息管理智能化的需要50CAPP的知識(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).CAPP的知識(shí)信息智能化需要工藝知識(shí)的復(fù)雜性51自動(dòng)工藝流程圖編碼分類專業(yè)工藝生成專業(yè)工藝審查工藝生成流工藝路線生成工藝路線審查工藝路線批準(zhǔn)專業(yè)工藝批準(zhǔn)工藝生成信息反饋工藝生成流自動(dòng)工藝流程圖編碼專業(yè)工藝生成專業(yè)工藝審查工藝生成流工藝路線52合理分類的前提零件特征知識(shí)的合理表達(dá)零件特征知識(shí)的充分獲取合理分類的前提零件特征知識(shí)的合理表達(dá)53已有的零件分類方法視檢法生產(chǎn)流程分析法順序分枝法聚類分析法編碼分類法已有的零件分類方法視檢法54零件信息管理中遇到的問題（1）零件本身包含大量的難以精確表述的特征零件之間的相似性不能充分表達(dá)，因此不能利用已有的相似零件的工藝信息以往傳統(tǒng)的零件數(shù)據(jù)組織形式已逐漸不能滿足要求：不能反映零件之間的特征關(guān)系；零件數(shù)據(jù)庫(kù)一般只有數(shù)據(jù)而沒有內(nèi)在規(guī)則。零件信息管理中遇到的問題（1）零件本身包含大量的難以精確表述55零件信息管理中遇到的問題（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)性的決策方式，而阻礙推理過程的智能化。零件信息管理中遇到的問題（2）對(duì)于多品種生產(chǎn)企業(yè)，利用計(jì)算機(jī)56提出的解決方案利用編碼輸入法的零件信息輸入和生產(chǎn)流程的聚類分析方法，克服二者的缺點(diǎn)，著重解決以下問題：1）確定合理的數(shù)據(jù)結(jié)構(gòu)或零件模型對(duì)零件信息進(jìn)行描述，能讓提高計(jì)算機(jī)辨識(shí)零件聚類的準(zhǔn)確度，并協(xié)助完成聚類工作；2）尋找一種有效的零件在數(shù)據(jù)庫(kù)的組織形式和智能聚類策略，在此基礎(chǔ)上建立合理的工藝推理過程；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)更新提出的解決方案利用編碼輸入法的零件信息輸入和生產(chǎn)流程的聚類分57零件聚類的特點(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)該是相似度與自身最高的簇。零件聚類中不存在某些聚類問題中需要特別處理的噪音或逃離點(diǎn)問題，因?yàn)檩斎氲拿織l零件信息都是實(shí)際存在的零件。零件聚類的特點(diǎn)零件的分簇?cái)?shù)事先是未知的58Highintra-classsimilarityLowinter-classsimilarity聚類方法的質(zhì)量還可以由該算法發(fā)現(xiàn)隱含模式的能力度量聚類概述Highintra-classsimilarity聚類概59動(dòng)植物的分類證券市場(chǎng)中的投資客戶行為規(guī)律WWW-有相同論題的文檔-聚類的Web日志數(shù)據(jù)以發(fā)現(xiàn)類似的訪問模式圖象處理聚類的應(yīng)用（1）

A B DC E

動(dòng)植物的分類聚類的應(yīng)用（1） A60聚類的應(yīng)用（2）土地使用：在土地測(cè)量數(shù)據(jù)庫(kù)中，識(shí)別相似土地使用的區(qū)域市場(chǎng)：在客戶菜籃中幫助商人發(fā)現(xiàn)不同的顧客群，以便他們利用這個(gè)知識(shí)開發(fā)有目的的市場(chǎng)計(jì)劃地震研究：觀察的地震中心應(yīng)該聚集在大陸斷層周圍聚類的應(yīng)用（2）土地使用：在土地測(cè)量數(shù)據(jù)庫(kù)中，識(shí)別相似土地使61聚類技術(shù)概述聚類分層聚類分割聚類單鏈接完全鏈接基于連接的算法核心密度估計(jì)法模式選擇K-Means算法最大期望算法平方錯(cuò)誤聚類技術(shù)概述聚類分層聚類分割聚類單鏈接完全鏈接基于連接的算法62分割算法給定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值，找到優(yōu)化所選的分區(qū)標(biāo)準(zhǔn)的K個(gè)簇63K-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):RandomizedsamplingK-Means算法的改進(jìn)算法K-Modes(Huang’964分層算法Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)BIRCHCUREROCKCHAMELEON分層算法Step0Step1Step2Step3St65基于密度的算法基本思想

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

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

數(shù)據(jù)預(yù)處理聚類聚類優(yōu)化工藝人員的知識(shí)或經(jīng)驗(yàn)結(jié)果抽象或解釋零件聚類過程零件信息特征選擇或加權(quán)相關(guān)特征 68零件的分層聚類將零件分成單個(gè)的簇并不是我們最終的目的。我們而是要通過從粗到細(xì)的零件類別的多層次的劃分為零件工藝的制作提供必要的信息。分層聚類方法能對(duì)聚類的數(shù)目有一個(gè)很好的接近因?yàn)樗鶚?gòu)造樹的情況反映了數(shù)據(jù)的結(jié)構(gòu)。零件的分層聚類將零件分成單個(gè)的簇并不是我們最終的目的。我們而69零件相似距離的表示距離一般用來(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)零件相似距離的表示距離一般用來(lái)度量?jī)蓚€(gè)物體之間的相似性或不相70概念距離A和B之間的歐拉距離明顯小于B和C之間的歐拉距離但是，B、C可以看作比A和B之間更相似。因?yàn)锽和C屬于同一概念（橢圓）而A（矩形）和B屬于不同的概念。概念上的相似度量可作為最一般的相似度量。概念距離A和B之間的歐拉距離明顯小于B和C之間的歐拉距離但是71基于概念的距離定義屬性Aj的值域取自有限個(gè)可以互相區(qū)別的符號(hào)(稱為概念)組成的域。用Dom(Aj)={a1,a2,...,am}表示屬性Aj的值域。Dl表示有序概念域，表示屬性值取自有序概念集合。如精度分類Dl={‘低精度’、‘中等精度’、‘高精度’、‘超高精度’}；Dc表示無(wú)序概念域，表示屬性值取自無(wú)序概念集合。如零件的各種細(xì)分類別Dc={‘盤、蓋’、‘墊圈片’、‘短圓柱’、‘外齒輪’、‘異形盤套’……}；基于概念的距離定義屬性Aj的值域取自有限個(gè)可以互相區(qū)別的符72基于概念的距離定義(2)Dh表示結(jié)構(gòu)化的概念域，屬性一般是樹狀層次的。父結(jié)點(diǎn)的概念是對(duì)其子結(jié)點(diǎn)概念的歸納和概括。對(duì)于每一個(gè)概念層，屬性也可以分為有序的和無(wú)序的兩種。零件總類回轉(zhuǎn)體非回轉(zhuǎn)體輪盤類桿條類環(huán)套類板塊類齒輪類座架類基于概念的距離定義(2)Dh表示結(jié)構(gòu)化的概念域，屬性一般73數(shù)據(jù)的規(guī)格化處理為統(tǒng)一性和易于處理規(guī)格化數(shù)值=例如，如果在所有數(shù)據(jù)中長(zhǎng)度的最大值為5000mm，最小值為0mm，那么長(zhǎng)度值3000mm一般化表示為

數(shù)據(jù)的規(guī)格化處理為統(tǒng)一性和易于處理74基于概念的距離定義(3)符號(hào)屬性的語(yǔ)義距離： 0aik=ajkdc(aik,ajk)=1aik≠ajk,i≠j.有序?qū)傩灾档恼Z(yǔ)義距離 dl(aik,ajk)=|aik-ajk|基于概念的距離定義(3)符號(hào)屬性的語(yǔ)義距離：75零件距離的計(jì)算直接利用零件第一位編碼對(duì)零件粗分類，語(yǔ)義距離的計(jì)算可以在此基礎(chǔ)上計(jì)算其他編碼綜合的語(yǔ)義距離定義 ①ai1≠aj1dist(Ci,Cj)=+∞ ②ai1=ai2

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

零件距離的計(jì)算直接利用零件第一位編碼對(duì)零件粗分類，語(yǔ)義距離的76簇的表示人們需要易于理解的簇的直觀描述。數(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ù)壓縮以便以后使用。簇的表示人們需要易于理解的簇的直觀描述。數(shù)據(jù)集合的模糊簇可以77簇的表示提高了任務(wù)決策的效率。比如說(shuō)，要檢索相關(guān)于某一特征的某些零件，查詢結(jié)果最終會(huì)和簇的中心匹配而不是對(duì)應(yīng)于所有零件的葉結(jié)點(diǎn)。這將有助于高效的檢索相關(guān)的零件。尤其是在大型的數(shù)據(jù)庫(kù)中，聚類可用來(lái)索引。零件總類零件某粗分類別零件某細(xì)分類別簇的表示提高了任務(wù)決策的效率。比如說(shuō)，要檢索相關(guān)于某一特征的78零件的分層聚類兩種解決方案：分而治之的方法（DivideandConquer）數(shù)據(jù)被劃分為多個(gè)子集，每個(gè)子集被分別聚類。接下來(lái)是產(chǎn)生整個(gè)模式集合聚類的合并步驟。我們將這個(gè)方法稱為分而治之的方法。增量聚類方法(IncrementalClustering)每次只考慮一個(gè)零件信息并且將它們分配給已有的簇。這里，一個(gè)新的數(shù)據(jù)項(xiàng)分配給一個(gè)簇時(shí)不會(huì)大幅度的影響已有的簇。零件的分層聚類兩種解決方案：79聚類過程第一階段：劃分子簇第三階段：動(dòng)態(tài)插入新零件（增量聚類）…第四階段：聚類優(yōu)化…第二階段：對(duì)每個(gè)子簇分別建立聚類樹聚類過程第一階段：劃分子簇第三階段：動(dòng)態(tài)插入新零件（增量聚類80劃分子簇定義：聚類中心，聚類中心、之間的距離Dij，聚類半徑作如下定義： Dij=||Ci,Cj||(||||使用歐拉距離)劃分子簇定義：聚類中心，聚類中心、之81子簇劃分流程否則當(dāng)n的數(shù)目大于N的2倍，或兩個(gè)聚類中心之間的距離比小于平均聚類中心距離的一半，則產(chǎn)生簇的合并當(dāng)n的數(shù)目小于N的一半，或某個(gè)簇的半徑Rk大于平均半徑的2倍，則產(chǎn)生簇的分裂Sk插入最近的簇中

…

…否則……結(jié)束子簇劃分流程否則當(dāng)n的數(shù)目大于N的2倍，或兩個(gè)聚類中心之間的82建立動(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)模糊樹確定n個(gè)樣本X=（x1,x2,…,xn）上的模83聚類樹的動(dòng)態(tài)生長(zhǎng)（1）添加新零件（1）為防止新結(jié)點(diǎn)的半徑影響閾值，選擇和最接近的結(jié)點(diǎn)同一個(gè)父結(jié)點(diǎn)和最相鄰葉結(jié)點(diǎn)合并后