聚類(lèi)分析(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-31 06:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-12-31 06:30:01 來(lái)源：信息時(shí)代

    聚類(lèi)分析 : 根據(jù)最大化類(lèi)內(nèi)的相似性、最小化類(lèi)間的相似性的原則將數(shù)據(jù)對(duì)象分組,所形成的每個(gè)分組稱(chēng)為簇,是一個(gè)數(shù)據(jù)對(duì)象類(lèi),用顯式或隱式的方法描述它們。
給定一個(gè)數(shù)據(jù)集D,D={X₁,X₂,…,X_i,…,X_n},其中,X_i(1≤i≤n)是D中的一個(gè)數(shù)據(jù)對(duì)象,由d個(gè)屬性值組成。X_i＝(x_i1,x_i2,…,x_ij,…,x_id),其中x_ij表示對(duì)象X_i中的屬性,d是屬性個(gè)數(shù)(或?qū)ο罂臻g的維數(shù))。
簇(cluster):數(shù)據(jù)集D分成k個(gè)簇{C₁,C₂,…,C_i,…,C_k}(1<=i<=k),每個(gè)簇C_i是相似對(duì)象的集合。相似對(duì)象在同一簇中,相異對(duì)象在不同簇中。C_i是D的子集,要求滿(mǎn)足如下條件:
C₁∪C₂∪…∪C_k＝D, 且C_i∩C_j＝ф(i≠j)。
當(dāng)有重疊聚類(lèi)時(shí), 允許C_i∩C_j≠ф(i≠j)。
簇C_i的特征由簇的質(zhì)心和半徑描述:
(1)簇的質(zhì)心(centroid):是簇的中間值(middle),即對(duì)象的平均值,但并不一定是簇中的實(shí)際點(diǎn)。
令n_i表示簇C_i中對(duì)象的數(shù)量,m_i表示對(duì)應(yīng)對(duì)象的均值,則簇C_i的質(zhì)心centroid由下式計(jì)算得出:

(2)簇的半徑(radius): 是簇中任意一點(diǎn)到質(zhì)心之間距離的均方差的平方根(average mean squared distance),如下式:

