基于概念相似的客体聚类优化信息时代安全技术

为了解决同类客体信息聚合而引起的泄密问题，笔者首先对客体进行了相似性分析，提出了基于概念相似的递归客体聚类算法。其思路为：对客体进行属性约简，去除不必要、冗余的属性，提取客体概念，通过概念引力，对客体进行相似性分析，并依据聚类因子与噪声因子对聚类进行合理的调整。

（一）客体属性约简

令 O={o1，…，on}为客体集合，A={a1，…，an}为属性集合，SL={C1，…，Ck}为安全级别集合。 一个客体可表示为 O（a1，C1，a2，C2，...，ak，Ck）。

属性重要度：给定一个客体O=（Ao，Co），其中Ao⊆A，Co⊆SL，对于∀B⊆Ao，若∀a⊆B，则定义 sig（a，B，Ao）=H（B）-H（B-{a}）为属性 a对属性集B的重要度。H（B）为B的信息熵。

在上述定义的基础上，本书给出了基于属性重要度的客体属性约简算法（Algorithm of Attribute Reduction Based on Significance，简称AARBS），即在保持客体特性不变的情况下，删除不必要、冗余的属性，以保证客体聚类的有效性。客体属性约简算法如下：

input A

Output B(B is a reduction of A)

(1)B=A;n=|A|;j=0;

(2)for i=1 to n do

(3)begin

(4)ai∈B;sig=H(B)-H(B-{ai})

(5)if sig＜n then

(6)B=B-{ai};j=i;

(7)if H(B)＜＞H(A)then B=B+{aJ}；

(8)endfor

(9)return B;

其中，A表示某一安全域内的属性空间，由单属性ai所组成；N表示A的属性值空间，属性值vi∈N。

该算法主要包括3个关键部分：第一部分计算属性集B中某一个属性对属性集B的重要程度；第二部分判断该单属性对属性集B来说是否重要，若重要度小于阈值h时，将该属性从属性集中去除；第三部分判断属性集B与原始的属性集A的信息熵是否相同，若不同，则说明该属性的去除将影响到客体O的特性。算法计算复杂度为O（n）。

（二）概念与概念核

定义 1：（属性矩阵）令 oi∈O，客体 oi的属性用 ω={ai1，ai2，…，aik}表示；客体 oi的属性值用 v={vi1，vi2，…，vik}表示；客体 oi的属性安全级用 π={Ci1，Ci2，…，Cik}；客体 oi的属性概率用 p={pi1，pi2，…，pik＞表示，即{aij，vij，Cij}在 oi中出现的频率。

定义 2：属性矩阵 M 等价于{β1，β2，…，βk}，其中 βj={aij，vij，pij，Cij}（j=1，2，…，k）为M的列，表示客体oi的单个属性向量。

定义3：令β为所有属性矩阵M列向量的集合，给定一个三元组{O，β，R}，其中 R 为一个二元关系，R⊆O×β，表示某一客体 oi拥有属性 βj。 令X⊆O，X'={s∈β|∀x∈X：（x，s）∈R}； 令 Y⊆β，Y'={x∈O|∀s∈Y：（x，s）∈R}；若X'=Y，Y'=X，则称二元对＜X，Y＞为属性空间A上的一个概念，记作concept（X）。

定理1：任何一个客体oi，均存在一个概念＜{oi}，{bj}＞与之对应。

证明：令 oi的属性矩阵 M={β1，β2，…，βk}，令{oi}=X∈O，由于存在二元关系 oiRβj，故有 X'={βj}；令{βj}=Y⊆β，对于∀βj，均存在二元关系oiRβj，故有Y'={oi}。 可见，X'=Y，Y'=X。

定义 4：令 X={oi，oj，…，ok}⊆O，且 X 中的客体相似，它们共同的必要属性项所组成的集合为{β1}⊆β，令 Y={β1}，则称＜X，Y＞为 oi，oj，…，ok的概念核，记Ccore（X）。

定理 2：给定某一安全域内的客体集合 O，o1，o2∈O，若 o1，o2相似，则o1，o2必有相似的概念，反之亦然。

定理3：概念核Ccore（X）是属性集A的一个概念，且Ccore（X）=∩concept（oi），oi∈X。

（三）概念引力与聚类评估因子

为了有效实现客体的聚类，本书引入了引力场理论，通过计算概念之间的引力，发现相似概念。通过计算可知，引力越大，相似性越高。

定义 5：给定 oi，oj∈O，两客体的概念质量分别记为 mi，mj，概念距离记为rij，概念引力定义为g（oi，oj）=G（mimj/rij），其中G=1，为引力常量；m1=∑ak∈A（oi）H（ak）指的是概念中属性信息熵和。

为了评估聚类效果，本书给出了两个聚类评估因子，分别为聚类因子（Aggregation Gene，简称 AG）和噪声因子（Noise Gene，简称 NG）。

（四）基于概念相似的递归客体聚类算法

在此基础上，笔者提出了基于概念相似的递归客体聚类算法（Recursive Clustering Algorithm Based on similar Concept，简称 RCABC）。

该算法主要分为三部分：第1部分为客体属性约简（1—5行），并形成客体概念；第2部分为客体概念相似性分析，并形成类（6—19行）；第3部分为依据类内与类间聚合因素，评估聚类的好坏，若达不到系统要求，则调整相似度阈值σ，再次聚类，直到满足需求（20—40行）。时间复杂度为o（n lgn）。

递归客体聚类算法：

Input:O，A(objects set;Attribute set)

Output:Z(cluster set)

(1)for I=1 to|O|do

(2)begin(www.xing528.com)

(3)A=A(oi);Bi=AARBS(A);

(4)Mi=maxtrix(Bi);concept(oi)←M;

(5)endfor

(6)k=1;Z1={o1};

(7))for i=1 to|O|do

(8)begin

(9)if i＜＞1 then

(10)if oiis not yet assigned to a cluster then

(11)for j=i+1 to|O|do

(12)begin

(13)g=g(oi，oj);

(14)if g≥s then

(15)if ojis not yet assigned to a cluster then

(16)Zk←oj;

(17)endfor

(18)k=k+1;

(19)endfor

(20)gin=0;gout=0;gnoise=0;t=0;

(21)for i=1 to k do

(22)begin

(24)endfor

(25)for i=1 to k do

(26)begin

(27)for j=i+1 to k do

(28)begin

(29)gout=gout+g(Zi，Zj);

(30)endfor

(31)endfor

(32)for i=1 to|O|do

(33)begin

(34)if ojis not yet assigned to a cluster then

(37)endfor

(38)compute AG，NG;

(39)if AG ＜0;NG＜ω then s←s';goto 8;

(40)else output Z