模糊数学聚类

2024-07-08

模糊数学聚类（共12篇）

模糊数学聚类篇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

其中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

一、聚类分析方法的内涵

聚类分析方法就是将研究对象（若干个个体的集合）按照某个标准分成若干类。因本文所涉及的数据量较大，所以选择K-均值聚类法实现数学分层教学的过程。K-均值聚类法，又称快速聚类法，核心思想为把每个样品聚集到其最近行心（均值）类中去。

二、数据来源

分层的依据是采用上学年各单元考核成绩。限于篇幅与数据的复杂度，现选取其中有代表性的七个单元作为分层的依据。本次分析数据来源于南通市经济技术开发区实验小学二年级九班一学年的每次单元测验，真实可靠。本文隐去了学生真实姓名，用样本号1，2，…，60来代替全班60名学生。X1表示“有余数的除法”单元；X2表示“认数”单元；X3表示“分米与毫米”单元；X4表示“加法”单元；X5表示“认识方向”单元；X6表示“减法”单元；X7表示“认识角”单元。

三、聚类分析方法在数学分层教学实现的过程以及分析

由于各变量是连续性的，量纲相同，数量级上无显著差异，所以在聚类分析前无需对数据进行标准化处理。

这里可采用SPSS软件（本论文数据分析采用SPSS Statistics 17.0版本）实现K-均值聚类法。由于我们在三年级教学过程中采取三层数学分层教学，所以将分类数定为3。根据运算结果，可以得到以下表格（对SPSS运算结果进行了格式调整）。

通过计算，可以得到各类的样本数，第一类为7个样本数；第二类为9个样本数；第三类为44个样本数。

可以得到第一类样本学生组成了基础层，所用的教材以基础教材为主，如《数学A》；课后作业以基础作业为主；在课堂教学上，要适当兼顾到这7位学生，在基本要掌握问题上，尽量给这部分学生以被提问的机会；在结对帮扶上，作为基础生与学优生结对，以获得额外的学业补助。

第二类样本学生组成了中间层，所用教材以基础教材为主；课后作业要求首先完成基础作业，可适当尝试《数学B》的习题。

第三类样本学生组成了能力层，该类学生占了全体学生的73.3%，教材以《数学A》与《数学B》两本教材，适当拓展知识面；在课堂教学上，在讲解完基本问题后，适当提出一些延伸有一定难度的问题供该类学生思考；课后，可组建兴趣小组研究思考一些问题，开展一些拓展思维训练；在结对帮扶上，作为帮扶的角色，通过教学相长的方式，亦获得成长的空间。

模糊聚类分析及其应用研究篇7

模糊聚类分析技术是智能信息处理中的一个重要研究方向, 是用模糊数学方法研究聚类问题, 模糊聚类算法[1,2]由于具有良好的聚类性能与数据表达能力, 已经成为近年来研究的热点, 广泛的应用在分析和解决实际问题当中, 包括工程、计算机科学、生命和医学科学、社会科学、经济学、无导师的学习、类型学分析或划分。这是由于实际问题中, 一组事物是否属于某一类常常带有模糊性, 也就是问题的界限不是十分清晰。我们不能明确回答是或否, 而只能在某种程度上回答是。聚类分析研究已经有几十年的历史, 它的重要性及与其他研究方向的交叉特性均已得到人们的肯定, 其中模糊聚类是数据挖掘、模式识别等研究方向的重要研究内容之一, 在天气形势分类、建筑的水泥适应性、汉字职别等方面具有极其重要的作用。本文将模糊聚类分析原理与实际问题结合起来, 重点研究模糊聚类分析的过程和步骤, 特别是聚类过程中参数的客主观处理方法。

1 基本概念与定理

定义1设R= (rij) n×n是n阶模糊方阵, I是n阶单位方阵, 若R满足自反性 (I≤R) , 对称性 (RT=R) , 传递性 (R 2≤R) , 则称R为模糊等价矩阵。