聚類(lèi)(clustering): 根據(jù)數(shù)據(jù)對(duì)象間的相似程度將數(shù)據(jù)集D劃分成k簇: {C₁,C₂,…,C_k},使得每個(gè)簇中的數(shù)據(jù)對(duì)象之間盡可能的相似,而與其他簇中的數(shù)據(jù)對(duì)象盡可能的不相似(即相似對(duì)象在同一簇中,相異對(duì)象在不同簇中)的過(guò)程稱(chēng)為聚類(lèi)。當(dāng)無(wú)重疊聚類(lèi)時(shí),要求滿(mǎn)足條件∪_i=1^kC_i＝D且C_i∩C_j=ф(i≠j); 當(dāng)有重疊聚類(lèi)時(shí), 允許C_i∩C_j≠ф(i≠j)。
同一個(gè)簇中的對(duì)象比來(lái)自不同簇的對(duì)象更為相似的判斷問(wèn)題主要涉及以下兩個(gè)子問(wèn)題:
1. 如何度量對(duì)象之間的相似性
相似度(或相異度): 衡量?jī)蓚€(gè)對(duì)象之間的相似(或差異)程度。它是定義一個(gè)簇的基礎(chǔ),影響聚類(lèi)分析過(guò)程的質(zhì)量。對(duì)象間的相似度(或相異度)的量化由相似性函數(shù)或距離函數(shù)來(lái)實(shí)現(xiàn)。兩個(gè)對(duì)象間依據(jù)距離函數(shù)計(jì)算出的值越大,則表示它們之間的相似性越小(差別越大),而相似性函數(shù)則相反。相似性函數(shù)和距離函數(shù)之間可以相互轉(zhuǎn)換。設(shè)f是一個(gè)距離函數(shù),值域在[0,1]之間,0表示兩個(gè)對(duì)象相等,而1表示兩個(gè)對(duì)象完全不同,其他數(shù)值則表示介于中間。它對(duì)應(yīng)的相似性函數(shù)可以是: 1-f(·)或者1/(1+f(·))。在很多應(yīng)用中需要f是一個(gè)度量(metric),滿(mǎn)足以下性質(zhì):
非負(fù)性:對(duì)數(shù)據(jù)集D中的對(duì)象X_i和X_j,有f(X_i,X_j)≥0,當(dāng)且僅當(dāng)X_i和X_j的d個(gè)屬性值對(duì)應(yīng)相等時(shí),f(X_i,X_j)＝0。
對(duì)稱(chēng)性:對(duì)數(shù)據(jù)集D中的對(duì)象X_i和X_j,有f(X_i,X_j)＝f(X_j,X_i)。
三角不等式: 即對(duì)數(shù)據(jù)集D中的對(duì)象X_i,X_j,X_k,有f(X_i,X_j)≤f(X_i,X_k)+f(X_k,X_j)。
一個(gè)函數(shù)滿(mǎn)足三角不等式的優(yōu)點(diǎn)是能夠提高搜索效率。例如設(shè)有對(duì)象X₁,X₂,X₃,和滿(mǎn)足三角不等式的距離函數(shù)f,如果已經(jīng)知道f(X₁,X₂₎+f(X₂,X₃₎小于等于某個(gè)數(shù)值k,則有f(X₁,X₃₎≤f(X₁,X₂₎+f(X₂,X₃₎≤k,故可以在不計(jì)算X₁,X₃之間距離值的情況下直接推斷f(X₁,X₃₎小于k。因?yàn)閒(S₂,S₃₎可以預(yù)先計(jì)算好,所以搜索算法可依賴(lài)中間節(jié)點(diǎn)X₂縮小搜索的空間。
對(duì)于相似度對(duì)稱(chēng)性和非負(fù)性通常成立,但通常沒(méi)有與三角不等式對(duì)應(yīng)的一般性質(zhì)。有時(shí)相似度也可以容易地將變換成一種度量距離,如Jaccard系數(shù)。
2. 如何衡量對(duì)數(shù)據(jù)集聚類(lèi)的好壞
評(píng)價(jià)聚類(lèi)過(guò)程質(zhì)量的另一個(gè)標(biāo)準(zhǔn)是簇間距離度量標(biāo)準(zhǔn)。常用于簇C_i和C_j間的距離度量標(biāo)準(zhǔn)是:
(1)最小距離: D_min(C_i,C_j)＝min|X_i-X_j|,其中X_i∈C_i和X_j∈C_j。
(2)最大距離:D_max(C_i,C_j)＝max|X_i-X_j|,其中X_i∈C_i和X_j∈C_j。
(3)中間距離:D_mean(C_i,C_j)＝max|m_i-m_j|,其中m_i和m_j是C_i和C_j的質(zhì)心。
(4)平均距離:D_avg(C_i,C_j)＝1/(n_in_j)∑∑|X_i-X_j|,
其中X_i∈C_i和X_j∈C_j,且n_i和n_j分別是簇C_i和C_j的對(duì)象數(shù)目。
聚類(lèi)分析過(guò)程包括以下幾個(gè)步驟:
步驟1: 收集數(shù)據(jù)對(duì)象。
步驟2: 屬性選擇從原始屬性中選取用于聚類(lèi)的更有效的屬性子集,屬性抽取利用對(duì)輸入屬性的一次或多次轉(zhuǎn)換產(chǎn)生新的更顯著的屬性。
步驟3: 計(jì)算相似度。
步驟4: 確定目標(biāo)劃分的簇的數(shù)目或聚類(lèi)劃分的某個(gè)終止條件。由聚類(lèi)算法實(shí)現(xiàn)。
步驟5: 實(shí)施聚類(lèi)分析,產(chǎn)生結(jié)果。
主要的聚類(lèi)算法有基于劃分的方法(partitioning method)、基于層次的方法(hierarchical method)、基于密度的方法(density-based method)、基于網(wǎng)格的方法(grid-based method)以及基于模型的方法(model-based method)等。
評(píng)價(jià)聚類(lèi)算法的聚類(lèi)分析能力的標(biāo)準(zhǔn)有: ①能夠適用于大數(shù)據(jù)量; ②能夠處理不同類(lèi)型數(shù)據(jù); ③能夠發(fā)現(xiàn)任意形狀的簇; ④能夠處理高維數(shù)據(jù); ⑤具有處理噪聲的能力: ⑥聚類(lèi)結(jié)果具有可解釋性、可使用性等。