基于距离的粒计算分类算法

陈旭生，刘宏兵，李为华

(信阳师范学院 计算机与信息技术学院，河南 信阳 464000)

0 引言

粒计算(Granular Computing,简称GrC)是一种基于问题空间的计算方法[1]，在模式识别、信息系统等领域有广泛应用.关于人类的认知过程,Zadeh[2]提出了3种基本概念，即粒化过程、粒之间的合并、粒之间的因果关系等.粒化过程是将整体分解成部分的过程，粒之间的合并是通过在两个颗粒之间引入运算，将部分变成整体的过程，而因果关系则牵涉到原因和影响的关联规则.集合、模糊集、关联规则、模糊关联规则是粒计算的主要研究领域.通常情况下，粒和合并粒可用于定义粒之间的模糊关系[3]，如粒的正评价函数用于构成模糊关系，但是存在一些问题，如无论两个原子粒之间有多远，它们之间的模糊关系都为0.

基于代数系统GrC是粒计算的一个范式，它将粒看作集合的子集，利用合并算子和分解算子实现不同粒度空间的转化[4].合并算子和分解算子与粒的形状有关，如：超菱形粒、超球粒和超正方体粒.

本文研究基于距离是指在两个空间集合中有相同形状的粒，用粒的中心和粒度来定义粒之间的距离，通过设计两粒之间的合并算子，实现不同粒度之间的转换合并，选取粒度阈值，用以控制粒之间的合并过程，并构造基于距离的粒计算分类算法.

1 基于距离的粒计算分类算法

对于N维空间数据集S={(xi,yi)|i=1,2,…,n},按照下面的步骤构造粒计算分类算法.第一，S中的单个点被表示为不可分割的原子粒；第二，定义相似形状两个粒之间的距离；第三，粒度和距离共同决定合并过程；最后，获取粒集，并使用该集合预测未知数据的类别.

1.1 粒和粒度的表示

在现实中，粒的形状是不规则的，因此两个粒之间的距离不容易度量，而合并粒和分解粒与粒的形状有关系[5].为了便于研究粒计算，选择形状规则的粒，比如：超菱形、超球和超正方体，这些粒在二维空间具有圆形、正方形和菱形等形状.

将粒表示为由中心c和粒度r组成的向量G=(c,r).粒度是粒的大小，如：超菱形粒的对角线长度、超球粒的半径、超正方体粒的边长等均可表示粒的粒度.超菱形粒的粒度表示为粒中样本与粒中心的最大曼哈顿距离，超球粒的粒度表示为粒中样本与粒中心的最大欧式距离，超正方体粒的粒度表示为粒中样本与粒中心的最大切比雪夫距离.

如图1所示，超菱形粒在R2空间表示为G1=(0.1,0.2,0.4)，其中(0.1,0.2)是其中心，0.4是其粒度.超球粒在R2空间表示为G2=(0.1,0.2,0.4),其中(0.1,0.2)是其中心，0.4是其粒度.超正方体粒在R2空间表示为G3=(0.1,0.2,0.4),其中(0.1,0.2)是其中心，0.4是其粒度.如图1(a)、1(b)和1(c)所示，可以看到，即便有相同的表示，不同粒还是有着不同的形状.

1.2 粒之间的距离

粒之间的距离是指相同形状两粒之间距离的最小值[6].两个超菱形粒G1=(C1,r1)和G2=(C2,r2)之间的距离为

d(G1,G2)=‖C1-C2‖1-r1-r2,

(1)

其中：C1=(x1,x2,…,xn)和C2=(y1,y2,…,yn)是超菱形粒G1和G2的中心；r1和r2是超菱形粒G1和G2的粒度.

‖C1-C2‖1=|x1-y1|+

|x2-y2|+…+|xN-yN|,

(2)

两个超球粒G1=(C1,r1)和G2=(C2,r2)之间的距离为

d(G1,G2)=‖C1-C2‖2-r1-r2,

(3)

其中：C1=(x1,x2,…,xn)和C2=(y1,y2,…,yn)是超球面粒G1和G2的中心；r1和r2是超球面粒G1和G2的粒度.

(4)

两个超立方体粒G1=(C1,r1)和G2=(C2,r2)之间的距离为

d(G1,G2)=‖C1-C2‖∞-r1-r2,

(5)

其中：C1=(x1,x2,…,xn)和C2=(y1,y2,…,yn)是超立方体粒G1和G2的中心；r1和r2是超立方体粒G1和G2的粒度.

‖C1-C2‖∞=max{|x1-y1|,…,|xN-yN|}.

(6)

两粒之间距离是一个任意实数.当d>0时，两粒之间有间隔；当d=0时，两粒之间有相同点；当d<0时，两粒之间有重叠.当d>0时，d的值越大，两粒之间的间隔越大；当d<0时，d的值越大，两粒之间的重叠越小.

1.3 粒之间的算子

任何一个不可分割的点都可以成为原子粒,与原子粒相比较，如何获取较大的粒是合并过程的关键[7].而当整个空间都是由最大粒度的粒构成，分解过程的关键就是如何将更大的粒分割为更小的粒.

对于两个超菱形粒G1=(C1,r1)和G2=(C2,r2)来说，合并超菱形粒G为