定义2设R= (rij) n×n是n阶模糊方阵, I是n阶单位方阵, 若R满足自反性 (I≤R) , 对称性 (RT=R) , 则称R为模糊相似矩阵。

定理1 R是n阶模糊等价矩阵λ∈[0, 1], Rλ是等价的布尔矩阵。

定理2设R是n阶模糊等价矩阵, 则0≤λ<μ≤1, Rμ所决定的分类中的每一个类是Rλ所决定的分类中的某个子类。

定理2表明, 当λ <μ时, Rμ的分类是Rλ分类的加细, 当λ由1变到0时, Rλ的分类由细变粗, 形成一个动态的聚类过程。

定理3设R是n阶模糊相似矩阵, 则存在一个最小的自然数k (k≤n) , 使得Rk 为模糊等价矩阵, 且对一切大于k的自然数l , 恒有Rl=RK。

2 模糊聚类方法与步骤

模糊聚类分析的实质一般是指根据研究对象本身的属性来构造模糊矩阵, 并在此基础上根据一定的隶属度来确定聚类关系, 即用模糊数学方法把样本之间的模糊关系定量的确定, 从而客观且准确地进行聚类。但大多数对象并没有严格的类属性和隶属关系, 它们在属性等方面存在着重叠性和交叉性, 具有亦此亦被的性质。

(1) 建立数据矩阵

设论域U={x1, x2, , xn }为被分类对象, 每个对象又由m个指标表示其性状:

则得到原始数据矩阵为

在实际问题中, 不同的数据一般有不同的量纲, 为了使观察的特征值具有相对意义, 使各特征值取值限定在[0, 1]上, 需进行规格化处理, 方法很多。

(2) 建立X上的模糊相似矩阵

鉴别X中xi与xJ的接近程度, 用[0, 1]中的数riJ表示xi与xJ的相似程度, 得到相似矩阵 (riJ) n×m , 对其求等价闭包或等价类, 就可对X中的元素进行分类。这里需要指出的是相似系数矩阵必须符合自反性、对称性要求, 可根据实际情况选择数量积法、夹角余选法、相关指数、指数相似系数法等。

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

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

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

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

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.

基于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

关键词：数据挖掘；聚类分析；聚类算法

中图分类号：TP301. 6 文献标识码：A文章编号：1009-3044(2007)12-21500-02

The Research of Clustering Algorithms

XIANG Bing-bing1, QIAN Guang-chao2

(1.School of Mathematics and Computational Science, Anhui University, Hefei, Anhui Province 230039, China；2. School of Computer Science and Technology ,Anhui University, Hefei, Anhui Province 230039, China)

Abstract：Clustering is an important technique in data mining. It’s used to discover the data distribution and concealed patterns. The paper elucidate the basic principle of the clustering algorithms and sum up the contemporary research of the clustering algorithms. It also analyze a few representative clustering algorithms and compare their differences，advantages and disadvantages. At last，the paper indicate the development trend of clustering integrating the application demand.

Key word:Data mining； Clustering Analysis；Clustering Algorithms

1 引言

数据挖掘是指从从大量无序的数据中提取隐含的、有效的、可理解的、对决策有潜在价值的知识和规则，为用户提供问题求解层次的决策支持能力。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神經网络算法等等。聚类算法是一种有效的非监督机器学习算法，是数据挖掘中的一个非常重要的研究课题。当人们使用数据挖掘工具对数据中的模型和关系进行辨识的时候，通常第一个步骤就是聚类，其目的就是将集中的数据人为地划分成若干类, 使簇内相似度尽可能大、簇间相似度尽可能小，以揭示这些数据分布的真实情况。但任何聚类算法都对数据集本身有一定的预先假设，根据文献[1]的理论，如果数据集本身的分布并不符合预先的假设，则算法的结果将毫无意义。因此，面对特定的应用问题，如何选择合适的聚类算法是聚类分析研究中的一个重要课题。本文比较了数据挖掘中现有聚类算法的性能，分析了它们各自的优缺点，并指出了其今后的发展趋势。

