【正文】 2 5 2 2 1 4 1 6 2 0 1 7 1 8 1 9 1 5 2 3 1 9 6 4 7 1 0 1 2 1 1 3 5 2 8 2 1 SNN Clusters of SLP. S N N D e n si t y o f S L P T i m e S e r i e s D a t alo n g it u d elatitude 1 8 0 1 5 0 1 2 0 9 0 6 0 3 0 0 3 0 6 0 9 0 1 2 0 1 5 0 1 8 0 9 0 6 0 3 0 0 3 0 6 0 9 0SNN Density of Points on the Globe. ? 41年期間，在 平均海平面氣壓（ SLP） 優(yōu)點與局限性 ? 基于 SNN密度的聚類的優(yōu)點與局限性類似于 JP聚類。 ? 然而，核心點和 SNN密度的使用大大增加了該方法的能力和靈活性。 可伸縮：一般問題和方法 ? BIRCH ? CURE ? 如果運行時間長得不可接受，或者需要的存儲量太大，即使最好的聚類算法也沒有多大價值。 ? 許多聚類算法所需要的存儲量都是非線性的。例如：使用層次聚類，存儲需求一般是 O(m2)。類似地，有些聚類算法所需要的計算量也是非線性的。 ? 可伸縮性可以通過如下技術(shù)實現(xiàn)：多維或空間存取方法、鄰近度約束、抽樣、劃分?jǐn)?shù)據(jù)對象、匯總、并行與分布計算。 CURE ? CURE（ Clustering Using REpresentative）是一種聚類算法，它使用各種不同的技術(shù)創(chuàng)建一種能夠處理大型數(shù)據(jù)、離群點、具有非球形和非均勻大小的簇的數(shù)據(jù)的方法。 ? CURE使用簇中的多個代表點來表示一個簇。理論上，這些點捕獲了簇的幾何形狀。 ? 具體來說，第一個代表點選擇離簇中心最遠(yuǎn)的點，而其余的點選擇離所有已經(jīng)選取的點最遠(yuǎn)的點。這樣，代表點相對分離。 ? 選取的點的個數(shù)是一個參數(shù)，但是一般取 10效果較好。 ? 一旦選定代表點，它們就以因子 a向簇中心收縮。這有助于減輕離群點的影響。 ? 例如，一個到中心的距離為 10個單位的代表點將移動 3個單位（對于 a=），而到中心距離為 1個單位的代表點僅移動 。 ? ? CURE使用一種凝聚層次聚類方案進(jìn)行實際的聚類。兩個簇之間的距離是任意兩個代表點（在它們向它們代表點的中心收縮之后）之間的最短距離。 ? 如果 a=0，它等價于基于質(zhì)心的層次聚類； a=1時，它與單鏈層次聚類大致相同。 ? 注意，盡管使用層次聚類方案，但是 CURE的目標(biāo)是發(fā)現(xiàn)用戶指定個數(shù)的簇。 ? CURE在聚類過程的兩個不同階段刪除離群點。首先，如果一個簇增長緩慢，則這意味它主要由離群點組成，因為根據(jù)定義，離群點遠(yuǎn)離其他點，并且不會經(jīng)常與其他點合并。 ? 在 CURE中，離群點刪除的第一個階段一般出現(xiàn)在簇的個數(shù)是原來點數(shù)的 1/3時。第二個離群點刪除階段出現(xiàn)在簇的個數(shù)達(dá)到 K的量級時。此時，小簇又被刪除。 ? CURE在最壞情況下復(fù)雜度為 O(m2logm)，它不能直接用于大型數(shù)據(jù)集。因此， CURE使用了兩種技術(shù)來加快聚類過程。 ? 第一種技術(shù)是取隨機(jī)樣本，并在抽樣的數(shù)據(jù)點上進(jìn)行層次聚類。隨后是最終掃描，將數(shù)據(jù)集中剩余的點指派到簇中。 ? 在某些情況下，聚類所需要的樣本仍然太大，需要第二種技術(shù)解決。在這種情況下， CURE劃分樣本數(shù)據(jù)，然后聚類每個劃分中的點。這種預(yù)聚類步后通常緊隨中間簇的聚類，以及將數(shù)據(jù)集中的每個點指派到一個簇的最終掃描。 CURE算法 ? 由數(shù)據(jù)集抽取一個隨機(jī)樣本集。 ? 將樣本集劃分成 p個大小相同的劃分。 ? 使用 CURE的層次聚類算法，將每個劃分中的點聚類成 m/pq個簇，得到總共 m/q個簇。 ? 使用 CURE的層次聚類算法對上一步發(fā)現(xiàn)的 m/q個簇進(jìn)行聚類，直到只剩下 k個簇。 ? 刪除離群點。 ? 將所有剩余的數(shù)據(jù)點指派到最近的簇，得到完全聚類。 ? K是期望的簇個數(shù)， m是點的個數(shù)， p是劃分的個數(shù)，而 q是一個劃分中的點的期望壓縮，即一個劃分中的簇的個數(shù)是 m/pq，簇的總數(shù)是 m/q ? 例如，如果 m=10000， p=10并且 q=100，則每個劃分包含 10000/10=1000個點，每個劃分有1000/100=10個簇，而總共有 10000/100=100個簇。 CURE的抽樣 ? CURE抽樣盡力確保抽到每個簇的樣本。為了保證這樣的抽樣， CURE的作者推算出了能夠?qū)崿F(xiàn)這一保證的樣本集大小的上界。 ? S為我們應(yīng)該抽取的樣本大小 ? 假設(shè)有 100000個對象，我們的目標(biāo)是以 80%的可能性得到10%的 Ci簇對象，其中 Ci的大小是 1000。在此情況下，f=， δ =， m=100000，這樣 s=11962。 ? S=11962是為了以 80%的概率得到 10%的 Ci簇對象，需要抽取的樣本大小 ???1l og***21l og1l og* 2iiimfmmmmfms ????劃分 ? 將點劃分成 p個大小為 m/p的組，使用 CURE對每個劃分聚類，將對象的個數(shù)壓縮一個因子 q1,其中q可以粗略地看作劃分中的簇的平均大小?？偣伯a(chǎn)生 m/q個簇。然后，預(yù)聚類后隨 m/q個中間簇的最終聚類，產(chǎn)生期望的簇個數(shù)。兩遍聚類都使用CURE的層次聚類算法，而最后一遍將數(shù)據(jù)集中的每個點指派到一個簇。 ? P和 q的選取是關(guān)鍵。應(yīng)盡力選擇合適的 p，使得整個劃分可以以合理的時間在內(nèi)存處理。此外，應(yīng)盡力選擇合適的 p和 q使得同一基本簇的對象最終在一個簇中。 ? A subwork is defined as a gene set that induces a single connected ponent in the protein–protein interaction work. Given a particular subwork M, let a represent its vector of activity scores over the tumor samples, and let c represent the corresponding vector of class labels (metastatic or nonmetastatic). 使用哪種聚類算法？ ? 聚類的類型 ? 簇的類型 ? 簇的特性 ? 數(shù)據(jù)集和屬性的特征噪聲和離群點 ? 數(shù)據(jù)對象的個數(shù) ? 屬性的個數(shù) ? 簇描述 ? 算法考慮 ? 數(shù)據(jù) ? 探索數(shù)據(jù) ? 分類：基本概念、決策樹與模型評估 ? 分類：其他技術(shù) ? 關(guān)聯(lián)分析：基本概念和算法 ? 關(guān)聯(lián)分析：高級概念 ? 聚類分析：基本概念和算法 ? 聚類分析：附加問題與算法 ? 異常檢測