【正文】 outlook temperature humidity windy sunny 85 85 FALSE sunny 80 90 TRUE overcast 83 86 FALSE rainy 70 96 FALSE rainy 68 80 FALSE rainy 65 70 TRUE overcast 64 65 TRUE sunny 72 95 FALSE sunny 69 70 FALSE rainy 75 80 FALSE sunny 75 70 TRUE overcast 72 90 TRUE overcast 81 75 FALSE rainy 71 91 TRUE 一趟聚類算法聚類過程示例 2 ? 解：聚類閾值取 r= 16(經(jīng)計算得 EX=19， DX=10) 。 ? (1) 取第 1條記錄作為簇 C1的初始簇中心，其摘要信息為 ? {sunny:1。85。85。FALSE:1}； ? (2) 讀取第 2條記錄，其到簇 C1的距離 d=0+5+5+1=11r，將其歸并到簇 C1中，簇 C1的摘要信息更新為 {sunny:2； ； ； FALSE:1,TRUE:1}； ? (3) 計算第 3條記錄到簇 C1的距離 d=10/2+++11/2=r， 將其歸并到簇 C1中，簇 C1的摘要信息更新為 {sunny:2,overcast:1； ； 87； FALSE:2,TRUE:1}； ? (4) 計算第 4條記錄到簇 C1的距離 d=10/3++9+1 2/3=2316，以第 4條記錄構(gòu)建一個新的簇 C2，其摘要信息為 { rainy:1； 70； 96； FALSE:1}； ? (5) 讀取第 5條記錄，其到簇 C1的距離為 10/3++7+1 2/3=2316，到簇 C2的距離為 0+2+16+0=1816，以第 5條記錄構(gòu) 建一個新的簇 C3，其摘要信息為 { rainy:1； 68； 80； FALSE:1}； 一趟聚類算法聚類過程示例 3 ? (6) 讀取第 6條記錄，其到簇 C1的距離為 10/3++17+11/3=16，到簇 C2的距離為 0+5+26+1=3216，到簇 C3的距離為 0+3+10+1=1416，將第 6條記錄劃分到簇 C3中，簇 C3的摘要信息更新為 {rainy:2； ； 75； FALSE:1,TRUE:1}。 ? (7) 讀取第 7條記錄，其到簇 C1的距離為 11/3++22+11/3=4216，到簇 C2的距離為 1+6+31+1=3916，到簇 C3的距離為1++10+11/2=1416，所以將第 7條記錄劃分到簇 C3中，更新簇 C3的摘要信息為 {rainy:2,overcast:1； ； ；FALSE:1,TRUE:2}。 ? (8) 讀取第 8條記錄，其到簇 C1的距離為 12/3++8+12/3=16，到簇 C2的距離為 1+2+1+0=416，到簇 C3的距離為 10/3+++11/3=16，將第 8條記錄劃分到簇 C2中，簇 C2的摘要信息更新為 {rainy:1,sunny:1； 71； ；FALSE:2}。 ? (9) 讀取第 9條記錄，其到簇 C1的距離為 12/3++17+12/3=16，到簇 C2的距離為 11/2+2++12/2=2816，到簇 C3的距離為 10/3+++11/3=16，將第 9條記錄劃分到簇 C3中，簇 C3的摘要信息更新為 {rainy:2,sunny:1,overcast:1；； ； FALSE:2,TRUE:2}。 一趟聚類算法聚類過程示例 4 ? (10) 讀取第 10條記錄，其到簇 C1的距離為 10/3++7+12/3=1616，到簇 C2的距離為 11/2+4++12/2=2016，到簇 C3的距離為 12/4+++12/4=16，將第 10條記錄劃分到簇 C1中，簇 C1的摘要信息更新為 {rainy:1,sunny:2,overcast:1； ；； FALSE:3,TRUE:1}。 ? (11)讀取第 11條記錄，其到簇 C1的距離為 12/4+++11/4=16，到簇 C2的距離為 11/2+4++10/2=3116，到簇C3的距離為 11/4+++12/4=1116，將第 11條記錄劃分到簇 C3中，簇 C3的摘要信息更新為 {rainy:2,sunny:2,overcast:1； ； 71；FALSE:2,TRUE:3}。 ? (12)讀取第 12條記錄，其到簇 C1的距離為 11/4+ ++11/4=1516，到簇 C2的距離為 10/2+1++10/2=16，到簇 C3的距離為 11/5++19+13/5=2416，將第 11條記錄劃分到簇 C2中，簇 C2的摘要信息更新為 {rainy:1,sunny:1,overcast:1； ； ；FALSE:2,TRUE:1}。 一趟聚類算法聚類過程示例 5 ? (13)讀取第 13條記錄，其到簇 C1的距離為 11/4+++13/4=16，到簇 C2的距離為 11/3+++12/3=16，到簇 C3的距離為 11/5++ 4+12/5=16，將第 11條記錄劃分到簇 C1中，簇 C1的摘要信息更新為{rainy:1,sunny:2,overcast:2； ； ； FALSE:4,TRUE:1}。 ? (14)讀取第 14條記錄，其到簇 C1的距離為 11/5+++11/5=16，到簇 C2的距離為 11/3+++11/3=16，到簇 C3的距離為 12/5++20+13/5=16，將第 11條記錄劃分到簇 C2中，簇 C2的摘要信息更新為 {rainy:2,sunny:1,overcast:1；； 93； FALSE:2,TRUE:2}。 ? (15) 全部記錄處理完之后，得到三個簇。簇 C1包含的記錄集合為{1， 2， 3， 10， 13}，摘要信息為 {rainy:1,sunny:2,overcast:2；； ； FALSE:4,TRUE:1}。簇 C2包含的記錄集合為 {4， 8，12， 14}，摘要信息為 {rainy:2,sunny:1,overcast:1； ； 93；FALSE:2,TRUE:2}。簇 C3包含的記錄集合為 {5， 6， 7， 9， 11}，摘要信息為 {rainy:2,sunny:2,overcast:1； ； 71；FALSE:2,TRUE:3}。 一趟聚類 算法的優(yōu)劣 ? 優(yōu)點：高效，參數(shù)選擇簡單，對噪聲不敏感 ? 缺點：不能用于發(fā)現(xiàn)非凸形狀的簇，或具有各種不同大小的簇。 基于模型的聚類算法 基于模型的聚類方法試圖將給定數(shù)據(jù)與 某個數(shù)學(xué)模型 達成最佳擬合 。此類方法經(jīng)常是基于數(shù)據(jù)都有一個內(nèi)在的混合概率分布假設(shè)來進行的。主要包括： ?期望最大化方法 ?概念聚類 ?自組織神經(jīng)網(wǎng)絡(luò)方法 期望最大化方法 EM 期望最大化 EM(Expectation Maximization)算法是一種流行的迭代求精算法， EM不是把每個對象指派到特定的簇，而是根據(jù)一個代表隸屬概率的權(quán)重將每個對象指派到簇。 算法描述如下： (1)對參數(shù)向量作初始估計：包括隨機選擇 k個對象代表簇的均值或中心 (就像 kmeans算法 )，以及估計其它的參數(shù)。 (2)按如下兩個步驟反復(fù)求精參數(shù) (或簇 )： (a)期望步 :計算每個對象 指派到簇 的概率；換言之，這一步對每簇計算對象 的簇隸屬概率。 (b)最大化步：利用前一步得到的概率估計重新估計 (或求精 )模型參數(shù)。這一步是對給定數(shù)據(jù)的分布似然“最大化”。 概念聚類 概念聚類是一種機器學(xué)習(xí)聚類方法，給定一組未標記的對象，產(chǎn)生對象的分類模式。與傳統(tǒng)的聚類不同，概念聚類除了確定相似的對象分組外，還找出每組對象的特征描述，其中每組對象代表一個概念或類。因此，概念聚類是一個兩步的過程：首先進行聚類，然后給出特征描述。 COBWEB是一個常用的且簡單的增量式概念聚類方法。它 的輸入對象是采用符號值對 (屬性 值 )來加以描述的。 COBWEB方法采用分類樹的形式來創(chuàng)建一個層次聚類。 SOM方法 SOM采用 WTA(Winner Takes All)競爭學(xué)習(xí)算法 ， 其聚類過程通過若干單元對當前單元的競爭來完成 ， 與當前單元權(quán)值向量最接近的單元成為贏家或獲勝單元 ， 獲勝神經(jīng)元不但加強自身 ， 且加強周圍鄰近神經(jīng)元 ， 同時抑制距離較遠的神經(jīng)元 。 SOM可以在不知道輸入數(shù)據(jù)任何信息結(jié)構(gòu)的情況下 ， 學(xué)習(xí)到輸入數(shù)據(jù)的統(tǒng)計特征 。 SOM方法網(wǎng)絡(luò)結(jié)構(gòu) 輸入單元 Xi 連接權(quán)值 Wij 輸出層 權(quán)重向量 Wj 輸入層 SOM方法 SOM學(xué)習(xí)算法由最優(yōu)匹配神經(jīng)元 (競爭 )的選擇和網(wǎng)絡(luò)中 權(quán)值的自組織 (確定權(quán)值更新鄰域和方式 )過程兩部分組 成，這兩部分相輔相成，它們共同作用完成自組織特征 映射的學(xué)習(xí)過程。選擇最優(yōu)匹配神經(jīng)元實質(zhì)是選擇輸入 模式對應(yīng)的中心神經(jīng)元。權(quán)值的自組織過程則是以“墨西 哥帽”的形態(tài)來使輸入模式得以存放。每執(zhí)行一次學(xué)習(xí)， SOM網(wǎng)絡(luò)中就會對外部輸入模式執(zhí)行一次自組織適應(yīng)過 程；其結(jié)果是強化現(xiàn)行模式的映射形態(tài)，弱化以往模式 的映射形態(tài)。下面討論 SOM算法的形式化描述。 SOM方法 在 SOM模型中，每一個權(quán)值的有序序列 (p為網(wǎng)絡(luò)中神經(jīng)元總數(shù) )都可以看作是神經(jīng)網(wǎng)絡(luò)的一種內(nèi)部表示，它是 有序輸入序列 的相對應(yīng)映象。 先介紹獲勝神經(jīng)元、拓撲鄰域和學(xué)習(xí)率參數(shù)等概念。 (1) 獲勝神經(jīng)元 對于輸入向量 x，使用 表示最優(yōu)匹配輸入向量 x的神經(jīng)元，則可以通 過下列條件決定 ： 這個條件概括了神經(jīng)元競爭的本質(zhì)，滿足這個條件的神經(jīng)元稱為最佳匹 配或獲勝神經(jīng)元。 (2) 拓撲鄰域 獲勝神經(jīng)元決定興奮神經(jīng)元的拓撲鄰域空間位置，一個獲勝神經(jīng)元傾向 于激活它緊接的鄰域內(nèi)神經(jīng)元而不是隔得遠的神經(jīng)元，這導(dǎo)致對獲勝神 經(jīng)元的拓撲鄰域的側(cè)向距離可以光滑地縮減。 pjWWWW njjjj ,2,1),( 21 ?? ??),( 21 nxxxX ??)(xi)(xi pjWxxi jj ,2,1,||||m i na r g)( ????SOM方法 具體地，設(shè) 表示以獲勝神經(jīng)元 i為中心的拓撲鄰域，設(shè) 表示獲 勝神經(jīng)元 i和興奮神經(jīng)元 j的側(cè)向距離，然后可以假定拓撲鄰域 是側(cè)向距離的單峰函數(shù)，并滿足下面兩個要求： 拓撲領(lǐng)域 關(guān)于 定義的最大點是對稱的；拓撲鄰域 的幅 度值隨 單調(diào)遞減，當 時趨于零。 滿足這些要求的典型選擇是高斯 (Gauss)函數(shù)： SOM算法的另一個特征是拓撲鄰域的大小隨著時間而收縮，可以通 過 隨時間而下降來實現(xiàn)： 式中， 是初始值， 是時間常數(shù)。因此拓撲鄰域具有時變形式， 表示如下： 關(guān)于拓撲鄰域函數(shù) 還有一些其它形式：如矩形鄰域，六邊形 鄰域等。 ijh,ijd,ijh,ijh,ijh,ijd,0, ?ijd??ijd ,)2e x p ( 22)(,)(, ?xijxijdh ????,2,1,0,)e x p ()(10 ??? ttt???0?1??,2,1,0,))(2e x p ()( 22)(,)(, ??? ttdth xijxij ?)()(, th xijSOM方法 (3) 權(quán)值更新與學(xué)習(xí)率參數(shù) 對于獲勝神經(jīng)元 i的拓撲鄰域里的神經(jīng)元，按以下方式更新權(quán)值： 這里 為學(xué)習(xí)率參數(shù)，它隨時間的增加單調(diào)下降，一種選擇就是： 這里 是另一個時間常數(shù)。學(xué)習(xí)率參數(shù) 也可以選擇線性下降函 數(shù)。 ])([)()()1( )(, xtWhttWtW jxijjj ???? ?)(t??,2,1,0,)e x p ()(20 ??? ttt???2? )(t?SOM學(xué)習(xí)完整的訓(xùn)練過程如下： (1) 初始化：隨機選取連接權(quán)值 (i＝ 1,2,…,m ， m是輸入神經(jīng)元的個數(shù)； j＝ 1， 2， … ， p， p為輸出神經(jīng)元的個數(shù) )，其值定義在 [1, 1]之間；初始化學(xué)習(xí)率參數(shù)，定義拓撲鄰域函數(shù)并初始化參數(shù)；設(shè)置 t=0； (2) 檢查停止條件。如果失敗，繼續(xù)；如果成功 (在特征映射里沒有觀察到明顯的變化 )，退出； (3) 對每個輸入樣本 x，執(zhí)行步驟 (4)到步驟 (7)； (4) 競爭 ——確定獲勝神經(jīng)元：計算輸入樣本 x與連接權(quán)值間的距離，并求得最小距離神經(jīng)元： )0