基于tsPSO 的聚类案例检索策略

王薇薇，王清心，桑海

0 引言

基于案例的推理(Case-based Reasoning,CBR)已经被广泛运用于各个领域，包括医学，矿业，以及问答系统等。竞争情报系统针对某一行业，收集相关的情报，并根据用户需求将信息推荐给用户。

由于CBR在不断解决问题的同时，越来越多的新范例被加入到范例库中，当范例数达到某一上限时就会产生沼泽问题(Swamping Problem)[1],为此我们必需对案例库进行必要的维护。

在本文中将采用带极值扰动的粒群优化(tsPSO)算法完成聚类，提高系统的查全率及有效性，将规模较大的案例库转化成规模较小的样本集合，方便维护，提高了查找的速度。

1 tsPSO的概述

粒群优化算法(particle swarm optimization,PSO)是一种基于群体搜索的算法，是Kennedy和Eberhar提出的，用于模拟鸟群社会，通过各个个体的竞争和协作来完成进化和寻优的过程。该算法具有收敛性快，运作简单等特点。但由于杂交，适应参数变化等原因，导致PSO及其复杂。而在文献[2]中已经证明了tsPSO的进化与速度无关。由下面的公式来指导粒子的运动：

其中ω为惯性系数，在这里 ω∈ [0.4,1]，pid为个体最佳，pgd为全局最佳。c1=c2=2，r1、r2为服从∪(0,1)随机分布。t0,tg分别为个体的极值和全局极值进化停滞步数；T0,Tg表示个体极值和全局极值需要扰动的停滞步数的阈值。其中

现设φ1=r1c1，φ2=r2c2，φ=φ1＋φ2，将式(1)改为一阶微分方程：

2 基于tsPSO的聚类算法

2.1 tsPSO适应度函数及聚类的优化

适应度函数的好坏直接影响了tsPSO聚类的效果，这里将所有案例到案例聚类中心的距离之和作为评价结果的适应度，而案例到中心案例之间的距离D(xi-ci)=1-sim，sim表示两个案例之间的相似度，0

n为聚类的个数。确定了适应度函数后，求解聚类的中心就是核心的问题，随机取出n个样本作为中心点，每个粒子优化通过公式(4)，重新计算各个聚类的中心。如c1表示一个聚类中心的位置，通过公式(4)则能很快的计算出c1的下一步的位置。从而不断的更新个体最优解及全局最优解，使各个粒子向最优的方向行进。

2.2 基于tsPSO算法的聚类规则

将案例库划分为n个聚类，方便维护，在同一聚类中各个粒子(即案例)应当满足一下规则：

规则 1：如果两个案例相似度大过阈值sim'时，则认为两者是同一案例不存储。

规则2：各个聚类之间只能有一个交点或没有交点。

由于本文采用的是欧氏距离计算案例到中心的距离，在N维上可能会导致两个聚类之间产生一个交集区域。如一个案例xi他属于ci聚类中，而此时xi到cj的聚类的距离小于离cj最远点到cj的距离，这是ci与cj之间就存在着交集。因为每个聚类的半径可以计算得到，这时如果两个聚类发生了交集，则使用直线弹离策略。两个聚类的中心相互弹开，距离与聚类的半径成正比。

规则3：噪音应该尽可能的少。

在这里噪声为那些不在各个聚类中的案例，称其为噪音案例，当噪音案例与聚类的案例之比超过某一阈值则认为噪音案例超标，重新进行聚类。

规则 4：当聚类时案例与中心案例之间的距离小于sim'时，则不将其放入该聚类中如：现有案例case1及聚类好的案例集c1,c2,c3...cn，如果case1与到其最短中心距离ci(1

2.3 基于tsPSO算法的聚类实现步骤

基于tsPSO算法聚类算法如下所述：

(1) 随机初始化各个粒子(案例)；

(2) 计算出当前各个粒子的最佳及全局最佳；

(3) 利用公式(4)更新各个粒子之间的位置；

(4) 计算各个粒子的适应度，判断是否有满足规则2，不满足则按上文所述进行弹离操作，更新全局最优解；

(5) 判断是否满足结束条件，如满足则跳向(6)，否则跳向(3);

(6) 输出结果；

这时就会从结果集中得到n个聚类，从而形成一个个小的案例库，为后面案例的快速查询提供了必要的准备。

3 案例检索的过程

本文采用的是异构案例库，从中找出与新增案例最相似的聚类中心cm，案例检索的策略归结如下：

（1）现有新生成的案例 targetCase，将其与聚类集合collection的各个案例进行比较并计算出各个距离dis1,dis2,...,disn。

（2）将计算出的案例之间的相似度放入list1中，并按相似度从大到小的顺序将该聚类中的各个案例推荐给用户。

（3）根据用户反馈，判断推荐是否成功，如果成功则判断是否满足规则1，如果该新增案例与聚类中的某一案例相似度过高，则认为是同一案例，不存储，再判断是否满足规则4，如果该案例与每个聚类中心的相似度都小于sim'时则将该案例放入listtmp中，最后判断是否满足规则 3，如果不满足，则重新聚类。

（4）如果都满足则将该案例存储。

4 实验与讨论

实验是以竞争情报系统作为实践的平台，现有案例2589个，在SSH框架下实现上述系统，并将带极值扰动粒群算法(tsPSO)与简单粒群算法(PSO)，自适应的蚁群算法(AAC)进行比较，以体现它的优越性，硬件环境是在 Intel Pentium4 1.6GHz 1.43GB的机子上完成测试及比对，实验结果如表1所示:

表1 各个聚类算法比对图

从表1可以看出tsPSO算法在聚类时间上及错误率上具有很好的性能，能够有效地提高速度及准确率。同时在基于tsPSO算法的聚类的结果上进行检索，只需花不到900ms大大降低了检索的时间，提高了效率。

5 结束语

本文针对在案例检索时，如果案例库过大容易导致沼问题，为此提出了基于tsPSO算法的案例检索策略，并且有效的解决了这个问题，使得在案例的维护及检索的速度和查全率上有了很大的提高。经实验结果证明该算法是可行的，并具有很好的效果。

[1]Francis A G Ram A．The Utility Problem in Case—based Reasoning[C]．In Proceedings AAAI～93 Case—based Reasoning Workshop，1993

[2]Clerc M. The swarm and the queen: Towards a deterministic and adaptive particle swarm optimization[j]. In:Proc. of the ICEC. Washington, 1999. 1951−1957.

[3]胡旺，李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报,2007,18(4):861-868.

[4]Van den Bergh F, Engelbrecht AP. Cooperative learning in neural networks using particle swarm optimizers[j].South African Computer Journal, 2000(11):84-90.