【正文】 簇用接近聚類中心的一個(gè)對(duì)象來表示。 ?缺點(diǎn)： 對(duì)初始參數(shù)敏感 。 ?3 重新計(jì)算當(dāng)前類別劃分下每類的中心 。 ?O（ kndt） 初始值敏感 初始化 4個(gè)類別中心 。 ?3 對(duì)于每個(gè)類 （ Oi）中，順序選取一個(gè) Or，計(jì)算用 Or代替 Oi后的消耗 —E（ Or）。 ? 最小方差 :衡量同一類別內(nèi)數(shù)據(jù)的平均誤差和 。 聚類 分析（續(xù) ） ?基于層次的方法： 層次的方法對(duì)給定數(shù)據(jù)集合進(jìn)行層次的分解。（DBSCAN， OPTICS， DENCLUE） ?基于網(wǎng)格的方法： 基于網(wǎng)格的方法把對(duì)象空間量化為有限數(shù)目的單元，所有的聚類操作都在這個(gè)量化的空間上進(jìn)行。 ?如果存在一個(gè)對(duì)象鏈 p1, ?, pn, p1 = q, pn = p ， pi+1 是從 pi關(guān)于 Eps和 MinPts 直接密度可達(dá)的，則對(duì)象 p是從對(duì)象q關(guān)于 Eps和 MinPts 密度可達(dá)的 。 ?密度相連性是一個(gè) 對(duì)稱 的關(guān)系。 根據(jù)所給的數(shù)據(jù)通過對(duì)其進(jìn)行 DBSCAN算法，以下為算法的步驟（設(shè) n=12，用戶輸入 ε =1， MinPts=4） 序號(hào) 屬性 1 屬性 2 1 2 1 2 5 1 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 1 3 10 2 3 11 5 3 12 2 4 樣本事務(wù)數(shù)據(jù)庫 DBSCAN聚類過程 ? 第 1步，在數(shù)據(jù)庫中選擇一點(diǎn) 1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含 2個(gè)點(diǎn)（小于 4），因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 DBSCAN聚類過程 ? 第 5步，在數(shù)據(jù)庫中選擇一點(diǎn) 5，已經(jīng)在簇 1中，選擇下一個(gè)點(diǎn)。 ? 第 9步，在數(shù)據(jù)庫中選擇一點(diǎn) 9，已經(jīng)在簇 1中，選擇下一個(gè)點(diǎn)。 序號(hào) 屬性 1 屬性 2 1 2 1 2 5 1 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 1 3 10 2 3 11 5 3 12 2 4 基于密度方法的聚類 DBSCAN 步驟 選擇的點(diǎn) 在 ε中點(diǎn)的個(gè)數(shù) 通過計(jì)算可達(dá)點(diǎn)而找到的新簇 1 1 2 無 2 2 2 無 3 3 3 無 4 4 5 簇 C1： {1， 3， 4， 5， 9， 10，12} 5 5 3 已在一個(gè)簇 C1中 6 6 3 無 7 7 5 簇 C2： {2， 6， 7， 8， 11} 8 8 2 已在一個(gè)簇 C2中 9 9 3 已在一個(gè)簇 C1中 10 10 4 已在一個(gè)簇 C1中， 11 11 2 已在一個(gè)簇 C2中 12 12 2 已在一個(gè)簇 C1中 算法執(zhí)行過程： DBSCAN Original Points Clusters 特點(diǎn)： ?抗噪聲 ? 能處理 任意形狀聚類 關(guān)聯(lián)規(guī)則 關(guān)聯(lián)規(guī)則： Association Rule ? 關(guān)聯(lián)規(guī)則挖掘： ?在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 :通過用戶給定 最小可信度 ，在頻繁項(xiàng)目集中，尋找關(guān)聯(lián)規(guī)則。 TID Itemset 100 1， 3， 4 200 2， 3， 5 300 1， 2， 3， 5 400 2， 5 ? 1994年， Agrawal 等人提出了著名的 Apriori 算法。 關(guān)聯(lián)規(guī)則挖掘 基本過 程 經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集 算法 Apriori算法是通過項(xiàng)目集元素?cái)?shù)目不斷增長來完成頻繁項(xiàng)目集發(fā)現(xiàn)的。 ? 舉例： ?規(guī)則形式 :“ Body = Head [support, confidence]” ? buys(x, “ diapers” ) = buys(x, “ beers” ) [%, 60%] ? major(x, “ CS” ) ^ takes(x, “ DB” ) = grade(x, “ A” ) [1%, 75%] 規(guī)則度量：支持度與可信度 ?查找所有的規(guī)則 X Y = Z 具有最小支持度和可信度 ?支持度 , s, 一次交易中包含 {X 、 Y 、 Z}的 可能性 ?可信度 , c, 包含 {X 、 Y}的交易中也包含 Z的 條件概率 交易 ID 購買的商品2023 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,F設(shè)最小支持度為 50%, 最小可信度為 50%, 則可得到 ? A = C (50%, %) ? C = A (50%, 100%) 買尿布的客戶 二者都買的客戶 買啤酒的客戶 ?關(guān)聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的 最小支持度和最小可信度來尋找強(qiáng)關(guān)聯(lián)規(guī)則。 ? 第 11步，在數(shù)據(jù)庫中選擇一點(diǎn) 11，已經(jīng)在簇 2中，選擇下一個(gè)點(diǎn)。 DBSCAN聚類過程 ? 第 7步，在數(shù)據(jù)庫中選擇一點(diǎn) 7，由于在以它為圓心的，以 1為半徑的圓內(nèi)包含 5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)，聚出的新類 {2， 6， 7， 8， 11}，選擇下一個(gè)點(diǎn)。 ? 第 3步，在數(shù)據(jù)庫中選擇一點(diǎn) 3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含 3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 ? 輸出：所有生成的簇，達(dá)到密度要求。 只有核心對(duì)象之間是 相互可達(dá) 的。（ STING， CLIQUE，WaveCluster） ?基于模型的方法： 為每個(gè)簇假設(shè)一個(gè)模型，發(fā)現(xiàn)數(shù)據(jù)對(duì)模型的最好匹配。 （Chameleon ， CURE， BIRCH） ?基于密度的方法： 只要臨近區(qū)域的密度超過某個(gè)閾值，就繼續(xù)聚類。39。 ?4 重復(fù) 23直到 medoids不變 。 Kmediods步驟 ?1 任意選 取 K個(gè)對(duì)象作為 medoids。 ?5 如果連續(xù)兩次的類別劃分結(jié)果不變則停止算法 。 Kmeans步驟 ?1 設(shè)置初始類別中心和類別數(shù) 。 ?聚類有效性函數(shù) 最小誤差 。 ?絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的 基于劃分的方法 ，這些基于劃分的聚類方法對(duì)在中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很適用。 ?No Train（聚類） 。 因 此，對(duì)于樣本 X， 樸素貝葉斯分類預(yù)測(cè) buys_puter=“yes” X=（ age=“ =30” ,ine=“ medium” ,student=“ yes” ,credit_rating=“ fair” ） 聚類 聚類： Cluster ?聚類就是對(duì)大量未知標(biāo)注的數(shù)據(jù)集，按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個(gè)類別 ?在 同一個(gè)類 中，對(duì)象之間具有 相似性 ； ?不同類 的對(duì)象之間是 相異 的。 (1) 需要最大化 P(X|Ci)*P(Ci)， i=1， 2。 (5) 對(duì) 未 知 樣 本 X 分類 ， 也 就 是 對(duì) 每 個(gè) 類 Ci ， 計(jì)算P(X|Ci)*P(Ci)。給定樣本的類標(biāo)號(hào)，假定屬性值相互條件獨(dú)立，即在屬性間，不存在依賴關(guān)系。否則 ， 需要最大化 P(X|Ci)*P(Ci)。 樸素貝葉斯分類將 未知的樣本分配給類 Ci（ 1≤ i≤ m）當(dāng)且僅當(dāng) P(Ci|X)P(Cj|X)， j≠ i。 后驗(yàn) 概率 P(C|X) 比先驗(yàn)概率 P(C)基于更多的信息 。 貝葉斯分類 貝葉斯分類 ? 貝葉斯定理 貝葉斯定理給出了如下計(jì)算 P(C|X)的簡單有效的方法 : P(C):是先驗(yàn)概率 ， 或稱 C的先驗(yàn) 概率 。 決策樹算法 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 21步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 青年買與不買比例為 128/256 S1(買 )=128 S2（不買） = 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 決策樹算法 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 22步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 中年買與不買比例為 256/0 S1(買 )=256 S2（不買） = 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256， 0) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) =0 決策樹算法 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 23步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 老年買與不買比例為 125/127 S1(買 )=125 S2（不買） =127 S=S1+S2=252 P1=125/252 P2=127/252 I(S1,S2)=I(125， 127) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 決策樹算法 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 24步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 所占比例 青年組 384/1025= 中年組 256/1024= 老年組 384/1024= 計(jì)算年齡的平均信息期望 E（年齡） =*+ *0+ * = G（年齡信息增益） = = （ 1） 決策樹算法 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高