对模糊聚类分析法的改进及其在SRM中的应用_黄闽英

??CN43??1258/TP

??ISSN1007??130X????????计算机工程与科学COMPUTERENGINEERING&SCIENCE2011年第33卷第6期????Vol??33,No??6,2011??

文章编号:1007??130X(2011)06??0144??06

对模糊聚类分析法的改进及其在SRM中的应用

ModificationoftheFuzzyClustering

AnalysisMethodandItsApplicationinSRM

黄闽英,牟??锐

HUANGMin??ying,MURui

(西南民族大学计算机科学与技术学院,四川成都610041)*

(SchoolofComputerScienceandTechnology,SouthwestUniversityforNationalities,Chengdu610041,China)摘??要:针对传统模糊聚类分析法在信息系统的决策分析中无法有效解决各因素之间的相关性干扰,以及不同特征属性对聚类目标存在重要性差异等问题,本文提出一种融合层次分析法、Mahalanobis距离法及专家群决策法的改进模糊聚类分析法。在特征属性的重要性处理环节,层次分析法用于判断不同特征属性的相对重要性差异;引入Mahalanobis距离法进行相似矩阵的构建,能解决变量之间的相关性干扰问题;专家群决策法用于确定最佳阈值??,能最大程度地降低主观因素对评价结论的不利影响。在SRM中的应用实验结果表明,改进的模糊聚类分析法在客观性和准确性上更能满足信息系统决策分析的需要。

Abstract:Inthedecisionanalysisofinformationsystems,thetraditionalfuzzyclusteringanalysishassomeshortcomings,whichnotonlycannotresolvetherelevanceinterferingproblemofthecharac??teristicattributes,butalsoignoresthedifferenceofimportancedimensionsamongthedifferentcharac??teristicattributes.Inordertoovercomethesedefects,animprovedalgorithmisproposedbasedontheanalytichierarchyprocess,theMahalanobisdistancealgorithmandthegroupdecisionmethod.Inthelinkofimportancetreating,ananalytichierarchyprocessisusedtoestimatetheimportancedimensionsofdifferentcharacteristicattributes.TheMahalanobisdistancealgorithmisintroducedtobuildthesimi??laritymatrix,anditcanresolvetheproblemofrelevanceinterferenceofthevariables.Theexpertsgroupdecisionmethodisalsointroducedtodecidethebestthreshold??,throughthismethod,thead??verseeffectsofthesubjectivefactorstotheconclusionoftheanalysishavebeenreducedgreatly.Theapplicationinthesupplierrelationshipmanagementsystemshowsthattheimprovedfuzzyclusteringa??nalysisisgreatlysatisfiedwiththeneedsofthedecisionanalysisininformationsystems.

关键词:模糊聚类分析;层次分析法;Mahalanobis距离法;群决策;供应商关系管理

Keywords:fuzzyclusteringanalysis;analytichierarchyprocess;Mahalanobisdistancealgorithm;groupdecision;supplierrelationshipmanagement

doi:10.3969/j.issn.1007??130X.2011.06.028

中图分类号:TP311文献标识码:A*收稿日期:2010??09??12;修订日期:2010??12??13

基金项目:西南民族大学博士创新基金(09NBS003)

通讯地址:610041四川省成都市武侯祠横街18号431402信箱

Address:MailBox431402,18WuhouciSideSt,Chengdu,Sichuan610041,P.R.China

1??引言

模糊聚类(FuzzyClustering,简称FC)是将模糊集的概念应用到传统聚类分析中,让数据集的对象在分组中的隶属用连续区间[0,1]中的某个值来表示,这个值就是隶属度,各对象以相应的隶属度分别隶属于多个簇。模糊聚类的优点在于能适应那些分离性不是很好的数据和类,但目前已有的传统模糊聚类分析法往往对聚类目标各特征属性之间的相关性以及不同特征属性对聚类目标存在重要性差异等问题没有充分考虑,而这些问题却是现代信息系统愈加复杂的决策分析中必须面对的现实问题。本文正是基于此,提出对传统模糊聚类分析法进行改进,让聚类分析过程兼顾到重要性差异和相关性干扰等因素,从而使聚类结果更客观地反映决策事务的实际情况,为信息系统提供准确的分析结论。

