当前位置：文档之家 › 一种自适应的混沌粒子群算法优化XML数据聚类策略

一种自适应的混沌粒子群算法优化XML数据聚类策略

  • 格式：pdf
  • 大小：446.23 KB
  • 文档页数：9

一种自适应的混沌粒子群算法优化XML数据聚类策略1刘波1，杨路明1，翟学敏2，邓云龙31中南大学信息学院，长沙（410083）2江南大学，江苏无锡（214122）3中南大学湘雅附三医院，长沙(410013)E-mail：ltbo99@，l-tb@摘要：针对海量XML文档数据挖掘进行聚类划分效率低的不足,本文尝试对XML数据聚类方法进行优化。

通过说明XML键及其聚类定义，结合混沌运动的特点融入一种新的基于混沌思想的粒子群优化算法，该算法以XML键为粒度利用混沌原理划分XML聚类时，通过提高自身聚类学习能力，增强对XML数据的全局寻优能力，改善聚类的收敛性；同时通过对权重因子的自适应地调整，更减少搜索局限及计算成本。

实验仿真表明，此算法不仅很大程度上避免了聚类过程停滞现象的发生，而且是一种有效的优化聚类方法。

关键词：XML数据库，XML键，混沌优化算法，自适应，粒子群优化算法中图分类号：TP301 文献识别码：A0. 引言随着互联网技术发展，XML作为一种具有灵活、开放、跨平台、跨语种等特点的文本标记描述语言被广泛用于信息的表达及交换,由此产生了海量XML文档，需要对这些文档进行查询、挖掘，提取有价值的信息，聚类是XML数据挖掘中的一种重要的分析手段，可以将数据对象归入到相应有意义的聚类中。

对于XML数据的聚类管理，XML文档本身的标签以及路径约束使其具有传统文档所没有的结构和层次特性,考虑到XML的结构信息,文献[1]利用相似路径进行XML聚类操作,通过对XML路径查询分类处理降低查询过程的IO页面处理,文献[2]则根据XML架构语义,结合路径相似性与路径权重系数进行XML文档聚类操作,这些都离不开对XML树进行相似性度量,其缺点是时间复杂度过高,一般为O(n3)，不适合多文档集处理；文献[3]则从XML文档结构入手，通过分析有序标签树结构、路径权重，利用各种树编辑距离理论提出树结构距离算法，降低XML嵌套层次,有利XML树间的匹配,但效果仍不甚理想,主要原因在于单纯的树“编辑距离”仅适合文档两两比较, 缺乏类原形描述与操作记忆力,针对以上方法的不足,本文尝试利用XML键与混沌原理、结合粒子群的有效记忆性探讨对XML文档进行自学习的聚类算法,希望有助于降低聚类过程中的计算规模。

该算法的主要过程是首先利用XML键及其约束条件求解XML文档集中的候选键信息,并组成有效的XML键组合，消除非关键信息造成的影响,然后以XML键组合信息为粒度,以类间距离大小为判断准则,利用粒子群算法寻找代价相似的XML文档集,再利用基于权重代价的XML文档相似性算法依次收集XML文档作为聚类结果，这一点与混沌原理的粗搜与细搜过程相似,而基于粒子群算法的聚类方法是以个体之间的协作和群体信息共享的基本模型为基础提出的一种自适应聚类结果 [4-5],这一特点与聚类过程中无须用户提供先验的分类知识，而是根据数据实际的分布情况得到自然的聚集结果相吻合。

作为进化计算的研究热点之一,目前已提出了多种改进PSO算法[6-8],但是这些算法大多着眼于PSO的参数选择或某个参数的动态修改策略,很少涉及其针对XML文档操作方面的应用1本课题是湖南信息职业学院科技创新项目（编号108652006011，名称：基于XML数据库压缩算法与概率查询分析及实现），同时本课题获得湖南省教育厅科研基金（编号05c671，名称：遗传算法参数设计）的资助。

与改进,为此本文以XML键为粒度,结合混沌原理, 提出针对XML文档一种自适应的混沌粒子群算法(ACPSO)聚类检测方法，为使ACPSO算法摆脱局部极小,提出粒子扰动策略,即根据运行时间,自动调整粒子的权重因子,从而提高XML文档聚类检测的速度和准确性。

1. 基于XML键约束的XML文档相似性代价度量为简化描述, 本文在研究XML树型结构中不特别区分元素和属性, 也不考虑树中叶结点的文本内容,毕竟在分析中,只有XPath轴及路径表达式才是重要的,这样容易度量XML文档的相似性。

本节首先基于路径表达式,在XML文档树定义的基础上给出XML键的定义及求解XML候选键的相应算法。

