模式識(shí)別與人工智能之五

1、Pattern Recognition & artificial IntelligenceLecture 5: 聚類算法（一）,主要內(nèi)容,聚類的定義聚類算法分類典型聚類算法講解,,聚類的定義,聚類的定義,典型的非監(jiān)督式機(jī)器學(xué)習(xí)數(shù)據(jù)類別不被事先標(biāo)識(shí)通過(guò)學(xué)習(xí)模型推斷出數(shù)據(jù)的一些內(nèi)在結(jié)構(gòu)，進(jìn)而進(jìn)行聚類。,,聚類算法分類,聚類算法分類,劃分方法：首先得到初始的K個(gè)劃分的集合。如K-平均、K-中心點(diǎn)、CLARANS以及對(duì)它

2、們的改進(jìn)。層次方法：創(chuàng)建給定數(shù)據(jù)對(duì)象集合的一個(gè)層次性的分解。根據(jù)層次分解的過(guò)程可以分為凝聚（自底向上）或分裂（自頂向下）?；诿芏鹊姆椒ǎ焊鶕?jù)密度的概念來(lái)聚類對(duì)象，如DBSCAN、DENCLUE、OPTICS。,聚類算法分類,基于網(wǎng)格的方法：首先將對(duì)象空間量化為有限數(shù)目的單元，形成網(wǎng)格結(jié)構(gòu)，然后在網(wǎng)格結(jié)構(gòu)上進(jìn)行聚類，如STING、CLIQUE、WaveCluster?；谀Ｐ偷姆椒ǎ簽槊總€(gè)簇假設(shè)一個(gè)模型，發(fā)現(xiàn)數(shù)據(jù)對(duì)模型的最好匹配，

3、如COBWEB、CLASSIT，GCM, AutoClass, SOM?；诮稻S的方法：如Spectral clustering，Ncut等,聚類算法分類,劃分聚類法 – K-means,,k-means算法，亦稱k-均值或k-平均，是一種基于質(zhì)心的啟發(fā)式聚類算法?；舅枷耄和ㄟ^(guò)迭代把數(shù)據(jù)集劃分為不同的類別（或稱簇），使得評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，使得每個(gè)聚類類內(nèi)緊湊，類間獨(dú)立。對(duì)于連續(xù)型屬性具有較好的聚類效果，不適合處理離

4、散型屬性。,劃分聚類法 – K-means,算法概述,平方誤差和準(zhǔn)則函數(shù) 即SSE（sum of the squared error） SSE是數(shù)據(jù)庫(kù)中所有對(duì)象的平方誤差總和，其中 為數(shù)據(jù)對(duì)象； 為簇 的平均值。 這個(gè)準(zhǔn)則函數(shù)使得生成的簇盡可能的緊湊和獨(dú)立。,劃分聚類法 – K-means,準(zhǔn)則函數(shù),劃分聚類法 – K-means,算法流程,

5、迭代計(jì)算中心點(diǎn),收斂！,選擇初始中心點(diǎn),劃分聚類法 – K-means,Simple Example,,劃分聚類法 – K-means,算法實(shí)現(xiàn)的具體流程,影響聚類效果！,一般采用歐氏距離、曼哈頓距離或者名考斯距離的一種，作為樣本間的相似性度量,劃分聚類法 – K-means,算法特點(diǎn)：影響主要因素,劃分聚類法– K-means,不足：k-means算法只有在簇的平均值被定義的情況下才能使用。k-means算法的不足之處在于它要

6、多次掃描數(shù)據(jù)庫(kù)。k-means算法只能找出球形的類，而不能發(fā)現(xiàn)任意形狀的類。初始質(zhì)心的選擇對(duì)聚類結(jié)果有較大的影響。k-means算法對(duì)于噪聲和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。,問(wèn)題描述： 如圖所示，一只遙望大海的小狗。此圖為100×100像素的JPG圖片，每個(gè)像素可以表示為三維向量（分別對(duì)應(yīng)紅綠藍(lán)三基色）。 要求使用k-means算法，將圖片分割為合適的背景區(qū)

7、域（三個(gè)）和前景區(qū)域（小狗）。,劃分聚類法 – K-means,應(yīng)用實(shí)例,Matlab程序?qū)崿F(xiàn),function [M, j, e] = kmeans(X, K, Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo = M;for n=1:Max_Its for k=1:K Dist(:,k) = sum((X - repmat(M(k,

8、:),N,1)).^2,2)'; end [i, j]=min(Dist, [], 2); for k=1:K if size(find(j==k))>0 M(k, :) = mean(X(find(j==k), :)); end end,劃分聚類法 – K-means,Z = zeros(N,K);

9、 for m=1:N Z(m,j(m)) = 1; end e = sum(sum(Z.*Dist)./N); fprintf('%d Error = %f\n', n, e); Mo = M;end,Matlab程序?qū)崿F(xiàn)（續(xù)）,劃分聚類法 – K-means,close all;clear all; clc;C_Segments=5;

