摘要

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括西寧網(wǎng)站建設(shè)、西寧網(wǎng)站制作、西寧網(wǎng)頁制作以及西寧網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，西寧網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到西寧省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

這篇博客是從一個(gè)網(wǎng)上下載的資料關(guān)于模糊c均值聚類和k-means均值聚類的數(shù)學(xué)方法衍生而來。我下載的那個(gè)文章討論的不是很清楚，還有一些錯(cuò)誤的地方，有些直接給了結(jié)果，但是中間的數(shù)學(xué)推導(dǎo)沒有給出，我感覺中間的數(shù)學(xué)推導(dǎo)應(yīng)該是最精華的地方，上網(wǎng)搜發(fā)現(xiàn)網(wǎng)上對(duì)于這兩個(gè)算法的數(shù)學(xué)推導(dǎo)還是很少的甚至是沒有，百度文庫有一篇，但是推導(dǎo)的是用窮舉找規(guī)律，數(shù)學(xué)的味道不是很濃厚。在這篇文章的基礎(chǔ)上，我增加了一些數(shù)學(xué)方面的理論推導(dǎo)，講的更加的詳細(xì)了一些，特別是在模糊c均值聚類的遞推公式的推導(dǎo)上，需要具有一定的數(shù)學(xué)功底。這是我一天的成果，就把這個(gè)記錄下來了啊，希望對(duì)大家有幫助，同時(shí)也可以為以后自己的復(fù)習(xí)做備份。算法其實(shí)很簡單，但是知其然并知其所以然卻很難。k-means的算法數(shù)學(xué)推導(dǎo)原理：http://9269309.blog.51cto.com/9259309/1864214

FCM聚類算法介紹

FCM算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對(duì)象之間相似度大，而不同簇之間的相似度最小。模糊C均值算法是普通C均值算法的改進(jìn)，普通C均值算法對(duì)于數(shù)據(jù)的劃分是硬性的，而FCM則是一種柔性的模糊劃分。在介紹FCM具體算法之前我們先介紹一些模糊集合的基本知識(shí)。

1. 模糊集基本知識(shí)^[21]

首先說明隸屬度函數(shù)的概念。隸屬度函數(shù)是表示一個(gè)對(duì)象x隸屬于集合A的程度的函數(shù)，通常記做μ_A(x)，其自變量范圍是所有可能屬于集合A的對(duì)象（即集合A所在空間中的所有點(diǎn)），取值范圍是[0,1]，即0<=

μ_A(x)<=1。μ_A(x)=1表示x完全隸屬于集合A，相當(dāng)于傳統(tǒng)集合概念上的x∈A。一個(gè)定義在空間X={x}上的隸屬度函數(shù)就定義了一個(gè)模糊集合A，或者叫定義在論域X={x}上的模糊子集 。對(duì)于有限個(gè)對(duì)象x₁，x₂，……，x_n模糊集合 可以表示為：

         .............. (6.1)

有了模糊集合的概念，一個(gè)元素隸屬于模糊集合就不是硬性的了，在聚類的問題中，可以把聚類生成的簇看成模糊集合，因此，每個(gè)樣本點(diǎn)隸屬于簇的隸屬度就是[0，1]區(qū)間里面的值。

1. K均值聚類算法(HCM)介紹

K均值聚類，即眾所周知的C均值聚類，已經(jīng)應(yīng)用到各種領(lǐng)域。它的核心思想如下：算法把n個(gè)向量x_j(1,2…,n)分為c個(gè)組G_i(i=1,2,…,c)，并求每組的聚類中心，使得非相似性（或距離）指標(biāo)的價(jià)值函數(shù)（或目標(biāo)函數(shù)）達(dá)到最小。當(dāng)選擇歐幾里德距離為組j中向量x_k與相應(yīng)聚類中心c_i間的非相似性指標(biāo)時(shí)，價(jià)值函數(shù)可定義為：

      ..............   (6.2)

其中是組i內(nèi)的價(jià)值函數(shù)。這樣J_i的值依賴于G_i的幾何特性和c_i的位置。

一般來說，可用一個(gè)通用距離函數(shù)d(x_k,c_i)代替組I中的向量x_k，則相應(yīng)的總價(jià)值函數(shù)可表示為：

        ........  (6.3)

