基于LLPCA的模拟退火聚类算法

《基于LLPCA的模拟退火聚类算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2.1基于LLPCA的模拟退火聚类算法(LLPCASAA)Li等人[38]提出的图像分类方法虽然考虑了图像分类过程中的不同类图像间的“敏感”特征不同的性质，但是他们所采用的K均值聚类方法难以避免局部极值“陷阱”。为了解决这一问题，作者提出了一种基于LLPCA的模拟退火聚类方法(LLPCASAA-LocalLinearPCASimulatedAnnealingclusteringAlgorithm)。该方法解决了LLPCA聚类方法中的应用导致的局部极值“陷阱”问题以及分类结果与数据的初始分类相关的缺点。在充分降温前提下，该方法可以保证到达全局最优点，从而达到了提高聚类性能的目的。3

2、.2.4.1数据预处理数据预处理的目的在于消除抽取的图像特征分量之间量纲不一致问题。量纲不一致会引起在图像相似性度量过程中，某些图像特征分量严重影响图像相似性度量值，从而导致误判。为了解决这一问题，我们采用归一化方法统一不同图像特征分量的量纲。设一个包含幅图像的数据库，第幅图像对应的图像特征向量表示为：(3-20)其中为图像特征向量的维数。数据库图像的图像特征分量的平均距离可以通过下式计算：(3-21)表示第个向量与其它向量的距离度量结果。我们还可以采用Ortega等人[89]提出的正态归一法进行归一化处理：(3-22)其中为标准方差，定义为：(3-23)若特征间的聚类分布为标准正态

3、分布，可以证明当时，特征值落在之间的概率为；而当时，概率为。如果我们无法预先判定该聚类是否满足正态分布，则可采用以下不等式：(3-24)根据上述概率表达式，当时，距离值落入的概率为。当时，为。通过(3-25)式的线性变换可以确保绝大多数距离值落在之间。根据标准正态分布理论，特征值落在范围外的概率是极少的。因此，在范围之外的特征值被映射到极值部分。(3-25)归一化处理是图像检索系统中重要的预处理步骤，它能有效地保证所有的图像特征在距离度量过程中的量纲一致性，从而使检索结果更加准确。3.2.4.1退火参数设定由Metropolis准则可以得到以下退火准则：(3-26)其中为类和的类内距

4、离：(3-27)退火过程是一个温度逐步下降的过程。一般采用下面的公式来计算新的温度。(3-28)其中为降温系数。算法实现过程中有关模拟退火的相关参数，例如凝固温度，降温系数，冷却进度表长度(Markov链的长度)，以及中止条件等，是决定聚类结果的关键。下面分别加以讨论。1．冷却进度表冷却进度表是一组控制算法进程的参数。用来控制模拟退火算法的渐进收敛性，使算法在有限执行过程中返回一个近似最优解。冷却进度表是影响模拟退火算法实验性能的重要因素，其合理选取是算法成功的关键。这里，我们首先给出冷却进度表的概念，然后详细讨论其参数的选择。模拟退火算法渐进收敛性的逼近通常采用以下方法实现：用控制

5、参数的一个递减有限序列，，以及与之对应的链长为的有限长齐次Markov链序列控制算法进程。为此需要确定一个确保算法收敛的参数集，这个参数集北称之为冷却进度表。定义3.1：冷却进度表包含以下参数：1)控制参数初值；2)控制参数衰减函数；3)控制参数终值；4)Markov链长。构造冷却进度表的核心概念是准平衡(quasi-equilibrium)，其定义如下：定义3.2：设是第个Markov链的长度，是对应的第个控制参数值。称模拟退火算法达到准平衡，若在第个Markov链的次变换后，解的概率分布充分逼近时的平稳分布，亦即：(3-29)对某些确定的正数成立。对于任意小的正数，算法至少要进行

6、解空间规模的平方次变换才能达到准平衡。此外，对多数问题而言，解空间规模是问题规模的指数倍，正如在货郎担问题中，为城市数。因此对平稳分别的任意逼近导致退火算法需要指数倍执行时间。5)Markov链选择；Markov链的长度是决定退火过程中接受次优解的数目。如果链长过短，无法跳出局部极值“陷阱”。而链长过长则会增加退火时间。康立山等人[122]提出了模拟退火过程中Markov链最佳长度。该长度与特征数目相关，一般采用以下三种形式决定：1.，其中为特征维数；2.；3.采用一个多项式的方法来决定Markov链的长度。因此，根据检索系统中图像特征维数为48。为简单起见，算法中将Markov链长

7、定义为480。6)中止条件；模拟退火过程是一个温度逐步下降的过程，其中止条件为到达温度最低点。但是在聚类过程中，往往出现在没有到达最低温度时已经完成了聚类过程。继续按照最低温度作为终止条件只会增加聚类时间，对结果没有影响。根据实际应用情况，作者提出了以下聚类中止条件：l当每类图像的类间误差不变，且其类间误差大于小于其温度的改变度的时候就可以认为后面的温度变化所产生的聚类结果已经不能够满足其要求。l。迭代过程中，只要满足上面的任何一个条件就可中止退火过程。降