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

3.2.1 基于LLPCA的模拟退火聚类算法(LLPCASAA)Li等人38提出的图像分类方法虽然考虑了图像分类过程中的不同类图像间的“敏感”特征不同的性质，但是他们所采用的K均值聚类方法难以避免局部极值“陷阱”。为了解决这一问题，作者提出了一种基于LLPCA的模拟退火聚类方法(LLPCASAA-Local Linear PCA Simulated Annealing clustering Algorithm)。该方法解决了LLPCA聚类方法中的应用导致的局部极值“陷阱”问题以及分类结果与数据的初始分类相关的缺点。在充分降温前提下，该方法可以保证到达全局最优点，从而达到了提高聚类性能的目的。3.2.4.1 数据预处理数据预处理的目的在于消除抽取的图像特征分量之间量纲不一致问题。量纲不一致会引起在图像相似性度量过程中，某些图像特征分量严重影响图像相似性度量值，从而导致误判。为了解决这一问题，我们采用归一化方法统一不同图像特征分量的量纲。设一个包含幅图像的数据库，第幅图像对应的图像特征向量表示为： (3-20)其中为图像特征向量的维数。数据库图像的图像特征分量的平均距离可以通过下式计算： (3-21)表示第个向量与其它向量的距离度量结果。我们还可以采用Ortega等人89提出的正态归一法进行归一化处理：(3-22)其中为标准方差，定义为：(3-23)若特征间的聚类分布为标准正态分布，可以证明当时，特征值落在之间的概率为；而当时，概率为。如果我们无法预先判定该聚类是否满足正态分布，则可采用以下不等式：(3-24)根据上述概率表达式，当时，距离值落入的概率为。当时，为。通过(3-25)式的线性变换可以确保绝大多数距离值落在之间。根据标准正态分布理论，特征值落在范围外的概率是极少的。因此，在范围之外的特征值被映射到极值部分。(3-25)归一化处理是图像检索系统中重要的预处理步骤，它能有效地保证所有的图像特征在距离度量过程中的量纲一致性，从而使检索结果更加准确。3.2.4.2 退火参数设定由Metropolis准则可以得到以下退火准则：(3-26)其中为类和的类内距离：(3-27)退火过程是一个温度逐步下降的过程。一般采用下面的公式来计算新的温度。(3-28)其中为降温系数。算法实现过程中有关模拟退火的相关参数，例如凝固温度，降温系数，冷却进度表长度(Markov链的长度)，以及中止条件等，是决定聚类结果的关键。下面分别加以讨论。1 冷却进度表冷却进度表是一组控制算法进程的参数。用来控制模拟退火算法的渐进收敛性，使算法在有限执行过程中返回一个近似最优解。冷却进度表是影响模拟退火算法实验性能的重要因素，其合理选取是算法成功的关键。这里，我们首先给出冷却进度表的概念，然后详细讨论其参数的选择。模拟退火算法渐进收敛性的逼近通常采用以下方法实现：用控制参数的一个递减有限序列，以及与之对应的链长为的有限长齐次Markov链序列控制算法进程。为此需要确定一个确保算法收敛的参数集，这个参数集北称之为冷却进度表。定义3.1：冷却进度表包含以下参数：1) 控制参数初值；2) 控制参数衰减函数；3) 控制参数终值；4) Markov链长。构造冷却进度表的核心概念是准平衡(quasi-equilibrium)，其定义如下：定义3.2：设是第个Markov链的长度，是对应的第个控制参数值。称模拟退火算法达到准平衡，若在第个Markov链的次变换后，解的概率分布充分逼近时的平稳分布，亦即：(3-29)对某些确定的正数成立。对于任意小的正数，算法至少要进行解空间规模的平方次变换才能达到准平衡。此外，对多数问题而言，解空间规模是问题规模的指数倍，正如在货郎担问题中，为城市数。因此对平稳分别的任意逼近导致退火算法需要指数倍执行时间。5) Markov链选择；Markov链的长度是决定退火过程中接受次优解的数目。如果链长过短，无法跳出局部极值“陷阱”。而链长过长则会增加退火时间。康立山等人122提出了模拟退火过程中Markov链最佳长度。该长度与特征数目相关，一般采用以下三种形式决定：1. ，其中为特征维数；2. ；3. 采用一个多项式的方法来决定Markov链的长度。因此，根据检索系统中图像特征维数为48。为简单起见，算法中将Markov链长定义为480。6) 中止条件；模拟退火过程是一个温度逐步下降的过程，其中止条件为到达温度最低点。但是在聚类过程中，往往出现在没有到达最低温度时已经完成了聚类过程。继续按照最低温度作为终止条件只会增加聚类时间，对结果没有影响。根据实际应用情况，作者提出了以下聚类中止条件：l 当每类图像的类间误差不变，且其类间误差大于小于其温度的改变度的时候就可以认为后面的温度变化所产生的聚类结果已经不能够满足其要求。l 。迭代过程中，只要满足上面的任何一个条件就可中止退火过程。降温系数的选择是模拟退火方法中决定数据聚类过程是否能够跳过局部极值的一个重要的因素。如果降温系数过小，则会增大聚类时间，如果降温系数过大，则会导致无法跳出局部极值，引起“淬火”现象。3.2.4.3 LLPCASAA算法流程下面给出LLPCASAA算法的具体实现步骤：1 设定起始温度，凝固温度，以及Markov链长，降温系数； 2 均匀分割图像数据为个类；3 由 (3-16) 式计算出每类的前个MEF；4 初始化Markov链；5 选择任意两个类别，将类中的某个图像特征向量，放入类中；6 重新计算两类的MEF；7 根据 (3-27) 式计算类间距离；8 如果，保存聚类结果。，转步骤5。9 根据 (3-26) 式计算是否接受计算结果；10 ，如果则转步骤5，否则转第11步；11 根据 (3-28) 式计算下一步温度；12 如果，转步骤4；否则转第12步；13 输出每类的样本以及其MEF；14 回溯所有的聚类结果，选择最优聚类结果作为最终结果。其中初始的聚类数目，一般人为根据图像库中的图像类型确定。3.2.2 实验结果与分析1 实验图像库建立为检验LLPCASAA方法的聚类性能，我们在现有图像数据基础上建立了两个实验用图像库：MIT图像库123以及自建图像库。这两类图像库均为纹理图像库。鉴于MIT图像库中图像较少，我们将MIT图像库中每幅纹理图像分割为4幅子图像，图3-1显示了其中部分纹理图像。自建库包含六类共1139幅纹理图像。实验中，作者通过对这两个图像数据库的图像所进行的聚类试验来检验LLPCASAA方法的聚类性能。2 图像特征抽取图像视觉特征主要包括图像颜色特征、形状特征以及纹理特征等。在本实验中，我们选择纹理特征作为提取的图像特征。纹理特征的表示方法主要有共生矩阵，Gabor滤波器等。Wu等人124认为使用Gabor滤波器方法提取出的纹理特征较共生矩阵的方法提取出的纹理特征检索效果更好。因此在实验中，作者采用Gabor滤波器抽取纹理特征。对于一幅图像, 其Gabor变换定义为：，(3-30)其中和是滤波器的尺度。自相关函数是一组通过放大及旋转后的母小波函数，由(3-31)式确定。，(3-31)其中是调制频率，分别代表,方向的方差。我们选用不同尺度和方向的均值和均方差作为图像纹理的特征构成图像特征向量。(3-32)其中，代表六个方向(，)。，代表四个尺度(1,2,3,4)。 (a)树皮(b)水(c)沙地(d)食物图3-1 MIT库中部分典型纹理图像(a)地毯(b)木门(c)木纹(d)墙纸(e)食物图3-2 自建库中部分典型纹理图像3 聚类性能评估聚类性能的评判方法很多。在实验过程中，我们将误分率、重建均方误差作为聚类方法性能的评判标准。其中误分率的计算方法如下：人工将图像分为类，每类含个模式（对象）。实施分类后，聚类算法生成类，每类含个模式。在类和对应的类中，我们定义它们的误分率为：(3-33)表3-1-表3-2分别给出了MEF3，凝固温度，初始温度为，降温系数以及Markov链的长度的情况下，LLPCA和LLPCASA两种聚类方法针对MIT图像库中图像的聚类结果，其中反馈图像数目为30。表3-3-表3-4显示了当MEF3，凝固温度，初始温度为，降温系数以及Markov链的长度的情况下，LLPCA和LLPCASA两种聚类方法针对自建图像库图像的聚类结果，其中反馈图像数目为30。 表3-1：MIT库LLPCA方法聚类结果树皮20%11.43%11.43%2.86%2.86%2.86%48.57%砖25.81%29.03%32.26%12.9%0%0%0%纤维30.3%0%15.15%15.15%19.7%16.67%3.03%食物2.78%0%0%50%5.56%27.78%11.11%沙地4.16%66.67%0%20.83%0%0%8.33%水0%78.57%7.14%14.29%0%0%0%金属0%0%0%0%20%0%80%表3-2：MIT库LLPCASA方法聚类结果树皮90.63%000009.38%砖21.88%46.88%00012.5%18.75%纤维17.65%035.29%17.65%17.65%011.77%食物8.33%013.89%77.78%000沙地00000100%0水10.71%0000089.29%金属40%00060%00表3-3：自建库LLPCA方法聚类结果木纹80.951.90%2.86%5.71%2.86%5.71%食物14,61%31.96%16.44%10.05%12.79%14.16%地毯44.38%0.51%36.22%0.51%8.67%9.69%木门0.37%34.32%0.74%42.07%2.58%19.93%瓷砖8.91%8.33%9.20%11.21%48.56%13.79%墙纸5.53%12.06%3.52%34.67%5.53%38.69%表3-4：LLPCASAA方法聚类结果木纹23.8129.52046.67%00食物27.40%26.03%031.96%3.65%10.96%地毯18.37%0.51%077.55%03.57%木门13.28%29.89%4.06%6.27%12.92%33.58%瓷砖20.40%19.654%048.56%6.32%5.17%墙纸18.08%10.05%23.12%6.53%26.63%15.58%表3-5：MIT库重建均方误差距离结果LLPCA方法LLPCASAA方法树皮288.3727263.6726砖297.921264.832纤维208.3293189.1389食物254.1307236.4234沙地285.7805245.4975水334.0503297.6872金属258.972248.382表3-6：自建库重建均方误差距离结果LLPCA方法LLPCASAA方法木纹530.2718478.0912食物131.469098.0912地毯60.325356.9827木门120.5089110.5528瓷砖460.1884443.6154墙纸684.9337642.5284(a)LLPCA方法(b)LLPCASAA方法图3-3 MIT库图像聚类结果示意图所有检索结果图像按照从左到右，自上而下的顺序排列(a)LLPCA方法(b)LLPCASAA方法图3-4 自建库图像聚类结果示意图通过表3-1表3-4的对比实验可以看出，采用LLPCASAA方法的聚类效果优于LLPCA方法的聚类效果。 。到底。，且MIT数据库的分类效果优于自建数据库的分类结果。但是我们也发现，在一部分图像聚类过程中，其结果出现了一些波动。这一点在自建库中特别明显。这主要是由于自建库更多是根据用户的主观判断而建立的图像库，其图像特征的分布离散度比MIT图像库更大。图3-3与图3-4显示了不同图像库中采用不同聚类算法得到的一个聚类结果。由其聚类结果可以发现LLPCASAA方法较LLPCA方法上对图像数据的分类性能更接近人类视觉感知。例如，图3-3中木纹图像在LLPCASAA方法中出现了减少的情况，表明这种分类结果更加符合人类心理感知。由上述的模拟退火理论以及模拟退火聚类方法，我们知道降温系数在统计过程中占据重要地位。只有充分的降温过程才能够保证最优的聚类结果。为此，我们在不同的降温系数下(；)，分别进行聚类实验以讨论降温系数对聚类结果的影响。表3-7 不同的降温系数下MIT图像库重建均方误差树皮263.6726263.6726271.5729288.3727砖264.832264.832281.692297.921纤维189.1389189.1389195.8399208.3293食物236.4234236.4234243.3633254.1307沙地245.4975245.4975258.1937285.7805水297.6872297.6872310.0316334.0503金属248.382248.382253.972258.972由表3-7可以发现，当降温系数低于0.95，不同的降温系数其聚类的重建均方误差距离也不相同。如果降温系数过低，如，则只能达到LLPCA方法的聚类结果。甚至会出现无法得到一个优于LLPCA方法的聚类结果。这表明选择一个恰当的降温系数能够得到较好的聚类结果，而降温系数的选择不当，特别是降温系数过大的情况下，则会导致无法得到最优聚类结果。通过上面的试验结果可以发现，当降温系数在0.95以上的时候，其误差