装备维修流程设计需求聚类分析

岳强斌，欧 渊，石 倩

(1.军械工程学院，石家庄 050003;2.中国国防科技信息中心，北京 100142)

装备维修流程是装备维修操作的具体实施程序，是装备维修任务能否完成的关键。对装备维修流程进行重新设计，能更加快速和有效地提高装备维修流程效率，快速完成装备维修任务，恢复装备战斗力。

装备维修流程设计需求是装备维修流程设计的重要依据和根本基础。由于获取的装备维修流程设计需求数量较大，因此需要将装备维修流程设计需求进行分类，将针对同一问题的装备维修流程设计需求归到一起，并且区分其层次关系，以便于后续的流程设计工作。

1 装备维修流程设计需求聚类分析过程

装备维修流程设计需求是针对不同的方面进行阐述的，可能涉及到层次上的区别，所以，本文选择采用凝聚层次聚类法(hierarchical agglomerative clustering，HAC)来进行聚类分析。HAC又称为合并型层次聚类，是一种自底向上的方法，将每一个对象看作一个聚类，把它们逐渐合并成越来越大的聚类［1］。在每一层中，根据一些规则将距离最近的2个聚类合并，直到满足预先设定的终止条件。例如，所有的对象最终合为了1类，或者聚类的数目达到了预定值，或者最近的2个类之间的距离达到预定的阈值［2－3］。根据HAC的原理，基于HAC的装备维修流程设计需求聚类分析过程如图1所示，包括4个关键步骤:分词、提取特征词、相似度计算和聚类处理［4］。

图1 基于HAC的装备维修流程设计需求聚类分析过程

1.1 分词

装备维修流程设计需求是以短句的形式存在。装备维修流程设计需求的基本要求是主题唯一，对象明确，语言简明、具体等。但是对于后续的相似度计算，需要计算装备维修流程设计需求之间的相似度，而句子之间的相似度是以词语之间的相似度为基础的，所以，首先要将其切分为词语，对装备维修流程设计需求进行分词［5－6］。

由于装备维修流程设计需求的结构比较明了和清晰，分词就变得相对比较容易，因此，本文采用基于规则分词法中相对精确的逆向最大匹配法(reverse maximum matching method，RMM)来进行分词，提出了基于RMM装备维修流程设计需求的分词方法［7］。

首先，定义进程P，其中x为待分词的装备维修流程设计需求所包含的汉字个数，如图2所示。由于RMM法的核心思想是将待分词的装备维修流程设计需求与装备维修流程设计需求词典库中的词条进行比对，因此，首先定义预处理分词进程，引入一个计数参数k，在将k置零后将待分的装备维修流程设计需求与词典库进行比对。若能匹配成功，则直接形成分词结果;当匹配不成功时去掉最左边的一位，此时计数参数k=k+1，取后(x－k)位的装备维修流程设计需求再进行匹配处理。若能成功匹配，则判断k是否为零。k为零，表示待分词的装备维修流程设计需求是一次匹配成功;若k不为零，则要将去掉的最左边的k位重新与装备维修流程设计需求词典库进行比对，分词成功以后，输出分词结果。

在定义了预定义的分词进程P以后，采用RMM算法进行处理，算法流程如图3所示。假设装备维修流程设计需求词典库中最长词条所包含的汉字个数为a，待分词的装备维修流程设计需求包含的汉字个数为b。

若a≥b，则表示待分词的装备维修流程设计需求中的汉字个数小于词典库中的最长词条的汉字数，此时应将整个装备维修流程设计需求与装备维修流程设计需求词典库进行匹配，利用预定义进程P得到分词的结果。

若a＜b，则表示待分词的装备维修流程设计需求中的汉字个数大于词典库中的最长词条的汉字数，此时应取装备维修流程设计需求的后a个字进行分词，同样利用预定义进程P得到后a个字的分词结果。再取装备维修流程设计需求剩余的(ba)个字，此时，需要比对(b－a)与词典库中的最长词条的汉字数a的大小关系。当(b－a)≤a时，则可以直接将装备维修流程设计需求剩余的(b－a)个字与词典库进行匹配，进行分词处理。但是当(b－a)＞a时，这样就与前述的a＜b的情况一样，因此，返回计算，重新取剩余装备维修流程设计需求(b－a)个字的后a个字进行分词处理。需要注意的是，在a＜b的条件下，最终需要将所得的分词结果进行合并，得到一个完整的分词结果。

