模糊聚类

模糊聚类（通用11篇）

模糊聚类 篇1

摘要：基于模糊商空间的模糊C-均值算法 (QFCM) 是在模糊商空间和模糊模糊C-均值 (FCM) 的基础上提出的。通过引入相似函数并构造出归一化距离, 得到模糊商空间的分层递阶的结构, 在此基础上提出了基于粒度思想的准则函数并选择出一个最佳层次, 从而确定聚类的个数, 并选择具有相似度高的样本作为初始聚类中心, 结合鲁棒性统计观点运用归一化距离来替代FCM目标函数中的欧式距离度量, 提出了QFCM算法。实验证明与传统的算法比较, QFCM算法能够自动确定最佳聚类数目, 发现大小不均的聚类, 迭代次数少, 有效地消除了传统FCM算法对初始值敏感, 提高了算法的稳定性和准确率。

关键词：模糊商空间,归一化距离,分层递阶结构,模糊C均值聚类,聚类中心

1模糊商空间基础

定义1设R∈F (X×X) , ∀x, y, z∈X, 有

(1) 自反性:R (x, x) =1

(2) 对称性:R (x, y) =R (y, x)

(3) 传递性:R (x, z) ≥supy (min (R (x, y) , R (y, z) )

命题1设R是X上的一个模糊等价关系, 若定义∀x, y∈X, x～y⇔R (x, y) =1, 则关系“～”是X上的一个普通的等价关系, 令其对应的商空间为[X]。

定义2设R是X上的一个模糊相似关系, 对于∀λ∈[0, 1], Rλ为R的截关系。Dλ={ (x, y) |∃x=x1, x2, …, xm=y, (xi, xi+1) ∈R, i=1, 2, …m-1}则称Dλ是由X上的Rλ引导出来关系, 其中Dλ是一个等价关系。

定义3给定X上的一个距离d, 若满足:

(1) ∀x, y∈X, 0≤d (x, y) ≤1

(2) ∀x, y, z∈X, 在距离序列{d (x, y) , d (y, z) , d (z, x) }中, 任一个值不超过另外两个的最大值, 则称d为X上的一个等腰归一化距离。同时也称 (1) 为归一化条件, (2) 为等腰条件。若X上的距离d仅满足条件 (1) , 则称d为X上的归一化距离。

定义4给定X上的2个粒度X (λ1) 、X (λ2) , 若满足:

(1) 若∀x∈X, 都有[x]λ1⊆[x]λ2, 则称粒度X (λ2) 不比X (λ1) 细, 记为X (λ2) ≤X (λ1) ;

(2) 若X (λ2) ≤X (λ1) , 且存在x0∈X, 使得[x0]λ1⊆[x0]λ2, 则称X (λ1) 比X (λ2) 细或称X (λ2) 是X (λ1) 的商空间, 记为X (λ2)

引理1若d∈D (X) , 则相应的粒度空间d (X) 构成一个有序集, 且∀λ1λ2∈[0, 1], λ1≤λ2, 有X (λ2) ≤X (λ1) ) , 特别地, ∀λ1λ2∈D, λ1<λ2, 有X (λ2)

如果所有λ按照从小到大排列形成一个序列{Sk}为0≤λ1<λ2<…<λk≤1则对应形成一个分层递阶结构序列{X (λ1) , X (λ2) , …, X (λk) }, 即一个有序粒度空间。

2基于模糊商空间原型的分析

通过引入相似函数来构造出模糊商空间的归一化距离, 从而可以构造出一个有序粒度空间。我们的目标是为FCM聚类提供强有力的初始化方法, 克服FCM算法对初始化中心敏感, 而且要人为的指定聚类数目的缺点。我们通过分析模糊商空间的距离函数的鲁棒性, 并引入基于粒度分析的聚类准则, 计算出最佳的粒度即某一个X (λ) 的商空间最为初始化的中心和最终类的数目, 因此我们选择模糊商空间的X (λ) 仅仅是作为一个可能性的聚类结果, 最后的结果通过QFCM算法得出。

2.1粒度空间的选择与初始中心选择

设λ∈{Sk}, 其对应的商空间为X (λ) ={Cundefined, Cundefined, …, Cundefinedm}, 所以对于∀i, j∈{1, 2, …, n}, 则存在着以下两种情况:①如果i, j属于同一个类, 则R (i, j) 衡量的是类内的相似度;②如果i, j不属于同一个类, 则R (i, j) 衡量的是类间的相似度。

因此我们提出基于粒度思想的准则函数, Scat (λ) 衡量X (λ) 的类内紧凑度, Sep (λ) 衡量X (λ) 的类间分离度。分别如下:

undefined

undefined

其中R (Cundefined, Cundefined) =R (i, j) , i∈Cundefined, j∈Cundefined。

一个好的聚类层次应尽可能的反映数据集的内在结构, 使得类内的样本尽可能的相似即Scat (λ) 尽可能的大, 同时还要求类间的个体尽可能不相似即Sep (λ) 尽可能的小。综合这两个方面, 可定义如下的聚类有效性指标undefined, 可见H (λ) 越小, 说明类内相似度越高, 类间差异性越大, 聚类结果越合理。

通过上面的准则函数, 我们可以得到一个在最佳的粒度层次, 可知类内有很好的紧凑型, 类间有很好的分离性, 因此我们把该粒度层次产生的类数作为FCM的聚类数目。

当一个粒度层次确定后, 可以得到m个类, 为了更好的定义m初始中心点, 定义以下函数undefined其中i∈{1, 2, …, m}, 因此我们只要找到每个类中的能使f (x) 最大的样本点作为中心点就可以, 可知f (x) 越大, 越接近聚类中心并且周围被很多点包围。

2.2基于模糊商空间的FCM均值聚类算法

Wu和Yang在鲁棒统计观点和影响函数基础上提出了一种新的非欧式距离以代替FCM和PCM中的欧式距离。在此基础上, 提出了基于模糊商空间下的归一化距离, 以使得该方法更有普遍性。

设R (x, y) 是一个模糊相似关系, 因此可以得到归一化距离为d (x, y) =1-R (x, y) , 从而用归一化距离代替FCM算法目标函数的欧式距离度量。设原空间样本集为, X={x1, x2, …, xn}, xj∈Rd, j=1, 2, …, n, 模糊商空间映射为Φ:x→Φ (x) , 则QFCM聚类的目标函数为:

undefined

其中undefined。

用Lagrange乘法子可得JQFCM最小化的必要条件是:

undefined (2)

undefined (3)

从 (3) 中可以得出离中心点较近的给了较大的相似值, 离中心点较远的给了较小的权值, 可知归一化距离能更好的反映样本与聚类中心的远近。

在面对实际问题时, 只要通过模糊相似关系, 构造出归一化距离, 并用该距离函数来定义模糊商空间的距离函数来构造有序粒度空间。本文选择exp (-β||x-y||2) 为相似函数, d (x, y) =1-exp (-β||x-y||2) 为X上的归一化距离。

QFCM算法:

Step1针对实际问题选择出适当的归一化距离函数;

Step2设置目标函数精度ε, 模糊指数m, 最大迭代次数Tm;

Step3根据准则函数H (λ) , 选出适当的层次, 得出聚类数目和初始聚类中心;

Step4置迭代次数t=0, 以Step3的结果作为初始聚类中心V (0) ;

Step5根据V (t) 按式 (2) 计算U (t) ;

Step6按 (3) 进一步调整类别中心V (t+1) ;

Step7检验||U (t) -U (t-1) ||<ε或t≥Tm, 则输出聚类结果, 否则t=t+1, 转Step5。

3实验结果

为了验证算法的有效性, 首先采用图1所示的一个二维数据集DataSet, 它是一个模拟数据集, 包含37个数据点, 数据分布呈现3个不同大小、密度的聚类。首先我们在模糊商空间下计算聚类的最佳层次和初始聚类中心, 并跟传统的FCM算法和文献中的随机选取的初始中心点的AFCM算法进行比较。从图2中可以看出在模糊商空间下得到的最佳层次的个数为3, 得到的初始中心点为12、28和34 (1.25, 0.68;2.81, 0.52;2.70, -0.20) 。

在确定聚类个数下, 采用传统的欧式距离的FCM进行聚类, 聚类结果如图3所示, 从图中可以看出FCM算法把右下方的两个小类合并成一个类, 而且把第一个大类分成2个类, 无法得到正确的聚类结果。从而也反映出了FCM算法忽略小类, 聚焦于大类, 在各类的大小不均的情况下, 无法得到正确的结果。下面对随机聚类中心的AFCM算法和QFCM算法分别聚类10次, 用聚类的平均准确率评价聚类结果的优越性, 准确率越高, 聚类结果的质量越高, 对于采用随机聚类中心的AFCM算法, 虽然有时能够得到正确的分类, 但如果中心选取的不当, 常常得到如图3和FCM算法一样的聚类结果, 而且缺乏稳定性。由于QFCM算法是选取具有代表性的点作为初始聚类中心, 这样初始中心更能够接近最终的聚类中心, 由于每次都是采取相同的初始聚类中心, 因此结果是稳定的, 每次的准确率为100%, 而且迭代次数比起采用随机初始中心的平均迭代次数低, 聚类结果如图4所示, QFCM和AFCM算法整体的性能比较如表1所示:

下面采用UCI数据库上的IRIS作为样本数据集, 它有4个属性组成, 包含3种植物种类, 每种有50个样本。

对于IRIS数据集, 在模糊商空间下得到聚类数为3性能指标最小如图5所示, 该层次下选择8、127和118作为的初始聚类中心 (5.0, 3.4, 1.5, 0.2;6.2, 2.8, 4.8, 1.8;7.7, 3.8, 6.7, 2.2) 。通过具有代表性的样本作为初始聚类中心, 克服了AFCM算法初始中心随机选取, 导致聚类结果不稳定的确定, 而且选择出的初始中心点比较接近实际的聚类中心, 更能够有效的减少迭代的次数。对随机聚类中心的AFCM算法和QFCM算法分别聚类10次, 用聚类的准确率评价聚类结果的优越性, 准确率越高, 表示聚类结果的质量越高, 如图6所示。

从图6中可以看出, 对于初始中心是随机选取的AFCM算法, 由于每次选取不同的随机值, 聚类结果也发生改变, 导致聚类结果的不稳定性, 平均准确率为79.59%;而QFCM算法, 是在模糊商空间下得出的具有代表性的点, 选取的初始中心更能够接近最终的聚类中心, 由于每次都是采取相同的初始聚类中心, 因此结果是稳定的, 每次的准确率为93.33%, QFCM和AFCM算法整体的性能比较如表2所示:

4结束语

