一个基于聚类分析的发现方法1

Shunuan Liu & Zhenming Zhang & Xitian Tian

摘要：典型过程路径实是编制过程路径的一个样本。它是一类编制知识的过程。为了在编制数据库的过程中从计算机半自动过程编制中（CAPP）发现典型过程路径,在数据库中知识发现被应用.数据选择过程,剔除过程和转换过程都被用于数据优化过程.聚类分析被采用于挖掘典型过程路径的运算法则.描述此过程路径的数学模型通过数据矩阵建立.在过程路径的聚类中有三类相似性:操作间的相似性用基于操作编码的的曼哈顿距离来度量;过程路径间相似性用欧氏距离来计算并表示成一个相异度矩阵;过程路径串间的相似性由基于相异度矩阵的平均距离来估计．那么,过程路径串最后通过会凝聚的分等级的聚类方法被合并.并且过程路径的聚类结果由过程路径的聚类粒度决定.这个方法已经被成功用来发现某一类轴套的典型过程路径.

关键词:计算机半自动编制过程典型过程路径聚类分析数据库里的知识发现

1．引言

过程编制是把一个设计规范集转换成一个用来描述如何加工一个零件科技说明书集的任务。因此，它是产品设计与制造间的基本连接。过程路径编制是编制科技说明的逻辑顺序的一个任务，考虑诸如几何形状，技术必备，经济要素，生产力和实际生产环境的约束。从而过程路径编制依赖于过程编制者拥有的知识和经验。过程知识是通过过程编制实践自身理解和经验的积累。它能帮助过程编制者完成编制任务并避免重复智力劳动。并且，随着产品复杂程度的增加，过程复杂程度也增加。过程知识的再使用变得越来越重要以确保过程编制的质量和有效性。制造型企业迫切地需要过程知识以使他们自己适应市场竞争。

1960s,计算机半自动过程编制（CAPP）开始被研究以减少过程编制者的劳动。已有大量在智能化CAPP 上的预先研究。人工智能技术诸如专家体系，基于推论的规则，神经网络，和黑板方法通常被应用。不管什么被应用，知识在智能化的CAPP是不可缺少的。它已经成为CAPP向智能化发展的一个瓶颈。

如何获得大量有效的知识是智能化CAPP和企业的关键。过程知识主要来源于指南和书本，相关的数据，专家和科技文件。来自专家和科技文件的只是被深深的植入到个体，产品和公司的关系在[4]中有描述。通常很难发现正确的到处方法。

现在，中国所有当前的CAPP系统有通过计算机逼近科技程序的功能。纸制的科技程序在大的制造型企业中被电子表格代替。因为CAPP更深的应用，大量的过程数据被累积在企业的数据库中以至编者者的职能和经验被隐藏了。过程数据库成为过程知识的新来源。此外，过程数据库有普遍数据结构的有利条件。用这个方式来发现和构造过程知识是非常有利的，它可以被用于只能计算工具。

数据库中的知识发现是在数据库里挖掘知识的智能工具。它已经被应用于制造业，例如在制造业数据中发现有用的和可理解的模式[5]，在设计和制造业的知识库中发现学问[6]。少数研究者努力把它应用到过程知识的获得上。Gao Wei [7]讨论了帮助导向的过程知识库的组成和应用的KDD知识获得方法。概要地引进几个可用的方法以自动获得过程知识。但并没有详细说明如何运用这些方法来获得具体知识如在过程编制中的决定规则和典型过程编制实例的。数据库中的过程知识发现有很多优势。它使维持，管理和扩展知识变得容易。而且，它能促进过程编制的标准化。这篇文章提出运用KDD在过程数据库中获得典型过程路径的方法。基于聚类分析的典型过程路径发现被着重论述。

2．典型过程路径发现理论

典型过程路径发现主要采用聚类分析把过程路径聚集成组。然后，同一组里的各零件的共同特征通过分析这些部分的过程路径而被了解。最后，包含个部分特征的典型过程路径被存储到知识库中。过程路径能够被查询和再使用通过匹配包含在典型过程路径中的特征。

2．1典型过程路径发现的步骤

典型过程路径发现被划在图1。最优化的过程路径应该根据过程类型，零件类型和过程路径长度来大致分类。过程类型包括技工加工过程，装配过程和专门的过程等。零件类型包括轴套，轮盘，盒子，包装等。它是根据零件外形的特征来分类的。过程路径长度是过程路径中操作的数目。它是不确定的，用K表示，K∈{正整数}，K可以定义为1≤K≤5，3≤K≤8，5≤K≤12，10≤K≤15等。然后，相似的过程路径可以用凝聚的层次聚类方法挖掘。结果，过程路径数据被聚集成组。聚类分析包括五个部分。第一，建立一个包含所有等着聚类的过程路径的数据表格（表1）。第二，描述工艺卡里所有的操作。第三，建立数据矩阵。第四，通过距离计算机算相异度并建立相异度矩阵。第五，确定聚类粒度。最后，得到经过过程路径聚类后的分组结果（表2）。在表1。L1～Ln代表过程路径，每条线是零件的一条过程路径。