图2 预定义的分词进程P

图3 RMM算法流程

1.2 提取特征词

对装备维修流程设计来说，装备维修流程设计需求就是对流程要达到水平的一些具体要求。那么，从意义上理解，其语句形式就是要使什么方面达到什么样的程度。例如，装备维修流程设计需求“工艺设计合理”，经过原始的需求转换得到的装备维修流程设计需求的表达形式本来就是比较简练，根据装备维修流程设计需求的结构特点，可以将装备维修流程设计需求的结构分为3部分:关键词、属性词和程度词。关键词是装备维修流程设计需求所描述的对象，是装备维修流程设计需求的中心词;属性词是装备维修流程设计需求所描述对象的某一具体属性;程度词是所述装备维修流程设计需求所要达到的目标。

根据装备维修流程设计需求的3部分结构，装备维修流程设计需求特征值提取就是区分关键词、属性词和核心词，它们是装备维修流程设计需求的主要内容，也是进行相似度计算时的重要指标。虽然装备维修流程设计需求的表述已经比较扼要，但分词进行完成后，还会存在一些与关键词、属性词和核心词无关的助词和副词等，因此在进行特征值提取时，要将这些与装备维修流程设计需求主要内容意义表达无关的词去掉。

1.3 相似度计算

装备维修流程设计需求包括关键词、属性词和程度词3部分结构，因此装备维修流程设计需求的相似度计算核心就是这3个词语之间的相似度计算。根据装备维修流程设计需求词语相似度计算的特点，本文提出了基于知网(Hownet)的装备维修流程设计需求语义相似度计算方法［8］。

装备维修流程设计需求包含3部分词语，本文所计算的装备维修流程设计需求词语相似度是指同类的词语的相似度，如关键词与关键词的相似度，属性词与属性词的相似度，而程度词是一些指标和目标方面的描述，可能是一些具体的数字，也可能是一些程度上的定性描述，所以计算它的相似度对整个装备维修流程设计需求的相似度意义不大。因此，基于知网的装备维修流程设计需求语义相似度计算方法计算的是关键词和关键词、属性词和属性词的相似度。分别计算出其相似度后，再对二者进行加权处理，得到整个装备维修流程设计需求的相似度。

1.3.1 词语相似度

假设有词语 W1和W2。W1的义项有 n个:F11，F12，…，F1n，用 F1i表示，i=1，2，…，n。W2的义项有 m 个:F21，F22，…，F2m，用 F2j表示，j=1，2，…，m。

定义词语W1和W2的相似度为

其含义是:2个词语 W1和 W2的相似度SimW(W1，W2)等于二者各义项之间相似度SimF(F1i，F2j)的最大值。

由于义项是用多个义原来描述的，所以，义原的相似度计算是目前需要考虑的问题。定义2个义原 T1、T2，其相似度为

其中:d是T1、T2在义原层次体系中的路径长度，是一个正整数;α是一个可调节的参数，其含义是相似度为0.5时的路径长度。

在知网中，将实词的语义表达分为4个部分:

1)第1独立义原描述式。将2个义项的这一部分的相似度记为SimT1(T1，T2)。

2)其他独立义原描述式。语义表达式中除第1独立义原以外的所有其他独立义原(或具体词)，将 2个义项的这一部分的相似度记为SimT2(T1，T2)。

3)关系义原描述式。语义表达式中所有的用关系义原描述式，将2个义项的这一部分的相似度记为 SimT3(T1，T2)。

4)符号义原描述式。语义表达式中所有的用符号义原描述式，将2个义项的这一部分的相似度记为 SimT4(T1，T2)。

在此定义的基础上，义项F1和F2的语义相似度为

其中βi(1≤i≤4)是各义原的调节参数，且β1+β2+ β3+β4=1，β1≥β2≥β3≥β4，表示从第 1 独立义原到符号义原的相似度对整个义项的相似度依次递减。第1独立义原对义项相似度影响最大，因此β1比较大，一般在0.5以上。