[1]

元素均置1,而其余都置0。若有相同的两列或多列,即表示这些列彼此之间接近,则列的标号即代表原来的元素,作为一组中的元素加以记录。不断重复上述过程直至所有样本归为一类。

(5)聚类结果评估:是指对聚类结果进行评估。评估主要有三种:外部有效性评估、内部有效性评估和相关性测试评估。

3??改进的模糊聚类分析法

虽然典型的模糊聚类分析法在信息系统的决策分析中有较多的研究和应用,但目前大多没有考虑聚类分析中各因素之间的相关性以及不同特征属性对聚类目标存在重要性差异,所以聚类结果往往不能很好地反映现实问题,这也正是改进算法中需要解决的问题。

3.1??特征的重要性处理和数据的标准化

在模糊聚类分析中,设Y=(y1,y2,??,yn)为n个待分类样本的集合,其中每一个分类样本有m种特征属性,用yi=(yi1,yi2,??,yim)表示,其中yij是第i个样本的第j个特征观测值。由此可以得这n个样本的m种特征组成的模糊指标矩阵Y=yijn??m。在实际问题中,所选定的分析特征属性不但对分析目标存在着重要性差异,而且还具有不同的量纲,若直接用观测值进行分析,则分类结果肯定无法体现这种重要性差异。因此,在改进方法中,首先要对所选特征的观测值进行重要性处理,再对重要性处理后的数据进行不同量纲下的标准化计算。

3.1.1??特征的重要性处理

在特征的重要性处理环节,我们引入层次分析法AHP(AnalyticHierarchyProcess,简称AHP)对特征数据进行加权,以体现不同特征对分析目标的重要性差异。比如在对企业销售人员的绩效评价中,销售额、岗位适应性等评价指标相对员工的绩效这一评价目标来说,具有不同的重要程度,即相对重要性有差异,而这种差异可由企业专门的评估小组给出的相对重要性判断值进行量化[3]。评估小组一般由评价目标所涉及业务部门的专家组成。

为有效降低专家评估时的主观性和评估难度,使量化的判断值能更客观地反映企业实际,我们引入??九分位法??让专家对各评价指标进行相对重要性的两两比较。比如在确定销售额与岗位适应性

2??模糊聚类分析法的典型步骤

对分类数不定的模糊聚类,其传统的聚类过程主要包括以下步骤[2]:

(1)数据准备。包括特征标准化和降维。为使不同量纲的数据能够进行比较,需要对数据进行标准化处理,即将数据压缩到[0,1]闭区间上。对于最常见的无序型数据的标准化,若为连续性或离散性较小的数据,可以采取划分区间的方法将其离散化;若数据的离散性大,则可用平移??标准差变换公式和平移??极差变换公式进行处理。

(2)建立模糊相似矩阵。相似矩阵由样本两两之间的相似系数组成,相似系数用于确定各个样本之间的关系,度量样本之间的接近程度。计算相似系数的方法有相关系数法、距离法、夹角余弦法等。

(3)建立模糊等价矩阵。由相似变换得到的相似矩阵已满足对称性及自反性,但并不一定满足传递性。以模糊相似矩阵为基础构建满足传递性的模糊等价矩阵有多种方法,主要有模糊等价矩阵聚类法、直接聚类法等。模糊等价矩阵聚类法又有平方法(传递闭包法)、Boole矩阵法等,直接聚类法又有最大树法、编网法等。

(4)聚类(或分组)。模糊等价矩阵建立后,取阈值0<??<2<??<(p-1)<1=p,在每一轮聚类过程中,凡是等价矩阵中相似度大于阈值的