本文在模糊商空间的基础上, 通过粒度准则函数选出一个适当的层次, 进而选出一组优化的初始聚类中心, 在目标函数中充分考虑各个样本对不同聚类中心的隶属度, 使得算法更有鲁棒性。实验表明, QFCM算法可以发现不同大小的聚类结构, 而且稳定性和准确度得到了较大的提高, 同时降低了迭代次数。

参考文献

[1]DUDA R, HART P, STORK D.Pattern Classification (2nd Edi-tion) [M].New York, USA:John Wiley&Sons, 2001.

[2]张铃, 张钹.模糊商空间理论 (模糊粒度计算方法) [J].软件学报, 2003 (4) .

[3]毛军军, 张铃, 许义生.基于商空间和信息粒度的Fuzzy聚类分析[J].运筹与管理, 2004 (4) .

[4]唐旭清, 朱平, 程家兴.基于模糊商空间的聚类分析方法[J].软件学报, 2008 (4) .

[5]卜东波, 白硕, 李国杰.聚类/分类中的粒度原理[J].计算机学报, 2002 (8) .

[6]徐峰, 张铃.基于商空间的非均匀粒度聚类分析[J].计算机工程, 2005 (3) .

[7]王加阳, 彭岚琳.模糊λ商空间研究[J].计算机工程与应用, 2009 (6) .

[8]张新波.两阶段模糊C-均值聚类算法[J].电路与系统学报, 2005 (2) .

[9]WU KUOLONG, YANG MINSHENG.Alternative C-means clus-tering algorithms[J].Pattern Recognition, 2002 (10) .

[10]唐旭清, 朱平, 程家兴.基于归一化距离的结构聚类分析[J].模式识别与人工智能, 2009 (5) .

模糊聚类 篇2

基于模糊聚类分析的柴油机故障诊断研究