10、img_original = imread('dog.png');%讀入圖像figure,imshow(img_original),title('原始圖像'); %顯示原圖像[m,n,depth]=size(img_original ); % 獲取圖像的長(zhǎng)寬% 將圖像進(jìn)行RGB——3通道分解% 將RGB分量各轉(zhuǎn)為kmeans使用的數(shù)據(jù)格式n行，一樣本A = reshape(img_or

11、iginal(:, :, 1), m*n, 1); B = reshape(img_original(:, :, 2), m*n, 1);C = reshape(img_original(:, :, 3), m*n, 1);dat = [A B C]; % r g b分量組成樣本的特征，每個(gè)樣本有三個(gè)屬性值，共width*height個(gè)樣本cRGB = kmeans(double(dat), C_Segments, 20)

12、;rRGB = reshape(cRGB, m, n); % 反向轉(zhuǎn)化為圖片形式figure, imshow(label2rgb(rRGB),[]),title('分類結(jié)果'); % 顯示分割結(jié)果,劃分聚類法 – K-means,分割后的效果,應(yīng)用實(shí)例,劃分聚類法 – K-means,,劃分聚類法 – K-means,應(yīng)用實(shí)例,注：聚類中心個(gè)數(shù)為5，最大迭代次數(shù)為10。,思路將聚類問(wèn)題中的類定義為模糊集

13、合，用模糊集的隸屬度函數(shù)定量描述樣本點(diǎn)與類之間的從屬關(guān)系，并通過(guò)尋找使目標(biāo)函數(shù)最小化的隸屬度函數(shù)，實(shí)現(xiàn)聚類。算法關(guān)鍵點(diǎn)隸屬度函數(shù)的數(shù)學(xué)定義模糊類中心的更新,劃分聚類法 – 模糊C均值聚類 fuzzy c-means,變量定義數(shù)據(jù)集X={x1, x2, … , xn}c個(gè)模糊類樣本xk對(duì)第i類的模糊隸屬度為uik，滿足條件隸屬度矩陣U={uik} 第i類的類中心為vi聚類中心矩陣為V={v1, v2, …, vc}建

14、立基于隸屬度矩陣U和聚類中心矩陣V的目標(biāo)函數(shù)Jm(U,V),劃分聚類法 – 模糊C均值聚類 fuzzy c means,目標(biāo)函數(shù)最小化求解,劃分聚類法 – 模糊C均值聚類 fuzzy c means,這里m>1,是隸屬度的加權(quán)指數(shù); 為第i個(gè)聚類中心與第k個(gè)數(shù)據(jù)樣本之間的歐幾里得距離;,限定條件：,最小化上述函數(shù)可以用拉格朗日乘子法求解,目標(biāo)函數(shù)最小化求解對(duì)上式進(jìn)行求導(dǎo)，使其達(dá)到最小的必要條件為：,劃分聚類法 –

15、模糊C均值聚類 fuzzy c means,公式（1）,公式（2）,模糊C均值聚類算法具體步驟,劃分聚類法 – 模糊C均值聚類 fuzzy c-means (FCM),確定聚類類別數(shù)目c、加權(quán)指標(biāo)m，用0~1的隨機(jī)值初始化隸屬矩陣U(0) ，并滿足令迭代次數(shù)為b，b=0,1,2…bmax根據(jù)公式（2）計(jì)算各個(gè)類的中心Vi(b);根據(jù)公式（1）更新U(b)為U(b+1)；比較U(b)和U(b+1)之間的差別，如果

16、 或者迭代達(dá)到最大次數(shù)，則聚類結(jié)束；否則，置b=b+1并返回第3步。,,劃分聚類法 – 模糊C均值聚類 fuzzy c means,MATLAB中提供了FCM函數(shù)：[center, U, obj_fcn] = fcm(data, cluster_n, options);% 輸入：% data ---- nxm矩陣,表示n個(gè)樣本,每個(gè)樣本具有m的維特征值% N_cluster

17、 ---- 標(biāo)量,表示聚合中心數(shù)目,即類別數(shù)% options ---- 4x1矩陣，其中% options(1): 隸屬度矩陣U的指數(shù)，>1 (缺省值: 2.0)% options(2): 最大迭代次數(shù) (缺省值: 100)% options(3): 隸屬度最小變化量,迭代終止條件 (缺省值: 1e-5

18、)% options(4): 每次迭代是否輸出信息標(biāo)志 (缺省值: 1)% 輸出：% center ---- 聚類中心% U ---- 隸屬度矩陣% obj_fcn ---- 目標(biāo)函數(shù)值,,劃分聚類法 – 模糊C均值聚類 fuzzy c means,應(yīng)用實(shí)例,close all;clear all; clc;C_Segments=4;

