Course 5集羣分析Cluster Analysis课件.pptVIP

* * * * 劃分方法 給定一個n個對象或元組的資料庫，一個劃分方法構建資料的k個劃分，每個劃分表示一個集羣，並且k=n。 每個組至少包含一個對象 每個對象屬於且僅屬於一個組 劃分準則︰同一個集羣中的對象儘可能的接近或相關，不同集羣中的對象儘可能的遠離或不同 集羣的表示 k-平均演算法 由集羣的平均值來代表整個集羣 k中心點演算法 由處於集羣的中心區域的某個值代表整個集羣 * 層次的方法 對給定資料對象集合進行層次分解 自底向上方法（凝聚）︰開始將每個對象作為單獨的一個組，然後相繼的合併相近的對象或組，直到所有的組合併為一個，或者達到一個終止條件。 自頂向下方法（分裂）︰開始將所有的對象置於一個集羣中，在迭代的每一步，一個集羣被分裂為多個更小的集羣，直到最終每個對象在一個單獨的集羣中，或達到一個終止條件 缺點︰合併或分裂的步驟不能被撤銷 * 基於密度的方法 基於距離的集羣方法的缺點︰只能發現球狀的集羣，難以發現任意形狀的集羣。 基於密度的據類︰只要臨近區域的密度（對象或資料點的數目）超過某個臨界值，就繼續集羣。 優點︰可以過濾掉“噪聲”和“孤立點”，發現任意形狀的集羣。 * 基於網格的方法 把對象空間量化為有限數目的單元，形成一個網格架構。所有的集羣都在這個網格架構上進行。 優點︰處理數度快（因為處理時間獨立於資料對象數目，只與量化空間中每一維的單元數目有關） * 基於模型的方法 為每個集羣假定一個模型，尋找資料對給定模型的最佳擬合。 一個基於模型的演算法可能透過構建反映資料點空間分配的密度函數來定位集羣 這種方法同時也用於自動的決定資料集中集羣的數目 透過統計學的方法，考慮噪聲和孤立點，從而產生健壯的集羣方法 * ? 孤立點挖掘 什麼是孤立點？ 一個資料集與其他資料有著顯著區別的資料對象的集合 例如︰運動員︰Michael Jordon, 舒馬赫，布勃卡 孤立點產生原因 度量或執行錯誤（年齡︰-999） 資料變異的結果 孤立點挖掘 給定一個n個資料對象的集合，以及預期的孤立點數目k，發現與剩餘的資料有著顯著差異的頭k個資料對象 應用 信用狀欺詐檢測 移動電話欺詐檢測 客戶劃分 醫療分析（異常） * 基於統計的孤立點檢測 統計的方法對於給定的資料集合假定了一個分配或機率模型（例如常態分配） 使用倚賴於以下參數的不一致性檢驗（discordancy tests） 資料分配 分配參數（e.g. 均值或方差） 預期的孤立點數 缺點 絕大多數檢驗是針對單個屬性的，而資料挖掘要求在多維空間中發現孤立點 大部分情況下，資料分配可能是未知的 * 基於距離的孤立點檢測 為了解決統計學方法帶來的一些限制，引入了基於距離的孤立點檢測 在不知道資料分配的情況下對資料進行多維分析 基於距離的孤立點︰即DB(p,d)，如果資料集合S中的對象至少有p部分與對象o的距離大於d，則對象o就是DB(p,d)。 挖掘基於距離的孤立點的高效演算法︰ 基於索引的演算法 巢狀－循環演算法 基於單元的演算法 * 基於偏離的孤立點檢測 透過檢查一組對象的主要特徵來確立孤立點 跟主要特徵的描述相“偏離”的對象被認為是孤立點 兩種基於偏離的孤立點探測技術 序列異常技術 模仿人類從一系列推測類似的對象中識別異常對象的模式 OLAP資料立方體技術 在大規模的多維資料中採用資料立方體來確定異常區域。如果一個立方體的單元值顯著的不同於根據統計模型得到的期望值，則改單元值被認為是一個異常，並用可視化技術表示。 * 國立聯合大學 資訊管理學系 資料探勘課程 (陳士杰) Data Mining 資料探勘 國立聯合大學 資訊管理學系 陳士杰老師 Course 5集羣分析Cluster Analysis ? Outlines 什麼是集羣分析？ 集羣分析的典型應用 集羣分析應用實例 什麼是好的集羣分析？ 資料挖掘對集羣分析的要求 集羣分析中的資料類型 相異度計算 主要的集羣方法 孤立點挖掘 * ? 什麼是集羣分析？ 集羣 (Cluster: 聚類、簇): 資料對象的集合 所謂集羣是指一群人、事或物的組合，這些人、事或物統稱為Objects 在同一個集羣 (簇) 中的對象彼此相似 不同集羣中的對象則相異 集羣分析 將一堆Object分成幾類，使性質類似的Object自成一個小集羣 假設每個Object在許多屬性 (或變數) 上均有一個觀測分數，有人在某些屬性上分數較高，在其它屬性上分數較低。 每個Object在這些屬性上分數高低的情況或輪廓，即為該Object在這些變項上分數的Profiles (輪廓)，每個profile在幾何座標圖中以一點表示。 * 設A和B二個Objects在x和y兩個變數上均有一個分數。Profiles A是由x