故障诊断的`基本方向是建立在基于先验知识和统计知识的基础上,通过模糊聚类分析找到故障征兆的聚类中心,然后通过模糊模式识别、判别新的故障征兆,达到对柴油机的故障诊断目的.文章对模糊聚类分析进行了重点研究.

作 者：冯二浩 潘宏侠 FENG Er-hao PAN Hong-xia 作者单位：中北大学机,械工程与自动化学院,山西,太原,030051刊 名：机械管理开发英文刊名：MECHANICAL MANAGEMENT AND DEVELOPMENT年，卷(期)：25(1)分类号：U464关键词：故障诊断 模糊聚类 FCM算法

模糊聚类 篇3

摘要：图像分割是路面裂纹识别的关键步骤，图像分割的效果直接影响路面裂纹的识别和分类。针对路面图像模糊核均值聚类算法中迭代结果容易出现局部最优的问题。提出一种改进的模糊核均值聚类算法，利用OTSU算法先获得最佳阈值，再通过该阈值得到各聚类的灰度均值，将这些均值作为聚类中心的初始值以实现模糊聚类算法。路面图像裂纹分割试验结果证明，提出的改进算法实现初始聚类中心的优化，避免算法出现局部最优，提高了分割效果，可以应用到路面裂纹图像分割的工程应用中。

关键词：图像分割；FCM算法；KFCM算法；路面裂纹

中图分类号：TP391.4文献标识码：A

1引言

基于图像法的路面裂纹识别通常采用三个步骤。第一个步骤是对原始路面图像滤波，通过滤波以抑制图像的噪声和增强裂纹信息。第二个步骤是对滤波后的图像进行分割处理以有效获取路面的裂纹信息。第三个步骤对分割后的图像进行特征提取和分类[1-2]。在这三个步骤中，图像分割是路面裂纹识别的关键步骤，图像分割的效果直接影响路面裂纹的识别和分类[3]。

图像分割是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法和基于特定理论的分割方法等[4-6]。

基于特定理论的图像分割算法发展较快，常见的算法有基于水平集的图像分割算法、基于图论的分割算法、基于形态学的分割算法、基于聚类分析的分割算法和基于模糊集理论的分割算法等[7-11]。

路面图像裂纹与背景对比度不大，裂纹细微变化较大，传统聚类算法对路面裂纹图像分割效果不好。将聚类算法与模糊理论结合以此来进行路面裂纹分割是目前一种比较有效的方法[9，12]。常见的模糊聚类算法有模糊均值聚类算法（FCM）和模糊核均值聚类算法（KFCM）[13-15]。FCM算法优点是能够进行图像自动分割，缺点是对聚类中心和隶属度的初始值较敏感，容易造成局部最优[16]。KFCM是用核模型代替FCM中的欧拉距离[17-18]。

本文结合FCM和KFCM的优势，对KFCM算法进行改进，以实现初始聚类中心的优化，避免算法出现局部最优。

4路面裂纹图像分割试验

为了验证本文的改进算法在路面图像分割方面的有效性，本文对路面图像分割算法进行了试验，对FCM算法，KFCM算法和本文提出改进算法的图像分割结果进行了对比。

试验硬件平台：Intel（R） Core2.0（TM） 2.93GHz处理器，3.0GB内存的工控机。软件开发环境：Visual C++ 6.0。

4.1纵向裂纹分割效果对比试验

为了验证本文提出的路面图像分割算法的有效性，分别进行了纵向裂纹和网状裂纹分割试验。对这两类裂纹分别采用FCM算法、KFCM算法和本文算法进行裂纹分割。

3种算法对纵向裂纹的分割效果如图1所示，图1的（a）为原始图像，（b）为FCM算法的分割结果，（c）为KFCM算法的分割结果，（d）为本文算法的分割结果。

4.2网状裂纹分割效果对比试验

3种算法对网状裂纹的分割效果如图2所示，图2的（a）为原始图像，（b）为FCM算法的分割结果，（c）为KFCM算法的分割结果，（d）为本文算法的分割结果。

采用本文提出的方法进行路面裂纹图像分割试验，本文方法的分割效果与文献中采用的FCM算法和KFCM算法图像分割效果的对比如表1和表2所示。表1为几种算法对纵向裂纹分割效果的对比，表2为对网状裂纹分割效果的对比。

从试验结果可以看出，对单一纵向裂纹，其裂纹的灰度和背景差别较大，三种算法的分割效果差别不大，都能很好的分割出较清晰的路面裂纹。

路面网状裂纹中路面的背景与裂纹对比度低，裂纹噪声和边缘细微变化较大，因此模糊聚类中心的选取是分割的关键。从对比结果可以看出FCM算法效果最差，分割结果噪声较大，有些微小裂纹信息丢失，本文改进算法效果最好，不但抑制了干扰噪声，同时分割出的裂纹也较清晰。从对比结果可以看出利用本文的改进算法进行路面裂纹分割效果明显。

5结束语

利用聚类算法与模糊理论进行路面裂纹分割是一种有效的方法，提出的改进模糊核聚类算法有效地解决了现有模糊核聚类算法中容易出现局最优的缺点。通过试验分析得到以下结论：

1）对路面纵向裂纹图像的分割，本文提出的改进算法比现有的FCM和KFCM算法的分割效果较好，但分割效果的优势不是很明显。

2）对路面网状裂纹图像的分割，本文提出的改进算法比现有的FCM和KFCM算法有明显的优势，不但能有效的抑制干扰噪声，同时分割出的裂纹也较清晰。

利用本文改进算法分割出了较清晰的路面裂纹，只要将分割结果图像进行二值化再进行简单形态学处理，就可以获得路面裂纹宽度等信息，为路面质量评估和养护提供精确基础数据。

参考文献

[1]HEINRICH FLA， GarcíaEscudero AMI. Robust constrained fuzzy clustering[J]. Information Sciences， 2013，245：38-52.

[2]KHANG ST，WEI HL， NORASHIDI MI. Novel initialization scheme for Fuzzy CMeans algorithm on color image segmentation[J]. Applied Soft Computing， 2013，13：1832-1852.

[3]章毓晋.图像分割评价技术分类和比较[J].中国图像图形学报，1996，1（2）：151-158.

[4]LUMINITA A. VESE， TONY F. Chan. A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model[J]. International Journal of Computer Vision， 2002， 50（3）， 271-293.

[5]WU， Z， LEAHY， R. An optimal graph theoretic approach to data clustering： theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1993， 15（11）： 1101-1113.

[6]陈蕾.基于边缘信息的图像分割技术研究[D].西安：西安电子科技大学，2009.

[7]马常霞，赵春霞，胡勇，等.结合NSCT和图像形态学的路面裂缝检测[J].工程图学学报，2008，2： 142-147.

[8]XU R， WUNSCH D. Survey of clustering algorithms[J]. Transactions on Neural Networks，2005， 16（3）： 645-678.

[9]陈凌.基于模糊聚方法的图像分割算法的研究.[D].赣州：江西理工大学，2012.

[10]林开颜，吴军辉，徐立鸿，等.彩色图像分割方法综述[J].中国图象图形学报，2005，10（1）：1-10.

[11]闫茂德， 伯绍波，贺昱曜. 一种基于形态学的路面裂缝图像检测与分析方法[J].工程图学学报， 2008， 2： 142-147.

[12]BENAICHOUCHE AN， OULHADJ H. Improved spatial fuzzy cmeans clustering for image segmentation using PSO initialization Mahalanobis distance and postsegmentation correction[J]. Digital Signal Processing， 2013，23：1390-1400.

[13]高新波，裴继红，谢维信.模糊C-均值聚类算法中加权指数m的研究[J].电子学报，2004，8（4）：80-83.

[14]王向阳，王春花.基于特征散度的自适应fcm图像分割算法[J].中国图象图形学报，2008，13（5）：906-910.

[15]JUN W，SHITONG W， et al. Fuzzy partition based soft subspace clustering and its applications in high dimensional data[J]. Information Sciences， 2013，246：133-154.

[16]李艳灵，沈轶.基于空间邻域信息的fcm图像分割算法[J].华中科技大学学报：自然科学版，2009，（6）：56-59.

模糊聚类及其实际应用 篇4

聚类分析显而易见就是把复杂没有分类的样本集按某种准则或属性进行聚类, 把具有相似属性的样本作为一类, 而不相似的样本尽量放到不同的类中[1]。聚类分析是一种无监督分类方法, 它被广泛地应用于人工智能[2]、模式识别、图像处理[3]、计算机视觉和模糊控制等领域。传统意义上的聚类分析是一种硬划分, 它并不能对实际大多数没有明显属性差别的对象进行划分, 模糊理论的提出为解决这种现实问题提供了有效途径, 人们开始用模糊的方法来处理聚类问题, 称之为模糊聚类分析[1,2], 它准确的反映了客观现实世界的诸多无法用精确聚类分析来描述的现象, 从而成为聚类分析发展的前沿。模糊聚类分析是建立在模糊数学的基础之上, 模糊数学[4]是伴随着上世纪五六十年代兴起的一种分析统计数据以及给出决策的方法。本文对模糊聚类的FCM算法和减法聚类算法进行介绍和分析, 重点介绍其数学模型和算法实现并利用matlab7.1的Fuzzy Logic Toolbox来对2005年度各行业废气排放和处理情况的数据进行模糊聚类分析。

2 聚类分析

2.1 聚类分析概况

聚类就是按照一定的规则来对事物进行区分和分类的过程, 在之中没有任何关于分类的先验知识的指导, 仅据事物属性的相似性作为类别划分的依据, 它属于无监督的范畴。聚类分析就是用数学的方法研究和处理给定对象的分类[1]。

聚类分析应用很广泛, 人们也投入了大量精力来研究它, 提出了许多效果很好的聚类方法, 归结出来可以大致分为4种[1]:谱系聚类法、基于等价关系的聚类方法、图论聚类法和基于目标函数的聚类方法等。前3种方法是传统的聚类方法主要缺点是不适用于大量数据的情况, 难以满足一些要求性较高的场合, 例如实时性场合。第4种方法基于目标函数的方法则得到了相当的重视, 人们做出了大量卓有成效的工作。基于目标函数的聚类算法是把聚类归为一个带约束的非线性规划问题, 通过优化求解而获得数据集的模糊划分和聚类, 其中模糊c均值[1,5] (FCM, Fuzzy C-Means) 类型算法理论发展最为成熟, 应用最广泛。模糊c均值算法最早是从硬聚类目标函数的优化中导出的。这种方法提供了一种如何将多维空间分布的数据点分组成特定数目的途径。FCM算法是模糊聚类最流行和应用最广泛的一种算法, 在许多领域都取得了非常成功的效果, 并成为许多其它新的模糊聚类算法的基础, 这都推动了模糊聚类在现实中的应用[1]。

2.2 基于目标函数的数学模型[1,5]

设A%=X=12 (, , , ) nX X LX目标集合全体, 对它的每个对象Xk用向量来表示, 其中Xki是第i个特征上的赋值, P (x) 称为Xk的特征向量。我们按照样本的隶属程度 (隶属函数用表示) 把目标集合划分成c个子集, 其中表示样本Xk于子集Xi的关系, 则可用c个集合的特征函数值构成的矩阵来表示。矩阵U中的第i行为第i个子集的特征函数, 而第k列为样本Xk相对于c个子集的隶属函数。首先是传统的c划分又称硬划分即:

我们把隶属函数从二值扩展到[0, 1]区间, 从而把硬c划分推广到模糊c划分即

模糊划分确定样本归属于各个类别的不确定程度, 此就是我们要对样本进行聚类分析需要产生的c划分[1,3]。

对于硬c划分, 定义硬聚类分析的目标函数[1]为

, 式中dik表示第i类中的样本Xk与第i类的典型样本Pi之间的失真度, 我们一般用两个矢量间的距离来度量。j1 (U, P) 表示了各类中样本与其典型样本的误差平方和。当我们把它推广到模糊聚类的情况时, 为了避免产生平凡解, 得到目标函数为

进而推广到一般情况可以得到:

其中, m称为加权指数。dik定义为:

其中A为s×s阶的对称矩阵, 聚类的准则是取jm (U, P) 的极小值。若数据集X、聚类类别c和权重m值已知, 我们就能确定最佳模糊分类矩阵和聚类中心[1]。

3 FCM算法和减法聚类算法

为了使基于目标函数的聚类分析得到更广泛的应用, 人们提出了模糊c均值 (FCM) 聚类算法, 它广泛应用到图像处理、模糊控制等诸多领域, 并取得了很好的效果。但是FCM算法对初值的选取非常敏感, 初值选取不当可能导致它最终达不到预期的效果甚至导致错误, 于是人们应用它的过程中用多次随机赋初值或在多个结果中寻找到最优解, 现在有人运用两层甚至多层FCM来获得最优解, 但是这些方法也有许多弊端, 后来人们又利用遗传算法对FCM进行改进, 这些方法虽能避免产生局部最优解, 但还是没有解决需要事先给定聚类个数的问题。如果在使用模糊c均值之前先使用减法聚类算法找到它的聚类初始中心, 可以避免陷入局部最优解, 能提高聚类速度, 而且不必事先就要确定要聚类的个数[6]。FCM算法是从硬c均值 (HCM) 聚类算法发展而来的, 下面我们将介绍FCM方法及减法聚类算法。

3.1 FCM算法

jm (U, P) 模糊c均值聚类算法 (FCM) 就是用隶属度确定每个元素属于某个类别的程度的一种聚类算法[7], FCM把n个数据向量Xk分c个模糊组, 并求每组的聚类中心, 使得非相似性指标的价值函数达到最小。FCM与普通分类的区别就在于FCM用模糊划分, 使得每个给定数据点用值在0与1间的隶属函数确定其属于各个类的程度[6]。FCM算法中当加权指数M=1时, 模糊聚类就退化为HCM;有人研究表明M的最佳选择范围是[1.5, 2.5], 通常m=2是比较理想的取值[3]。FCM是通过反复迭代优化目标函数即执行下列步骤[1]:

初始化:设定聚类类别数c, 2≤c≤n, n是数据个数, 设定算法停止阈值, 初始化聚类中心 (原型模式) P (0) , 设置迭代计数器b=0;

步骤1:用下式计算或更新划分矩阵U (b) :对于∀i, k, 如果∃dik (b) >0, 则有:

如果∃i, r, 使得, 则有, 且对j≠r,

步骤2:用下式更新聚类原形模式矩阵P (b+1) :

步骤3:如果, 则算法停止并输出划分矩阵U和聚类原型P, 否则令b=b+1, 转向步骤1。

该FCM聚类算法能从任意给定初始点开始而收敛到其目标函数jm (U, P) 的局部极小点或鞍点。

3.2 减法聚类 (Subtractive Clustering) 算法[5,6]

减法聚类是一种用来估计一组数据中的聚类个数以及聚类中心位置的快速实用的单次算法。减法聚类方法将每个数据点都作为可能的聚类中心, 然后根据各个数据点周围的数据点密度来计算该点作为聚类中心的可能性。被选为聚类中心的数据点周围具有最高的数据点密度, 同时该数据点附近的数据点就被排除作为聚类中心的可能性;在选出第一个聚类中心后, 从剩余的可能作为聚类中心的数据点中, 继续用类似方法选择下一个中心。直至所有剩余的数据点作为聚类中心的可能性低于设定的阈值时[5]。

假设所有数据点位于一个单位超立方体内, 即各维的坐标都在0~1之间, 通常指定数据向量的每一维坐标上聚类中心的影响范围在0.2~0.5。定义数据点Xi的密度为:

半径定义了该点的密度范围, 范围外的数据点对密度影响很微小, 计算每个数据点密度后, 选取密度最高的数据点为第一个聚类中心, 计此数据点为Xx1, Dx1为其密度, 则其他数据点密度修正为:

常数定义了一个密度显著减小的范围, 通常大于ra。然后重复以上步骤, 直至所有剩余的数据点作为聚类中心的可能性低于某一阈值时[6]。

4 应用MATLAB的Fuzzy Logic Toolbox对工业污染进行分析

MATLAB模糊逻辑工具箱提供对两种聚类方法:一种是模糊c均值聚类方法即FCM命令行函数, 另一种是减法聚类分析方法, fuzzy工具箱中的函数subclust就是通过减法聚类算法来进行模糊聚类的。本文从国家统计局网站找到2005工业按行业分废气排放及处理情况的统计数据如表1所示:

首先我们对各行业二氧化硫、烟尘和粉尘的排放量进行聚类分析

这样我们就把这些企业的产污能力分为3类, 其中类一表示排污量较小的行业, 类二表示排污量较多的行业, 而类三就表示排污量最多的行业。得到分类结果见图1及表2:

我们得到的数据结果如表2所示:

第4列的数字1表示属于第一类, 2表示属于第2类, 3表示属于第3类。按产污能力聚类得到的结果见表3:

然后综合考虑排污量和处理情况进行聚类分析可得到结果见图2和表4为:

最终聚类结果如表4所示:

同理第7列的数字表示类别:1表示综合排污和处理情况较好, 2表示综合排污和处理情况尚需改进, 3表示综合排污和处理情况需要重点治理。分类结果如表5所示。

综合比较上面两组结果可以看出:当考虑一个行业的废物处理情况时, 有许多行业从第一类降为第2类, 从第2类降为第3类, 比如石油和天然气开采业、农副食品加工业等行业;并且属于第一类的行业数量明显减小, 而属于第2类的行业数却明显增多。可见许多企业对污染处理的力度较小, 归其原因一是处理污染投资较大, 有的企业单纯追求效益而不愿意投资排污处理;二是人们对污染造成的后果还没有得到较清晰的认识, 重视程度不够。

5 结束语

传统的聚类分析是一种硬划分, 每个对象都只能归于一类, 而现实的分类问题往往伴随着模糊性, 即每个对象属于某一类是程度问题。这时候单纯的严密的理论推导和数学计算往往达不到很好的效果, 相反, 模糊逻辑在这方面具有极大的优势, 因此用模糊理论和方法来描述和解决现实聚类问题更为自然和方便。随着模糊聚类研究的深入, 人们提出或正在努力研究一些新的算法和实现方法, 例如基于神经网络的模糊聚类新算法实现途径[8]等领域都对模糊聚类的应用产生了促进作用。

摘要：随着模糊数学的产生和发展, 模糊聚类分析也随之产生并得到广泛应用。本文主要介绍模糊聚类及其应用领域, 分析和探讨模糊聚类的基本原理、方法, 重点介绍C-均值聚类分析算法 (FCM) 以及减法聚类算法, 并结合中国统计局的2005年度各行业废气排放和处理情况的数据用matlab模糊逻辑工具箱对其进行模糊聚类分析, 所得结果可为各行业污染分类情况进行处理提供参考。

关键词：模糊聚类,目标函数,FCM算法,减法聚类算法

参考文献

[1]高新波.模糊聚类分析及其应用[M].西安电子科技大学出版社, 2004:1～65

[2]覃俊华, 张洪伟, 赵世政.基于遗传算法的模糊聚类研究及其应用[J].计算机应用, 2007.1, 27 (1)

[3]林开颜, 徐立鸿, 吴军辉.快速模糊C均值聚类彩色图像分割方法[J].中国图像图形学报, 2004.2, 9 (2)

[4]李洪兴, 汪培庄著.模糊数学[M].北京:国防工业出版社, 1994

[5]吴晓莉, 林哲辉等.Matlab辅助模糊系统设计[M].西安电子科技大学出版社, 2002

[6]肖春景, 张敏.基于减法聚类与模糊C均值的模糊聚类的研究[J].计算机工程增刊, 2005.7

[7]钱同惠, 沈其聪, 葛晓滨等.模糊逻辑及其工程应用[M].北京:电子工业出版社, 2001:303～325

模糊聚类 篇5

基于遗传算法与FCSS相结合的模糊球壳聚类算法

模糊球壳聚类(FCSS)算法广泛地应用于模式识别与机器学习等领域.由于其采用基于梯度法和交替寻优策略,对初始化比较敏感,容易陷入局部极值点,从而影响聚类效果.将现代全局优化方法之一的遗传算法(GA)与FCSS算法相结合,得到一种新的`球壳聚类算法GA-FCSS.数值实验表明:新方法对球壳形数据有令人满意的聚类效果.