??

??

??

相比的重要性指标时,理论上有如表1所示的可取值[4]。

假定某一企业的评估小组根据企业的情况,认为对员工绩效这一评价目标来说,销售额显得??极重要??,而岗位适应性则显得??极不重要??,则根据表1可知,销售额的重要性判断值为9,岗位适应性的重要性判断值应为1/9。评估小组给出所有指标的重要性判断值后,将这些值组成一个n??n的判断矩阵M,M中的元素mij表示横行指标mi对各列指标mj的相对重要性判断值,n是评价指标的数量。

依据相对重要性指标组成的判断矩阵即可计算各特征属性的权重,计算过程如图1

所示。

为样本平均值,即x??ij=

n

i=1

??x

n

ij

,si为重要性处理

后的模糊指标矩阵第i列数据的标准差,即:

si=

2

(xij-??xij)

-1i??=1

????变换后每个变量的均值为0,标准差为1,所有数据已被标准化到[0,1]闭区间,且消除了量纲的影响x??ij

[

5]

。

标准化后的数据组成标准化矩阵X??=

n??m

。

3.2??建立模糊相似矩阵

对样本观测值进行上述标准化处理后,就可以对样本进行相似矩阵的计算和构建。这里引入Mahalanobis距离法进行计算,该方法具有尺度无关性(Scale??Invariant),且有由标准化数据和中心化数据(即原始数据与均值之差)计算出的二点之间的Mahalanobis距离相同的优点,同时还可以排除变量之间相关性的干扰,适合于企业信息系统中类似问题的相似矩阵的构建[6]。

Mahalanobis距离定义为两个服从同一分布

图1??计算特征属性权重的UML活动图

通过层次分析法确定的m个指标的权重向量为:

??=(??1,??2??,??m)

满足

k=1

并且其协方差矩阵为异程度:

d(xi,xj)=其中,

??的随机变量x

-1

i

与xj的差

xi-xj)

(xi-xj)T(2)

-1

??

m

??k=1。设样本yi=(yi1,yi2,??,yim)被

??

为样本的协方差矩阵,

??

为样本协

赋予权重后的向量为xi,即:

xi=(xi1,xi2,??,xim)=(yi1????1,yi2????2,??,yim????m)并组成重要性处理后的模糊指标矩阵X

=xij

n??m

方差矩阵的逆矩阵。d越小,表示xi与xj两样本越接近,即样本的相似程度越高。构建模糊相似矩阵时,令:

rij=1-cd(xi,xj)

其中,c为适当选取的参数,它使得0??rij??1,比如可取c为所有d(xi,xj)中的最大值的倒数。

由rij组成的矩阵R=(rij)n??n即为所需的模糊相似矩阵,该矩阵是一方阵。3.3??建立模糊等价矩阵

以上计算得到的模糊相似矩阵R一般只满足自反性和对称性。自反性保证任一样本不能同时属于不同的类;对称性保证样本xi与样本xj同类时,样本xj与样本xi也一定同类。但是,这样的

略不

重要1/3

不重要1/5

。

3.1.2??数据的标准化

数据标准化就是将数据压缩到[0,1]闭区间上。企业信息系统中的特征数据一般都是离散性较大的无序型数据,且具有不同量纲,为使这些数据能进行比较,需要进行标准化处理。这里我们采用平移??标准差变换公式:

ijij

(1)xij??=si

其中,xij为重要性处理后的特征观测值数据,x??ij

表1????九分位法??中相对重要性指标取值及意义

销售额与岗位

适应性相比销售额的重要性指标可取值备??????注

极重要9

很重要7

重要5

略重要3

相等1

极不重要1/7

1/9

取8,6,4,2,1/2,1/4,1/6,1/8为上述评价值的中间值