定义1(XML文档树)一棵XML文档树被定义为T=(V,chl,lab,val,Vr),其中V为XML文档树T中的节点集合,Vr为根结点,chl表子节点的集合,val表从集合V到E∪S∪A(E:元素名称集合,S:指代#PCDATA,A:属性名称集合)的映射函数。

针对XML树T及其对应的DTD,一个关键字就是一个对(H,{p1,p2,…,pn}),其中H是一个路径表达式Paths(T),{p1,p2,…,pn}是一个简单路径表达式的集合,其约束关系如下：取出任意两个节点(n1,n2)∈[[H]],对应两个节点集合对(n1[[pi]],n2[[pi]])，这两个集合分别是从n 1,n2沿着路径pi所到达的节点的集合。

定义2(XML键)给定DTD D=(E,A,P,R,r),任意的XML文档树T|=D,Paths(T)为文档树T上的路径集合,{p1x ,…,pxn}⊆Paths(T),如果FD XMLϕ(H,[p1x,…,p xn→Paths(T)])在D上成立,则称K:(H,[p1x ,…,pxn])在D上成立,并且不存在任何{p'1x,…,p'xn}⊂{p1x,…,p xn},使得(H,[p'1x ,…,p'xn→Paths(T)])也成立,称K(H,[p1x,…,pxn])为XML的一个候选键,其中H称上下文路径, {p1x ,…,pxn}称键路径。

定义3(XML候选键约束) )给定DTD D=(E,A,P,R,r),任意的XML文档树T|=D,Paths(T)为文档树T上的路径集合,Σ是FDXML 集,K是FDXML集Σ的候选键,当且仅当(1)K是Paths(T)中元素构成的集合；(2)存在路径P',P"使得(a)P',P"和K构成Paths(T)的一个划分；(b)∀P'i,P'i∈P',K→P'i；(c)∀P'j,P'j∈P",∃{p'1x,…,p'xn},使得{p'1x,…,p'xn}∪K→P'j；(3)K的任何真子集都不满足(1)和(2)。

根据上述的定义及约束条件,给出一个求解FDXML集Σ的候选键算法:输入:一个FDXML集Σ,路径集Paths(T)输出:Σ的一个候选健KFinding a Candidate Key for XML(Σ,Paths(T))(1)初始化:{LP:=左部路径集;RP:=右部路径集,DP:=双部路径集,EP:=外部路径集}；(2)P":=EP；(3)if DP=Φthen {K:=LP; return(K)；}else{ K:=LP∪{所有右部路径的左部路径};P':=RP；Σ:=Σ-{所有右部路径出现过的FDXML的约束}；while Σ≠Φ do{foreach(每个FDXML ：p1x,…,pxn→p1y,…,pymin Σ中){K:=K∪{ p1x,…,p }；Σ:=Σ-{ p1x ,…,pxn→p1y,…,pym}；foreach (p1y ,…,pym的FDXML:ϕ in RP){K:=K∪{ϕ的左部路径}；Σ:=Σ-ϕ；foreach(∀p1y,…,p ym的FD XML:ϕ' in LP){Σ:=Σ-ϕ'；} }}}}(4)return(K).<paper><conference><id/><title/><author/><date/></conference> </paper><paper><conference><id/><title/><authors><date/></conference> </paper><author/></authors>XML文档1XML文档21234512345paperconferenceid title6author date67paperconferenceid titleauthorauthors date图1 XML文档集图2 XML文档树集合Fig.1 XML document set Fig.2 XML document trees’ set为了减少单个键值的操作冲突,一般会选择相应一组XML键构成相应集合,如图1对应键{paper→conference→id, paper→conference→title}。

确定XML候选关键字后,就可以由确定的XML键组合进行XML文档聚类了,一个XML聚类就是彼此相似的一组XML文档对象所构成的集合[9],这一系列集合如何从海量XML文档中获取，主要分两步进行，首先以类间距离函数为适应值,利用混沌粒子群算法寻找代价相似的XML文档集,其次再利用XML文档相似性权重代价算法分类收集XML文档，在此首先论述XML文档的权重代价度量定义及相似性检测算法。

定义4(权重代价度量)主要是计算查询树与目标树之间的距离，即把XML键组合从查询树转换目标树的最小编辑操作代价的总和。

