自动集群侦测课件

1、自動集群偵測韓 家 興 陳 君 彥 國立中興大學行銷研究所自動集群偵測韓 家 興 陳 君 彥 自動集群偵測簡介實際情況中，資料是相當複雜的 (沒有固定的型態、變數多、維度、複雜的結構)集群分析主要的目的在於將複雜的資料區分為較小部分，讓每部分更容易解釋與簡化如果區隔適當則可從各集群中找更簡化的解釋方式 例如：樹木顏色的分類資料庫行銷集群偵測分析自動集群偵測簡介實際情況中，資料是相當複雜的 (沒有固定的型報告流程兩個實際例子運用的介紹(天文學、軍服尺寸設計)K-means集群演算法使用幾何方式的解釋方法相似性與距離集群事前的準備工作單位的一致性權重設定其他集群方法Gaussian mixture

2、高斯演算法Agglomerative clustering凝聚分析法Divisive clustering階層式分裂演算法Case study報紙編輯區的分類資料庫行銷集群偵測分析報告流程資料庫行銷集群偵測分析搜尋簡化的集群資料 Searching for Islands of Simplicity資料採礦可分為：有方向性有一個應變數(Y)，其餘都是自變數(X)沒有方向性沒有任何分類好的變數，目的是找出所有變數中，是否存在某些關係資料的可用性取決於使用者本身在行銷中的應用上，集群代表了市場區隔的概念自動集群偵測很少單獨使用，集群之後必須使用其他方法進一部加以分析集群所代表的意義資料庫行銷集群偵

3、測分析搜尋簡化的集群資料 Search實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料庫行銷集群偵測分析恆星相對太陽亮度的倍數恆星表面溫度實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料庫行銷集群偵測分析實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料庫行銷集群偵測分析紅巨星白矮星實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料實際例子應用軍服尺寸設計資料庫行銷集群偵測分析1001251502001756065707580Weight (Pounds)Height (Inches)實際例子應用軍服尺

4、寸設計資料庫行銷集群偵測分析10012實際例子應用軍服尺寸設計資料庫行銷集群偵測分析二維或三維時我們還可以用肉眼觀察出集群分類的情形，但當構面數多時，便難以觀察出集群的情形目的是提供合身的軍服，與減少不同尺寸軍服，降低庫存數量使用的構面腿長、腰圍、胸圍最後分類出一百多種體型量測實際例子應用軍服尺寸設計資料庫行銷集群偵測分析二維或三維K-Means 集群法K-Means 集群法是1967由J.B.MacQueen提出最常使用的集群方法所謂的“K”，將資料分成幾組的組數以下為了簡化，以二維的圖解來解釋其方法(實際情況中往往為多維度的情況)資料庫行銷集群偵測分析K-Means 集群法K-Means

5、集群法是1967由J.K-Means 集群法步驟步驟一：隨機選取個點作為種子點步驟二：將各個數據資料與最接近之種子點分為同一集群(原始集群)資料庫行銷集群偵測分析X1X2Seed 3Seed 2Seed 1K-Means 集群法步驟步驟一：隨機選取個點作為種子點資K-Means 集群法步驟資料庫行銷集群偵測分析步驟三：計算各(原始)集群之中心點步驟四：新的中心點此時成為新的種子點X1X2Seed 2Seed 1Seed 3K-Means 集群法步驟資料庫行銷集群偵測分析步驟三：計K-Means 集群法步驟資料庫行銷集群偵測分析X1X2持續重復上述的步驟，直到達到穩定的狀態K-Means 集群法

6、步驟資料庫行銷集群偵測分析X1X2持K Means的意義有時集群無法對其結構做出最標準之敘述(市區的定義)各集群的一內致性高低，可用集群內所有資料之平均距離來做比較整個方法的過程可使用機械化(例如：電腦軟體)方式來完成，但集群的適用性與可用價值則需要用更主觀的衡量方式第一次使用K-Means Clustering法時，大部分資料都會落入一個大的集群，而週遭會圍繞著許多小的集群(例如：定義欺騙行為或不良品的衡量)資料庫行銷集群偵測分析K Means的意義有時集群無法對其結構做出最標準之敘述(市相似性與距離 照理來說，相同集群內的資料比其他集群之資料有較高之相似性測量相似性高低最簡易之方法，為將其

7、資料量化，並在幾何空間中計算比較，但此方法會有以下限制：許多資料不適合量化或使用幾何向量方式呈現在幾何中，距離為非加權的，與有些資料屬性不符合資料庫行銷集群偵測分析相似性與距離 照理來說，相同集群內的資料比其他集群之資料有較相似性量測與變數型態資料庫行銷集群偵測分析四種尺度型態(老生常談) 類別尺度順序尺度區間尺度比例尺度幾何距離可直接適用於區間尺度與比例尺度的資料上類別變數與順序變數則需要做轉換才可使用幾何距離。但這些轉換有可能造成資料真實性降低(將冰淇淋編號1-28號難道5&6號真的口味接近，1&28味道就差很遠嗎?)相似性量測與變數型態資料庫行銷集群偵測分析四種尺度型態(老相似性量測的方

8、法 以下介紹三種方法，前兩種適用於區間尺度與比例尺度的資料，第三種方法適用於類別尺度兩點之間的幾何距離兩向量間的角度曼哈頓距離資料庫行銷集群偵測分析相似性量測的方法 以下介紹三種方法，前兩種適用於區間尺度兩點之間的幾何距離歐幾里得距離兩點之間的距離近則相似性高資料庫行銷集群偵測分析兩點之間的幾何距離歐幾里得距離資料庫行銷集群偵測分析兩項量間的角度 有時需同時考量一個以上之因素來測量相似性。例子：鯉魚應與沙丁魚、鱈魚、鮪魚屬同集群，而小貓應與獅子、美洲獅、老虎同集群；雖然小貓在體型這個變項上與大魚很接近。資料庫行銷集群偵測分析大貓大魚小魚小貓（圖11.7）兩項量間的角度 有時需同時考量一個以上之

9、因素來曼哈頓距離算法有如紐約曼哈頓市區的方形格子的型態在幾何上，曼哈頓距離是行經所有變數軸之和。（有時此法較歐幾里得距離好用，因為距離不需平方，所以不會因為一個構面（變項）的小小差異因為平方而造成對總距離有主導性的影響）資料庫行銷集群偵測分析曼哈頓距離算法有如紐約曼哈頓市區的方形格子的型態資料庫行銷量測相似性的共同特性 當資料是類別尺度時，幾何方法並非最好，較好的方法是資料間重疊的程度將所有的資料是一個範圍與一個範圍的比較是否相配衡量所有變數相符的比例資料庫行銷集群偵測分析量測相似性的共同特性 當資料是類別尺度時，幾何方法並非最好，集群的事前的準備工作 單位的一致性(Scaling for c

10、onsistency) 若欲以幾何距離量測相似性，須先將資料轉換成同一單位基準，以下有三種常用方式： 常態化(Normalizing)：將資料案全距劃分成固定範圍（例：01或-11）指數調整(Indexing)標準化(standardizing)權重設定 主要目的：決定變數間的相對重要性資料庫行銷集群偵測分析集群的事前的準備工作 單位的一致性(Scaling for 使用K-Means集群的缺點無法妥善處理集群之間重疉的狀況(類別尺度)集群易受離群值的影響各資料被明確決定屬於某集群內或非屬於該集群，非黑即白，沒有模棱兩可。資料庫行銷集群偵測分析使用K-Means集群的缺點資料庫行銷集群偵測分析

11、Gaussian mixture高斯演算法適用處 理多構面資料，是 K-Means的一種轉變 資料庫行銷集群偵測分析X1X2G2G1G3步驟一：估計。計算各高斯集群對所有資料點Responsibility毎個資料點離高斯點越近，則Responsibility愈大，離高斯點越遠則Responsibility越小。Responsibility在下一階段被當作的權重Gaussian mixture高斯演算法適用處資料庫行銷Gaussian mixture高斯演算法步驟二：最大化新的中心點被計算出，以進一步算出更新Responsibility步驟三：重複以上動作直到達成穩定資料庫行銷集群偵測分析X1X

12、2Gaussian mixture高斯演算法步驟二：最大化資料Agglomerative clustering 凝聚集群法 K-Means的集群法在開始時便有設好K(集群數)為多少。凝聚性集群每筆資料皆屬各自的集群開始，然後再將集群漸漸擴大，合併這些集群，至最後，全部資料皆屬同一集群。凝聚性集群法一開始的集群很小很純，且各資料高度相關；愈後面的集群愈大、資料愈雜，集群屬性預難定義。凝聚集群法最重要事項之一就是選擇要焠鍊至何種層級的集群，效果最佳！資料庫行銷集群偵測分析Agglomerative clustering 凝聚分析法的步驟 步驟一：相似性矩陣。兩兩資料(集群)之間的距離或相似度之矩陣

13、(若有n筆資料，則需n2次的計算)步驟二：找出相似性矩陣的最小值。這樣可以找出最相似的兩筆資料(集群)，並將其合併為一新的集群。(此時剩下n-1個集群)步驟三：繼續以上的步驟直到所有的資料(集群)，接成為同一集群為止。選擇使用至哪一層級的集群，將是決定性的關鍵資料庫行銷集群偵測分析凝聚分析法的步驟 步驟一：相似性矩陣。資料庫行銷集群偵測分凝聚分析法的實例 以年齡進行集群分析資料庫行銷集群偵測分析51545438931114913123765距離一距離二距離三距離四距離五距離六缺點：若其中一個集群中的資料合併錯時，便不能返回45494337凝聚分析法的實例 以年齡進集群與樹狀圖凝聚性集群法以層級

14、性的方式製造集群，於是可使用樹狀圖。與決策樹的差異凝聚集群樹狀圖並沒有敘述為何資料歸為同一集群，而以最短距離來分成集群的決策樹由根部出發，以發展出所預定之葉(目標)，凝聚性集群法則是相反的由葉出發，以集群為目的，往最終的根部前進資料庫行銷集群偵測分析集群與樹狀圖凝聚性集群法以層級性的方式製造集群，於是可使用樹集群之間的距離量測方式 資料庫行銷集群偵測分析X1X2C2C3C1用單一連結方法最接近的集群用完整連結方法最接近的集群用質心點方法最接近的集群集群之間的距離量測方式 資料庫行銷集群偵測分析X1X2C2Divisive clustering 階層式分裂演算法以決策樹的觀念來做集群分類階層式分

15、裂演算法由根部出發，往葉子邁進；凝聚性集群法是相反的由葉出發，往最終的根部前進資料庫行銷集群偵測分析Divisive clustering 集群的評估問題一：如何決定K-mean中K的數目問題二：如何決定那一個層級的集群擁有較佳的集群(凝聚與層級分裂法)問題三：到底怎樣才算是一個好的集群資料庫行銷集群偵測分析集群的評估問題一：如何決定K-mean中K的數目資料庫行銷集群的內外部資料庫行銷集群偵測分析X1X2集群內部集群內部裡面， 差異越小越好平均數變異數集群外部集群之間差異越大越好集群的內外部資料庫行銷集群偵測分析X1X2集群內部集群分析與區別分析的差異(補充)區別分析群落、市場區隔為已知(選

16、擇題、是非題)集群分析群落、市場區隔的分佈為未知(問答題)資料庫行銷集群偵測分析集群分析與區別分析的差異(補充)區別分析群落、市場區隔為已其他集群分析的應用資料庫行銷集群偵測分析主要目的：使銷售人員能在第一時間經由顧客的臉型、表情、長相區分出顧客可能的購物情形其他集群分析的應用資料庫行銷集群偵測分析主要目的：使銷售人其他集群分析的應用資料庫行銷集群偵測分析主要目的：區分出不同品牌的Pizza不同的特色其他集群分析的應用資料庫行銷集群偵測分析主要目的：區分出不Case study報紙編輯區的集群資料庫行銷集群偵測分析Boston Globe是Boston與Boston週遭地區Massachuse

17、tts、New Hampshire最主要的日報面臨問題：主要市場Boston讀者數下降郊區市場受到地區性報紙的競爭威脅而造成閱讀的移轉Boston Globe希望將現行不理想的12個地理區域的編輯區，做出更好的分類，每個編輯區中每周會有兩天報導當地的新聞Case study報紙編輯區的集群資料庫行銷集群偵測分編輯區的限制編輯區應擁有地理區域上的連續性編輯區的緊密性，以及編輯區中人口的充足與否將會直接影響到報導內容編輯區會因為地理區域而調整使用的廣告 受到上面的限制，Boston Globe希望將擁有共同特性的城市，設計合適的編輯區。但哪些城市具有相似性呢? 資料庫行銷集群偵測分析編輯區的限制編

18、輯區應擁有地理區域上的連續性資料庫行銷集群偵創造出城市的共同變數在分類出不同城市屬於哪個集群前，必須能夠先描述出每個城市的特性而資料採礦人員早期的計劃是希望能夠從這些城市已經定義好的共同變數探勘出未來發行率會持續成長的城市資料庫行銷集群偵測分析創造出城市的共同變數在分類出不同城市屬於哪個集群前，必須能夠資料來源與特性城市的特性大多來自不同的來源處，但大多的變數來自1990以及2001年美國城市的人口調查 (變數包含年齡、種族、職業、收入、Home value)此外，Globe從各城市中送報商中取得每戶家庭的資料在促銷時訂閱戶所留下的資訊抱怨電話訂閱的方式(日報、Sunday )資料庫行銷集群偵

19、測分析資料來源與特性城市的特性大多來自不同的來源處，但大多的變數來創造城市共同特性的步驟Aggregation:將所有資料轉換成城市的共同特性，在進一歨行成不同城市的層級Normalization常態化:將所有的數值轉換成用百分比的形態表示Calculation of trends :推測趨勢:趨勢能夠反應出一個城市的特性Creation of derived variables :創造來源變數:除了在變數中找尋共同特性，找出城市中的重要特性資料庫行銷集群偵測分析創造城市共同特性的步驟Aggregation:將所有資料轉換創造集群當描述城市特性時可以藉由人口統計和地理區域來建立集群，但集群的建

20、立並不能夠馬上的就找出合適編輯區因為一些地理上的限制都會導致編輯區將週遭的城市納入人口統計相似的城市並不能代表相近的地理區域人口統計的集群能夠使用單一因素設計編輯區，並且考量到地理上的限制資料庫行銷集群偵測分析創造集群當描述城市特性時可以藉由人口統計和地理區域來建立集群決定合理的集群數在建立編輯區的集群數時，會因為許多商業上的考量形成許多的編輯區，但我們往往不能夠保證每個好的集群都能夠被發現但若是結合K-Means法以及分裂樹狀圖能夠解決集群數的問題步驟一：先決定較低的K值做區分，並使用K-Means演算法步驟二：利用平均距離或變異數將目前的單一集群分裂出較合適的集群步驟三：重覆以上步驟直到集

21、群內相似性較高資料庫行銷集群偵測分析決定合理的集群數在建立編輯區的集群數時，會因為許多商業上的考利用集群樹將Boston Globe做區分資料庫行銷集群偵測分析PopulationCluster 2Cluster 1Cluster 1BCluster 1AACluster 1ABCluster 1AHome value高教育程度高 低收入年長訂閱戶鄰近BostonHome value低收入普通Home value /收入接近Population的平均值利用集群樹將Boston Globe做區分資料庫行銷集群偵使用Thematic Cluster調整區域疆界資料庫行銷集群偵測分析Town Edi

22、torial zoneCluster assignmentBrooklineCity 2Boston City1BCambridge City1BSomerville City1BNeedham West 12NewtonWest 12Wellesley West 12Waltham West 11BWestonWest 12Watertown West 11B221B 集群1B ：低收入年長訂閱戶鄰近Boston集群2： Home value高教育程度高使用Thematic Cluster調整區域疆界資料庫行銷結論自動集群偵測法是非直接的資料採礦技術，主要目的是將複雜的資料簡化。自動集群偵測

23、通常與其他資料採礦技術一起使用，效果更佳！自動集群偵測能夠處理（幾乎）任何型態的資料，功能十分強大。距離是自動集群偵測處理量化資料的核心觀念。K-Means是自動集群偵測最常使用的方法。利用自動集群偵測能夠將有用的集群轉換成商業用途達成企業目標。資料庫行銷集群偵測分析結論自動集群偵測法是非直接的資料採礦技術，主要目的是將複雜的THE END THANK YOU!THE END THANK YOU補 充： Gaussian Mixture補 充： Gaussian MixtureGaussian MixtureThe Gaussian mixture architecture estimates

24、 probability density functions (PDF) for each class, and then performs classification based on Bayes rule:Where P(X | Ci) is the PDF of class j, evaluated at X, P( Cj ) is the prior probability for class j, and P(X) is the overall PDF, evaluated at X. Gaussian MixtureThe Gaussian mGaussian MixtureUn

25、like the unimodal Gaussian architecture, which assumes P(X | Cj) to be in the form of a Gaussian, the Gaussian mixture model estimates P(X) as a weighted average of multiple Gaussians.Where wk is the weight of the k-th Gaussian Gk and the weights sum to one. One such PDF model is produced for each c

26、lass. Gaussian MixtureUnlike the uniGaussian MixtureEach Gaussian component is defined as: Where Mk is the mean of the Gaussian and Vk is the covariance matrix of the Gaussian. Gaussian MixtureEach Gaussian Gaussian MixtureFree parameters of the Gaussian mixture model consist of the means and covari

27、ance matrices of the Gaussian components and the weights indicating the contribution of each Gaussian to the approximation of P(X | Cj). Gaussian MixtureFree parameterG1,w1G2,w2G3,w3G4,w4G5.w5Class 1 Variables: i, Vi, wkWe use EM (estimate-maximize) algorithm to approximate this variables.Compositio

28、n of Gaussian MixtureG1,w1G2,w2G3,w3G4,w4G5.w5ClassGaussian MixtureThese parameters are tuned using a complex iterative procedure called the estimate-maximize (EM) algorithm, that aims at maximizing the likelihood of the training set generated by the estimated PDF.The likelihood function L for each class j can be defined as: Gaussian MixtureThese parameteGaussian Mixture Training Flow Chart (1)Initialize the initial Gaussian means i, i=1,G using the K means clustering algorithmInitialize the covariance matrices, Vi, to the distance to the nearest cluster.Initialize the weights i