為簡單起見，這里用歐幾里德距離作為向量的非相似性指標(biāo)，且總的價(jià)值函數(shù)表示為（6.2）式。

劃分過的組一般用一個(gè)c×n的二維隸屬矩陣U來定義。如果第j個(gè)數(shù)據(jù)點(diǎn)x_j屬于組i，則U中的元素u_ij為1；否則，該元素取0。一旦確定聚類中心ci，可導(dǎo)出如下使式（6.2）最小u_ij：

  (6.4)

重申一點(diǎn)，如果c_i是x_j的最近的聚類中心，那么x_j屬于組i。由于一個(gè)給定數(shù)據(jù)只能屬于一個(gè)組，所以隸屬矩陣U具有如下性質(zhì)：

         (6.5)

且

               (6.6)

另一方面，如果固定u_ij則使（6.2）式最小的最佳聚類中心就是組I中所有向量的均值：

 ，             (6.7)

這里|G_i|是第i個(gè)簇中元素對(duì)象的個(gè)數(shù)

為便于批模式運(yùn)行，這里給出數(shù)據(jù)集x_i（1，2…，n）的K均值算法；該算法重復(fù)使用下列步驟，確定聚類中心c_i和隸屬矩陣U：

步驟1：初始化聚類中心c_i,i=1,…,c。典型的做法是從所有數(shù)據(jù)點(diǎn)中任取c個(gè)點(diǎn)。

步驟2：用式（6.4）確定隸屬矩陣U。

步驟3：根據(jù)式（6.2）計(jì)算價(jià)值函數(shù)。如果它小于某個(gè)確定的閥值，或它相對(duì)上次價(jià)值函數(shù)質(zhì)的改變量小于某個(gè)閥值，則算法停止。

步驟4：根據(jù)式（6.5）修正聚類中心。返回步驟2。

該算法本身是迭代的，且不能確保它收斂于最優(yōu)解。K均值算法的性能依賴于聚類中心的初始位置。所以，為了使它可取，要么用一些前端方法求好的初始聚類中心；要么每次用不同的初始聚類中心，將該算法運(yùn)行多次。此外，上述算法僅僅是一種具有代表性的方法；我們還可以先初始化一個(gè)任意的隸屬矩陣，然后再執(zhí)行迭代過程。

K均值算法也可以在線方式運(yùn)行。這時(shí)，通過時(shí)間平均，導(dǎo)出相應(yīng)的聚類中心和相應(yīng)的組。即對(duì)于給定的數(shù)據(jù)點(diǎn)x，該算法求最近的聚類中心c_i，并用下面公式進(jìn)行修正：

             (6.8)

這種在線公式本質(zhì)上嵌入了許多非監(jiān)督學(xué)習(xí)神經(jīng)元網(wǎng)絡(luò)的學(xué)習(xí)法則。

6.2.3  模糊C均值聚類

模糊C均值聚類（FCM），即眾所周知的模糊ISODATA，是用隸屬度確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)聚類的程度的一種聚類算法。1973年，Bezdek提出了該算法，作為早期硬C均值聚類（HCM）方法的一種改進(jìn)。

FCM把n個(gè)向量x_i（i=1,2,…,n）分為c個(gè)模糊組，并求每組的聚類中心，使得非相似性指標(biāo)的價(jià)值函數(shù)達(dá)到最小。FCM與HCM的主要區(qū)別在于FCM用模糊劃分，使得每個(gè)給定數(shù)據(jù)點(diǎn)用值在0，1間的隸屬度來確定其屬于各個(gè)組的程度。與引入模糊劃分相適應(yīng)，隸屬矩陣U允許有取值在0，1間的元素。不過，加上歸一化規(guī)定，一個(gè)數(shù)據(jù)集的隸屬度的和總等于1：

             (6.9)

那么，F(xiàn)CM的價(jià)值函數(shù)（或目標(biāo)函數(shù)）就是式（6.2）的一般化形式：

 ，        (6.10)

這里u_ij介于0，1間；c_i為模糊組I的聚類中心，d_ij=||c_i-x_j||為第I個(gè)聚類中心與第j個(gè)數(shù)據(jù)點(diǎn)間的歐幾里德距離；且 是一個(gè)加權(quán)指數(shù)。

構(gòu)造如下新的目標(biāo)函數(shù)，可求得使（6.10）式達(dá)到最小值的必要條件：

     (6.11)