用X和Y分别表示两个XML文档,其表达式为：div (X,Y)=∑jijiv opt,))((cos (1)这里opi 为源树X上的节点vj上的操作，此外令o(opi)和θ(v j)是op i操作和节点v j的代价，则上式可更改为:div (X,Y)=∑j i,∆1(∑∀iiiiopow)(+))(jjjjvw∑∀θ) (2)其中wi ,wj是权重,∆是规范化因子。

针对(3)式主要考虑以下3种操作类型和3类节点特性:(1)o1:插入操作类型；(2)o2:删除操作类型；(3)o3:更新操作类型；(4)θ1:节点层次；(5)θ2:节点分支；(6)θ3:语义解释。

为了在给定应用领域能求得最适合的代价,应该使用自适应技术,下面给出基于自适应的权重代价度量算法。

(1)假设存有n个XML文档集{Ii}(1≤i≤n),每个集合包含三元组{Q i,A i,L i},其中Q i：查询请求，Ai ：近似结果，Li=⎩⎨⎧1无关与相关与iiiiAQAQ(2)存在目标函数u和它的近似函数−u,根据XML键抽取θi和应用领域进行计算。

初始化目标函数u(Ir ),如u(Ir)=⎩⎨⎧−+111Li==iL计算近似值:−u(Ii)=∑=kiiiw1θ那么相应基于权重代价的XML文档进行相似性度量算法如下：算法:基于权重代价的XML文档相似性度量输入：文档树I1,I2输出：文档树X，Y的相似性div (I1,I2)Similarity_Weight_Cost(I1,I2)(1)初始化系数：权重值wi,θi,η,u(I i);(2)while !(终止条件)(3){foreach (Path(Ii) in Path(T)){(4)−u(Ii)=w1θ1+w2θ2+…+ wkθk;(5)∆u i=u(I i)-−u(Ii);(6)−iw=wi+η×∆u i×θi;//η用来调整权重范围(7)∆w i=−iw-wi;}(8)}(9)div (I1,I2)=k1∑=kiiiw1θ;(10)r eturn div (I1,I2)终止条件：若∆w i为0，或小于某个指定的阈值,或超过预先指定的循环次数。

合集下载

PSO_TSP问题综述

PSO_TSP问题综述

科技论坛PSO-TSP 问题综述傅刚（福州职业技术学院，福建福州350001）1TSP 问题介绍旅行商问题（Traveling Salesman Problem ）是一个典型的组合优化问题，旅行商问题描述如下：给定n 个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最逗路线。

其图论描述为：设给定带权图G=（V ，E ），其中V 为顶点集，E 为各顶点相互连接组成的弧集，已知各顶点间连接距离，要求确定一条最短Hamil －ton 回路，即遍历所有顶点一次且仅一次的最短回路。

设dij 为城市i 与j 之间的距离，即弧（i ，j ）的长度，引入变量：x ij1，若旅行商访问城市i 后访问城市j ；0，否则。

则TSP 的目标函数为minZ=ni ，j=1Σx ij d ijTSP 问题的求最优化解是很困难的。

对于有着n 个城市的TSP 问题，存在着（n-1）!/2条可能的路径。

随着城市数目n 的增长，可能路径的数目以n 的指数倍增加，如果使用穷举法搜索，需要考虑所以的可能情况，并两两比较，找出最优解，那么可搜索的路径及其距离之和的计算量将正比于n!/2，算法的复杂度呈指数增长，人们把这类问题称为“NP 完全问题”。

由于TSP 具有实际应用价值，例如：城市管道铺设优化、物流等行业中的车辆调度优化、制造业中的切割路径优化以及电力系统配电网络重构等现实生活中的很多优化问题都可以归结为TSP 模型来求解，目前TSP 应用的一个重要方面就是无人飞机的航路设计问题，即事先针对敌方防御区内的威胁部署和目标的分布情况，对无人作战飞机的飞行航路进行整体规划设计，可以综合减小被敌方发现和反击的可能性、降低耗油量，从而显著提高UCAV 执行对地攻击（或侦察）任务的成功率。

目前求解TSP 的主要方法有最近邻域搜索算法、模拟退火算法、遗传算法、Hopfield 神经网络算法和蚁群算法等。

本文主要介绍用粒子群优化算法解决TSP 问题及其各种改进方法。

群智能优化算法及其应用

群智能优化算法及其应用

群智能优化算法及其应用随着复杂问题的不断涌现，传统优化算法往往难以求解出满意解。

而群智能优化算法作为一种新型的优化策略，以其强大的自组织、协作和学习能力，在解决这类问题上具有显著优势。

本文将介绍群智能优化算法的背景、概念及其应用，展望未来的研究方向和挑战。

群智能优化算法是一类基于群体行为启发的优化算法，通过模拟自然界中生物群体觅食、协作等行为来求解优化问题。

这类算法包括蚁群算法、粒子群算法、蜂群算法等，它们都具有以下特点：群体协作：群智能优化算法利用群体中个体的协作和信息共享机制，共同寻找最优解。

分布式计算：群智能优化算法采用分布式计算方式，将问题分解成若干个子问题，交由不同个体进行处理。

自适应调整：群智能优化算法能够根据问题的特性和解的分布情况，自适应地调整算法参数和策略。

蚁群算法是一种模拟蚂蚁觅食行为的优化算法，通过蚂蚁之间留下的信息素来指导寻优过程。

其应用领域广泛，包括函数优化、路径规划、任务调度等。

然而，蚁群算法易出现早熟收敛和信息素更新方式单一的问题。

粒子群算法是通过模拟鸟群飞行行为来求解优化问题的一种算法，每个粒子代表一个潜在解。

粒子群算法在求解多目标优化、约束优化等问题上具有较好表现，但可能陷入局部最优解。

蜂群算法是一种模拟蜜蜂觅食和酿蜜行为的优化算法，通过蜜蜂之间的协作和信息共享来寻找最优解。

蜂群算法在处理复杂优化问题时具有较高效率和鲁棒性，适用于多目标优化、约束优化等领域。

群智能优化算法在解决优化问题上具有广泛应用，除了上述的蚁群算法、粒子群算法和蜂群算法，还包括遗传算法、模拟退火算法、灰色狼群算法等。

这些算法在解决不同类型的问题时具有各自的优势和适用范围。

遗传算法是模拟生物进化过程的优化算法，通过选择、交叉和变异操作来产生新的解。

遗传算法在求解大规模、高维度优化问题时具有较好表现，但可能存在早熟收敛和计算效率低下的问题。

模拟退火算法是模拟固体退火过程的优化算法，通过引入随机因素来避免陷入局部最优解。

自适应粒子群算法

自适应粒子群算法

自适应粒子群算法自适应粒子群算法（Adaptive Particle Swarm Optimization，APSO）是一种基于群体智能的优化算法，它模拟了鸟群觅食行为中的信息共享和合作策略，通过不断调整粒子的位置和速度来寻找最优解。

在APSO算法中，粒子代表了解的候选解，它们通过不断更新自身的位置和速度来搜索最佳解。

与传统的粒子群算法不同之处在于，APSO算法引入了自适应机制，使得粒子的搜索能力和适应度可以根据问题的特点进行调整。

APSO算法需要初始化一组粒子的位置和速度。

初始位置可以通过随机生成或根据问题的特点进行设定。

初始速度可以根据粒子的邻居粒子的位置和速度进行计算。

然后，APSO算法通过迭代更新粒子的位置和速度，直到达到停止条件。

在每次迭代中，粒子根据自身的历史最优解和全局最优解来更新速度和位置。

具体而言，粒子的速度更新公式如下：\[ V_i(t+1) = w \cdot V_i(t) + c_1 \cdot rand() \cdot (Pbest_i(t) - X_i(t)) + c_2 \cdot rand() \cdot (Gbest(t) - X_i(t)) \]其中，\(V_i(t+1)\)为粒子的速度，\(w\)为惯性权重，\(V_i(t)\)为上一次迭代的速度，\(c_1\)和\(c_2\)为学习因子，\(rand()\)为随机数函数，\(Pbest_i(t)\)为粒子的历史最优解，\(X_i(t)\)为粒子的当前位置，\(Gbest(t)\)为群体的全局最优解。

粒子的位置更新公式如下：\[ X_i(t+1) = X_i(t) + V_i(t+1) \]在更新完所有粒子的位置和速度后，需要计算粒子的适应度，并更新粒子的历史最优解和全局最优解。

适应度的计算方法根据具体问题而定。

APSO算法引入了自适应机制，通过动态调整学习因子和惯性权重来提高搜索效率。

学习因子可以根据粒子的适应度进行调整，适应度越高，学习因子越小，粒子的搜索范围越小；适应度越低，学习因子越大，粒子的搜索范围越大。

混沌映射优化粒子群

混沌映射优化粒子群

混沌映射优化粒子群
混沌映射优化粒子群算法是一种基于混沌映射的粒子群优化算法。

混沌映射，如Logistic 映射，被用于生成随机数序列，以增加算法的随机性和多样性。

该算法通过设计一种无质量的粒子来模拟鸟群中的鸟，每个粒子仅具有两个属性：速度和位置。

然后通过迭代找到最优解。

在每一次的迭代中，粒子通过跟踪两个“极值”(pbest，gbest)来更新自己。

在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。

混沌映射优化粒子群算法的具体步骤如下：
1. 初始化粒子群，包括每个粒子的位置和速度。

2. 采用混沌映射生成随机数序列，用来更新每个粒子的速度和位置。

3. 根据粒子的当前位置和历史最优位置来更新粒子的历史最优位置。

4. 根据所有粒子的历史最优位置来更新全局最优位置。

5. 根据更新后的速度和位置，继续迭代。

该算法具有简单、容易实现并且没有许多参数的调节等优势，已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。