Xij是一个操作并在聚类分析前被编码。在表2中，TL代表相同的过程路径，SL代表相似的过程路径，PARTij代表第i组里j零件的编码。

2．2 获得优化过程数据

在过程路径挖掘前，为了获得最优化的过程数据和建立最优化的过程路径数据库，过程数据需要经由数据选择，数据剔除，数据转换等预先处理。

—过程数据选择

数据选择是在过程数据库中通过选择与典型过程路径相关的数据和样本来确定目标数据。过程数据库是合理的数据库。它有自己的查询语言，目标数据通过查询语言拟定。

—过程数据剔除

目标数据是数据剔除的对象。数据剔除用于检查数据的完整性和一致性，并过滤掉多余的数据。过程编制标准化，即用统一的标准表示制造业过程，使剔除过程数据的最好方法之一。

—过程数据转换

数据转换是在数据剔除之后用来减少数据的。这篇文章主要利用数据库操作，如SQL数据库中色“SELECT”和“DELETE”语句来减少数据。

3．操作编码图解

近期基于分类和编码的the part 聚类方法有很好的效果[17]。在聚类的步骤中，过程路径被编码过的操作描述。对过程路径编码使得求过程路径间的相异度变得容易因为数字可以正好无异议地被电脑理解，正文也是。例如，判断“milling”,”turning”和”turning cylindrical surface”之间的相异度。判断它们之间的不同是很困难的。如果他们被各自编码为31200，31100和31102，它们的差别通过距离方程式是可计算的。结果是“milling”和“turning”之间的距离比“turning”和”turning cylindrical surface”之间的距离要大。这是符合实际的，“milling”和“turning”属于不同类型的工具加工，“turning”和”turning cylindrical surface”有相同类型的工具加工，只是外表不同。

每条过程路径是一个操作顺序的编制。因而，它可以被认为是一个操作序列。过程路径编码可以采用把每个操作编成一个单元并把这些单元排序的方式。每个阿拉伯数字的编码由从0到9的阿拉伯数表示。编码由两部分构成，如图2。一个是代表加工方法分类的操作编码，第一个数字代表粗糙分类的第一类。第二个数字代表比第一类好的类。第三类比第二类好。例如，制造业的过程方法包括锻压工作，切割工作，加膜等。这些属于第一类。切割又包括使用切割工具磨擦，装配和加工方法。那些饱含在第二类。用切割工具的加工方法包括旋转，轧齿边和碾等。那些饱含在第三类。制造业过程方法的分类是三倍。另一个是包含图形，维度，在操作中加工特征的精度的操作目录编码。图形和维度被表示成两个阿拉伯数字。制造业的过程方法的部分编码如图3。根据图3中的编码，“turning plane”编为“31101”。它的第一级是切割工作，第二级是用切割工具加工，第三级是旋转。

4．对典型过程路径发现的聚类分析法则

聚类分析是一种DM方法，和一个重要的数据分析技术[8]。它已经被用于多个领域[9—11]。有很多聚类法则如k-平均方法，K-中心点方法，层次聚类方法（HCA）等[12]HCA被广泛应用因为它能在不同粒度水平探究数据及容易测量距离的优点。HCA被应用在制造业中。再Joines’s的评论中[13]，HCA 被运用于制造业单元设计。WON[16]运用多重标准聚类方法来测量在零件的过程路径中的设计的相似性为了划分制造业的单元。Angel A.Cedefňo[14]提出了一个基于在一个大的数据集合里把零件分成零件家庭方法的相似系数。Rafael S.Gutierrez[15]运用HCA对生产进度表里初始的产品/生产量进行分配。事实上，上述的运用都与把零件分簇和把加工和/或操作分成单元有关。

HCA通过数据分层建立簇并形成以簇为节点的树。此树叫做聚类系统树图。HCA包括两种方法：凝聚的HCA(AHCA)和的HCA。这里，AHCA用来过程路径聚类，它采用自底向上的策略。聚类中，一个对象看作一个簇，然后逐步地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。同时，簇合并必须服从距离规则或相异规则。

4．1过程路径聚类的数学表达式

基于聚类分析的典型过程路径发现实质上是高度相似的过程路径簇通过过程路径聚类分析被发现的步骤。这里，运用AHCA进行过程路径的聚类分析。

矩阵X n×p (Eq. (1))由p个属性和n个数据对象被用于数据矩阵来描述过程路径数据集。矩阵里，行代表过程路径，n是要聚类的过程路径的数目，p是要聚类的过程路径的长度的最大值。元素xij代表过程路径i中操作j的编码。计算相异度前，必须把过程路径的操作数目少于p的在数据矩阵中补“000”。