19、img_original = imread('pepper.png');%讀入圖像figure,imshow(img_original),title('原始圖像'); %顯示原圖像[m,n,p]=size(img_original ); % 獲取圖像的長(zhǎng)寬% 將圖像進(jìn)行RGB——3通道分解% 將RGB分量各轉(zhuǎn)為kmeans使用的數(shù)據(jù)格式n行，一樣本A = reshape(img_orig

20、inal(:, :, 1), m*n, 1); B = reshape(img_original(:, :, 2), m*n, 1);C = reshape(img_original(:, :, 3), m*n, 1);dat = [A B C]; % r g b分量組成樣本的特征，每個(gè)樣本有三個(gè)屬性值，共width*height個(gè)樣本,,聚類法 – 模糊C均值聚類 fuzzy c means,應(yīng)用實(shí)例,[center,U,

21、fct] = fcm (double(dat),C_Segments);[~, label] = max(U, [],1);figure; LAB = reshape(label,m,n);imshow(LAB,[])figure; map = [0 0 0; center(1,1)/255, center(1,2)/255,center(1,3)/255];imshow(LAB==1),colormap(map)fig

22、ure; map = [0 0 0; center(2,1)/255, center(2,2)/255,center(2,3)/255];imshow(LAB==2),colormap(map)figure; map = [0 0 0; center(3,1)/255, center(3,2)/255,center(3,3)/255];imshow(LAB==3),colormap(map)figure; map = [0

23、0 0; center(4,1)/255, center(4,2)/255,center(4,3)/255];imshow(LAB==4),colormap(map),,聚類法 – 模糊C均值聚類 fuzzy c means,應(yīng)用實(shí)例,分割結(jié)果,,劃分聚類法 – K-medoids,k-中心點(diǎn)(k-Medoids): 不采用簇中對(duì)象的平均值作為參照點(diǎn), 而是選用簇中位置最中心的對(duì)象, 即中心點(diǎn)(medoid)作為參照點(diǎn).,,劃分聚

24、類法 – K-medoids,基本思想:找聚類中的代表對(duì)象(中心點(diǎn))PAM (Partitioning Around Medoids)首先為每個(gè)簇隨意選擇一個(gè)代表對(duì)象, 剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇; 然后反復(fù)地用非代表對(duì)象來(lái)替代代表對(duì)象，以改進(jìn)聚類的質(zhì)量 PAM 對(duì)于較小的數(shù)據(jù)集非常有效, 但不能很好地?cái)U(kuò)展到大型數(shù)據(jù)集。,劃分聚類法 – K-medoids,為了判定一個(gè)非代表對(duì)象Orandom 是否是當(dāng)

25、前一個(gè)代表對(duì)象Oj的好的替代, 對(duì)于每一個(gè)非代表對(duì)象p,考慮下面的四種情況： 第一種情況：p當(dāng)前隸屬于代表對(duì)象 Oj. 如果Oj被Orandom所代替, 且p離Oi最近, i≠j, 那么p被重新分配給Oi 第二種情況：p當(dāng)前隸屬于代表對(duì)象 Oj. 如果Oj 被Orandom代替, 且p離Orandom最近, 那么p被重新分配給Orandom,劃分聚類法 – K-medoids,第三種情況：p當(dāng)前隸屬于Oi，i≠j。如果Oj被Oran

26、dom代替，而p仍然離Oi最近，那么對(duì)象的隸屬不發(fā)生變化 第四種情況：p當(dāng)前隸屬于Oi，i≠j。如果Oj被Orandom代替，且p離Orandom最近，那么p被重新分配給Orandom,劃分聚類法 – K-medoids,算法: k-中心點(diǎn)(1) 隨機(jī)選擇k個(gè)對(duì)象作為初始的代表對(duì)象；(2) repeat(3) 指派每個(gè)剩余的對(duì)象給離它最近的代表對(duì)象所代表的簇；(4) 隨意地選擇一個(gè)非代表對(duì)象Orandom；(5)

27、 計(jì)算用Orandom代替Oj的總距離E, 如果E比取代前下降則則用Orandom替 換Oj，形成新的k個(gè)代表對(duì)象的集合，返回（4）；(6) until 不發(fā)生變化(7) 如果所有非代表對(duì)象都無(wú)法取代已存在的簇中心，則結(jié)束替代過(guò)程，并輸出結(jié)果,劃分聚類法 – K-medoids,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10