作 者：惠周利 杨明 潘晋孝 HUI Zhou-li YANG Ming PAN Jin-xiao  作者单位：中北大学数学系,山西,太原,030051 刊 名：传感器与微系统  PKU英文刊名：TRANSDUCER AND MICROSYSTEM TECHNOLOGIES 年，卷(期)：2008 27(12) 分类号：O235 关键词：模糊聚类   模糊球壳聚类算法   遗传算法  

模糊聚类 篇6

关键词：说话人识别；模式匹配；FCM

中图分类号：TP18 文献标识码：A文章编号：1009-3044(2007)16-31104-02

A Ameliorated Method Of Speaker Recognition With Fuzzy C-meansClustering

SUN De-yi, CUI Lian-yan

(Information Science & Engineering College,Liaoning Institute of Technology, Jinzhou 121001，China)

Abstract:Pattern matching plays a very important role in the speaker recognition system, whose method can affect the system recognition rate directly. This article presents a method about fuzzy vector quantization(FVQ) and a method of the speaker recognition with subtractive clustering and fuzzy c-means clustering arithmetic by analyzing the arithmetic to fuzzy c-means. The experiment indicated that this method enhanced the recognition rate and is a effective speaker recognition method.

Key words:the speaker recognition; pattern matching; FCM

1 引言

随着社会的发展,安全问题日趋重要,用生物特征并结合计算机技术进行安全验证是当今的热门课题,说话人识别技术是生物识别技术的一种,与其它生物识别技术相比, 说话人识别具有更为简便、准确、经济及可扩展性良好等众多优势,可广泛应用于安全验证、控制等方面。说话人识别是一项根据语音波形中反映说话人生理和行为特征的语音参数,自动识别说话人身份的技术。它的基本原理是通过分析人的发声和听觉,为每个人构造一个独一无二的数学模型,由计算机对模型和实际输入的语音进行精确匹配,根据匹配结果辨认出说话人是谁。在声纹识别过程中最主要的两部分内容是特征提取和模式匹配。特征提取,就是从声音中选取唯一表现说话人身份的有效且稳定可靠的特征；模式匹配就是对训练和鉴别时的特征模式做相似性匹配。

2 模式匹配

本文所研究的说话人识别系统主要以美尔倒谱系数MFCC和差分美尔倒谱系数ΔMFCC作为说话人的特征参数，采用模糊矢量量化的识别方法。在分析了模糊C均值（FCM）聚类和改进的FCM聚类算法的性能的基础上，引入减法聚类算法，对改进的FCM算法的初始聚类中心进行初始化，从而避免改进的FCM聚类算法仍然对聚类中心的初值十分敏感，收敛结果易陷入局部极小的弊端，保证获得的改进的FCM聚类结果为全局最优解。

2.1 模糊C-均值（FCM）聚类算法

FCM聚类是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。它把n个数据向量xk（k= 1，2，…，n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。并且使得每个给定数据点用值在（0，1）间的隶属函数确定其属于各个组的程度。FCM的目标函数定义为：

2.2 改进的FCM算法

2.2.1 放松隶属度

在FCM算法中，因引入了各个聚类的隶属度之和为1的归一化条件，在样本集不理想的情况下可能导致结果不好。如当存在某个野点样本远离各类的聚类中心时，它严格属于各类的隶属度都很小，但由于各个聚类的隶属度之和为1这个条件的要求，将会使它对各类都有较大的隶属度，这种野点的存在将影响迭代的最终结果。对于此缺点，采用一种放松的归一化条件，使所有样本对各类的隶属度总和为N，即：

这样，在有野点存在的情况下得到较好的聚类结果。

2.2.2 加权模糊C-均值聚类

在解决实际问题的过程中,我们经常发现利用经典的模糊C-均值聚类所得到的结果与主成分分析的结果有较大的差异，本文将模糊C-均值聚类进一步加以改进，使得聚类的结果与主成分分析基本一致。我们的方法将模糊C-均值聚类的迭代公式中的欧氏距离改为加权欧氏距离，其中的权向量采取主成分分析的方法计算。

加权模糊C-均值聚类表示如下：

其中，ωj通过以下方法计算得到：

(1)将原始数据矩阵统一趋势化，得到无量纲矩阵Y；

(2)计算矩阵Y的相关系数矩阵R；

(3)计算相关系数矩阵R的特征值λj；

经过改进的加权模糊C-均值聚类的结果与主成分分析基本一致，特别适用于大样本的聚类。

2.3 减法聚类算法

与传统的FCM聚类算法一样，改进的FCM聚类算法仍然对聚类中心的初值十分敏感，收敛结果易陷入局部极小。为了得到较好的结果，在使用改进的FCM聚类之前先用减法聚类算法进行初始化聚类中心，以保证获得的改进的FCM聚类结果为全局最优解。

减法聚类算法是把所有的数据点作为聚类中心的候选点，它是一种快速而独立的近似聚类方法，计算量与数据点的数目成简单的线性关系，而且与所考虑问题的维数无关。

考虑M维空间的n个数据点xi(i=1,2,…,n)，其减法聚类过程分为下面几步：

（1）计算每个数据点xi的密度指标：

这里ra是一个正数，选择具有最高密度指标的数据点xc1为第一个聚类中心，Dc1为其密度指标。

（2）假定xck为第k次选出的聚类中心，相应密度指标为Dck，对于每个数据点的密度指标按式（5.19）修正：

是否成立。若不成立，则转到（2）；若成立则退出。其中δ<1是事先给定的参数，此参数决定了最终产生的初始化聚类中心数目，δ越小，则产生的聚类数越多。

本系统将减法聚类与改进的FCM聚类相结合，以减法聚类的聚类中心作为改进的FCM聚类算法的初始聚类中心，以保证改进的FCM聚类结果为全局最优解。

3 系统仿真及结果

将减法聚类与改进的FCM聚类相结合的算法应用于说话人识别，为评价识别方法的性能，使用Matlab 6.5 软件进行仿真实验。

3.1 系统设定

本系统语音采样频率为8kHz，量化位数为16bit，采集到的语音用PCM编码的wav格式文件保存。取帧长为30ms，帧移10ms，加海明窗。这里使用短时能量和过零率的端点检测方法，提取语音信号的有声段。

本系统特征参数提取采用从语音信号的有声段提取12维MFCC参数及其12维一阶差分MFCC参数并进行组合，作为说话人的特征参数。说话人码本的建立与识别采用减法聚类与改进的FCM聚类算法相结合的方法对每一个说话人的特征参数进行聚类分析，在Matlab模糊逻辑工具箱中，提供了subclust函数来完成减法聚类的功能，该函数的调用格式如下：

[C，S]=subclust（X，radii，XBounds，options）

其中X为输入数据，radii取为0.5，XBounds、options参数取缺省值。

3.2 仿真结果及分析

在实验中，语音数据是10名说话人相隔3个月在实验室的两组录音，每组录音中每个人录10次音，得到每个人的20次录音。对于每个人的录音，从两组中分别取出3次（共6次）录音进行训练，得到这个人语音的6个码本，其余14次录音用于识别测试。测试结果的总平均量化误差见表3.1，其中，第 行数据代表第 个人的语音分别用第1～10个人的码本进行模糊量化产生的总平均量化误差；从每行的最小值可以看出，每个人的语音用自己的码本进行模糊量化时产生的总平均量化误差最小，即可以代表正确的说话人。

表1 总平均量化误差表

图1 总平均量化误差对比

4 结束语

测试的结果表明：本方法的识别率较高，达到百分之九十以上。该方法以减法聚类的聚类中心作为改进的FCM聚类的初始聚类中心，避免了收敛结果陷入局部极小的问题，识别性能有了明显的改善，是一种行之有效的说话人识别方法。

参考文献：

[1]张军英.说话人识别的现代方法与技术[M].贵州:西北大学出版社,1994.

[2]何英，何强.扩展编程[M].北京:清华大学出版社,2002.

[3]杨彦、赵力.一种改进的模糊C-均值聚类算法在说话人识别中的应用[J].电声技术,2006.01.

[4]LiH. Fuzzy clustering method based on perturbation.Fuzzy Sets and Systems[J] ,1989,33:291-302.

模糊聚类的方法及应用 篇7

关键词：模式识别,隶属函数,隶属度,神经网络

模糊数学被很多人认为是解决很多人工智能问题,尤其是常识性问题最合适的数学工具。而将模糊技术应用于不同的领域就会产生一些新的学科分支。模糊模式识别一开始就是一个模糊技术应用和研究的活跃领域,人们对传统的模式识别中的一些方法利用模糊数学的方法进行了许多改进。模糊模式识别的方法是利用模糊数学中的基本概念,原理,方法解决分类识别问题。

模糊模式识别问题大致可分为两种:一种是模糊库是模糊的,而待识别对象是分明的;另一种是模糊库和待识别对象都是模糊的模式识别问题。

1 模糊聚类法

所谓聚类分析是指按一定的要求和规律将事物进行分类的一种数学方法,它在天气预报,地震预测,地质勘探,环境保护以及图像语言识别等领域有着广泛的应用,是模糊理论应用最广泛的领域之一。其基本思想是要把需要识别的事物与模板进行模糊比较,从而得到所属的类别。简单地说,模糊聚类事先不知道具体的分类类别,而模糊识别是在已知分类的情况下进行的。

1.1 模糊等价关系法

人们常常利用模糊等价关系(模糊矩阵)来进行模糊分类,若R为等价关系,则对于给定的λ∈[0,1]使可得到的普通等价关系Rλ,从而得到一个λ水平分类,若0≤λ≤μ≤1,则Rμ分的类是Rλ的某一类的子类,即Rμ的分类是Rλ的分类的加细。

1.2 传递闭包法

在很多应用中,模糊关系具有自反性和对称性,但不满足传递性,即仅是相似关系,此时可对模糊相似关系R进行改造,寻找一个包含R的传递闭包,将其转化为模糊等价关系,进而进行模式分类。这种方法称为传递闭包法。