1.3.2 装备维修流程设计需求相似度

对于装备维修流程设计需求，分别计算出对应的关键词和关键词、属性词和属性词之间的相似度后，就可以计算整个装备维修流程设计需求的相似度。

假设2个装备维修流程设计需求为V1和V2，V1的关键词和属性为W11、W12，V2的关键词和属性为W21、W22，那么装备维修流程设计需求V1和V2的相似度为

其中γ是关键词和属性词的在计算相似度时的权重，根据实际情况确定。

1.4 聚类处理

聚类处理［9］是将装备维修流程设计需求归类的一个过程。首先对装备维修流程设计需求聚类处理做如下假设:

1)装备维修流程设计需求集V={V1，V2，…，Vi，…，Vn}。

2)将V中的每个装备维修流程设计需求Vi都看作是一个包括单个装备维修流程设计需求的类Ci={Vi}，因此，这些类构成了V的一个聚类C={C1，C2，…，Ci，…，Cn}。

3)设t为相似度阈值，当2个装备维修流程设计需求相似度大于等于t时，才符合聚类基本条件，才可能归为一类;当2个装备维修流程设计需求相似度小于t时，则认为二者属于同一类。

聚类处理算法处理过程:

1)首先，计算其他聚类Cj(j≠i)分别与Ci的相似度Sim(Vi，Vj)，计算出的相似度有(n－1)个。

2)判断Sim(Ci，Cj)是否达到相似度阈值要求。若Sim(Ci，Cj)≥t，则将其列为可能相似的对象;若Sim(Ci，Cj)＜ t，则二者肯定不相似。

3)取满足相似度阈值要求的Sim(Ci，Cj)，取它们中的最大值即Max Sim(Ci，Cj)，将二者聚为一类 CiCj。

4)将新的CiCj归类继续与其他类进行聚类。有CiCj与 Ck(Ck为其他任一类)，则分别计算Sim(Ci，Ck)和 Sim(Cj，Ck)，取二者均值 Average=［Sim(Ci，Ck)+Sim(Cj，Ck)］/2。若 Average≥t，则认为Ck与 CiCj相似，将其聚为新类 CiCjCk;若Average＜t，则认为Ck与CiCj不相似，不进行聚类。

5)重复上述步骤，直至C中所有对象均不符合以上聚类条件，则聚类完成。

2 结束语

本文提出装备维修流程设计需求聚类分析方法，以HAC为基本原理，通过分词、提取特征词、相似度计算和聚类处理4个关键步骤，实现了装备维修流程设计需求的聚类分析，进行了层次关系区分，为后续装备维修流程设计打下坚实基础。

［1］孙卫，马德云，欧阳为民，等.基于聚类的体制数据库中的知识发现［J］.计算机与现代化，2008(9):58－64.

［2］刘文军，游兴中.一种改进的凝聚层次聚类法［J］.吉首大学学报:自然科学版，2011，32(4):11－14.

［3］罗可，洪亮亮，童小娇.一种有效的分类型数据聚类方法［J］.控制与决策，2011，26(10):1542 －1544.

［4］李玲玲.关于凝聚层次聚类时间复杂度的研究［J］.宿州学院学报，2011，26(2):21 －22.

［5］罗桂琼，费洪晓，戴弋.基于反序词典的中文分词技术研究［J］.计算机技术与发展，2008，18(1):80 －83.

［6］胡锡衡.正向最大匹配法在中文分词技术中的应用［J］.鞍山师范学院学报，2008，10(2):42 －45.

［7］徐殿军，崔宝华.PHP+MYSQL环境下的中文分词技术研究［J］.辽宁师范大学学报:自然科学版，2008，31(1):57－59.

［8］金博，史彦军，滕弘飞.基于语义理解的文本相似度算法［J］.大连理工大学学报:自然科学版，2005，45(2):291－297.

［9］潘有能.XML文档自动聚类研究［J］.情报学报，2006，25(2):215－220.

［10］王伟.文本自动聚类技术研究［J］.情报杂志，2009(2):94－97.