矩阵只是相似矩阵,而模糊聚类需要进一步求矩阵R的传递闭包t(R),以使矩阵满足传递性,即将模糊相似矩阵R改造为模糊等价矩阵R*。模糊等价矩阵R*不但满足自反性和对称性,还具有传递性,以保证样本间的间接关系,即当样本xi与样本xj同类,样本xj与样本xk同类时,可以得出样本xi与样本xk同类。

在众多的构建等价矩阵的方法中,平方法是常用的运算效率相对较高的一种方法,也是本文所采

[7]

用的方法。平方法所依据的定理是:对模糊相似矩阵R=(rij)n??n,一定存在一个最小自然数k(2k??n),使得t(R)=R=R。

该定理说明,通过采用平方法(R??R2??R4

k

??????R2????),经过有限次运算可求得相似矩阵R的传递闭包t(R),由此得到其对应的模糊等价矩阵R*,R*=t(R)。3.4??进行聚类

对模糊等价矩阵R中的元素我们可在任意选定的阈值??水平上进行分类,当??从1降到0,对样本所分的类将由细到粗,依次逐步归并,则形成一个动态聚类图。选取最佳的??,即可由该??水平下的截矩阵和动态聚类图得出一种最好的分类结果。由此可知,阈值??的确定会对聚类结果产生重要影响,不同阈值的选取使得分类的数量具有任意性,这也是聚类过程中的主要问题。

那么,该如何选择最佳的阈值??呢?在实际的系统应用中,阈值??往往是根据业务的需要,依据领域知识工程师的经验选取。这里我们引入专家群决策的方法确定最佳阈值??,其中不同专家意见权重的确定采用委托过程法。具体如下:

设有p个专家,每个专家都为其??委托人??(除自身以外的所有专家)赋权wij,wij为第i个专家对第j个专家给出的权重,其中i,j=1,2,??,p。每个专家都像在自己缺席的情况下,委托其他专家去估计群体专家的权重,而自己又作为委托人去判定其他各专家的权重。wij反映了专家i对专家j的权威和信赖程度进行的估计和赋值,说明了专家

[8]

i认为专家j对决策的影响程度。每个专家都有一组相应的委托人,用委托人的群体决策代替自己的决策。wij满足

j=1

*2k

+12k

其中,mi表示第i个专家的意见在群决策中的权

重。通过求解线性方程组可得专家意见的权重向量(m1,m2,??,mp)。设第k个专家所确定的??值

k,则利用求得的权重对专家意见进行综合评为??

定,确定??=

k=1

,即可对??m??。确定了最佳阈值??

k

k

p

样本进行分类,得到最佳分类结果。

4??改进算法在SRM中的应用实例

4.1??实例分析过程

在对某企业供应商关系管理SRM(SupplierRelationshipManagement,简称SRM)进行数据挖掘的开发项目中,我们根据企业的历史数据及企业管理理念,将{price(价格),quality(质量),r_de??liver(交货准确率),service(售后服务),co_value(合作价值)}作为对供应商进行聚类分析的特征指标体系。利用AHP法对五个特征指标进行重要性处理,得各指标的相对权重如表2所示。

表2??指标的相对权重

指??标相对权重

price0.21

quality0.22

r_deliver0.18

service0.20

co_value0.19

????选取六个供应商进行模拟聚类分析,经过数据挖掘流程的数据准备和数据预处理后,六个供应商的特征观测值如表3所示。

表3??供应商的特征观测值

suppliers

123456

price867783729285

quality838984708683

r_deliver747575747577

service768478707978

co_value738180728085

????用表2的相对权重数据对表3数据进行重要性处理,得到处理后的样本值,如表4所示。

表4??重要性处理后的样本值

suppliers

123456

price18.0616.1717.4315.1219.3217.85

quality18.2619.5818.4815.418.9218.26

r_deliver13.3213.513.513.3213.513.86

service15.216.815.61415.815.6

co_value13.8715.3915.213.6815.216.15

??w

p

ij

=1,wii=0,i=1,??,

