《《自动集群侦测》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《自动集群侦测》PPT课件.ppt（58页珍藏版）》请在三一办公上搜索。
1、自動集群偵測,韓 家 興 陳 君 彥 國立中興大學行銷研究所,自動集群偵測簡介,實際情況中，資料是相當複雜的(沒有固定的型態、變數多、維度、複雜的結構)集群分析主要的目的在於將複雜的資料區分為較小部分，讓每部分更容易解釋與簡化如果區隔適當則可從各集群中找更簡化的解釋方式 例如：樹木顏色的分類,資料庫行銷集群偵測分析,報告流程,兩個實際例子運用的介紹(天文學、軍服尺寸設計)K-means集群演算法使用幾何方式的解釋方法相似性與距離集群事前的準備工作單位的一致性權重設定其他集群方法Gaussian mixture高斯演算法Agglomerative clustering凝聚分析法Divisive
2、clustering階層式分裂演算法Case study報紙編輯區的分類,資料庫行銷集群偵測分析,搜尋簡化的集群資料 Searching for Islands of Simplicity,資料採礦可分為：有方向性有一個應變數(Y)，其餘都是自變數(X)沒有方向性沒有任何分類好的變數，目的是找出所有變數中，是否存在某些關係資料的可用性取決於使用者本身在行銷中的應用上，集群代表了市場區隔的概念自動集群偵測很少單獨使用，集群之後必須使用其他方法進一部加以分析集群所代表的意義,資料庫行銷集群偵測分析,實際例子應用 天文學(一閃一閃亮晶晶散佈圖),資料庫行銷集群偵測分析,恆星相對太陽亮度的倍數,恆星表
3、面溫度,實際例子應用 天文學(一閃一閃亮晶晶散佈圖),資料庫行銷集群偵測分析,實際例子應用 天文學(一閃一閃亮晶晶散佈圖),資料庫行銷集群偵測分析,紅巨星,白矮星,實際例子應用軍服尺寸設計,資料庫行銷集群偵測分析,實際例子應用軍服尺寸設計,資料庫行銷集群偵測分析,二維或三維時我們還可以用肉眼觀察出集群分類的情形，但當構面數多時，便難以觀察出集群的情形目的是提供合身的軍服，與減少不同尺寸軍服，降低庫存數量使用的構面腿長、腰圍、胸圍最後分類出一百多種體型量測,K-Means 集群法,K-Means 集群法是1967由提出最常使用的集群方法所謂的“K”，將資料分成幾組的組數以下為了簡化，以二維的圖解
4、來解釋其方法(實際情況中往往為多維度的情況),資料庫行銷集群偵測分析,K-Means 集群法步驟,步驟一：隨機選取個點作為種子點步驟二：將各個數據資料與最接近之種子點分為同一集群(原始集群),資料庫行銷集群偵測分析,K-Means 集群法步驟,資料庫行銷集群偵測分析,步驟三：計算各(原始)集群之中心點步驟四：新的中心點此時成為新的種子點,Seed 2,Seed 1,Seed 3,K-Means 集群法步驟,資料庫行銷集群偵測分析,持續重復上述的步驟，直到達到穩定的狀態,K Means的意義,有時集群無法對其結構做出最標準之敘述(市區的定義)各集群的一內致性高低，可用集群內所有資料之平均距離來做
5、比較整個方法的過程可使用機械化(例如：電腦軟體)方式來完成，但集群的適用性與可用價值則需要用更主觀的衡量方式第一次使用K-Means Clustering法時，大部分資料都會落入一個大的集群，而週遭會圍繞著許多小的集群(例如：定義欺騙行為或不良品的衡量),資料庫行銷集群偵測分析,相似性與距離,照理來說，相同集群內的資料比其他集群之資料有較高之相似性測量相似性高低最簡易之方法，為將其資料量化，並在幾何空間中計算比較，但此方法會有以下限制：許多資料不適合量化或使用幾何向量方式呈現在幾何中，距離為非加權的，與有些資料屬性不符合,資料庫行銷集群偵測分析,相似性量測與變數型態,資料庫行銷集群偵測分析,四
6、種尺度型態(老生常談)類別尺度順序尺度區間尺度比例尺度幾何距離可直接適用於區間尺度與比例尺度的資料上類別變數與順序變數則需要做轉換才可使用幾何距離。但這些轉換有可能造成資料真實性降低(將冰淇淋編號1-28號難道5&6號真的口味接近，1&28味道就差很遠嗎?),相似性量測的方法,以下介紹三種方法，前兩種適用於區間尺度與比例尺度的資料，第三種方法適用於類別尺度兩點之間的幾何距離兩向量間的角度曼哈頓距離,資料庫行銷集群偵測分析,兩點之間的幾何距離,歐幾里得距離兩點之間的距離近則相似性高,資料庫行銷集群偵測分析,兩項量間的角度,有時需同時考量一個以上之因素來測量相似性。例子：鯉魚應與沙丁魚、鱈魚、鮪魚
7、屬同集群，而小貓應與獅子、美洲獅、老虎同集群；雖然小貓在體型這個變項上與大魚很接近。,資料庫行銷集群偵測分析,（圖11.7）,曼哈頓距離,算法有如紐約曼哈頓市區的方形格子的型態在幾何上，曼哈頓距離是行經所有變數軸之和。（有時此法較歐幾里得距離好用，因為距離不需平方，所以不會因為一個構面（變項）的小小差異因為平方而造成對總距離有主導性的影響）,資料庫行銷集群偵測分析,量測相似性的共同特性,當資料是類別尺度時，幾何方法並非最好，較好的方法是資料間重疊的程度將所有的資料是一個範圍與一個範圍的比較是否相配衡量所有變數相符的比例,資料庫行銷集群偵測分析,集群的事前的準備工作,單位的一致性(Scaling
8、 for consistency)若欲以幾何距離量測相似性，須先將資料轉換成同一單位基準，以下有三種常用方式：常態化(Normalizing)：將資料案全距劃分成固定範圍（例：01或-11）指數調整(Indexing)標準化(standardizing)權重設定 主要目的：決定變數間的相對重要性,資料庫行銷集群偵測分析,使用K-Means集群的缺點,無法妥善處理集群之間重疉的狀況(類別尺度)集群易受離群值的影響各資料被明確決定屬於某集群內或非屬於該集群，非黑即白，沒有模棱兩可。,資料庫行銷集群偵測分析,Gaussian mixture,高斯演算法適用處 理多構面資料，是 K-Means的一種轉
9、變,資料庫行銷集群偵測分析,步驟一：估計。計算各高斯集群對所有資料點Responsibility毎個資料點離高斯點越近，則Responsibility愈大，離高斯點越遠則Responsibility越小。Responsibility在下一階段被當作的權重,Gaussian mixture高斯演算法,步驟二：最大化新的中心點被計算出，以進一步算出更新Responsibility步驟三：重複以上動作直到達成穩定,資料庫行銷集群偵測分析,Agglomerative clustering 凝聚集群法,K-Means的集群法在開始時便有設好K(集群數)為多少。凝聚性集群每筆資料皆屬各自的集群開始，然後再
10、將集群漸漸擴大，合併這些集群，至最後，全部資料皆屬同一集群。凝聚性集群法一開始的集群很小很純，且各資料高度相關；愈後面的集群愈大、資料愈雜，集群屬性預難定義。凝聚集群法最重要事項之一就是選擇要焠鍊至何種層級的集群，效果最佳！,資料庫行銷集群偵測分析,凝聚分析法的步驟,步驟一：相似性矩陣。兩兩資料(集群)之間的距離或相似度之矩陣(若有n筆資料，則需n2次的計算)步驟二：找出相似性矩陣的最小值。這樣可以找出最相似的兩筆資料(集群)，並將其合併為一新的集群。(此時剩下n-1個集群)步驟三：繼續以上的步驟直到所有的資料(集群)，接成為同一集群為止。選擇使用至哪一層級的集群，將是決定性的關鍵,資料庫行銷
11、集群偵測分析,凝聚分析法的實例 以年齡進行集群分析,資料庫行銷集群偵測分析,缺點：若其中一個集群中的資料合併錯時，便不能返回,45,49,43,37,集群與樹狀圖,凝聚性集群法以層級性的方式製造集群，於是可使用樹狀圖。與決策樹的差異凝聚集群樹狀圖並沒有敘述為何資料歸為同一集群，而以最短距離來分成集群的決策樹由根部出發，以發展出所預定之葉(目標)，凝聚性集群法則是相反的由葉出發，以集群為目的，往最終的根部前進,資料庫行銷集群偵測分析,集群之間的距離量測方式,資料庫行銷集群偵測分析,Divisive clustering 階層式分裂演算法,以決策樹的觀念來做集群分類階層式分裂演算法由根部出發，往葉
12、子邁進；凝聚性集群法是相反的由葉出發，往最終的根部前進,資料庫行銷集群偵測分析,集群的評估,問題一：如何決定K-mean中K的數目問題二：如何決定那一個層級的集群擁有較佳的集群(凝聚與層級分裂法)問題三：到底怎樣才算是一個好的集群,資料庫行銷集群偵測分析,集群的內外部,資料庫行銷集群偵測分析,集群內部集群內部裡面，差異越小越好平均數變異數集群外部集群之間差異越大越好,集群分析與區別分析的差異(補充),區別分析群落、市場區隔為已知(選擇題、是非題)集群分析群落、市場區隔的分佈為未知(問答題),資料庫行銷集群偵測分析,其他集群分析的應用,資料庫行銷集群偵測分析,主要目的：使銷售人員能在第一時間經由
13、顧客的臉型、表情、長相區分出顧客可能的購物情形,其他集群分析的應用,資料庫行銷集群偵測分析,主要目的：區分出不同品牌的Pizza不同的特色,Case study報紙編輯區的集群,資料庫行銷集群偵測分析,Boston Globe是Boston與Boston週遭地區Massachusetts、New Hampshire最主要的日報面臨問題：主要市場Boston讀者數下降郊區市場受到地區性報紙的競爭威脅而造成閱讀的移轉Boston Globe希望將現行不理想的12個地理區域的編輯區，做出更好的分類，每個編輯區中每周會有兩天報導當地的新聞,編輯區的限制,編輯區應擁有地理區域上的連續性編輯區的緊密性，以
14、及編輯區中人口的充足與否將會直接影響到報導內容編輯區會因為地理區域而調整使用的廣告 受到上面的限制，Boston Globe希望將擁有共同特性的城市，設計合適的編輯區。但哪些城市具有相似性呢?,資料庫行銷集群偵測分析,創造出城市的共同變數,在分類出不同城市屬於哪個集群前，必須能夠先描述出每個城市的特性而資料採礦人員早期的計劃是希望能夠從這些城市已經定義好的共同變數探勘出未來發行率會持續成長的城市,資料庫行銷集群偵測分析,資料來源與特性,城市的特性大多來自不同的來源處，但大多的變數來自1990以及2001年美國城市的人口調查(變數包含年齡、種族、職業、收入、Home value)此外，Globe
15、從各城市中送報商中取得每戶家庭的資料在促銷時訂閱戶所留下的資訊抱怨電話訂閱的方式(日報、Sunday),資料庫行銷集群偵測分析,創造城市共同特性的步驟,Aggregation:將所有資料轉換成城市的共同特性，在進一歨行成不同城市的層級Normalization常態化:將所有的數值轉換成用百分比的形態表示Calculation of trends:推測趨勢:趨勢能夠反應出一個城市的特性Creation of derived variables:創造來源變數:除了在變數中找尋共同特性，找出城市中的重要特性,資料庫行銷集群偵測分析,創造集群,當描述城市特性時可以藉由人口統計和地理區域來建立集群，但集
16、群的建立並不能夠馬上的就找出合適編輯區因為一些地理上的限制都會導致編輯區將週遭的城市納入人口統計相似的城市並不能代表相近的地理區域人口統計的集群能夠使用單一因素設計編輯區，並且考量到地理上的限制,資料庫行銷集群偵測分析,決定合理的集群數,在建立編輯區的集群數時，會因為許多商業上的考量形成許多的編輯區，但我們往往不能夠保證每個好的集群都能夠被發現但若是結合K-Means法以及分裂樹狀圖能夠解決集群數的問題步驟一：先決定較低的K值做區分，並使用K-Means演算法步驟二：利用平均距離或變異數將目前的單一集群分裂出較合適的集群步驟三：重覆以上步驟直到集群內相似性較高,資料庫行銷集群偵測分析,利用集群
17、樹將Boston Globe做區分,資料庫行銷集群偵測分析,Home value高教育程度高,低收入年長訂閱戶鄰近Boston,Home value低收入普通,Home value/收入接近Population的平均值,使用Thematic Cluster調整區域疆界,資料庫行銷集群偵測分析,2,2,1B,集群1B：低收入年長訂閱戶鄰近Boston,集群2：Home value高教育程度高,結論,自動集群偵測法是非直接的資料採礦技術，主要目的是將複雜的資料簡化。自動集群偵測通常與其他資料採礦技術一起使用，效果更佳！自動集群偵測能夠處理（幾乎）任何型態的資料，功能十分強大。距離是自動集群偵測處理
18、量化資料的核心觀念。K-Means是自動集群偵測最常使用的方法。利用自動集群偵測能夠將有用的集群轉換成商業用途達成企業目標。,資料庫行銷集群偵測分析,THE END THANK YOU!,補 充：Gaussian Mixture,Gaussian Mixture,The Gaussian mixture architecture estimates probability density functions(PDF)for each class,and then performs classification based on Bayes rule:,Where P(X|Ci)is the P
19、DF 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 Mixture,Unlike 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
20、 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 class.,Gaussian Mixture,Each Gaussian component is defined as:,Where Mk is the mean of the Gaussian and Vk is the covariance matrix of the Gaussian.,Gaussian Mixture,Free par
21、ameters 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|Cj).,Class 1,Variables:i,Vi,wkWe use EM(estimate-maximize)algorithm to approximate this variables.,Co
22、mposition of Gaussian Mixture,Gaussian Mixture,These 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
23、as:,Gaussian 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=1/G so that all Gaussian are equally likely.,Present each pattern X of
24、 the training set and model each of the classes 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.,Gaussian Mixture Training Flow Chart(2),Compute:,Iteratively update the weights,means and covariances:,Gaussian Mixture Trai
25、ning 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,continue the iterative updates.,Gaussian Mixture Test Flow Chart,Present 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.,Gaussian Mixture End,
