數(shù)據(jù)分析聚類分析

聚類分析：聚類分析(ClusterAnalysis)是一個(gè)將數(shù)據(jù)集中的所有數(shù)據(jù)，按照相似性劃分為多簇是相似數(shù)據(jù)的集合。聚類分析是一種無監(jiān)督分類方法：數(shù)據(jù)集中的數(shù)據(jù)沒有預(yù)定義的類別標(biāo)號(hào)(無訓(xùn)練集和訓(xùn)練的過程)。要求：聚類分析之后，應(yīng)盡可能保證類別相同的數(shù)據(jù)之間具有較高的相似性，而類別不同的數(shù)據(jù)之間具有較低的相似性。聚類分析在數(shù)據(jù)挖掘中的作用：作為一個(gè)獨(dú)立的工具來獲得數(shù)據(jù)集中數(shù)據(jù)的分布情況；作為其他數(shù)據(jù)挖掘算法的預(yù)處理步驟。聚類分析的典型應(yīng)用：圖像處理——灰度圖像的二值化(對灰度像素進(jìn)行聚類)。對WEB日志數(shù)據(jù)進(jìn)行聚類，以發(fā)現(xiàn)類似的用戶訪問模式。用戶交易數(shù)據(jù)的聚類分析，以獲得奇異點(diǎn)(異常交易)。常用的聚類分析方法：劃分法：以距離作為數(shù)據(jù)集中不同數(shù)據(jù)間的相似性度量，將數(shù)據(jù)集劃分成多個(gè)簇。層次法：對給定的數(shù)據(jù)集進(jìn)行層次分解，形成一個(gè)樹形的聚類結(jié)果。屬于這樣的聚類方法有：自頂向下法、自底向上法。相似性計(jì)算方法4特例：當(dāng)兩個(gè)樣本之間的距離為零時(shí)，表示樣本之間的距離是在樣本的描述屬性(特征)上進(jìn)行計(jì)算的。連續(xù)性屬性(如：重量、高度、年齡等)二值離散型屬性(如：性別、考試是否通過等)多值離散型屬性(如：收入分為高、中、低等)混合類型屬性(上述類型的屬性至少同時(shí)存在兩種)q=1pointXYpl02p220p331p45pl0p22.8280p33.16202p45.0993.16220polntXYpl02p220p331p451pl pl0 p24 p34 p46p24024p34202p46420二值離散型屬性只有0和1兩個(gè)取值。1X■如果樣本的屬性都是對稱的二值離散型屬如果樣本的屬性都是不對稱的二值離散型屬性，則樣本間的距離可用Jaccard系數(shù)計(jì)和aathenumberofatributeswacthenumberofattributesw多值離散型屬性的相似性計(jì)算方法：多值離散型屬性是指取值個(gè)數(shù)大于2的離散型屬性。例如：成績可以分為優(yōu)、良、中、差。假設(shè)一個(gè)多值離散型屬性的取值個(gè)數(shù)為N,給定數(shù)據(jù)集X={x;|i=1,2,..,total}。=(xj,x?,.,xu),如何計(jì)算它們之間的距離?□方法二：先將多值離散型屬性轉(zhuǎn)換成多個(gè)二值離散型屬性，然后再使用Jaccard系數(shù)計(jì)算樣本距離計(jì)算公式如下：樣本序號(hào)學(xué)歷收入X高X2低X?X老年本科以下中X4中年高ud(xj,x?)=(3-2)/3≈0.3方法二：先將多值離散型屬性轉(zhuǎn)換成多個(gè)二值學(xué)歷收入X高X?X低X?X本科以下中X中年高青中老年以下本科高中低X1001100X?X1010001X?X0100010X4010001100問題：對于包含混合類型屬性的數(shù)據(jù)集，在聚類之前，對樣本的屬性值進(jìn)行預(yù)處理：對連續(xù)型屬性，將其各種取值進(jìn)行規(guī)范化處理，使得屬性值規(guī)范化到區(qū)間[0.0,1.0];其轉(zhuǎn)換成多個(gè)二值離散型屬性。預(yù)處理之后，樣本中只包含連續(xù)型屬性和二值離散型屬性。典型的劃分方法：□k-means(k-均值)□k-medoids(k-中心點(diǎn))由處于簇中心區(qū)域的某個(gè)樣本代表整個(gè)簇。序號(hào)屬性1屬性21序號(hào)屬性1屬性2123322455111 根據(jù)所給的數(shù)據(jù)通過對其實(shí)施k-means(設(shè)n=8,k=2),根據(jù)所給的數(shù)據(jù)通過對其實(shí)施k-means(設(shè)n=8,k=2),其主第一次迭代：假定隨機(jī)選擇的兩個(gè)對象，如序2)和(3,4,5,6,7,8)。對于(1,2),平均值點(diǎn)為(1.5,1);對于[3,4,5,6,7,8},平均值點(diǎn)為(3.5,3)。即將所有點(diǎn)按離平均值點(diǎn)(1.5,1)、(3.5,3)最近的原則重新分配。得到兩個(gè)新的簇：(1,2,3,4)和[5,6,7,8}.重新計(jì)算簇平均值點(diǎn)，得到新的平均值點(diǎn)為(1.5,1.5)和(4.5,3.5)。第三次迭代：將所有點(diǎn)按離平均值點(diǎn)(1.5,1.5)和(4.5,3.5)最近的原則重新分配，調(diào)整對象，簇仍然為[1,2,3,4)和[5,6,7,8},發(fā)現(xiàn)沒有出現(xiàn)重新分配，而且準(zhǔn)則函數(shù)選代次數(shù)平均值平均值產(chǎn)生的新族新平均值新平均值(簇1)(簇2)(簇1)(簇2)(1,1)(1,2)(1,2),[3,4,5,6,7,8(1.5,1)(3.5,3) 的類內(nèi)龍我的零旋族而他寬齡類在間借可能分□對于同一個(gè)數(shù)據(jù)集，由于k-means算法對初始選取的聚類中心敏感，因此可用該準(zhǔn)則評價(jià)聚類達(dá)到全局最優(yōu)，只能達(dá)到局部最優(yōu)。□可擴(kuò)展性較好，算法復(fù)雜度為O(nkt)?！醮?cái)?shù)目k需要事先給定，但非常難以選定；□初始聚類中心的選擇對聚類結(jié)果有較大的影響；□對噪聲和離群點(diǎn)數(shù)據(jù)敏感?！踹x取有代表性的樣本(而不是均值)來表示整個(gè)簇，即：選取最靠近中心點(diǎn)(medoid)的那個(gè)樣本來代表整個(gè)簇?！跻越档途垲愃惴▽﹄x群點(diǎn)的敏感度。的劃分)算法，于1987年提出。AlgorithmmedoidsPAMakmedoidsdlgorithmforpartitioni ■其中：n是數(shù)據(jù)集中樣本的個(gè)數(shù)；Cpin表示中心點(diǎn)O,被非中心點(diǎn)O,替代后，樣本點(diǎn)p的代價(jià)?！栴}：如何計(jì)算每個(gè)樣本點(diǎn)p產(chǎn)生的代價(jià)Cm?O0+p+p的隸屬不發(fā)生變化，00p9p被重新分配給O假設(shè)空間中的五個(gè)點(diǎn){A、B、C、D、E},如下圖所示。各點(diǎn)之間的距離關(guān)系如下表所示，根據(jù)所給的數(shù)據(jù)對其運(yùn)行k-medoids算法實(shí)現(xiàn)劃分聚類(設(shè)k=2)。ABCDE33530A0122B1024C2201D2410E3353第一步建立階段：假如從5個(gè)對象中第一步建立階段：假如從5個(gè)對象中隨機(jī)抽取的2個(gè)中心點(diǎn)為{A,B},則樣本被劃分為{A、C、D}和{B、E},如圖所示?！龅诙浇粨Q階段：假定中心點(diǎn)A、根據(jù)PAM算法需要計(jì)算下列代價(jià)e)E原先屬于B中心點(diǎn)所在的簇，當(dāng)A被C替換以后，離E最近的中心仍然是B,根據(jù)PAM算法代價(jià)函數(shù)的第三種情況CEac=0。可按上述步驟依次計(jì)算代價(jià)TC、TC以及TCac、TCm、TCBE·當(dāng)存在噪聲和離群點(diǎn)時(shí)，k-medoids算法比k-means算法更加魯棒(穩(wěn)定)。k-medoids算法的執(zhí)行代價(jià)比k-means算法要兩種方法都需要事先指定簇的數(shù)目k。對給定的數(shù)據(jù)集進(jìn)行層次分解：□自底向上方法(合并):開始時(shí)，將每個(gè)樣本作為單獨(dú)的一個(gè)組；然后，依次合并相近的樣本或組，直至所有樣本或組被合并為一個(gè)組或者達(dá)到終止條件為止。□自頂向下方法(分裂):開始時(shí)，將所有樣本置于一個(gè)簇中；然后，執(zhí)行迭代，在迭代的每一步中，一個(gè)簇被分裂為多個(gè)更小的簇，直至每個(gè)樣本分別在一個(gè)單獨(dú)的簇中或者達(dá)到終止條件為止。AGNES(AgglomerativeNesting)算法合并準(zhǔn)則：每次找到距離最近的兩個(gè)簇進(jìn)行合并。AGNESAGNES算法(自底向上合并算法)AGNES算法在這個(gè)算法中，需要使用單鏈接(Single-Link)方法和相異度矩陣?！鯁捂溄臃椒ㄓ糜诖_定任意兩個(gè)簇之間的距離；□相異度矩陣用于記錄任意兩個(gè)簇之間的距離(它是一個(gè)下三角矩陣，即：主對角線及其上方表1數(shù)據(jù)集2空江0211.6705個(gè)樣本之間的相異度矩陣015dy=13.80dμ=13,12d;sdydy2340河南與甘肅的距離最進(jìn)，先將二者(3和4)合為一類G6=[G3.G4]——doi=d34?=min{d,d?)=13.12d??=d?zmin620河南、甘肅與青海并為一新類采用歐氏距離：d?2=d?45i?=min(d2,dd700808AGNES算法AGNES算法的優(yōu)、缺點(diǎn)：□算法簡單，但有可能遇到合并點(diǎn)選擇困難的情□在該種層次聚類算法中，也是以希望得到的簇的數(shù)目作為聚類的結(jié)束條件。同時(shí)，使用下面兩種測度方法：簇的直徑：在一個(gè)簇中，任意兩個(gè)樣本間距離的最大值。平均相異度(平均距離):輸入：包含n個(gè)樣本的數(shù)據(jù)集，終止條件簇的數(shù)目k。輸出：k個(gè)簇，達(dá)到終止條件規(guī)定的簇的數(shù)目。例：有如下表所示的數(shù)據(jù)集，使用DIANA算法對該數(shù)據(jù)集進(jìn)行分裂層次聚類。12345678屬性1屬性211223344第1步，首先找到具有最大直徑的簇，然后計(jì)算該簇中每個(gè)樣本的平均相異度(假定采用是歐式距2345678屬性1112233441212454500第1步，首先找到具有最大直徑的簇，然后計(jì)算第1步，首先找到具有最大直徑的簇，然后計(jì)算該簇中每個(gè)樣本的平均相異度(假定采用是歐式距樣本5的平均距離為：2.18樣本6的平均距離為：2.68大于該樣本與oldparty中其他樣本之間的最小距離，述條件的是樣本2。group中的樣本，并且此時(shí)達(dá)到算法的終止條件(k=2),算法結(jié)束。(如果沒有達(dá)到算法的終止條件，應(yīng)該從分裂出來的簇中再挑選一個(gè)具有直徑最大的簇繼續(xù)分裂。){2,3,4,5,6,7,8}{3,4,5,6.7,8}2,3,4,5,6,7,8]{1,2,3}[4,5,6,7.8}2,3,4,5,6,7,8]{1,2,3,4){5,6,7,8]2.3,4,5,6,7,8j(1