這里λ_j，j=1到n，是（6.9）式的n個(gè)約束式的拉格朗日乘子。對(duì)所有輸入?yún)⒘壳髮?dǎo)，使式（6.10）達(dá)到最小的必要條件為：

             ......... 6.12

由上述兩個(gè)必要條件，模糊C均值聚類算法是一個(gè)簡單的迭代過程。在批處理方式運(yùn)行時(shí)，F(xiàn)CM用下列步驟確定聚類中心c_i和隸屬矩陣U[1]：

步驟1：用值在0，1間的隨機(jī)數(shù)初始化隸屬矩陣U，使其滿足式（6.9）中的約束條件

步驟2：用式（6.12）計(jì)算c個(gè)聚類中心c_i，i=1,…,c。

步驟3：根據(jù)式（6.10）計(jì)算價(jià)值函數(shù)。如果它小于某個(gè)確定的閥值，或它相對(duì)上次價(jià)值函數(shù)值的改變量小于某個(gè)閥值，則算法停止。

步驟4：用（6.13）計(jì)算新的U矩陣。返回步驟2。

上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。由于不能確保FCM收斂于一個(gè)最優(yōu)解。算法的性能依賴于初始聚類中心。因此，我們要么用另外的快速算法確定初始聚類中心，要么每次用不同的初始聚類中心啟動(dòng)該算法，多次運(yùn)行FCM。

對(duì)于式(6.12)結(jié)果的推導(dǎo)的數(shù)學(xué)原理：

FCM算法的數(shù)學(xué)模型其實(shí)是一個(gè)條件極值問題：

我們需要把上面的條件極值問題轉(zhuǎn)化為無條件的極值問題，這個(gè)在數(shù)學(xué)分析上經(jīng)常用到的一種方法就是拉格朗日乘數(shù)法把條件極值轉(zhuǎn)化為無條件極值問題，需要引入n個(gè)拉格朗日因子，如下所示：

然后對(duì)各個(gè)變量進(jìn)行求導(dǎo)，從而得到各個(gè)變量的極值點(diǎn)：

對(duì)C中心點(diǎn)進(jìn)行求導(dǎo)：

拉格朗日函數(shù)分為兩部分，我們需要分別對(duì)其進(jìn)行求導(dǎo)，先算簡單的，對(duì)后一部分進(jìn)行求導(dǎo)：

對(duì)前一部分進(jìn)行求導(dǎo)就比較復(fù)雜和困難了：

把兩部分放到一起則是：

上面的一些公式用到了英文，不是我裝，我的英語很差的，我用的google公式編輯器不能打漢字，沒辦法，湊活著看吧。

上式推導(dǎo)中的一些點(diǎn)的解釋：

1. FCM算法的應(yīng)用

通過上面的討論，我們不難看出FCM算法需要兩個(gè)參數(shù)一個(gè)是聚類數(shù)目C，另一個(gè)是參數(shù)m。一般來講C要遠(yuǎn)遠(yuǎn)小于聚類樣本的總個(gè)數(shù)，同時(shí)要保證C>1。對(duì)于m，它是一個(gè)控制算法的柔性的參數(shù)，如果m過大，則聚類效果會(huì)很次，而如果m過小則算法會(huì)接近HCM聚類算法。

算法的輸出是C個(gè)聚類中心點(diǎn)向量和C*N的一個(gè)模糊劃分矩陣，這個(gè)矩陣表示的是每個(gè)樣本點(diǎn)屬于每個(gè)類的隸屬度。根據(jù)這個(gè)劃分矩陣按照模糊集合中的大隸屬原則就能夠確定每個(gè)樣本點(diǎn)歸為哪個(gè)類。聚類中心表示的是每個(gè)類的平均特征，可以認(rèn)為是這個(gè)類的代表點(diǎn)。

從算法的推導(dǎo)過程中我們不難看出，算法對(duì)于滿足正態(tài)分布的數(shù)據(jù)聚類效果會(huì)很好，另外，算法對(duì)孤立點(diǎn)是敏感的。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章題目：模糊c均值聚類和k-means聚類的數(shù)學(xué)原理-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://www.rwnh.cn/article28/ceijcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、品牌網(wǎng)站建設(shè)、建站公司、ChatGPT、網(wǎng)站排名、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)