自动集群侦测.ppt

《自动集群侦测.ppt》由会员分享，可在线阅读，更多相关《自动集群侦测.ppt（58页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、自动集群侦测 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望自動集群偵測簡介n實際情況中，資料是相當複雜的 (沒有固定的型態、變數多、維度、複雜的結構)n集群分析主要的目的在於將複雜的資料區分為較小部分，讓每部分更容易解釋與簡化n如果區隔適當則可從各集群中找更簡化的解釋方式 例如：樹木顏色的分類資料庫行銷集群偵測分析報告流程n兩個實際例子運用的介紹(天文學、軍服尺寸設計)nK-means集群演算法使用幾何方式的解釋方法n相似性與距離n集群事前的準備工作單位的一致

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

3、分析集群所代表的意義資料庫行銷集群偵測分析實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料庫行銷集群偵測分析恆星相對太陽亮度的倍數恆星表面溫度實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料庫行銷集群偵測分析實際例子應用 天文學(一閃一閃亮晶晶散佈圖)資料庫行銷集群偵測分析紅巨星紅巨星白矮星白矮星實際例子應用軍服尺寸設計資料庫行銷集群偵測分析1001251502001756065707580Weight (Pounds)Height (Inches)實際例子應用軍服尺寸設計資料庫行銷集群偵測分析n二維或三維時我們還可以用肉眼觀察出集群分類的情形，但當構面數多時，便難以觀察出集群的情形n目的是提

4、供合身的軍服，與減少不同尺寸軍服，降低庫存數量n使用的構面腿長、腰圍、胸圍n最後分類出一百多種體型量測K-Means 集群法nK-Means 集群法是1967由J.B.MacQueen提出n最常使用的集群方法n所謂的“K”，將資料分成幾組的組數n以下為了簡化，以二維的圖解來解釋其方法(實際情況中往往為多維度的情況)資料庫行銷集群偵測分析K-Means 集群法步驟n步驟一：隨機選取個點作為種子點n步驟二：將各個數據資料與最接近之種子點分為同一集群(原始集群)資料庫行銷集群偵測分析X1X2Seed 3Seed 2Seed 1K-Means 集群法步驟資料庫行銷集群偵測分析n步驟三：計算各(原始)集

5、群之中心點n步驟四：新的中心點此時成為新的種子點X1X2Seed 2Seed 1Seed 3K-Means 集群法步驟資料庫行銷集群偵測分析X1X2n持續重復上述的步驟，直到達到穩定的狀態K Means的意義n有時集群無法對其結構做出最標準之敘述(市區的定義)n各集群的一內致性高低，可用集群內所有資料之平均距離來做比較n整個方法的過程可使用機械化(例如：電腦軟體)方式來完成，但集群的適用性與可用價值則需要用更主觀的衡量方式n第一次使用K-Means Clustering法時，大部分資料都會落入一個大的集群，而週遭會圍繞著許多小的集群(例如：定義欺騙行為或不良品的衡量)資料庫行銷集群偵測分析相似

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

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

8、不需平方，所以不會因為一個構面（變項）的小小差異因為平方而造成對總距離有主導性的影響）資料庫行銷集群偵測分析量測相似性的共同特性 n當資料是類別尺度時，幾何方法並非最好，較好的方法是資料間重疊的程度n將所有的資料是一個範圍與一個範圍的比較是否相配n衡量所有變數相符的比例資料庫行銷集群偵測分析集群的事前的準備工作 n單位的一致性單位的一致性(Scaling for consistency) 若欲以幾何距離量測相似性，須先將資料轉換成同一單位基準，以下有三種常用方式： 常態化(Normalizing)：將資料案全距劃分成固定範圍（例：01或-11）指數調整(Indexing)標準化(standar

9、dizing)n權重設定權重設定 主要目的：決定變數間的相對重要性資料庫行銷集群偵測分析使用K-Means集群的缺點n無法妥善處理集群之間重疉的狀況(類別尺度)n集群易受離群值的影響n各資料被明確決定屬於某集群內或非屬於該集群，非黑即白，沒有模棱兩可。資料庫行銷集群偵測分析Gaussian mixturen高斯演算法適用處 理多構面資料，是 K-Means的一種轉變 資料庫行銷集群偵測分析X1X2G2G1G3n步驟一：估計。計算各高斯集群對所有資料點Responsibility毎個資料點離高斯點越近，則Responsibility愈大，離高斯點越遠則Responsibility越小。Respo