2 聚类算法分类研究

聚类的目的是把大量数据点的集合分成若干类，使得每个类中的数据之间最大程度地相似，而不同类中的数据最大程度地不同。通常聚类算法可以分为层次聚类、分割聚类、密度型聚类、网格型聚类和其他聚类等几种。

2.1 层次聚类

层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类，它又可以分为两类，即自底向上的聚合层次聚类和自顶向下的分裂层次聚类。聚结型算法采用自底向上的策略，首先把每个对象单独作为一个聚类，然后根据一定的规则合并成为越来越大的聚类，直到最后所有的对象都归入到一个聚类中。大多数层次聚类算法都属于聚结型算法，它们之间的区别在于类间相似度的定义不同。与聚结型算法相反，分裂型算法采用自顶向下的方法，它先将所有的对象都看成一个聚类，然后将其不断分解直至每个对象都独自归入一个聚类。一般情况下不使用分裂型方法，因为在较高的层次很难进行正确的拆分。纯粹的层次聚类算法的缺点在于一旦进行合并或分裂之后，就无法再进行调整。现在的一些研究侧重于层次聚类算法与循环的重新分配方法的结合。

主要的层次聚类算法有BIRCH， CURE， ROCK， CHAMELEON， AMOEBA，COBWEB， Clustering with Random Walks 算法等。CURE算法[2]不用单个中心或对象来代表一个聚类，而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类，这样就可以识别具有复杂形状和不同大小的聚类，从而能很好地过滤孤立点。ROCK算法[3]是对CURE的改进，除了具有CURE算法的一些优良特性之外，它还适用于类别属性的数据。CHAMELEON算法[4]是Karypis等人于1999年提出来的，它在聚合聚类的过程中利用了动态建模的技术。

2.2 分割聚类

分割聚类算法是另外一种重要的聚类方法。它先将数据点集分为k个划分，每个划分作为一个聚类，然后从这k个初始划分开始，通过重复的控制策略，使某个准则最优化，而每个聚类由其质心来代表( k- means 算法) ，或者由该聚类中最靠近中心的一个对象来代表( k- medoids 算法)，以达到最终的结果。分割聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k 可以合理地估计，并且初始中心的选择和噪声会对聚类结果产生很大影响。这类方法又可分为基于密度的聚类、基于网格的聚类等。

很多算法中都使用距离来描述数据之间的相似性，但是，对于非凸数据集，只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于密度的聚类算法。基于密度的算法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可以发现任意形状的类。此类算法除了可以发现任意形状的类，还能够有效去除噪声。

基于网格的聚类算法，把空间量化为有限个单元( 即长方体或超长方体) ，然后对量化后的空间进行聚类。此类算法具有很快的处理速度。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜边界。此类算法具有很快的处理速度。时间复杂度一般由网格单元的数目决定，而与数据集的大小无关。此外，聚类的精度取决于网格单元的大小。此类算法不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小和数目；二是怎样对每个单元中对象的信息进行汇总。

主要的分割聚类算法有k - means， EM， k - medoids， CLARA， CLARANS 等。常见的k -medoids 算法有PAM算法、CLARA 算法、CLARANS 算法。

2.3 其他聚类

主要有：基于约束的聚类算法、机器学习中的聚类算法、用于高维数据的聚类算法等。

基于约束的聚类算法，其约束可以是对个体对象的约束，也可以是对聚类参数的约束，它们均来自相关领域的经验知识。该方法的一个重要应用在于对存在障碍数据的二维空间数据进行聚类。COD (Clustering with Obstructed Distance) [ 5]就是处理这类问题的典型算法，其主要思想是用两点之间的障碍距离取代了一般的欧氏距离来计算其间的最小距离。