根据标定所得的模糊相似矩阵,先求出传递闭包R,R为模糊等价矩阵,当λ从0到1取不同的值,即得截集矩阵Rλ,由于λ1刍λ2,所以,因而对任意对象元素(x1,x2),若(x1,x2),则Rλ2(x1,x2)∈Rλ1,即Rλ2(x1,x2)=1。

则Rλ1(x1,x2)=1.

1.3 最大树方法

由于利用模糊等价矩阵的聚类方法,因此,在n很大时,其工作量是成指数规律增加的,所以,此时可以应用在模糊相似矩阵上进行的聚类方法——最大树方法。

1.4 编网法

编网法实现了在R是、的a截矩阵所得到的布尔矩阵上直接进行聚类,此方法相对简单。

求出截矩阵,且空去布尔矩阵主对角线右上部分;将主对角线上的1对应的用其对象xi的标号i来代替;将剩下的0,1中的0去掉,拥*代替1;用竖线和横线将*与对角线上的序号连接,即编网,通过如此打结的对象连为一类。

1.5 模糊C均值法

在C均值法中,吧N个样本划分为C个子类,G1,G2,...,Gc,使得所有样本到聚类中心的距离平方和最小,即使准则函数

而模糊C均值算法设μj(xi)是第i个样本xi属于第j类Gj的隶属度。则聚类损失函数其中b>1是一个可以控制聚类结果的模糊程度常数。

2 模糊模式识别在自适应控制中的应用

一般的神经网络量化机制中,输入变量与个状态之间隶属关系都是简单的'0','1'关系,而将模糊模式识别的观念引入量化过程中,使得量化过程更加精确,以cmac网络来说,第一层将输入引入网络,第二层对对输入进行模糊量化,过程如下,对于输入(x1,x2…,xm)每个输入的区域上定义n个块(X1,X2,…,Xm),输入对于块的隶属关系采用高斯基函数关系,cj表示高斯隶属函数的中心值,σj表示高斯隶属函数的宽度。

假设第二层的第p个神经元是对第i个输入进行第j个块的模糊量化,则神经元的输入输出关系Op=Ip=μXj(xi),p=1,2,…,n,Op,Ip分别为第二层第P个神经元的输入输出。采用这种模糊化方法,即可克服CMAC的主要缺陷,即泛化能力与存储量之间的矛盾。

3 结束语

模糊聚类方法及其相关隶属度函数的确定方法是多种多样的,需要在实践中不断地学习,通过实践检验,利用信息反馈,不断进行调整,加以修改,使之逐步完善,从而达到优化算法,提高分类精确度的目的。

参考文献

[1]陈水利,李敬功.模糊及理论及其应用[M].科学出版社,2005.

[2]刘普寅,吴孟达.模糊理论及其应用[M].长沙国防科技大学出版社,1998.

[3]李程,邵美珍,黄洁.模式识别原理与应用[M].西安电子科技大学出版社,2008.

[4]边肇祺,张学工.模式识别[M].清华大学出版社,2007.

[5]吴士力.通俗模糊数学与程序设计[M].中国水利水电出版社,2008.

模糊聚类 篇8

1模糊控制系统I/O样本空间的划分①

1.1模糊核聚类算法的原理

聚类的目的是为了使同类的样本尽可能地靠近,不同的聚类中心尽可能地疏远[3]。模糊核聚类方法增加了对样本特征的优化,能有效地提高算法的分类效果,并且核函数的选择并不困难[4]。根据Mercer定理,只有满足Mercer条件的函数才是核函数[5]。通过Mercer核,把输入空间的样本映射到高维特征空间后,在特征空间中进行聚类。由于经过了核函数的映射,使原来没有显现的特征凸显出来,从而能更好地聚类[6]。

将模糊C-均值聚类算法(FCM)中的欧式距离‖xj-vi‖改写成其中φ(·)为非线性变换函数,则FCM聚类算法的目标函数改写为:

约束条件为:

其中,φ(xj)和φ(vi)分别表示样本和聚类中心在特征空间H中的像。‖φ(xj)-φ(vi)‖2的计算如下:

核函数选择高斯核函数:

其中,σ为高斯核函数的宽度。

将式(3)代入式(1),在式(2)的约束条件下优化式(1)得:

由式(6)可知,vi仍属于输入空间,但由于加权系数K(xj,vi)的加入(尤其是高斯核函数),使其对噪声点和野值赋予了不同的权值,这样大幅减少了噪声和野值对聚类结果的影响。

1.2 I/O样本集的获取

为了验证笔者所提算法的有效性和可行性,对Matlab中的沐浴水温模糊控制系统(shower)进行隶属度函数的优化。shower是一个典型的Mamdani型模糊控制系统,它有两个输入和两个输出,输入分别是flow(代表流量偏差,语言变量的论域为[-1,1])和temp(代表温度偏差,语言变量的论域为[-20,20]),输出分别为cold(代表冷水阀的阀速,语言变量的论域为[-1,1])和hot(代表热水阀的阀速,语言变量的论域为[-1,1])。要获得shower系统的I/O样本集,必需使样本集具有代表性,这就要求所取数据尽可能地遍历其取值范围,取值时先固定flow,按照表1的temp设置系统参数并进行系统仿真后分别取5组temp、cold和hot数据,每组2 000个点;然后固定temp,按照表1的flow设置系统参数并进行系统仿真后分别取5组flow、cold和hot数据,每组也取2 000个点,这样就得到了所需要的I/O样本集。

1.3 I/O样本空间的划分

利用所述的模糊核聚类算法对上节得到的I/O样本集进行聚类分析,为了与shower的模糊控制规则相适应,在进行聚类分析时,设置flow、temp、cold和hot的聚类个数分别为3、3、5和5,并做出聚类隶属度曲线。图1~4分别为flow、temp、cold和hot的聚类隶属度曲线。

从图1~4可以看出,经过模糊核聚类算法得到的聚类隶属度曲线中间非常接近高斯型函数,所以可以用高斯型函数进行数据拟合,而两端不是非常贴合高斯函数,考虑到两端极限位置的实际物理意义,两端可以用S型函数进行数据拟合。

2模糊控制系统I/O样本空间的隶属度函数参数优化

模糊控制系统I/O样本空间的隶属度函数参数优化就是对1.3节中得到的数据进行曲线拟合,用得到的参数调整模糊控制中的隶属度函数类型和参数。通过1.3节的分析可知,采用有理论模型的非线性最小二乘曲线拟合方法对1.3节中得到的数据进行曲线拟合。非线性最小二乘曲线拟合的过程实际上是一个最优化过程,常用的最优化方法有Gauss-Newton法、Levenberg-Marquardt法及Trust-Region法等,Trust-Region算法在解决疑难非线性问题上比目前的大多数算法更为有效,且具有全局收敛性[7],因此笔者采用Trust-Region优化算法。图5为流量偏差样本数据经过聚类后采用上述方法拟合得到的曲线,其他3个I/O的拟合曲线不再赘述。通过上述方法,得到I/O的隶属度函数类型和参数(表2)。

3仿真结果对比分析

按照表2得到的函数类型和参数设置shower模糊控制系统中模糊推理系统的隶属函数类型和参数,并将优化后的模糊控制系统与原系统进行对比分析。图6、7分别为优化前后水温和水流量的控制(跟随)曲线。从图6、7可以看出,经过优化后水温和水流量的调节时间均有所降低,而且水温的超调量也有所降低,这验证了笔者提出的优化方法的有效性,采用笔者提出的方法不仅能有效地减少模糊空间划分和参数试凑的时间,而且系统更加精确且便于实现,这有助于提高模糊控制系统的应用效率。

4结束语

将模糊核聚类算法与模糊控制结合起来,利用模糊核聚类算法对模糊系统的输入、输出样本集进行聚类,然后用Trust-Region(信赖域)最优化方法对聚类结果进行有理论模型的曲线拟合,实现了模糊控制系统输入、输出空间的划分和隶属度函数的确定和参数优化。该算法克服了输入、输出变量隶属度函数参数设计的主观性和盲目性,通过对Matlab中的沐浴水温模糊控制系统(shower)的仿真分析,结果表明模糊控制器的隶属函数经过上述算法优化后控制品质有较大的改善和提高。

参考文献

[1]林小峰,廖志伟,方辉.隶属函数对模糊控制性能的作用与影响[J].电机与控制学报,1998,2(4):197~200.

[2]王锋,张国煊,张怀相.模糊隶属度函数的遗传优化[J].杭州电子科技大学学报,2009,29(4):34~37.

[3]梅振益,杨慧中.基于加权模糊聚类方法的多模型建模[J].化工自动化及仪表,2010,37(5):6~8.

[4]章森,朱美玲,侯光奎.改进的模糊核聚类算法[J].北京工业大学学报,2012,38(9):1408~1411.

[5]刘晓峰,张雪英,Wang Z J.Logistic核函数及其在语音识别中的应用[J].华南理工大学学报(自然科学版),2015,43(5):100~106.

[6]Kamel M S,Selim S Z.New Algorithms for Solving the Fuzzy Clustering Problem[J].Pattern Recognition,1994,27(3):421~428.

基于4D航迹的模糊聚类分析 篇9

近年来, 广播式自动相关监视 (automatic dependent surveillance-broadcast, ADS-B) 技术的发展使航空器实际飞行4D航迹数据 (纬度、经度、高度和时间) 的获取成为可能。4D航迹数据充足、具体, 能够反映出每架航空器运动轨迹。在实际运行中, 航空器一般是按设计的标准飞行程序, 依靠地面导航设施的引导进行飞行的。但是由于特殊天气、临时航线直飞、航班流量过大、管制员工作负荷等因素, 为保证航空器之间有足够的安全间隔, 会出现实际飞行航迹偏离标准飞行程序的情况。偏离程度的大小可以用来检验飞行程序的优劣, 即通过航迹历史运行数据分析来检验飞行程序。

采用航迹数据分析的方法评价飞行程序, 不能只看1架航空器1次飞行的航迹与飞行程序的偏差, 应该以多架航空器的历史数据为依据, 通过聚类分析得到平均航迹与实际飞行程序相比来检验。此外, 还可以对现有飞行程序及空域结构进行优化。

目前国内外学者对轨迹数据等相关问题研究较多。轨迹数据主要应用于移动物体运动轨迹[1,2]、车辆轨迹数据研究[3,4,5,6]等, 以上文献均采用聚类分析的方法对物体的轨迹数据进行分析, 研究的数据一般是基于时间、位置 (横纵坐标) 三维向量的。而在航迹数据的聚类研究方面, 王增福等[7]基于距离、方位角的平面坐标数据, 提出基于减法聚类的自适应航迹聚类算法;M.Gariel等[8]采用K均值聚类方法进行航迹聚类, 对航迹运行进行实时监控;王超等[9]在对实际航迹数据特征分析的基础上, 建立基于对应雷达航迹点逆向比对方法的航迹相似性测度模型, 并建立管制适用性指标。以上文献在聚类分析时主要考虑位置数据的聚类, 数据中的高度信息基本用来提取航迹特征点;陆志伟等[10]采用极大代数方法建立有导航点汇聚的航路模型, 实现4D航迹的无冲突预测, 可用于优化空域资源。

