1、基于聚类方法的CAPP动态零件库构建报告人：金辉主要内容CAPP信息管理智能化的需要已有的零件分类方案分析问题和解决方法聚类技术概述距离等参数设置聚类过程划分子簇聚类树构建聚类树的优化和压缩CAPP的知识信息智能化需要工艺知识的复杂性 工艺知识总结工作量大，高层次的总结难度较大，这是CAPP应用的关键难点之一工艺设计的复杂性 在制造业向计算机集成制造系统(CIMS)的发展转变中，随着CAD/CAM/CAPP集成与并行化的发展，工艺设计变得越来越复杂，寻找一种有效的CAPP 推理策略，成为CAPP研究的重点.自动工艺流程图编码分类专业工艺生成专业工艺审查工艺生成流工艺路线生成工艺路线审查工艺路线
2、批准专业工艺批准工艺生成信息反馈工艺生成流合理分类的前提零件特征知识的合理表达零件特征知识的充分获取已有的零件分类方法视检法生产流程分析法 顺序分枝法聚类分析法编码分类法 零件信息管理中遇到的问题（1）零件本身包含大量的难以精确表述的特征零件之间的相似性不能充分表达，因此不能利用已有的相似零件的工艺信息以往传统的零件数据组织形式已逐渐不能满足要求：不能反映零件之间的特征关系；零件数据库一般只有数据而没有内在规则。零件信息管理中遇到的问题（2）对于多品种生产企业，利用计算机辅助制造时需要收集、分析和处理大量的信息，若按照单一零件来存贮它们的工艺，生产信息，会造成信息的重复和检索的困难。CAPP的
3、系统运行在一个处于持久变化着的应用环境中，这包括所需制造数据的动态性，各决策机制所需知识的动态性，一个不能适应动态数据变化的数据库系统只能导致经验性的决策方式，而阻碍推理过程的智能化。提出的解决方案利用编码输入法的零件信息输入和生产流程的聚类分析方法，克服二者的缺点，着重解决以下问题：1）确定合理的数据结构或零件模型对零件信息进行描述，能让提高计算机辨识零件聚类的准确度，并协助完成聚类工作；2）寻找一种有效的零件在数据库的组织形式和智能聚类策略，在此基础上建立合理的工艺推理过程；3）构造一种有着自学习自适应能力的零件数据库。使得零件在数据库中的排列位置更为合理，反映特征、功能上的内在联系；4）
4、数据库能及时反映零件信息的动态更新 零件聚类的特点零件的分簇数事先是未知的零件的编码虽然是用数值表示的，但大部分位并非真正意义上的数值，比如，第五位编码表示零件的基本形状，0表示无轴线孔，1表示非加工孔，2表示光滑单向台阶，等等，第十三、十四、十五位的数字大小有数值意义上，但是又不完全就是数值意义，如第十三位表示直径或长度，0表示小于或等于14mm，1表示在14mm到20mm之间，2表示20mm到58mm之间，等等。聚类结果不一定是多维空间中的一个规则的超球体。但是，它们所属于的簇应该是相似度与自身最高的簇。零件聚类中不存在某些聚类问题中需要特别处理的噪音或逃离点问题，因为输入的每条零件信息都
5、是实际存在的零件。High intra-class similarityLow inter-class similarity聚类方法的质量还可以由该算法发现隐含模式的能力度量聚类概述 动植物的分类证券市场中的投资客户行为规律 WWW -有相同论题的文档 -聚类的Web日志数据以发现 类似的访问模式图象处理聚类的应用（1）ABDCE聚类的应用（2）土地使用：在土地测量数据库中，识别相似土地使用的区域市场：在客户菜篮中帮助商人发现不同的顾客群，以便他们利用这个知识开发有目的的市场计划地震研究：观察的地震中心应该聚集在大陆断层周围聚类技术概述聚类分层聚类分割聚类单链接完全链接基于连接的算法核心密度估
6、计法模 式选择K-Means算法最 大 期望算法平 方错误分割算法给定K值，找到优化所选的分区标准的K个簇 k-means(MacQueen67):每个簇由簇的中心代表 k-medoids or PAM(Partition around medoids)(Kaufman&Rousseeuw87):每个簇由簇中的某个点代表 K-Means算法的改进算法K-Modes(Huang98)：处理非数值型数据K-Prototype:处理非数值型数值型的混合数据EM(Expectation maximization)PAM(Partitioning Around Medoids,1987)CLARA(Ka
7、ufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):Randomized sampling分层算法Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0agglomerative(AGNES)divisive(DIANA)BIRCH CUREROCKCHAMELEON基于密度的算法基本思想 对于每个簇中的每个对象，给定的半径中的邻域（称为邻域）内必须包含至少(MinPts)个对象。只要邻域中的数据对象的密度超过某个阈值，这个簇就会加入新的点，不断
8、的增长。DBSCANOPTICSDENCLUECLIQUE基于模型的方法基于模型的方法假设对于每个簇都有一个适用的模型，并且找到该模型的适当参数基于统计的方法基于神经网络的方法代表算法COBWEBCLASSITCOMPETITIVE LEARNINGAUTOCLASSSOM零件聚类过程零件信息特征选择或加权相关特征 聚类引擎处理后 分簇结果的数据 数据预处理聚类聚 类优化工艺人员的知识或经验结 果 抽 象或解释零件的分层聚类将零件分成单个的簇并不是我们最终的目的。我们而是要通过从粗到细的零件类别的多层次的划分为零件工艺的制作提供必要的信息。分层聚类方法能对聚类的数目有一个很好的接近因为所构造树
9、的情况反映了数据的结构。零件相似距离的表示距离一般用来度量两个物体之间的相似性或不相似性常用的距离有：Minkowski 距离qqppqqjxixjxixjxixjid)|.|(|),(2211性质：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,
10、a2 ,.,am 表示属性 Aj的值域。Dl表示有序概念域，表示属性值取自有序概念集合。如精度分类 Dl=低精度、中等精度、高精度、超高精度；Dc表示无序概念域，表示属性值取自无序概念集合。如零件的各种细分类别Dc=盘、盖、垫圈片、短圆柱、外齿轮、异形盘套；ljDA cjDA 基于概念的距离定义(2)Dh 表示结构化的概念域，属性一般是树状层次的。父结点的概念是对其子结点概念的归纳和概括。对于每一个概念层，属性也可以分为有序的和无序的两种。零件总类回转体非回转体轮盘类杆条类环套类板块类齿轮类座架类数据的规格化处理为统一性和易于处理规格化数值=例如，如果在所有数据中长度的最大值为5000mm，最
11、小值为0mm，那么长度值3000mm一般化表示为MINMAXMIN属性值6.00500003000)(iaN基于概念的距离定义(3)符号属性的语义距离：0 aik=ajk dc(aik,ajk)=1 aik ajk,ij.有序属性值的语义距离 dl(aik,ajk)=|aik-ajk|零件距离的计算直接利用零件第一位编码对零件粗分类，语义距离的计算可以在此基础上计算其他编码综合的语义距离定义 ai1aj1 dist(Ci,Cj)=+ai1=ai2 dist(Ci,Cj)=1/14dc(ai2,aj2)+1/14|ai13aj13|+1/14|ai14 aj14|簇的表示人们需要易于理解的簇的直
12、观描述。数据集合的模糊簇可以获得模糊规则。这些规则可以用来构造模糊分类器和模糊控制器。在许多涉及到决策的应用场合中，最终的聚类结果必须以简要的聚类形式表示或描述已达到数据的抽象。可以产生数据压缩以便以后使用。簇的表示提高了任务决策的效率。比如说，要检索相关于某一特征的某些零件，查询结果最终会和簇的中心匹配而不是对应于所有零件的叶结点。这将有助于高效的检索相关的零件。尤其是在大型的数据库中，聚类可用来索引。零件总类零件某粗分类别零件某细分类别零件的分层聚类两种解决方案：分而治之的方法（Divide and Conquer）数据被划分为多个子集，每个子集被分别聚类。接下来是产生整个模式集合聚类的合
13、并步骤。我们将这个方法称为分而治之的方法。增量聚类方法(Incremental Clustering)每次只考虑一个零件信息并且将它们分配给已有的簇。这里，一个新的数据项分配给一个簇时不会大幅度的影响已有的簇。聚类过程第一阶段：划分子簇第三阶段：动态插入新零件（增量聚类）第四阶段：聚类优化第二阶段：对每个子簇分别建立聚类树划分子簇定义：聚类中心 ，聚类中心 、之间的距离Dij，聚类半径 作如下定义：Dij=|Ci,Cj|(|使用欧拉距离)iCiCjCiRiSSSCii.21)1(211 nnDDninijijijiCSRikkki122)(子簇划分流程否则当n的数目大于N的2倍，或两个聚类中心
14、之间的距离比小于平均聚类中心距离的一半，则产生簇的合并当n的数目小于N的一半，或某个簇的半径Rk大于平均半径的2倍，则产生簇的分裂Sk插入最近的簇中否则结束建立动态模糊树确定n个样本X=（x1,x2,xn）上的模糊相似关系；将R按下面计算改造为一个等价矩阵R R=R2R2 R2=R4 直到存在一个k，满足 。/在R是相似矩阵的假设下，已证明必有这样的k存在，满足klogn。按聚类水平的大小构造模糊聚类树停止 1222kkkRRR 122kkRR聚类树的动态生长（1）添加新零件（1）为防止新结点的半径影响阈值，选择和最接近的结点同一个父结点和最相邻叶结点合并后，新结点的半径不影响阈值聚类树的动态
15、生长（2）添加新零件（2）回溯修改各层结点的值 某一层的结点分裂聚类树的动态生长（3）删除旧零件 旧结点的删除聚类树的压缩和优化最近邻链怎样找到距离最近的结点？怎样判定每个子类所属父类是距其最近的上层结点？最近邻链第i条结点链第1条结点链N13N12N11d12d13d11 d1k-1N1k-1N1kNi3Ni2Ni1di2di3dik-1di1Nik-1Nik 聚类树的压缩 DTi?合并后的结点插入最近邻链 断裂的结点链插入最近邻链1）最近邻链的拆分2）3）聚类树的优化 对类中的聚类损失贡献最大的结点定义：测试各层中对聚类损失贡献最大的点是否可以属于其他结点的子结点零件分类树结论零件的相似性
16、得以充分表达,每个子结点都继承父结点的特征工艺人员根据树上每一层的分类编制工艺路线，父层的工艺路线可适用于子层工艺知识存储于零件树的各个结点上，已有的经验得以很好的利用，最终随着树的增长，能识别的零件种类不断也增长减少工艺人员的重复劳动为零件的虚拟制造提供方便需要改进的地方零件特征的提取，可以考虑直接从CAD图的零件表示中提取特征，这样可以减少繁琐、费时的零件二次输入的过程，便于建立CAD、CAPP和CAM的统一模型；相似度的计算，对于不同的零件信息输入方式，应该有不同的相似度的计算方式；各个码位对零件特征的刻划程度不同,因此对零件分组的影响也不尽相同,而在模糊数学的运算中并没有考虑这一因素
17、需要改进的地方簇的表示聚类树的优化和压缩算法 二维图形中的聚类点p聚类技术的发展前景聚类技术是数据挖掘技术的一种，随着计算机应用的越来越广泛，每年都要积累大量的数据，运用数据挖掘技术在这些数据当中我们可以找出“金子”来。据国外专家预测，在今后的510年内，随着数据量的日益积累以及计算机的广泛应用，数据挖掘将在中国形成一个产业。2000年7月IDC发布了关于信息存取工具市场的报告，其中估计1999年的数据挖掘的市场大概是7.5亿美元，估计在下个5年内市场的年增长率（Compound Annual Growth Rate）为32.4%，其中亚太地区为26.6%，并且预测此市场在2002年时会达到22亿美元。Hope you to enjoy my report!