机器学习中的聚类算法是指与机器学习相关、采用了某些机器学习理论的聚类方法，它主要包括人工神经网络方法以及基于进化理论的方法。如自组织特征映射( SOM) 网络是利用人工神经网络进行聚类的较早尝试，它也是向量量化方法的典型代表之一。在基于进化理论的聚类方法中，模拟退火的应用较为广泛， SNICC算法[ 6 ]就是其中之一。遗传算法也可以用于聚类处理，它主要通过选择、交叉和变异这三种遗传算子的运算以不断优化可选方案从而得到最终的聚类结果。

高维数据聚类是目前多媒体数据挖掘领域面临的重大挑战之一，除了降维这一最直接的方法之外，对高维数据的聚类处理还包括子空间聚类以及联合聚类技术等。子空间聚类算法，认为在高维数据集中，聚类往往不是存在于整个空间中，而是存在于某些子空间中。它们针对高维空间数据，寻找子空间中的聚类。主要子空间聚類算法有CLIQUE，PROCLUS 等。

3 典型聚类算法性能比较

3.1 CLARANS 算法

CLARANS通过利用多次不同抽样改进了CLARA算法，是一种k-中心点聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxeighbar个的一些邻接点。假如找到一个比它更好的邻接点，则把它移入该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须预先调入内存，并且需多次扫描数据集，其时空复杂度都相当大，虽通过引入R*—树结构对其性能进行改善，但构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据输入顺序异常敏感，且只能处理凸形或球形边界聚类，效率较高。

3.2 BIRCH 算法

BIRCH是一个综合性的层次聚类方法，它利用层次方法的平衡迭代进行归约和聚类。其核心是用一个聚类特征三元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法具有对象数目的线性易伸缩性，及良好的聚类质量。一次扫描就可以进行较好的聚类，其计算复杂度为O( n)。BIRCH 算法只适用于类的分布呈凸形及球形的情况，对不可视的高维数据则是不可行的。

3.3 DBSCAN 算法

DBSCAN是基于密度的聚类算法，可以将足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时，就必须有大量内存支持，I/O 消耗也非常大。其时间复杂度为O(nlogn)，聚类过程的大部分时间用在区域查询操作上。DBSCAN算法能够发现空间数据库中任意形状的密度连通集；在给定合适的参数条件下，能很好地处理噪声点；对用户领域知识要求较少；对数据的输入顺序不太敏感；适用于大型数据库。但DBSCAN算法要求事先指定领域和阈值，具体使用的参数依赖于应用的目的。

3.4 STING 算法

STING 是一种格的多分辨率聚类技术。它将空间区域划分为矩形单元，针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O (n) ，其中n是对象的数目。在层次结构建立后，查询处理时间是O ( g)，g是最低层风格单元的数目，通常远远小于n。

STING 是独立于查询的，有利于并行处理和增量更新且效率较高。但由于STING 采用了一个多分辨率的方法来进行聚类分析，聚类的质量取决于网格结构的最低层粒度。如果数据粒度比较细，处理的代价会明显增加。并且，STING 在构建一个父单元时没有考虑子单元和其相邻单元之间的关系，因此，尽管该技术处理速度快，但可能降低簇的质量和精确性。

4 结论和展望

聚类分析是数据挖掘中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析，还可以作为一个独立的工具来获得数据分布的情况。聚类算法的研究具有广泛的应用前景，其今后的发展也面临着越来越多的挑战。首先是聚类算法的选择，建议使用者根据实际情况(例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率)来选择合适的聚类算法。其次，对于特征数据本身所具备的高维性、复杂性、动态性以及容易达到大规模的特性，聚类算法的设计还应该更多地考虑融合不同的聚类思想形成新的聚类算法，从而综合利用不同聚类算法的优点。

参考文献：

[1]R O Duda，P E Hart，D G Stork. Pattern Classification ( 2nd Edition) [M]. New York: Wiley， 2001. 4542458.