10、nsibility在下一階段被當作的權重Gaussian mixture高斯演算法n步驟二：最大化新的中心點被計算出，以進一步算出更新Responsibilityn步驟三：重複以上動作直到達成穩定資料庫行銷集群偵測分析X1X2Agglomerative clustering 凝聚集群法 nK-Means的集群法在開始時便有設好K(集群數)為多少。n凝聚性集群每筆資料皆屬各自的集群開始，然後再將集群漸漸擴大，合併這些集群，至最後，全部資料皆屬同一集群。n凝聚性集群法一開始的集群很小很純，且各資料高度相關；愈後面的集群愈大、資料愈雜，集群屬性預難定義。n凝聚集群法最重要事項之一就是選擇要焠鍊至何種

11、層級的集群，效果最佳！資料庫行銷集群偵測分析凝聚分析法的步驟 n步驟一：相似性矩陣。步驟一：相似性矩陣。兩兩資料(集群)之間的距離或相似度之矩陣(若有n筆資料，則需n2次的計算)n步驟二：找出相似性矩陣的最小值。步驟二：找出相似性矩陣的最小值。這樣可以找出最相似的兩筆資料(集群)，並將其合併為一新的集群。(此時剩下n-1個集群)n步驟三：繼續以上的步驟直到所有的資料步驟三：繼續以上的步驟直到所有的資料( (集群集群) )，接成為同一集群為止。，接成為同一集群為止。n選擇使用至哪一層級的集群，將是決定性的關選擇使用至哪一層級的集群，將是決定性的關鍵鍵資料庫行銷集群偵測分析凝聚分析法的實例 以年齡

12、進行集群分析資料庫行銷集群偵測分析51545438931114913123765距離一距離二距離三距離四距離五距離六缺點：若其中一個集群中的資料合併錯時，便不能返回45494337集群與樹狀圖n凝聚性集群法以層級性的方式製造集群，於是可使用樹狀圖。n與決策樹的差異凝聚集群樹狀圖並沒有敘述為何資料歸為同一集群，而以最短距離來分成集群的決策樹由根部出發，以發展出所預定之葉(目標)，凝聚性集群法則是相反的由葉出發，以集群為目的，往最終的根部前進資料庫行銷集群偵測分析集群之間的距離量測方式 資料庫行銷集群偵測分析X1X2C2C3C1用單一連結方法最接近的集群用完整連結方法最接近的集群用質心點方法最接近

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

14、隔的分佈為未知(問答題)資料庫行銷集群偵測分析其他集群分析的應用資料庫行銷集群偵測分析主要目的：使銷售人員能在第一時間經由顧客的臉型、表情、長相區分出顧客可能的購物情形其他集群分析的應用資料庫行銷集群偵測分析主要目的：區分出不同品牌的Pizza不同的特色Case study報紙編輯區的集群資料庫行銷集群偵測分析nBoston Globe是Boston與Boston週遭地區Massachusetts、New Hampshire最主要的日報n面臨問題：主要市場Boston讀者數下降郊區市場受到地區性報紙的競爭威脅而造成閱讀的移轉nBoston Globe希望將現行不理想的12個地理區域的編輯區，做

15、出更好的分類，每個編輯區中每周會有兩天報導當地的新聞編輯區的限制n編輯區應擁有地理區域上的連續性n編輯區的緊密性，以及編輯區中人口的充足與否將會直接影響到報導內容n編輯區會因為地理區域而調整使用的廣告 受到上面的限制，Boston Globe希望將擁有共同特性的城市，設計合適的編輯區。但哪些城市具有相似性呢? 資料庫行銷集群偵測分析創造出城市的共同變數n在分類出不同城市屬於哪個集群前，必須能夠先描述出每個城市的特性n而資料採礦人員早期的計劃是希望能夠從這些城市已經定義好的共同變數探勘出未來發行率會持續成長的城市資料庫行銷集群偵測分析資料來源與特性n城市的特性大多來自不同的來源處，但大多的變數來

16、自1990以及2001年美國城市的人口調查 (變數包含年齡、種族、職業、收入、Home value)n此外，Globe從各城市中送報商中取得每戶家庭的資料在促銷時訂閱戶所留下的資訊抱怨電話訂閱的方式(日報、Sunday )資料庫行銷集群偵測分析創造城市共同特性的步驟nAggregation:將所有資料轉換成城市的共同特性，在進一歨行成不同城市的層級nNormalization常態化:將所有的數值轉換成用百分比的形態表示nCalculation of trends :推測趨勢:趨勢能夠反應出一個城市的特性nCreation of derived variables :創造來源變數:除了在變數中找

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

