Clustering聚類分析

1、Clustering聚類分析聚類分析江川江川2013.8.7聚類聚類 分類分類 相似的歸為一類相似的歸為一類 不相似的歸入不同類不相似的歸入不同類 未知類未知類 僅依靠對(duì)象的相似度僅依靠對(duì)象的相似度應(yīng)用應(yīng)用 生物學(xué)生物學(xué) 經(jīng)濟(jì)學(xué)經(jīng)濟(jì)學(xué) 應(yīng)用應(yīng)用 文檔分類文檔分類 文檔文檔向量向量 1、分量、分量 表示第表示第i個(gè)詞條的頻率個(gè)詞條的頻率 2、分量、分量 為為0或或1，表示是否引用第，表示是否引用第i篇文檔篇文檔 ,.,21naaaAiaia應(yīng)用應(yīng)用 社交網(wǎng)絡(luò)社交網(wǎng)絡(luò) 對(duì)象間的比較對(duì)象間的比較 相似度相似度 例：例： 距離（不相似度）距離（不相似度） 例：例： 歐幾里得距離歐幾里得距離),cos(

2、ba),cos(1ba距離函數(shù)的選擇距離函數(shù)的選擇 根據(jù)數(shù)據(jù)的情況選擇根據(jù)數(shù)據(jù)的情況選擇 例：將圖中的點(diǎn)按連邊情況分類例：將圖中的點(diǎn)按連邊情況分類 點(diǎn)表示成鄰接矩陣的行點(diǎn)表示成鄰接矩陣的行 a=(0,1,0,1,0,1) b=(0,1,1,0,1,0) 14|2baba研究顧客的行為研究顧客的行為 D種商品種商品 N個(gè)顧客個(gè)顧客 K種顧客類型，種顧客類型，KN 每種類型的顧客購(gòu)買物品的情況滿每種類型的顧客購(gòu)買物品的情況滿足一種概率分布足一種概率分布 研究顧客的行為研究顧客的行為 顧客顧客1：2種蔬菜，種蔬菜，3種水果，種水果，1種海鮮，種海鮮，0種零食，種零食， 顧客顧客2：1種蔬菜，種蔬菜，

3、3種水果，種水果，1種海鮮，種海鮮，1種零食種零食 顧客顧客3：4種蔬菜，種蔬菜，0種水果，種水果，3種海鮮，種海鮮，2種零食種零食 顧客顧客4：0種蔬菜，種蔬菜，0種水果，種水果，0種海鮮，種海鮮，4種零食種零食 顧客顧客5：3種蔬菜，種蔬菜，1種水果，種水果，5種海鮮，種海鮮，1種零食種零食 可能的結(jié)果：可能的結(jié)果： 1,2 3,5 4 顧客顧客1( 2 , 3 , 1 , 0 ) 蔬菜蔬菜 水果水果 海鮮海鮮 零食零食 判斷標(biāo)準(zhǔn)判斷標(biāo)準(zhǔn) 每個(gè)類中，所有對(duì)象間的距離之和每個(gè)類中，所有對(duì)象間的距離之和 每個(gè)類中，所有對(duì)象到每個(gè)類中，所有對(duì)象到“中心中心”的距離之和的距離之和 k-median

4、 criterion 每個(gè)類中，所有對(duì)象到每個(gè)類中，所有對(duì)象到“中心中心”的距離平方之的距離平方之和和 k-means criterion 通過(guò)最小化這些值得到最優(yōu)的劃分通過(guò)最小化這些值得到最優(yōu)的劃分判斷標(biāo)準(zhǔn)的選擇判斷標(biāo)準(zhǔn)的選擇 根據(jù)分類的目標(biāo)，依靠經(jīng)驗(yàn)根據(jù)分類的目標(biāo)，依靠經(jīng)驗(yàn) 例：距離的平方和例：距離的平方和 1、異常點(diǎn)的誤差被放大，得到更多關(guān)注、異常點(diǎn)的誤差被放大，得到更多關(guān)注 2、數(shù)學(xué)計(jì)算上的優(yōu)勢(shì)、數(shù)學(xué)計(jì)算上的優(yōu)勢(shì)最優(yōu)化判斷標(biāo)準(zhǔn)最優(yōu)化判斷標(biāo)準(zhǔn) 通常是通常是NP-Hard 多項(xiàng)式算法多項(xiàng)式算法 并非精確的最優(yōu)解，而是相對(duì)優(yōu)的解或者局并非精確的最優(yōu)解，而是相對(duì)優(yōu)的解或者局部的最優(yōu)解部的最優(yōu)解

5、算法一算法一 判斷標(biāo)準(zhǔn)：判斷標(biāo)準(zhǔn)：k-center criterion 最小化任意點(diǎn)到所分的類中心的最大距離最小化任意點(diǎn)到所分的類中心的最大距離 基本思想：基本思想： 存在存在k個(gè)半徑為個(gè)半徑為r的球體覆蓋所有點(diǎn)的球體覆蓋所有點(diǎn) 存在最大距離為存在最大距離為r的劃分的劃分算法一算法一 步驟步驟 每次選取一個(gè)未被覆蓋的每次選取一個(gè)未被覆蓋的數(shù)據(jù)數(shù)據(jù)點(diǎn)作為一個(gè)類點(diǎn)作為一個(gè)類的中心，作半徑為的中心，作半徑為r的球體，覆蓋某些點(diǎn)。重復(fù)的球體，覆蓋某些點(diǎn)。重復(fù)k次得到次得到k個(gè)類。個(gè)類。算法一算法一 不靠譜？有點(diǎn)不靠譜？有點(diǎn) 但是：但是： 若存在最大距離為若存在最大距離為r/2的劃分，這個(gè)算法一定的劃分

6、，這個(gè)算法一定能找到最大距離不超過(guò)能找到最大距離不超過(guò)r的劃分。的劃分。 證明：反證法證明：反證法 假設(shè)無(wú)法找到最大距離為假設(shè)無(wú)法找到最大距離為r的劃分的劃分 至少一個(gè)點(diǎn)不在至少一個(gè)點(diǎn)不在k個(gè)半徑為個(gè)半徑為r的球體中的球體中 存在存在k+1個(gè)點(diǎn)兩兩的距離大于個(gè)點(diǎn)兩兩的距離大于r k個(gè)半徑為個(gè)半徑為r/2的球體無(wú)法覆蓋這的球體無(wú)法覆蓋這k+1個(gè)點(diǎn)個(gè)點(diǎn) 不存在最大距離為不存在最大距離為r/2的劃分（矛盾）的劃分（矛盾）類中心類中心 要求類中心必須是數(shù)據(jù)點(diǎn)要求類中心必須是數(shù)據(jù)點(diǎn) 類的劃分有限，可窮舉類的劃分有限，可窮舉 類中心可以是空間中的任意點(diǎn)（使距離函類中心可以是空間中的任意點(diǎn)（使距離函數(shù)最小的

7、點(diǎn)）數(shù)最小的點(diǎn)） 結(jié)果精確結(jié)果精確 某些判斷標(biāo)準(zhǔn)下，類中心具有特殊性質(zhì)某些判斷標(biāo)準(zhǔn)下，類中心具有特殊性質(zhì)算法二算法二 判斷標(biāo)準(zhǔn)：判斷標(biāo)準(zhǔn)：k-means criterion 將將d維的點(diǎn)集維的點(diǎn)集 劃分到劃分到k個(gè)聚類個(gè)聚類 中，最小化所有點(diǎn)到所分的類中心（中，最小化所有點(diǎn)到所分的類中心（c）的）的距離平方之和。距離平方之和。 minimize ,.,21naaaA kjSaijjiac12)(kSSS,.,21算法二算法二 最好的中心是類中所有點(diǎn)的重心最好的中心是類中所有點(diǎn)的重心 證明：證明： 設(shè)設(shè)x為一個(gè)類的中心，類中有為一個(gè)類的中心，類中有 m個(gè)點(diǎn)。個(gè)點(diǎn)。則距離的平方和可以表示為則距離的

8、平方和可以表示為 maaa,.,21iixa2iixcca222)()(2xcmcaxccaiiii定值定值0 x=c時(shí)最小時(shí)最小算法二算法二 初始情況：選取初始情況：選取k個(gè)點(diǎn)作為個(gè)點(diǎn)作為k個(gè)類的中心個(gè)類的中心 操作一：將每個(gè)數(shù)據(jù)點(diǎn)歸入最近的中心所在類操作一：將每個(gè)數(shù)據(jù)點(diǎn)歸入最近的中心所在類 操作二：對(duì)每個(gè)類，將類的中心更新為類中所操作二：對(duì)每個(gè)類，將類的中心更新為類中所有數(shù)據(jù)點(diǎn)的重心有數(shù)據(jù)點(diǎn)的重心 終止條件：重復(fù)兩個(gè)操作直到距離的平方和逼終止條件：重復(fù)兩個(gè)操作直到距離的平方和逼近局部最優(yōu)近局部最優(yōu) 算法二算法二 例子： n=9,k=3算法二算法二 例子： n=9,k=3算法二算法二 例子： n=9,k=3算法二算法二 終止條件終止條件 算法一定會(huì)向局部最優(yōu)解收斂，因?yàn)橹貜?fù)的兩個(gè)算法一定會(huì)向局部最優(yōu)解收斂，因?yàn)橹貜?fù)的兩個(gè)操作都在不斷優(yōu)化距離平方和操作都在不斷優(yōu)化距離平方和 操作一操作一 操作二操作二 設(shè)置誤差標(biāo)準(zhǔn)以逼近局部最優(yōu)解設(shè)置誤差標(biāo)準(zhǔn)以逼近局部最優(yōu)解算法二算法二 初始情況初始情況 初始時(shí)對(duì)于初始時(shí)對(duì)于k個(gè)點(diǎn)的選法不同，也會(huì)使收斂的結(jié)果個(gè)點(diǎn)的選法不同，也會(huì)使收斂的結(jié)果不同，因此無(wú)法得到全局最優(yōu)解。不同，因此無(wú)法得到