笔者从航空器实际运行的4D航迹历史数据出发, 分析了4D航迹数据的特征, 处理异常数据并提取特征值, 然后使用模糊聚类法对同一方向进场航空器航迹飞行数据进行聚类分析, 最后给出实例分析, 将聚类出的平均航迹与实际飞行程序相比较, 结果表明该方法较有效, 可用于飞行程序的优化。

1 4D航迹数据介绍

1.1 ADS-B航迹数据采集

ADS-B技术是基于卫星定位和地/空数据链通信的航空器运行监视技术, 可以把来自机载设备的航空器4D位置数据 (纬度、经度、高度和时间) 以及航空器的识别信息通过地空数据链自动传送到地面。然而由于信号遮挡、干扰、系统误差等诸多原因, 航迹数据会出现丢失、冗余等问题。此外, ADS-B设备通常1s返回1次信号范围内的所有航空器的航迹位置数据, 导致数量多、庞杂异常, 同时也会有航迹数据不全的情况。因此要选择按时间序列数据较全的航迹数据。

进场航空器的航迹数据是从进入ADS-B能够探测到航迹数据开始直到航迹数据消失为止的所有数据, 即从航空器返回的第1个数据至最后高度数据为0所对应的航迹数据。

1.2 4D航迹数据特点

ADS-B设备返回的数据是每架航空器在某一时间对应的航迹点信息。通过航空器的识别信息, 可以得到每架航空器对应的多个航迹点组成的航迹数据。ADS-B设备通常的时间间隔是1s, 因此每架航空器的飞行数据不是连续的, 而是由一系列离散的航迹点组成。

选取航迹数据较多的方向, 设这一方向的所有进场航空器的航迹集合为A={A1, A2, …, AN}, 其中每个Ak为1条进场航空器的航迹;N为共有N个进场航空器对应的航迹。

每架航空器对应不同的航迹, 每条航迹由多个航迹点组成的集合, Ak={m1, m2, …, mn}, 其中:k为航空器识别号;n为Ak对应的航迹点共有n个。每架航空器的航迹都是由一系列航迹点组成的, 且每条航迹点的数量也不一定相同。

每个航迹点mi定义为1个四维的向量:mi (xi, yi, zi, ti) 为地面。其中:xi为航迹点mi的横坐标;yi为航迹点mi的纵坐标;zi为航迹点mi的飞行高度数据;ti为对应航迹点mi当前位置的相对时间。由于ADS-B返回的是经纬度信息, 需要进行坐标转换。通过兰伯特投影将返回航迹的经纬度数据转换为以机场基准点为原点对应的空间直角坐标;航迹数据中的时间数据是获取位置信息时的时间, 在航迹聚类中, 采用相对时间的概念, 即均以航迹数据出现的最后值, 且航班高度降为0的时间为基准时间0, 按照返回时间计算, 得到相对时间ti。

聚类是将数据分类到不同的类或者簇这样的1个过程, 要求同1个簇中的对象有很大的相似性, 而不同簇间的对象有很大的相异性。通常, 聚类分析方法包括:划分方法、层次方法、网格方法、模型方法和密度方法等。每种方法各有侧重, 本文针对航迹数据的聚类先采用模糊减法聚类得到相应的航迹点分类数和聚类中心, 再按分类数进行模糊减法聚类。

2 异常数据处理

由于ADS-B地面设备、机载设备、信号遮挡等影响, 4D航迹数据可能出现严重偏离航线、数据不足和重要数据点缺失等问题。因此在选取航迹数据后需要对数据进行预处理。

2.1 异常航迹与离群点

异常航迹指的是航空器严重偏离标准进场程序, 与大多数航空器飞行轨迹差异较大。直飞或者偏离航线或者有等待程序的航迹。在提取数据时, 异常航迹未被选取。

离群点是异常数据的1种, 指的是严重偏离聚类中心航线的点簇。在对航迹数据聚类之前需要先找出离群点。如图1所示, 将航班号为CBJ5195的ADS-B位置和高度数据显示出来, 发现2个严重偏离航迹的点。在数据聚类时, 需要将这些离群点剔除。

2.2 数据缺失航迹

由于信号遮挡等问题, 可能出现部分航迹数据缺失, 航班号为KAL805航班对应的部分ADS-B航迹数据如表1所列, 其中t指返回航迹数据的世界协调时;x、y分别指距离天津机场基准点的横向和纵向的空间距离, H返回高度数据, 从表1可以看出230~120m之间的高度数据缺失。

2.3 特征点提取

提取特征点可以用较少的航迹点来反应航迹特征, 减少运算量, 提高运算速度。ADS-B返回数据的间隔时间为1s, 因此航迹点数据较多, 如图1为航班号为CBJ5195的进场航空器航迹数据, 飞行时间为604s, 共412个航迹点。航迹点数量过大, 因此对数据特征点进行提取。

航迹的特征点包括航迹转弯点, 高度变换点, 速度改变点等。其中高度变换点可以直接看出, 航迹转弯点需要表1的数据进行计算, 还要确定角度变换的阈值。笔者采用模糊减法聚类的方法直接求出航迹点的聚类中心点, 用来表示航迹。

文中每条航迹采用50个左右的特征点反映航迹特征, 如图2, 星号点为提取的航迹特征点, 能够比较充分的反映航迹特征。

3 算例分析

笔者以天津机场16跑道方向的西侧进场飞行程序进行优化飞行程序研究, 其进场程序如图3所示。其中1A, 2A, 3A是标准程序, 4A是临时程序, 可供管制员调配使用。

3.1 数据准备

以ADS-B返回航迹数据为数据采集依据, 选取西侧进场方向的航迹共44条。采用3.3节的方法, 对选用的每条航迹进行航迹特征点的提取, 得到2 340个特征点。

图4是航迹特征点对应的44条航迹的二维显示。图5是其对应的三维显示, 多一维高度向量, 航迹聚类不能明显看出, 可以看出在最后进场阶段, 由于高度不同, 航迹出现2个比较明显的分类。

3.2 聚类分析

提出特征值后, 对所有航迹点的聚类问题转化为对用模糊聚类得出的2 340个聚类中心点的聚类分析问题。采用2.2节的模糊C均值聚类, 若选取的聚类中心太少, 不能反映不同航迹的区别;若聚类中心太多, 则不能反映航迹的聚类效果。设航迹点聚成30个航迹点聚类中心, 聚类的中心点和航迹的位置关系如图6, 其中星号点表示聚类中心, 可以看出这些航迹可以聚成4大类。图中灰色线条为航迹, 黑色为聚类中心。

比较2条航迹的相同聚类中心点, 由于在最后进场航段的航迹点均相同, 相同航迹点超过8个的则认为这2条航迹即为同一聚类。以此计算所有航迹对, 可以得出44条航迹的聚类结果如图7、图8所示, 数字表示是第n个聚类中心。每条线表示1个平均聚类航迹, 最后在进场航段均沿同一航迹进场。

按1.2节中对航迹数据中t的定义, 得出这4条中心航迹的运行时间分别是1 045, 498, 813和929s。

将图3与图8进行比较, 1A进场的航空器数量比较多, 流量过大时出现将1A进场航空器转至流量较少的进场方向;2A进场航空器的进入高度较低, 在480~520m, 且中心聚类航迹与3A进场程序比较接近;4A进场的航空器有部分采取直飞, 航迹偏离较多。因此, 可以分流使用1A进场的航空器流量;增加4A直飞最后进场航段, 优化4A进场程序。

4 结束语

笔者采用ADS-B的航迹数据, 对航迹数据进行处理, 运用模糊减法聚类简化了航迹特征点的提取, 而且能够较好地反映航迹的数据特征, 采用模糊均值C聚类方法对提出的航迹特征点进行聚类, 最后与实际所用的飞行程序相比较, 证实聚类结果合理。对实际飞行程序的优化有一定的借鉴作用。

由于ADS-B数据信号遮挡、设备等问题, 获取较完整航迹比较困难。笔者采用的数据航迹点虽然很多, 但包含的航迹不多。此外没有对机型、天气等因素进行考虑。

参考文献

[1]Nanni M, Pedreschi D.Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems, 2006, 27 (3) :267-289.

[2]夏英, 温海平, 张旭.基于轨迹聚类的热点路径分析方法[J].重庆邮电大学学报:自然科学版, 2011, 23 (5) :602-606.

[3]Saunier N, Sayed T.Clustering vehicle trajectories with hidden markov models application to automated traffic safety analysis[C]∥International Joint Conference on Neural Networs, Canada:IJCNN, 2006:4132-4138.

[4]Junejo I N, Foroosh H.Trajectory rectification and path modeling for video surveillance[C]∥IEEE.11th International Conference on Computer Vision, Brazil:IEEE, 2007:1-7.

[5]丁军, 张佐, 陈洪昕, 等.车辆轨迹数据的若干处理方法研究[J].交通信息与安全, 2011, 29 (5) :10-14.

[6]曹妍妍, 崔志明, 吴健, 等.一种改进Hausdorff距离和谱系聚类的车辆轨迹模式学习方法[J].计算机应用与软件, 2012, 29 (5) :38-40.

[7]王增福, 潘泉, 郎林, 等.基于减法聚类的动态航迹聚类算法[J].系统仿真学报, 2009, 21 (16) ;5240-5246.

[8]Gariel M, Srivastava A N, Feron E.Trajectory clustering and an application to airspace monitoring[J].IEEE.Transactions on Intelligent Transportation Systems, 2011, 12 (4) :1511-1524.

[9]王超, 徐肖豪, 王飞.基于航迹聚类的终端区进场程序管制适用性分析[J].南京航天航空大学学报, 2013, 45 (1) :130-139.

[10]陆志伟, 汤新民, 韩松臣, 等.基于极大代数的多航空器无冲突4D航迹生成[J].交通信息与安全, 2012, 30 (3) :147-151.

[11]李柏年, 吴礼斌.MATLAB数据分析方法[M].北京:机械工业出版社, 2012.

基于Weblog的模糊聚类分析 篇10

关键词：Web日志,模糊聚类,Web数据挖掘