[2]Guha S， Rastogi R，Shim K. CURE: An Efficient Clustering Algorithm for Large Databases[C]. Seattle: Proceedings of the ACM SIGMOD Conference，1998. 73-84.

[3]Guha S，Rastogi R，Shim K. ROCK: A Robust Clustering Algorithm for Categorical Attributes[C]. Sydney: Proceedings of the 15 th ICDE，1999. 512-521.

[4]Karypis G，Han E-H，Kumar V. CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling[J]. IEEE Computer，1999，32 (8) : 68-75.

[5]Tung A K H，Hou J，Han J. Spatial Clustering in the Presence of Obstacles[C]. Heidelberg: Proceedings of the 17 th ICDE，2001. 359-367.

基于模糊聚类的国画图像分割研究篇12

随着网络技术与数字化技术的迅速发展, 针对中国书画作品的研究越来越受到研究者的关注。而中国书画作为中国文化中的重要组成部分, 由于其独特的构图方式、绘画手法等等, 使其具有独特的艺术特点。如何应用图像处理技术处理中国书画图像, 成为一个新的研究热点。

在目前的研究中, 对图像的研究主要集中在自然图像领域, 且技术相对成熟, 包括图像检索、图像标识、图像修复等等。而对于书画图像的研究相对较少, 对国画图像的分割是图像标识、图像检索等研究的基础。

本文针对国画图像分割进行了探讨, 根据国画图像的用色特点, 提出了以图像的灰度特征作为各像素点的颜色特征, 通过模糊C均值聚类对图像的像素点进行分类, 从而实现图像的分割。

1 中国画的特点

中国书画是书法和国画的统称。中国书画是中华民族文化的优良传统之一, 它不仅是进行思想文化交流的工具, 也是独放异彩的艺术瑰宝。中国书画的历史源远流长, 历转千年而不衰, 可以说是中华民族文化宝库中一门具有独特形式的艺术, 是东方艺术中历史最悠久的艺术。

中国画同西洋画相比, 在使用材料、工具方面不同。中国画所使用的笔、墨、纸、砚、色等传统工具材料。

中国画以墨为主, 其它颜料为附, 墨分五彩, 干、湿、浓、淡、焦。只用墨一种色足以表显物象。有许多中国画大家都很少用其它颜色, 如徐渭、八大山人、郑板桥等都是用墨绘画的绝顶高手。如图1所示。

2 中国画的相关研究

国外在书画图像研究领域, 宾夕法尼亚大学州立大学的James.Wang等人采用了多尺度小波变换后的特征系数描述中国书画图像的纹理特征, 于2003年提出了二维多尺度隐马尔科夫模型 (2D-MHMMs) 对沈周、唐寅、张大千等人的中国书画数字图像进行建模并构建分类器, 以实现对未知书画图像的自动分类。

2004年, 澳大利亚昆士兰理工大学的Danqing Zhang等人提出了一种适合于中国画基于内容的图像分类和检索的框架模型。

2009年, 新加坡管理大学的Jialie Shen利用Gabor小波系数描述中国书画图像的统计局部纹理特征, 针对中国书画提出了一个通用的分类框架。

国内在书画图像研究领域, 2006年, 中科院计算所Shuqiang Jiang, Qing Ming Huang等基于Tamura等人提出的一组对应人类视觉感知的纹理特征集, 采用自相关纹理特征来描述中国书画数字图像的复杂程度, 针对中国画中工笔画和写意画的特性提出使用边缘大小直方图来测量图像边缘的稀疏程度和粒度。

3算法设计

根据中国国画颜色以墨破色的特点, 首先将读入的国画图像转换到灰度图;利用模糊C均值聚类对每个像素点进行分类;再利用分类图像标识出分割图像, 从而实现国画图像的分割。

3.1 将图像转换为灰度图

