分群与应用讲解

分群与应用讲解1内容21.1前言1.2K-means分群法1.3植基于K-D树的分群法1.4植基于对称假设的分群法1.5变异数控制式的分群法1.6模糊分群法及其加速1.7结论1.1前言3分群(Clustering)是将一组资料依据某种距离的量度将其分割成若干群。图1.1.1分群示意图41.2K-means分群法

K：分群数；means：分群质心。范例1：给n笔资料，利用K-means分群法来进行分群的工作，如何决定起始的K个分群质心？

解答：随机挑选K个资料当作起始分群质心。例如点v1和点v8。解答完毕图1.2.1起始的两个群心选定5图1.2.2各点的归类范例2：K=2的情况下，如何以叠代(Iterative)的方式继续修正两个群心以达到最后稳态为止？计算各资料点分别与两个群心的距离，将资料点归类到距离最短的群心那一类。之后，再以归类好的资料点计算出新的质心位置和。反覆为之，直到群心不改变。解答：解答完毕范例3：在前面介绍的K-means分群法中，碰到较极端的例子，例如：Outlier的例子，是否会产生不理想的分群结果？

解答：[9]6图1.2.3一个Outlier例子p利用的条件，将点p这个Outlier另外归为一类；否则就遵循K-means分群法。解答完毕1.3植基于K-D树的分群法7解答：图1.3.1十一笔资料的分布图范例1：何谓K-D树?8图1.3.2第一次分割9图1.3.3最后分割的结果图1.3.4

K-D树解答完毕1.4植基于对称假设的分群法10图1.4.1一个对称图的例子根据K-means的作法，资料点O因为距离群心A较近，它会被归属于群心A。事实上，从资料集E2的分布来看，资料点O应该被归属于群心B的。造成了误判的情形。11范例2：如何修改K-means分群方法中的距离公式避免上述误判情形？解答：

利用式(1.4.1)，图1.4.1中的点O之对称点为点P，如此一来，点O就不会被归属为群心A了。解答完毕(1.4.1)利用K-means算法找到了K个群心。点对称距离量度可表示为12图1.4.3(a)为一K-means方法所得的分群结果，而图1.4.3(b)为SC方法所得的分群结果。SC方法由于反应了对称的考量，故得到较佳的分群结果。13(b)SC所得的分群结果(a)K-means所得的分群结果图1.4.3分群结果14范例4：SC方法有哪些可能的小弱点？解答：SC方法的第一个小弱点为缺乏对称的强健性。给一图如图1.4.4所示：图1.4.4SC第一个小弱点的例子依式(1.4.2)可推得，对资料点pi而言，相对于群心ck，最对称的点为pj+1，这说明了SC方法会较偏爱较远的点。这也多少减低了SC方法在对称上的强健性。SC方法的第二个小弱点为碰到资料集为SIIC(SymmetricalIntra/InterClusters)时，分群的效果不是很理想。如图1.4.5中但p4属于c3：15图1.4.5SIIC的一个例子这造成了和分别属于不同群，破坏了封闭性(ClosureProperty)。16为了克服SC方法中的缺乏对称强健性，我们提出一种称为DSL(DistanceSimilarityLevel)的算子。为了能纳入方向近似程度，我们定义一种称为OSL(OrientationSimilarityLevel)的算子。DSL算子

OSL算子

解答完毕17将这两个算子整合成SSL(SymmetrySimilarityLevel)

为了保有封闭性，上式改写为

SSL算子可说是对SIIC资料集分群的核心算子。给定一资料集，如图1.4.6所示。在图1.4.7中分别显示K-means方法、SC方法以及SSL方法所得分群结果与分群效果评比。18图1.4.6SIIC资料集19(b)SC方法所得分群结果(c)SSL方法所得分群结果(a)K-means方法所得分群结果图1.4.7三种方法的分群效果评比1.5变异数控制式的分群法20资料集，将集合X分割成，

这里21一开始，我们任意将X

分割成成。接下来，我们计算出它们的变异数，，。如果，则进行隔离(Isolation)的动作。这里表示y

和x

有最远距离。接下来，我们将个

内部边点予以分离出去。如果，则对算出y

：视为点x

的外部边缘点。我们针对外部边缘集

这里ND(x,y)表示y和x有最近距离。随机选取个外边缘点并将它们和Ci合并(Union)起来。在[1]中，学者们提出利用干扰法(Perturbation)来改善最后的群效果。对群Ci来说，我们在OB(Ci)中挑一点，如果下式成立，则将x从Cj中移除，而将x纳入Ci中22231.6模糊分群法及其加速给资料点集，FCM分群法将资料点集X

分成C群。令这C群的群心集为。令资料点

xj

对群心vi的隶属函数值为

uij，隶属矩阵U表示为24群心集V和资料点集X

的误差为：

依据LagrangeMultiplier方法，可得：(1.6.1)25对微分后令为零，可得到对微分后令为零，可得到(1.6.3)由式(1.6.3)可解得(1.6.4)(1.6.2)26由式(1.6.2)和式(1.6.4)可得到(1.6.5)从式(1.6.5)可得

(1.6.6)27(1.6.7)群心可调整为

(1.6.8)将式(1.6.6)代入式(1.6.4)，得28模糊C-means共分下列五个步骤：步骤一：选定群数C、次方m、误差容忍度和起始隶属矩阵。步骤二：根据资料点集和

算出起始的群心集。步骤三：重新计算