网站服务器日志(Weblog)记录了使用者每次访问网站的一些资料,它最能反映使用者对网站的浏览需求。通过对Web日志的挖掘和对用户访问行为、频度、内容等分析,我们可以从大量的Web日志信息提取出我们需要的有用知识,并由此可以得到用户的访问模式,从而改进我们的Web站点设计。

聚类分析是按照一定的要求和规律将事物进行分类的一种数学方法,随着近年来数据挖掘技术的发展,聚类分析越来越多地用于大量的未知类别数据的分类。人们提出了很多聚类算法,不同的算法有着不同的应用背景。由于现实中的分类多具有模糊性,使用模糊聚类分析方法更接近自然。

1 模糊聚类算法

传统的聚类把每个样本严格地划分到某一类,体现了非此即彼的性质,这种类的类别界线是分明的。然而客观事物之间的界线往往是不分明的。自Ruspinis于1969年提出模糊划分以来,传统聚类被推广为模糊聚类,出现了很多模糊聚类算法,如传递闭包法、最大树法、编网法等。在模糊聚类中,每个样本不再仅属于某一类,而是以一定的隶属度属于每一类。换句话说,通过模糊聚类分析,得到了样本属于各个类别的不确定性程度,即建立起了样本对于类别的不确定性的描述,这样就更能准确地反映现实世界。

1.1 模糊聚类的数学原理

模糊数学是由扎德(Zadeh,L.A.)在1965年提出的一种数学理论,模糊数学理论在很多方面都产生深远影响。

定义1:设U,V是两个论域,R是U×V的一个模糊子集,它的隶属函数:

确定了U中的元素u与V中的元素v的关系程度,则称R为从U到V的模糊关系。

定义2:模糊矩阵:设矩阵R=(rij)n×n,rij∈[0,1],则称R是一个模糊矩阵。

定义3:模糊关系的对称性、自反性和传递性。

对称性:若坌(u,v)∈U×V,RT(u,v)=R(u,v)则称R具有对称性。

自反性:若R=(rij)n×n且rij=1,则称R为具有自反性。

传递性:设d坌(u,v)∈U×V,如果对λ∈[0,1]均有:

R(u,v)≥λ,R(u,w)≥λ圯R(u,w)≥λ则称R具有传递性。

定义4:λ截矩阵:设R=(rij)n×n坌λ∈[0,1]记Rλ=(rij(λ))n×n。

其中:则称Rλ为R的λ截矩阵。

对带有模糊特征的事物进行聚类分析,显然应该采用模糊数学的方法,因此称其为模糊聚类分析法。

1.2 模糊聚类分析步骤

模糊聚类分析包含下面三个步骤:原始数据标准化,标定,聚类。

1)原始数据标准化

在实际应用问题中,不同的数据可能会有不同的量纲,为了使不同量纲的数据也能进行比较,所以需要对数据进行适当的变换。要对数据进行标准化,就是根据模糊矩阵的要求,将数据压缩到区间[0,1]上。

根据不同数据类型,标准化要作下面两种变换。

(1)平移标准差变换:

经过标准差变换后,每个变量的均值都为0,标准差为1,并且消除了量纲的影响。但是,这样得到的xik'还不一定在[0,1]上,所以还要作下一个变换,即平移极差变换。

(2)平移极差变换

经过平移极差变换后,显然有0≤xij''≤1,而且也消除了量纲的影响。

2)建立模糊相似矩阵(标定)

建立模糊相似矩阵又称为标定,即标出衡量被分类的对象之间相似程度的统计量rij。设论域U={x1,x2,…,xn},xi={xi1,xi2,…,xin},依据传统聚类方法确定相似系数,建立模糊相似矩阵,xi与xj的相似程度rij=R(xi,xj)。确定rij=R(xi,xj)的方法主要是借用传统聚类分析的相似系数法、距离法以及其他方法。

1.3 常用模糊聚类算法

1)传递闭包法

在通常的情况下,由标定过程构造出的模糊关系一般能满足自反性和对称性,而不满足传递性。自反性保证任一样本不能属于不同的类;对称性保证A与B同类时,B也与A同类。这样生成的只是一个模糊相似矩阵R,而不是模糊等价矩阵,所以为了进行分类,还要去求该模糊相似矩阵R的传递闭包t(R),在这个模糊相似矩阵的基础之上生成一个模糊等价矩阵,这样便可以得到一个模糊等价矩阵。生成模糊等价矩阵后,取某一实数λ∈[0,1],计算出t(R)(布尔矩阵),便得到X的一个等价划分:当Pij=1时说明xi与xj在同一个等价类中;否则他们两个不在同一个等价类中。依次将λ值从1变小至0时,便可以得到X的一个逐渐由细变粗的动态分类。

2)最大树法

采用传递闭包法要利用模糊相似矩阵改造成模糊等价矩阵才能进行正确的分类。但是多次的合成运算将会花费大量的时间,特别是当样本数目较大时,问题会变得更加突出,所以我们希望找出基于模糊相似矩阵直接进行分类的方法,这里的最大树法便是其中之一。

最大树法就是根据图论中树的概念,直接利用模糊相似矩阵,构造一个特殊图进行聚类的方法。它以模糊相似矩阵R的元素rij为权值的一棵最大的树,取定λ∈[0,1],砍断权重小于λ的枝,得到一棵不连通的图,各个连通的分支便构成了在λ水平上的分类。

2 Web日志挖掘

2.1 Web日志结构

Web日志挖掘的主要数据来源是服务器访问日志,它完整且详细地记录了网站访问者们的浏览行为,并具有良好的结构便于应用数据挖掘技术。它主要是以文本形式存储的,其中存放了大量与挖掘工作无关的数据。最常见的日志数据格式包括常规日志格式(Common Log Format)、扩展日志格式(Extended Log Format)、NCSA,CERN,Apache日志格式。日志文档以纯文本的形式存储,后缀为.log。

以下是一个记录的例子:见表1。

2.2 Web日志预处理

1)数据清洗

我们注意到,Web日志文件中包含有大量冗余数据,而有的记录却并不完整。因此,Web日志中的信息首先要进行数据清洗才能使用。数据清洗就是检查日志中URL的后缀,删除那些认为不相关的数据。

结合网站的拓扑结构,通过检查URL的后缀名,删除认为不相关的数据。这些数据包括的后缀名有gif、jpeg、pdf、ico等格式的文件,也包括模板框架,如left.Html,css等。还包括cgi、js、txt等文件。过滤GET以外的其他动作。协议状态代码中只保留值为200的数据。只保留那些能说明访问过的页面的文件。例如后缀为htm,asp,php等的文件。另外,由于Web Robot对网站的浏览是不带任何感性色彩的,所以日志中的Web Robot的请求也要被过滤掉。经过这样的净化,我们可以进行会话识别操作。

2)数据属性的约简

在收集到的Weblog中,用户访问的是同一台服务器,访问请求方式在数据清洗中都保留为GET,服务器端口号都是80,协议状态我们保留的都是200。由于访问习惯的原因,大多数用户愿意匿名访问。而对于匿名用户来说,Username一项是空的。

这也就意味着我们所关心的是什么人(c-ip,scs(User-Agent))在什么时间(time)访问的什么网页(cs-uri-stem),删除其它的属性,得到精简后的Weblog日志。

3)用户识别

从日志中识别出每个访问网站的用户,这一任务因为本地缓存、公司防火墙和代理服务器的存在变得复杂。由于Username中的内容常是空白的,我们通常采用IP地址的方法识别用户。但是由于代理服务器和防火墙的存在使这个方法变得很复杂。常会出现以下情况:使用同一代理或防火墙的不同用户会ip相同;同一用户使用不同的计算机,会是不同的ip地址;多人使用同一台计算机,ip也会相同。

我们在这里采用基于IP和Agent的方法进行用户识别,认为拥有相同的IP和Agent的用户就是同一个用户。

4)会话识别

由于网络状况不同,页面的大小不同,服务器记载用户的请求页面的时刻,浏览页面的时间也有较大的差别。服务器记载的用户浏览页面的时间明显比实际的时间长。服务器记的时间是从响应用户请求开始,在收到下一条请求结束。由于种种原因无法准确确定用户访问时间,在实际操作中一般把服务器记录的用户访问时间当作用户浏览时间。在跨越时间区段较大的Web服务器日志中,用户可能多次访问。会话识别的目的就是将用户的访问记录分为单个会话,一般采用超时识别法,当用户的访问时间间隔大于阈值时(时间设置为30分钟),可以判断用户进行了2次会话。

2.3 模糊聚类

分析用户的访问信息可以了解用户的访问模式,实现用户聚类和页面聚类。用户聚类主要是把用户划分成若干组,具有相似浏览模式的用户分在一组,这类信息在为用户提供个性化服务等应用中特别重要。

假设某网站共有n个页面,用Y表示该网站各页面的URL的集Y={p1,p2,...,pn},用X表示在某段时间内访问该网站的m个用户的集合X={u1,u2,…um},此时,X为待分类对象。对预处理后的Web日志进行统计,计算出每一用户ui(i=1,2,...m)在这段时间内访问各页面pj(j=1,2...,n)的次数T(ui,pj),得到一个m行n列的原始数据矩阵A。然后根据原始数据矩阵A,用模糊聚类方法进行数据标准化,建立模糊相似矩阵,然后对用户进行聚类分析。

3 基于Weblog的模糊聚类实例

本实验数据采用驻马店广播电视大学(www.zmdtvu.net)2008年11月17日访问日志,文件1.58M,共9418条数据。经过数据清洗、用户识别和会话识别,我们从驻马店广播电视大学2008年11月17日日志中保留记录4743条,识别用户587个,识别会话880个,访问页面397个。为了研究方便,对用户、会话和页面进行编号处理。由于数据量大,这里选取8个用户和10个页面进行分析。

把表中的数据作为原始的Web数据矩阵A,经过数据标准化及用直接海明距离法标定后得到Web模糊相似矩阵A',其中标定采用的直接距离法中的参数c=0.01。

采用直接聚类法对模糊相似矩阵A'进行聚类分析。

λ=1时,用户分为{u1,u4,u6,u8},{u3,u5,u7},{u2}

λ=0.96,用户分为{u1,u4,u6,u8,u3,u5,u7},{u2}

4 结论

Web日志分析对了解用户的访问模式,改进网站设计非常重要,但是由于复杂的原因,Web日志中的数据有很大的模糊性、不完整性,研究起来有一定的难度。本文使用模糊聚类的方法挖掘用户之间的关系,取得了较好的结果,有一定的实用价值。

参考文献

[1]Han J W.数据挖掘:概念与技术[M].北京:机械工业出版社,2004.

[2]邵峰品.数据挖掘原理与算法[M].北京:中国水利水电出版社,2003.

[3]许海洋.模糊聚类分析在数据挖掘中的应用研究[J].计算机工程与应用,2005(17):177-179.