4.2 过程路径聚类中的距离计算

有三种距离：过程路径之间的距离，操作之间的距离，簇间的距离。

4．2．1 操作间的距离计算

测量相似过程路径的关键就是确定操作间的距离。距离计算方法直接地影响聚类结果。操作编码只是一个代号不能立即用于判断操作间的距离。因此，专家评级方法，计算方法和混合方法能用于测量距离。专家评级是相当精确的方法，因为此距离等于专家给出的评级的平均。但是，它依赖于专家的经验。计算方法通过处理操作编码确定距离因此它在灵活性和实用性上是不足的。混合方法在计算时通过考虑专家经验和一定的权重可以解决上面方法的劣势。

操作间的距离由混合方法季曼哈顿距离计算。曼哈顿距离[12]对计算编码距离是一个合适的测量距离的方法。基于曼哈顿距离公式，距离标准化公式由加了权重的Eq(2)给出

下面两段讲述具体应用。这里就不赘述了。

4．2．2 过程路径间的距离计算

欧几里得距离[12]涌来计算过程路径之间的距离。Eq(3)表示过程路径间的标准化距离。

4．2．3 簇间的距离计算

平均距离[12]应用于簇间的距离计算，Eq(4)

4.3 相异度矩阵

根据上面提到的计算方法，相异度矩阵可表示位Eq(5),与Eq（1）相对应。

4．4 动态聚类系统树图（DCD）

在聚类的开始，根据AHCA每个过程路径仅仅是一个簇，也就是说，有n个过程路径就有n个簇。簇间的距离有Eq(4)计算。为了判断簇是否能合并，定义阈值(α)。α一般等于聚类中簇间的最小距离。有时候，它需要根据实际情况确定。当簇间的距离小于这个阈值时，则把它们合并成一个新的簇。新的簇再和另外的簇重复上面的操作直到聚类停止。DCD描述聚类过程。相异度矩阵里的每个不同的数据时DCD的左边坐标轴上的点。根据Eq(4)和相异度矩阵，簇间的每次的距离最小值都被标在DCD的左边坐标轴。图3是一个n=5的DCD。图4的左边，αi是i步聚类的阈值。图4的右边gi为i步聚类时簇的个数。

4．5 确定聚类粒度

随着聚类地进行，簇的个数减少，簇中过程路径的个数增加。此外，簇间的距离增加，过程路径间的距离也增加。这表示簇的相异度随着簇的个数的减少而增加。因此，聚类中的另一个关键问题是如何确定簇的个数以使簇中有更多的过程路径并使它们更加相似。据类粒度正是解决这个问题。

从上面的分析知聚类粒度与簇的个数和距离有关。它也可由动态聚类系统树图推出。下面定义两个的参数：

— g(1≤g≤n),确定簇的个数。一旦簇的个数少于它，聚类停止。

—α(0<α<1),确定阈值。一旦距离最小值大于α，聚类停止。

人工地初始化g和α是靠不住的。需要阐明一个规则来确定聚类粒度。

Λk有计算相邻两个阈值得到，Eq(6).它反映了聚类k把低的阈值带到了簇里过程路径的相似性。Λk=（1-αk-1）/(1-αk) (6)

Ηk是簇的个数的比值。它反映了增加的程度。

ηk=gk-1/gk (7)

μk是聚类粒度判断的基础。它由Eq(8)计算

μk=λk/ηk (1≤k≤n) （8）

它意味着μk越小，聚类越有意义。决定聚类粒度的几种方法如下：

— 当μk=min{μk}时，聚类粒度是最好的，这是一种冒险的方法

— 当μk首先小于μk-1，聚类粒度被选择，这是个保守的方法。

— 当μk=min(1/m∑μk)时，聚类粒度是最好的。这是个更合理的方法因为它在聚类m前囊括地考虑了每个结果。尽管如此，判断聚类粒度仍旧需要人为地来获得更好的聚类。

5 一个计算的例子

这部分运用上面讲的方法，带入具体数据进行计算，考虑用不同的方法，得到相应的结果。

6 结论

CAPP朝向智能化发展的指示已经进入发展瓶颈。随着CAPP应用的深入，大量的过程数据已经在企业的数据库里积累。充足的数据和贫乏的指示显得突出。所以，KDD被引进。作为KDD在获得过程知识中的一个应用，此文章提出了在过程数据库中典型过程路径发现的方法，这个数据库是合理的并且有大量的过程数据。针对典型过程路径发现的聚类法则被发展。在这个法则里，过程路径聚类备表示为矩阵。操作编码的图解用工时表示出来。根据聚类法则，三种计算距离的方法被给出，过程路径的聚类粒度被确定。第五节的例子用来检验对典型过程路径发现的聚类法则和这个典型过程路径发现方法。