p:

m1+m2+??+mp=1

w11m1+w21m2+??+wp1mp=m1??

w1pm1+w2pm2+??+wppmp=mp

????对表4的数据进行标准化处理,得到标准化矩

阵X。

0.70290.1154

0.81361.1457X=

0.66740.70870.00330.10001.10000.78880.76320.6565

0.59980.00201.10001.00000.00000.2120

0.43121.10000.56540.10000.85610

.5341

0.0.85090.45330.00020.74791.{1}、{4}各为一类。

针对以上同样的实例数据,用未改进的模糊聚类法进行分析,即首先不用表2的相对权重数据对表3的样本数据做重要性处理,而是直接进行标准化,且在对标准化数据进行模糊相似矩阵的构建时,不采用Mahalanobis距离法进行标定,而采用传统的Euclidean距离法,在确定最佳阈值时用通常的F??统计量法而不采用专家群决策法,由此得到的聚类结果为{2,5}为一类,{6}、{3}、{1}、{4}各为一类。

比较分类结果,传统聚类法的分类数量较多,导致样本聚类较为分散,且样本6在企业长期的实

????对标准化矩阵X采用Mahalanobis距离法进行标定,得到模糊相似矩阵,再对模糊相似矩阵用平方法计算得到对应的模糊等价矩阵R。

10.5440.5440.5440.2570.544

10.6710.7170.2570.717

10.671

1

10.257

0.2570.2570.6710.741

R=

际业务评定中,与样本2、5常被看着一类,这与改进方法的聚类结论一致,而传统聚类法却将其分离出来,与业务实际有所差异。

由此可以看出,改进后的算法中,AHP对聚类目标的特征属性进行重要性处理,以及专家群决策法选择最佳阈值,既充分应用了评估小组集体决策的优势,又最大限度地降低了主观因素对评价结论的不利影响。

同时,根据经济学的相关知识可知,选定的供应商评价特征指标体系中,各指标之间势必存在一定的相关性。比如一个企业商品的价格与商品的质量肯定存在一定的联系,即??价格??与??质量??两指标间具有一定的相关性。Euclidean距离法无法有

????取任意的??值,由相应的截矩阵得到供应商分类的动态聚类图,如图2所示。

图2??动态聚类图

效排除变量之间相关性对分析结果的干扰,但Ma??halanobis距离法却适合相关性干扰问题的解决,符合企业管理与决策分析的现实需要。

应用专家群决策的方法确定最佳阈值??时,共有4位专家,其权重计算方程为:m1+m2+m3+m4=1

0.15m1+0.39m2+0.27m3+0.15m4=m10.22m1+0.10m2+0.27m3+0.22m4=m20.39m1+0.49m2+0.10m3+0.69m4=m30.39m1+0.15m2+0.51m3+0.10m4=m4????由此方程计算专家意见的权重和??取值,如表5所示。

表5??专家意见权重及??值

专家权重??值

A0.200.671

B0.190.717

C0.350.717

D0.260.652

5??结束语

本文通过引入AHP、Mahalanobis距离法以及专家群决策法对传统模糊聚类分析法作改进,有效解决了特征属性的重要性差异及属性之间相关性干扰等问题,使聚类的结果更具科学性和客观性,更有利于企业的决策参考。

在SRM中的应用实验结果表明,改进的模糊聚类分析法在客观性和准确性上更能满足信息系统决策分析的需要,因而改进后的算法可以在信息系统的决策分析中进行实际应用。参考文献:

[1]??孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19

(1):9.

[2]??SambasivamS,TheodosopoulosN.AdvancedDataCluste??

????结合专家意见,确定最佳阈值为??=0.717。4.2??与传统聚类法的分类结果比较

在应用以上改进算法得到的最佳阈值??=0.717的水平上,根据图2所示的动态聚类图可知,这六个供应商的最佳分类为:{2,5,6}为一类,{3}、