[4]罗兰星.模糊聚类分析中传递闭包法及其应用[J].四川卫生管理干部学院学报,2005(2):108-111.

[5]梁榕辉.模糊聚类分析法及计算机实现[J].成组技术与生产现代化,1997(12):41-45.

[6]郭凤鸣.模糊聚类分析最大树构造方法研究[J].中国地质矿产经济,1999(1):29-32.

模糊聚类 篇11

关键词：Web用户聚类,差分进化算法,模糊C-均值算法,局部搜索

1 聚类与聚类算法

聚类是将一个数据集中的成员按照某些方面相似度进行分类组织,使得类内成员尽可能相似而类间成员尽可能不同的过程。Web用户聚类是web使用挖掘中重要的聚类问题之一,是建立拥有相同浏览模式用户分组的过程。目前用于解决Web用户聚类问题的算法主要分为基于划分、层次、网格以及密度的方法。模糊c-均值算法(FCM)是在传统的K-均值算法的基础上,运用模糊数学理论改进的一种基于划分的聚类算法,其实现比较简单,收敛速度比较快,但是该算法本质上是一种局部搜索技术,对于初始值十分敏感,容易陷入到局部极小值,从而得不到全局最优解。[1]

使用启发式优化技术改进聚类算法是聚类研究的一种重要方法。差分进化算法(Differential Evolution,简称DE)是由R.Storn和K.Price在1995年提出的一种基于种群差异的启发式随机搜索技术,最初用于解决切比雪夫多项式问题[2]。作为一种基于群体智能理论的优化方法,DE在解决复杂连续优化问题显示出比GA、PSO等更好的效果。该算法受控系数少,原理简单,易于理解和实现,有较好的全局搜索能力。文献[3]将局部搜索和DE相结合,提出了一种具有局部搜索策略的差分进化算法(LSDE),使之具有更强的寻优能力。

基于上述考虑,针对模糊C-均值算法容易陷入局部极小值的缺陷,结合差分进化算法全局搜索能力强的特点,提出了一种混合算法,用于web用户聚类算法,使得该算法具有较强的全局寻优能力,实现较好的用户聚类效果。

2 Web用户兴趣度矩阵的建立

2.1 数据预处理

在进行Web用户聚类之前,必须首先对原始的Web日志文件进行预处理,以得到若干用户事务。通常,数据预处理主要包括数据清洗、用户识别、会话识别和事务识别等阶段。

2.2 用户兴趣度矩阵

用户兴趣度矩阵直接关系到web用户聚类的效果,本文在衡量用户兴趣度时综合考虑了用户浏览率和相对访问时间两个方面的因素。

定义1相对浏览率

其中hij表示事务i访问页面j的次数

定义2相对访问时间

其中tij表示事务i访问页面j的总时间

定义3用户兴趣度矩阵

用户兴趣度矩阵是一个m行、n列的数据矩阵,其中m为用户事务数,n为访问页面的个数,矩阵的一行表示一个用户事务,每一列表示web站点的一个页面,矩阵元素值rij表示用户事务i对访问页面j的兴趣度,定义如下:

定义4用户事务相似度

对于两个用户事务向量ti、tj,其相似度采用修正的余弦相似性(adjusted cosine)表示[4]:

其中,Iij表示用户事务i与j共同访问的页面的集合,Ii和Ij分别表示用户事务i与j访问的页面的集合。

3 模糊聚类问题与FCM算法[1]

模糊聚类是相对于传统的硬聚类分析而言的。传统的聚类分析是对数据对象的“硬划分“,是把每个待处理的数据对象严格地划分到某一个类中,即每个对象对于某个类的隶属度为0或1。但是在现实世界中,客观事物的类属关系往往并不十分明确,对待处理的数据对象更适合进行软划分,由Zadeh提出的模糊集合论为这种划分提供了数学理论基础。模糊集合论采用隶属度函数表示一个对象x隶属于集合A的程度,很好地处理了这种不明确的类属关系。FCM算法是1974年由Dunn提出并由Bezdek加以推广的算法,该算法的主要过程如下:

给定具有n个样本模式的集合O={O1,O2,O3,….On},其中Oi是d维向量,模糊聚类是将这n个模式分配到k个模糊簇中,求得每个簇的聚类中心,使得目标函数达到最小值。FCM算法通常使用误差平方和函数作为聚类目标函数:

其中,uij表示第j个样本对第i个簇的隶属度,,m是模糊加权指数,m≥1。dij=||ci-oj||为第i个聚类中心与第j个样本间的欧几里德距离。为使得目标函数达到最小值,FCM算法将聚类中心和隶属度分别按公式(6)和(7)不断进行迭代更新,直到达到满足终止条件:

为了使FCM算法更好地用于Web用户聚类,本文对聚类目标函数作了改进,采用用户事务相似度取代欧式距离,改进后的目标函数如下:

4 基于差分进化的模糊聚类算法(DE-FCM)的实现

4.1 算法使用的策略

4.1.1 染色体编码策略

染色体编码是实施DE的前提。本文采用实数编码方式。设将n个样本d维样本分到k个类中,把一条染色体看成k个聚类中心组成的实数串,即用P={c1,c2,c3,...cn}表示一条染色体的结构,P是一个长度为d×k的行向量:ci表示第i个聚类中心,其中i∈{1,2,3,...k}。

4.1.2 适应度函数的确定

差分进化算法是一种基于群体进化的优化方法,在群体进化过程中,差分进化算法是以适应度值为依据对染色体个体进行搜索的,染色体个体的适应度值越大,被保留的几率就越大。因此,本文使用公式(8)作为适应度函数。

4.1.3 局部搜索策略

为了进一步增强算法的全局寻优能力,在DE操作完成后加入局部搜索策略。局部搜索的过程可以描述为:从当前记录的最优个体pbest出发,按照公式(5)对pbest的某个邻域进行q次搜索,得到q个pbest的邻域内的个体pq,找出其中的最优个体pqbest,如果pqbest的适应度Fqbest优于pbest的适应度Fbest,则用Fqbest取代Fbest,更新当前记录的最优个体pbest,并用pqbest替换群体中的最差个体后返回,否则直接返回。在pbest的某个邻域进行搜索的公式如下:

其中,ηq是一个满足标准正态分布的随机数。

4.1.4 FCM优化操作

由于FCM算法的运算速度快,局部搜索能力强,因此,在进行完变异、交叉和选择操作和局部搜索之后,对于生成的中间个体进FCM优化操作,这样能够加速算法的收敛,提高算法的局部搜索能力,进而提高聚类的准确率。FCM优化操作的主要步骤是:

1)依据新产生染色体得到聚类中心矩阵,利用公式(7)计算新的隶属度矩阵

2)根据新的隶属度矩阵,按公式(6)更新聚类中心矩阵,将其编码成新的染色体。

3)重新计算中间群体的最优个体和最差个体,并与当前记录的最优个体作对比,如果中间群体的最优个体优于当前记录的最优个体,则用中间群体的最优个体替换当前最优个体,否则用当前最优个体替换中间群体的最差个体。

4.2 基于差分进化模糊聚类算法(DEFG)描述

DEFG算法的流程如下:

Step 1;设置种群规模N、交叉因子CR、种群最大进化代数GMax、聚类数k和模糊权重指数m。

Step2;从样本集合中随机选择k个样本作为初始聚类中心并编码为一条染色体,重复进行N次,生成初始群体P(0),置进化代数t=0。

Step3;按照公式(7)计算隶属度矩阵Uij0,并根据最大隶属度原则和公式(8)计算每条染色体的适应度,找出最优适应度值Fbest,,并记录最优个体pbest。

Step4;按照如下式进行变异操作,得到变异向量vi(t):

r1、r2、r3是[1,N]中互不相同的随机整数,F为缩放因子。

Step5;按照公式(10)进行交叉操作,得到交叉后的群体:

Step5;按照公式(11)进行贪婪选择得到个体pi(t+1),更新最优个体pbest及其适应度值Fbest。

其中f(.)表示个体(.)的适应度值。

Step 6;对pbest根据公式(9)进行局部搜索。

Step 7:进行FCM优化操作,得到下一代群体pi(t+1)。

Step 8;t=t+1,如果t

Step 9;输出Fbest和pbest,按最大隶属度原则对样本分类,输出聚类结果。

5 实验分析

实验的原始数据来自华盛顿大学计算机学院网站(http://www.cs.washington.edu/research/adaptive/)某一天的服务器日志文件。原始文件大小为4.57MB,共有43532条记录。实验中选取了其中的1000条记录进行数据预处理,最后得到用户事务98条,访问页面数为53个。实验在CPU为Celeron M1.3GHz、内存为512M的计算机上进行测试,在Microsoft Visual C++6.0环境下实现了DEFG算法。新算法的参数设置如下:种群规模N=50,交叉因子CR=0.8、种群最大进化代数GMax=120、模糊权重指数m=2。FCM算法最大迭代次数为120,模糊权重指数m=2。

为了验证算法准确性,在实验中用DEFG算法和FCM算法做对比分析,引入了参考文献[5]中的准确性度量方法作为评价标准,分别对聚类个数k为10、15、20、25、30进行了30次测试,图1和表1分别给出了得到的平均适应度曲线和准确度。

从实验结果可以看出,在聚类数相同的情况下,DEFG算法的平均适应度要优于FCM算法,且具有较好的准确度,说明使用新算法得到的聚类的类内相似度较高,得到了理想的聚类结果。

图2显示了聚类数为20时算法收敛情况。从收敛曲线可以看出,DEFG算法最后收敛趋于平稳的迭代次数要比FCM算法多,曲线比较平滑,而FCM算法收敛速度相对较快,容易陷入局部最优,说明DEFG算法具有较强的全局能力。

6 结束语

Web用户聚类作为电子商务的重要问题之一,在自适应网站设计、提供个性化服务等方面具有重要作用。解决Web用户聚类问题最关键的是要设计出合理的用户兴趣度矩阵及其度量标准,以及使用有效的聚类算法进行聚类。本文提出的DEFG算法采用修正的余弦相似性作为度量用户事务的依据,并将FCM算法局部搜索快和差分进化算法全局搜索能力强的优点相结合,通过实验可以看出,本文的算法是有效的,取得了有意义的Web用户聚类结果。

参考文献

[1]董云影.基于遗传算法的模糊聚类技术的研究[D].大连:大连海事大学,2005.

[2]杨启文,蔡亮,薛云灿.差分进化算法综述[J].模式识别与人工智能,2008,21(4):506-513.

[3]谭跃,谭冠政,涂立.具有局部搜索策略的差分进化算法[J].计算机工程与应用,2009,45(7):56-58.

[4]邓爱林,朱扬勇,施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报,2003,14(9):1621-1628.