28、,0,1,2,3,4,5,6,7,8,9,10,,,,K=2,,Arbitrary choose k object as initial medoids,,,Assign each remaining object to nearest medoids,,Randomly select a nonmedoid object,Oramdom,,Compute total cost of swapping,Total Cost = 26,,

29、Swapping O and Oramdom If quality is improved.,Do loopUntil no change,劃分聚類法 – K-medoids,當(dāng)存在噪音和孤立點(diǎn)時(shí), PAM 比 k-平均方法更健壯. 這是因?yàn)橹行狞c(diǎn)不象平均值那么容易被極端數(shù)據(jù)影響 PAM對(duì)于小數(shù)據(jù)集工作得很好, 但不能很好地用于大數(shù)據(jù)集 每次迭代O(k(n-k)2 )其中 n 是數(shù)據(jù)對(duì)象數(shù)目, k 是聚類數(shù),CLARA (

30、Clustering LARge Applications),Improvement over PAMFinds medoids in a sample from the dataset[Idea]: If the samples are sufficiently random, the medoids of the sample approximate the medoids of the dataset[Heuristics]

31、: 5 samples of size 40+2k gives satisfactory resultsWorks well for large datasets (n=1000, k=10),劃分聚類法 – K-medoids,CLARA (Clustering LARge Applications),劃分聚類法 – K-medoids,Draw multiple samples of the datasetSample shou

32、ld be able to represent the datasetApply PAM to each sampleReturn the best clustering,Set mincost to MAXIMUM;Repeat q times // draws q samplesCreate S by drawing s objects randomly from D;Generate the set of medoids

33、 M from S by applying the PAM algorithm;Compute cost(M,D)If cost(M,D)< mincost Mincost = cost(M, D); Bestset = M;End if;End repeat;Return Bestset;,Algorithms:,CLARA (Clustering LARge Applications),劃分聚類法 –

34、K-medoids,s: the size of the samplek: number of clustersn:number of objects,Complexity of each iteration is: O(ks2+k(n-k)),CLARA (Clustering LARge Applications),劃分聚類法 – K-medoids,PAM find the best K medoids from a give

35、n dataset;CLARA finds the best kMedoids from several selected samples.,Problems:The best k-medoids may not be selected during the sampling Process, in this case, CLARA will never find the best clusteringIf the samplin

36、g is biased, we can not have a good clustering.Trade off-of efficiency.,CLARANS (Clustering Large Applications based on Randomized Search),劃分聚類法 – K-medoids,It was proposed to improve the quality and scalability of CLAR

37、AIt combines sampling techniques with PAMIt does not confine itself to any sample at a given timeIt draws a sample with some randomness in each step of the search,CLARANS draws sample in solution space dynamicallyA s

38、olution is a set of k medoidsThe solutions space contains Cnk solutions in totalThe solution space can be represented by a graph where every node is a potential solution, i.e., a set of k medoids,CLARANS,劃分聚類法 – K-medo

39、ids,Every node is a potential solution (k-medoid)Every node is associated with a squared errorTwo nodes are adjacent if they differ by one medoidEvery node has k(n?k) adjacent nodes,,{O1,O2,…,Ok},,{Ok+1,O2,…,Ok},,{Ok+

40、n,O2,…,Ok},,,…,,n-k neighbors for one medoid,,k(n? k) neighbors for one node,…,,劃分聚類法 – K-medoids: CLARANS,Start with a randomly selected node, check at most m neighbors randomlyIf a better adjacent node is found, moves

41、 to node and continue; otherwise, current node is local optimum; re-starts with another randomly selected node to search for another local optimumWhen h local optimum have been found, returns best result as overall resu

42、lt,劃分聚類法 – K-medoids: CLARANS,<,,Compare no more than maxneighbor times,,Best Node,劃分聚類法 – K-medoids: CLARANS,Algorithms:,Set mincost to MAXIMUM; For i=1 to h do // find h local optimumRandomly select a node as the

43、 current node C in the graph;J = 1; // counter of neighborsRepeatRandomly select a neighbor N of C;If Cost(N,D) mUpdate mincost with Cost(C,D) if applicable End for;End ForReturn bestnode;,劃分聚類法 – K-medoids: CL

44、ARANS,Algorithms:,Notes:,Each vertex is a set of k-representative objects (means, modes, medoids)Each iteration produces a new set of k-representative objects with lower overall dissimilarityIterations correspond to a

45、hill descent process in a landscape (graph) of vertices,劃分聚類法 – K-medoids: CLARANS,Advantages:CLARANS is more effective than both PAM and CLARAHandles outliersDisadvantages:Computational complexity of CLARANS is O(N