18、均距離或變異數將目前的單一集群分裂出較合適的集群步驟三：重覆以上步驟直到集群內相似性較高資料庫行銷集群偵測分析利用集群樹將Boston Globe做區分資料庫行銷集群偵測分析PopulationCluster 2Cluster 1Cluster 1BCluster 1AACluster 1ABCluster 1AHome value高教育程度高 低收入年長訂閱戶鄰近BostonHome value低收入普通Home value /收入接近Population的平均值使用Thematic Cluster調整區域疆界資料庫行銷集群偵測分析Town Editorial zoneCluster ass

19、ignmentBrooklineCity 2Boston City1BCambridge City1BSomerville City1BNeedham West 12NewtonWest 12Wellesley West 12Waltham West 11BWestonWest 12Watertown West 11B221B 集群1B ：低收入年長訂閱戶鄰近Boston集群2： Home value高教育程度高結論n自動集群偵測法是非直接的資料採礦技術，主要目的是將複雜的資料簡化。n自動集群偵測通常與其他資料採礦技術一起使用，效果更佳！n自動集群偵測能夠處理（幾乎）任何型態的資料，功能十分強

20、大。n距離是自動集群偵測處理量化資料的核心觀念。nK-Means是自動集群偵測最常使用的方法。n利用自動集群偵測能夠將有用的集群轉換成商業用途達成企業目標。資料庫行銷集群偵測分析THE END THANK YOU!補 充： Gaussian MixtureGaussian MixturenThe Gaussian mixture architecture estimates probability density functions (PDF) for each class, and then performs classification based on Bayes rule:)()()|

21、()|(XPCPCXPXCPiiiWhere 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 MixturenUnlike the unimodal Gaussian architecture, which assumes P(X | Cj) to be in the form of a Gaussian, the Gaussian mixture

22、 model estimates P(X) as a weighted average of multiple Gaussians.NckkkGwXP1)(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 class. Gaussian MixturenEach Gaussian component is defined as: )()(2/12/12/1|)2(1kkTkMXVMXknkeVGWhere Mk is

23、 the mean of the Gaussian and Vk is the covariance matrix of the Gaussian. Gaussian MixturenFree parameters of the Gaussian mixture model consist of the means and covariance matrices of the Gaussian components and the weights indicating the contribution of each Gaussian to the approximation of P(X |

24、 Cj). G1,w1G2,w2G3,w3G4,w4G5.w5Class 1 )()()|()|(XPCPCXPXCPjjjNckkkGwXP1)()()( 2/ 12/ 12/1|)2 (1)|(iTiXViXidikeVGXpGVariables: i, Vi, wkWe use EM (estimate-maximize) algorithm to approximate this variables.Composition of Gaussian MixtureGaussian MixturenThese parameters are tuned using a complex ite

25、rative procedure called the estimate-maximize (EM) algorithm, that aims at maximizing the likelihood of the training set generated by the estimated PDF.nThe likelihood function L for each class j can be defined as: trainNijijCXPL0)|(trainNijijCXPL0)|(ln()ln(Gaussian Mixture Training Flow Chart (1)In

26、itialize 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 =1 / G so that all Gaussian are equally likely.Present each pattern X of the training set and model each of the c

27、lasses K as a weighte sum of Gaussians:Where G is the number of Gaussians, the is are the weights, andWhere Vi is the covariance matrix.)|()|(1iGiisGXpXp)()(2/12/12/1|)2(1)|(iTiXViXidieVGXpGaussian Mixture Training Flow Chart (2)Compute: GjkjjkiikiiiipCXpCGXpXpCGXpXGP1),|(),|()(),|()|(Iteratively up

28、date the weights, means and covariances: cNppicitNt1)(1)1(pNppiicXttNtic1)()(1)1()()()()(1) 1(1TipipNppiicitXtXttNtVcGaussian Mixture Training Flow Chart (3)Recompute ip using the new weights, means and covariances. Stop training if Or the number of epochs reach the specified value. Otherwise, conti

29、nue the iterative updates.thresholdttpipipi)() 1(Gaussian Mixture Test Flow ChartPresent each input pattern X and compute the confidence for each class j:Where is the prior probability of class Cj estimated by counting the number of training patterns. Classify pattern X as the class with the highest confidence.),|()(jxjCXPCPNNCPcij)(Gaussian Mixture End