G=G1∨G2=(C,R),

(7)

其中

对于两个超球粒G1=(C1,r1)和G2=(C2,r2)来说，合并超球面粒G为

(8)

其中:P=C1-r1(C12/‖C12‖2),Q=C2+r2(C12/‖C12‖2),C12是从C1到C2的向量，C12=C2-C1.

对于两个超正方体粒G1=(C1,r1)和G2=(C2,r2)来说，合并超立方体粒G为

(9)

其中，I是和向量C1有相同长度的向量，其所有分量均为1.

1.4 基于粒之间距离的粒计算分类算法

粒计算分类算法包括训练算法和测试算法，如下文中的算法1和算法2.

对于训练集S，通过以下步骤构造分类粒计算算法.第一，从样本中构造原子粒；第二，设定粒度阈值作为上述所提到的原子粒合并运算的条件，粒集由所有合并粒构成；第三，如果所有原子粒都在粒集GS中，合并进程终止，否则重复第二步.

原生态(原址)保护模式就是对遗址原样保存,不进行大规模的改造,这是最符合文化遗产保护理念的一种模式。这种模式的劣势在于相对浪费土地等资源,无法产生相关的经济效益。这种模式主要针对一些具有特殊价值的近现代矿冶文化遗产和大多数古代矿冶文化遗产。德国弗尔克林根钢铁厂、日本石见银山遗迹及其文化景观和中国绝大多数古代矿冶文化遗产就采取了这类模式。

假设训练集中有相同的样本构造的原子粒g1，g2，g3，g4，g5.使用如图2所示的树形算法，叶子节点为原子粒，根节点GS包括其子节点G1、G2和g5，G1由子节点g1和g2合并构成，G2由子节点g3和g4合并构成，整个GS构造过程是有底向上过程.

粒度阈值用ρ表示，对于相同的训练集，ρ越大表明算法1中的粒集包含更大的粒，相反，ρ越小表明算法1中的粒集包含更小的粒.基于距离的粒计算分类算法的目的是预测未知数据的类别.

图2 包含5节点的训练集S

2 实验

三螺旋分类问题用于检验文中的基于距离的粒计算分类算法的可行性.该数据集包括312个2维空间数据，有101个第一类数据，105个第二类数据，106个第三类数据.利用文中提出的粒计算分类算法，参数以步长0.1从10下降到0，以最大分类精度和最少数量的粒作为最优参数选取的两个指标.表1列出了基于距离不同形状的粒计算的分类性能，该性能包括粒集的大小、训练精度、测试精度和训练时间等.

表1 粒计算分类算法的性能

图3 算法得到的33个菱形粒

图4 算法得到的26个球形粒

图5 算法得到的30个正方形粒

算法1 训练算法

输入：训练集S，粒度阈值ρ，类别n

输出：粒集GS，类别标识lab

Step1：初始化粒集GS=∅，lab= ∅

Step2：i=1

Step3：选取第i类样本，构造样本集X

Step4：初始化粒集GSt= ∅

Step5：j=1

Step6：提取X中第j个样本为xj，构造原子粒Gj

Step7：k=1

Step8：计算粒Gj与粒集GSt中Gk的距离djk

Step9：k=k+1

Step10：找出最小距离djm

Step11：将Gj与Gm合并，如果合并粒Gj∨Gm的粒度阈值ρ小，则Gm=Gj∨Gm，否则GSt={Gj}∪GSt.

Step12：删去xj，直到样本集X为空

Step13：GS=GS∪GSt,lab=lab∪{i}

Step14：如果i=n,输出GS和类别标识lab，否则i=i+1

算法2 测试算法

输入：输入未知数据x，粒集GS，类别标识lab

输出：x的类别标识labx

Step1：用x表示粒G

Step2：令i=1：|GS|

Step3：计算GS中G和Gi的距离di

Step4：找出最小距离dm，m=argmindi

以机器学习数据集(UCI, http://archive.ics.uci.edu/ml/index. html)中的多类分类问题验证文中算法的性能，采用10折交叉验证试验，将每类数据分成10份，选取其中的9份用于训练并得到分类粒，剩余的1份用于测试算法的推广能力即测试精度，这样每个数据集需要做10次实验，算法在这些数据集上的性能如表2所示.从表2中可以看出：(1)文中的粒计算分类算法可以推广至高维空间；(2)对于相同的数据集，不同形状的粒计算分类算法取得了不同的分类精度，说明粒计算分类算法的性能与粒的形状有关；(3)从标准差的大小可以看出，不同形状的粒计算分类算法的稳定性不同，标准差较小的算法具有较好的稳定性.

表2 粒计算分类算法在N维空间上的性能

3 结语

本文提出了一种基于距离的粒计算分类算法.首先，将粒表示为二维空间的菱形、圆形和正方形等三种形式，该表示形式可以推广至高维空间的超菱形、超球和超立方体等形式；其次，定义粒之间的距离，并根据距离和粒度设计粒之间的合并算子；最后设计基于距离的粒计算分类算法.实验结果表明了基于距离的粒计算分类算法的可行性.作为粒计算分类算法的一种改进算法，文中算法的理论基础需要进一步研究，如粒之间的距离是否能构造粒集上的度量空间.