《自动集群侦测》PPT课件.ppt

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