聚類分析ppt課件(2)(存儲(chǔ)版)
【正文】 59 K中心點(diǎn)聚類算法 基本策略： ? 首先為每個(gè)簇隨意選擇一個(gè)代表對(duì)象，稱為中心點(diǎn)，剩余的對(duì)象根據(jù)其與中心點(diǎn)間的距離分配給最近的一個(gè)簇。 算法 91 AGNES（自底向上凝聚算法） 輸入 ： 包含 n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，終止條件簇的數(shù)目 k。 （ 7） UNTIL 沒有新的 old party的點(diǎn)被分配給 splinter group； （ 8） splinter group和 old party為被選中的簇分裂成的兩個(gè)簇，與其它簇一起組成新的簇集合。 基于層次的聚類方法 大體上，主要的聚類算法可以劃分為如下幾類： （ 1）劃分方法； （ 2）層次方法； （ 3）基于密度的方法； （ 4）基于網(wǎng)格的方法； （ 5）基于模型的方法 。 先介紹該方法中涉及到的一些基本的定義。 85 基于密度的方法： DBSCAN 定義 5： 密度相連的：如果對(duì)象集合 D中存在一個(gè)對(duì)象 o，使得對(duì)象 p和 q是從 o關(guān)于 ε和 MinPts密度可達(dá)的，那么對(duì)象 p和 q是關(guān)于 ε和 MinPts密度相連的 。 88 DBSCAN算法描述 DBSCAN算法描述 算法 93 DBSCAN 輸入：包含 n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，半徑 ε，最少數(shù)目 MinPts。 ? 然后， DBSCAN反復(fù)地尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過程可能涉及一些密度可達(dá)簇的合并。 84 基于密度的方法： DBSCAN 定義 4： 密度可達(dá)的：如果存在一個(gè)對(duì)象鏈 p1， p2， … ， pn，p1=q， pn=p，對(duì) pi∈ D，（ 1=i=n）， pi+1是從 pi關(guān)于 ε和 MitPts直接密度可達(dá)的，則對(duì)象 p是從對(duì)象 q關(guān)于 ε和 MinPts密度可達(dá)的。該算法將具有足夠高密度的區(qū)域劃分為簇，并可以在帶有噪聲的空間數(shù)據(jù)中發(fā)現(xiàn)任意形狀的聚類。簇的分裂過程反復(fù)進(jìn)行，直到最終每個(gè)新的簇只包含一個(gè)對(duì)象。 i≠k。 68 層次方法 層次方法： 該方法對(duì)給定的數(shù)據(jù)對(duì)象集合進(jìn)行層次分解，根據(jù)層次分解的方式，層次的方法被分為凝聚的和分裂的： ?凝聚層次方法 ：也稱自底向上方法，一開始將每個(gè)對(duì)象作為單獨(dú)的一組，然后相繼地合并相近的對(duì)象或組，直到所有的組合并為一個(gè)，或達(dá)到某個(gè)終止條件，代表： AGNES算法； ? 分裂層次方法 ：也稱自頂向下方法，一開始所有對(duì)象置于一個(gè)簇中，在迭代的每一步，一個(gè)簇被分裂為更小的簇，直到最終每個(gè)對(duì)象單獨(dú)為一個(gè)簇，或達(dá)到某個(gè)終止條件，代表： DIANA算法。 53 示例 54 示例 55 示例 56 示例 2. k中心點(diǎn)（ kmediods）聚類算法？ 58 K中心點(diǎn)聚類算法 ?K平均（ kmeans）算法對(duì)于孤立點(diǎn)是敏感的，如何消除？ ? 思路 ：不采用簇中對(duì)象的平均值作為參照點(diǎn)，而選用簇中位置最中心的對(duì)象，即中心點(diǎn)（ mediod），仍然基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和的原則來進(jìn)行。 ?一個(gè)好的劃分的一般 準(zhǔn)則 ： ?在同一個(gè)類內(nèi)的對(duì)象間盡可能接近或相似 (high intraclass similarity)； ?不同類中的對(duì)象間盡可能遠(yuǎn)離或不同 (low interclass similarity) 。 ? 一種更可取的方法是將所有的變量一起處理，只進(jìn)行一次聚類分析。此處的整數(shù)僅是為方便數(shù)據(jù)處理而采用的，并不代表任何的特定的順序。 ?基于對(duì)稱二元變量的相似度，稱為恒定的相似度。給定一個(gè)屬性變量 f，可用如下公式對(duì)其進(jìn)行標(biāo)準(zhǔn)化： （ 1）計(jì)算平均的絕對(duì)偏差 |)|...|||(|1 21 fnffffff mxmxmxns ???????其中 x1f, x2f,…,x nf是變量 f的 n個(gè)測(cè)量值； mf為變量 f的 均值，即： .)...211 nffff xx(xn m ????（ 2）計(jì)算標(biāo)準(zhǔn)化測(cè)量（ zscore）： 20 度量值的標(biāo)準(zhǔn)化 21 度量值的標(biāo)準(zhǔn)化 22 度量值的標(biāo)準(zhǔn)化 3. 二元變量？ 24 什么是二元變量 二元變量 （二值變量）： ?一個(gè)二元變量只有兩個(gè)狀態(tài)： 0或者 1。數(shù)據(jù)矩陣采用關(guān)系表形式或 n*p矩陣來表示： 14 （ 2）相異度矩陣 相異度矩陣（差異矩陣）： 是一個(gè)對(duì)象 — 對(duì)象結(jié)構(gòu)，存放 n個(gè)對(duì)象兩兩之間的近似性（差異性），采用 n*n的矩陣形式表示： 15 （ 2）相異度矩陣 相異度矩陣（差異矩陣）： 所以，矩陣呈現(xiàn)出上三角或下三角的形式。 ? 因此，聚類是觀察式學(xué)習(xí)，而不是示例式學(xué)習(xí)。 什么是聚類分析 聚類 (Clustering)： ?聚
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1