《模糊聚類分析》PPT課件.ppt

第七章模糊聚類分析 一 模糊聚類分析 聚類分析 按照一定要求和原則對事物進(jìn)行分類 聚類 普通分類 清晰事物模糊分類 帶有模糊性的事物三種模糊聚類方法 傳遞閉包法 基于模糊等價關(guān)系 直接聚類法 基于模糊相似關(guān)系 模糊聚類法 基于模糊劃分 二 模糊聚類分析的步驟 1 選取特征指標(biāo)特征要有明確的意義 要有較強(qiáng)的分辨力 有代表性 并確定描述特征的變量 分類事物的特征指標(biāo)選擇的如何 對分類結(jié)果有直接的影響 2 數(shù)據(jù)標(biāo)準(zhǔn)化 正規(guī)化 令 其中 xi為原始數(shù)據(jù) 是原始數(shù)據(jù)的均值 是原始數(shù)據(jù)的標(biāo)準(zhǔn)差 是數(shù)據(jù)處理后的數(shù)據(jù) 3 標(biāo)定 設(shè) 為待分類的對象 uj有m個刻劃其特征的 數(shù)據(jù) 就是根據(jù)實(shí)際情況 按一個準(zhǔn)則或某一種方法 給論域U中的元素兩兩之間都賦以區(qū)間 0 1 內(nèi)的一個數(shù) 叫做相似系數(shù) 它的大小表征兩個元素彼此接近或相似的程度 然后對于ui與uj 用 rij表示ui與uj的 當(dāng)rij 0時 表示ui與uj截然不同 當(dāng)rij 1時 表示ui與uj可以等同 不能說是完全相同 rij可根據(jù)具體問題來選取 方法有 的相似程度 要求 1 數(shù)量積法 其中 顯然 如果rij中出現(xiàn)負(fù)值 可采用下面方法 將全體rij進(jìn)行重新調(diào)整 方法1令 則 方法2令 其中 于是 2 夾角余弦法 如果rij中出現(xiàn)負(fù)值 也可采用上面方法調(diào)整 3 相關(guān)系數(shù)法 其中 4 最大最小法 5 算術(shù)平均最小法 6 幾何平均最小法 8 指數(shù)相似系數(shù)法 其中sk適當(dāng)選擇 9 絕對值倒數(shù)法 M適當(dāng)選取使rij在 0 1 中且分散開 7 絕對值指數(shù)法 11 非參數(shù)法 中正數(shù)個數(shù) 中負(fù)數(shù)個數(shù) 令 則 10 絕對值減數(shù)法 12 貼近度法 如果特征 則ui uj可看作模糊向量 以它們的貼近度D ui uj 為其相似程度 i 格貼近度 其中 ii 距離貼近度 其中c a為適當(dāng)選擇參數(shù)值 d ui uj 為模糊集各種距離 iii 算術(shù)平均最小貼近度 13 主觀評定法 請有實(shí)際經(jīng)驗(yàn)者直接對ui uj的相似程度評分 作為rij的值 通過標(biāo)定求出相似系數(shù)后 便可得到以rij為元素的模糊相似矩陣R rij 4 聚類 選擇一種合適的聚類方法 便可得到分類結(jié)果 三 傳遞閉包法 1 傳遞閉包法 根據(jù)標(biāo)定所得模糊矩陣R 求出其傳遞閉包 為模糊等價矩陣 對 令 從1降到0得到 根據(jù) 進(jìn)行分類 歸為一類 2 最佳閾值 的選取 聚類圖給出各 值對應(yīng)的分類 形成一種動態(tài)聚類 便于全面了解元素聚類 然后根據(jù)實(shí)際需要選擇其閾值 便可確定元素的一種分類 至于如何選擇閾值 使分類更加合理 除了憑經(jīng)驗(yàn)外 還可用F 統(tǒng)計(jì)量來選取 F 統(tǒng)計(jì)量 為待分類事物的全體 設(shè) xjk為描述元素uj第k個特征的數(shù)據(jù) 設(shè)c為 對應(yīng)于 值的類數(shù) ni為第i類元素的個數(shù) 第i類元素記為 記 為第i類元素的第k個特征的平均值 而稱 為第i類的聚類中心向量 為全體元素的中 心向量 而 于是 稱 為F 統(tǒng)計(jì)量 其中 為第i類中元素 與中心 的距離 可見 F 統(tǒng)計(jì)量的分子表征類與類間的距離 分母表征類內(nèi)元素間的距離 因此 F值越大 說明分類越合理 與此分類相對應(yīng)的F 統(tǒng)計(jì)量最大的閾值 為最佳值 求傳遞閉包的簡便方法 設(shè) 為模糊相似矩陣 求t A 1 求 假定 把A中的a1m am1 a11 amm用圓圈 圈起來 并記 2 在A中第一行 第m行中剩下的元素中 找最大元素 即 且設(shè) 在第p列 用 即分別代替a1p與amp以及它們的對稱元素 最后用圓圈將它們及圈起來 3 假定A中有圈的k行 是 行 而 所在的列是ij列 在這些行中剩下的元素中 找最大元 并設(shè)在第l行 用 分別代替 繼續(xù)此過程 到k n 1 得到t A 還有逐步平方法 及其對稱矩陣 并把a(bǔ)ll圈起來 四 基于模糊相似關(guān)系的直接聚類法 1 最大樹法 聚類原則是 ui與uj在 水平同類當(dāng)且僅當(dāng)在相似矩陣R的圖中 存在一條權(quán)重不低于 的路聯(lián)結(jié)ui與uj 畫出以被分類元素為結(jié)點(diǎn) 以相似矩陣R的元素rij為權(quán)重的一顆最大樹 2 取定 砍斷權(quán)重低于 的枝 得到一個不連通圖 各連通分支變構(gòu)成了在 水平上的分類 2 編網(wǎng)法 對給定的模糊相似矩陣R 取定水平 作截矩陣 R 在R 的主對角線上填入元素的符號 在對角線下方以結(jié)點(diǎn)號 代替1 而 0 則略去不寫 由結(jié)點(diǎn)向主對角線上引經(jīng)線和緯線 稱之為編網(wǎng) 通過經(jīng)線和緯線能互相連接起來的元素 屬于同類 從而實(shí)現(xiàn)了分類 五 基于模糊劃分的模糊聚類法 1 c 劃分 1 普通c 劃分 如果劃分把普通集合分成c類 則此劃分就叫普通c 劃分 即 若設(shè) 的特征可表為 那么U的普通c 劃分是指U的c個子集 滿足 1 2 其中 且滿足 1 2 表示每個uj必屬于且僅屬于一類 表示每類Ai至少有一個元素 反過來 任一滿足條件 1 2 3 的矩陣對應(yīng)著U的一個分類 1 2 3 這樣的分類結(jié)果可以用一個c n矩陣 稱為c 劃分 來表示 例如 設(shè)U u1 u2 u3 u4 若分類結(jié)果為 u1 u2 u3 u4 則對應(yīng)的分類矩陣為 如果分類矩陣為 則對應(yīng)著U的分類為 u1 u2 u3 u4 記V為c n實(shí)矩陣的集合 且 顯然 對于給定的U及分類數(shù)c 類的分法不是唯一的 Mc包含了U的所有可能c類劃分的結(jié)果 Mc稱為將U分成c類的分類空間 這樣的分類是通常的分類 稱為硬分類 2 模糊c 劃分 設(shè) 一個c n模糊矩陣 若滿足 1 2 表示每個uj屬于c個模糊子集Ai的程度總和為1 表示每類Ai不等于空集或U 則稱A稱為U的模糊c 劃分矩陣 記 Mfc稱為U的c類軟分類空間 顯然 若將Mc和 Mfc定義中的條件 放寬為 則這樣的分類空間分別稱為退化的硬分類空間和退化的軟分類空間 分別記為Mco和Mfco 顯然 2 目標(biāo)函數(shù)聚類法和硬c 均值算法劃分 1 目標(biāo)函數(shù)法 目標(biāo)函數(shù)是對給定的c的所有候選類進(jìn)行度量 最優(yōu)的類就是使目標(biāo)函數(shù)達(dá)到局部最小值的類 對于硬分類情形 通常所選取的目標(biāo)函數(shù)是總體組內(nèi)誤差平方和 其定義為 這里將每類Ai中元素各特征分別取平均值 所得的聚類中心向量記為vi 也稱為Ai的聚類中心 由于Ai類中元素個數(shù) Ai類中元素向量和為 因此聚類中心向量 記 V稱為聚類中心矩陣 若 則uj到聚類中心vi的距離為 Ai中全體元素到中心距離平方和為 而V中所有元素到其所在類中心距離平方和為 最理想的c 劃分顯然是使J A V 取極小的A 2 硬c 均值算法 步驟1 假設(shè)給出n個數(shù)據(jù)點(diǎn) 其中 取定 并初始化 步驟2 當(dāng)?shù)螖?shù)為 時 計(jì)算聚類中心向量 其中 步驟3 用下式將A l 更新為 步驟4 比較A l 和A l 1 若 則停止算 法 否則 令l l 1 返回步驟2 直觀上看 硬c 均值算法 猜想c的硬分類 步驟1 尋找各分類的中心 步驟2 重新分配類的隸屬度以減少數(shù)據(jù)和當(dāng)前中心的誤差平方 步驟3 當(dāng)循環(huán)不再能顯著的降低J A V 時 停止算法 步驟4 3 模糊c 均值算法 定義目標(biāo)函數(shù) 其中是一個加權(quán)指數(shù) 模糊c 均值算法的目標(biāo)在于找到 和 使得Jm A V 最小 下面 首先建立這個最小化問題的必要條件 然后根據(jù)此條件提出模糊c 均值算法 定理令 為一給 定數(shù)據(jù)集 設(shè)定 假設(shè)對所有 則僅當(dāng) 和 時 才是Jm A V 的局部最小值 模糊c 均值算法 ISODATA方法 步驟 步驟1 給定數(shù)據(jù)集 設(shè)定 并初始化 步驟2 當(dāng)?shù)螖?shù)為 時 計(jì)算聚類中心向量 步驟3 用下式將 更新為 步驟4 若 則停止算法 否則令l l 1 返回步驟2 注意 本方法要求 因此取初始分類A 0 時 遇到 只有一個樣本的類 要在聚類前先排除 待聚類后再加上該類 而參數(shù)r一般常取r 2 4 模糊劃分清晰化 在實(shí)際問題中 最后的分類結(jié)果都要求是明確的 因此 在使用模糊c 劃分分類后 都必須將模糊劃分清晰化 可用下述方法進(jìn)行 方法1對 若 則將uj歸入Ai類 方法2對 若 則將uj歸入Ai類