通过函数读取国画图像, 并将图像转化为灰度图像, 从而提高了分割处理的效率。

3.2 模糊C均值聚类

模糊C均值聚类 (FCM) , 即众所周知的模糊ISODATA, 是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年, Bezdek提出了该算法, 作为早期硬C均值聚类 (HCM) 方法的一种改进。

FCM把n个向量xi (i=1, 2, …, n) 分为c个模糊组, 并求每组的聚类中心, 使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分, 使得每个给定数据点用值在0, 1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应, 隶属矩阵U允许有取值在0, 1间的元素。不过, 加上归一化规定, 一个数据集的隶属度的和总等于1:

那么, FCM的价值函数 (或目标函数) 就是如下形式:

这里uij介于0, 1间;ci为模糊组I的聚类中心, 为第I个聚类中心与第j个数据点间的欧几里德距离;且是一个加权指数。

构造如下新的目标函数, 可求得使 (3.2) 式达到最小值的必要条件:

这里j, j=1到n, 是 (3.1) 式的n个约束式的拉格朗日乘子。对所有输入参量求导, 使式 (3.2) 达到最小的必要条件为:

和

由上述两个必要条件, 模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时, FCM用下列步骤确定聚类中心ci和隶属矩阵U[1]:

步骤1:用值在0, 1间的随机数初始化隶属矩阵U, 使其满足式 (3.1) 中的约束条件。

步骤2:用式 (3.4) 计算c个聚类中心ci, i=1, …, c。

步骤3:根据式 (3.2) 计算价值函数。如果它小于某个确定的阀值, 或它相对上次价值函数值的改变量小于某个阀值, 则算法停止。

步骤4:用 (3.5) 计算新的U矩阵。返回步骤2。

上述算法也可以先初始化聚类中心, 然后再执行迭代过程。

3.3 根据分类结果进行分割

每个像素点根据分类结果, 填充不同的颜色, 从而得到分割的图像。如图3所示。

4 实验结果与讨论

为了验证上述算法, 从收集到的元明清56名著名书画家2145幅国画图像中, 选取500幅国画图像作为实验测试数据。本文利用图像灰度特征进行模糊C均值聚类, 实现国画图像的分割。

通过上面的模拟实验可以发现, 本文提出的算法能够保证较好的分割效果, 大部分情况下能够保证国画各个对象的准确分割。但使用的模糊C均值聚类方法, 由于不能确保FCM收敛于一个最优解, 算法的性能依赖于初始聚类中心, 因此, 在后续的工作中硬采用另外的快速算法确定初始聚类中心, 保证分割的稳定性。

摘要：国画图像分割是图像理解、计算机视觉等研究领域的重要内容。文章根据国画颜色有限性的特点以及视觉的颜色聚类特性, 提出了一种基于模糊C均值聚类 (FCM) 的国画图像分割算法, 实现对国画图像的分割。算法根据中国国画颜色以墨色为主, 以墨破色的特点, 通过选取国画图像每个像素点的灰度颜色特征, 计算各像素点到各个聚类中心之间的欧式距离, 并利用模糊C均值聚类的方法更新聚类中心, 聚类结束后得到分类后的图像;再利用分类图像标识出分割图像, 从而实现国画图像的分割。通过实验得出, 算法有效地保证了各区域图像的完整, 提高了分割的精确度。

关键词：模糊聚类,图像分割,国画图像

参考文献

[1]高新波.模糊c均值聚类算法中加权指数m的研究[J].电子学报, 2000, 28 (4) :80-83

[2]Jia Li, James.Wang.Studying digital imagery of ancient paintings by mixtures of stochastic models[J].IEEE Trans.On Image Processing, 2003, 13 (3) :340-353

【模糊数学聚类】推荐阅读：

模糊聚类11-05

核模糊聚类12-09

模糊数学算法01-15

模糊数学方法05-21

模糊数学原理08-31

>> 查看更多相关文档