【導(dǎo)讀】usagepatterns.itsowncluster.changeovertime.

　　

【正文】 （相對(duì)于分類 而言 ）： ? 聚類的（最佳）數(shù)目 是不知道的 ? 對(duì)于某個(gè)聚類 可能沒有任何先驗(yàn)知識(shí) ? 聚類 的 果是動(dòng)態(tài)的。 聚類問題 敘述的正如定義 ， 這里 我們假設(shè) 創(chuàng)建的聚類的數(shù)目為一個(gè)輸入值 k， 每個(gè)聚類 jk ,（ 1 jk??） 的 實(shí)際內(nèi)容（ 說明 ），作為一個(gè) 功能定義 。 不失一般性 ， 我們 認(rèn)為，解決問題的結(jié)果 建立的聚類集合：K={ 12, ,..., kk k k }。 定義 已知 一個(gè) 數(shù)組 集合 D={ 12, ,..., nt t t }和一個(gè)整數(shù) k， 聚類 問題是定義一個(gè) 映射 f： {1,..., }Dk? ， 其中 分配 it 到 聚類 jK （ 1 jk??） 。 聚類 jK ，就是 集合 D 映射到 jK ={ | ( ) ,1 ,i i jt f t K i n? ? ?and itD? }。 聚類算法的不同類型的分類如圖 。聚類 算法 本身 就可 視為分層或 分塊 的。分層聚類 分析可以建立 一個(gè)嵌套的 聚類集合 。在層次結(jié)構(gòu)中的每 層都有單獨(dú)的 聚類 。在最低 層，每 個(gè)項(xiàng)目 都劃分在不同的特殊的集合中 。在最 頂層 ，所有的項(xiàng)目屬于同一 集合 。 通過 分層聚類， 需要的聚類 數(shù)目并 沒有 輸入。 分塊聚類分析算法只 創(chuàng)建一個(gè) 聚類集合 。這些方法 通過所需的聚 類集合數(shù)目促使最終集合的建立。傳統(tǒng)的聚類算法往往是針對(duì) 適合 小數(shù)據(jù)庫 。然而， 現(xiàn)在 的聚類算法， 從 分類數(shù)據(jù) 上來 看， 是 針對(duì)動(dòng)態(tài) 的大 數(shù)據(jù)庫。 針對(duì)大型數(shù)據(jù)庫的算法可適應(yīng)內(nèi)存限制 通過數(shù)據(jù) 采樣或 者是 使用該數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)， 從而 可以被壓縮或修 訂 ，以適應(yīng)數(shù)據(jù)庫 的內(nèi)存限制 。也可能 是基于 是否產(chǎn)生重疊聚類算法。即使我們只考慮重疊的 聚類 ，它可以 把某個(gè)項(xiàng)目 放置在多個(gè) 聚類中 。反過來，不重疊的 聚 類 可以被看作是外在 的 或 者 內(nèi)在 的。外源性技術(shù)使用 項(xiàng)目標(biāo)簽 以協(xié)助 分類 。這些算法是傳統(tǒng) 的 分類監(jiān)督學(xué)習(xí) 算法 ， 這個(gè)算法用到了 特殊的輸入訓(xùn)練集 合 。內(nèi)在的算法 沒有 使用任何先驗(yàn)的類別標(biāo)簽，僅僅依賴于矩陣 中 鄰 近 對(duì)象之間的距離。我們?cè)诒菊卵芯?的 所有算法 都屬于 內(nèi)在類。 聚類算法的類型 基于實(shí)現(xiàn)技術(shù)使用的基礎(chǔ)上可以被進(jìn)一步 分類。分層算 法可以 歸類為凝聚 算法 或 者 分裂 算法。 “ 凝聚 ”意味著在一個(gè) 聚類 是 通過自下而上的方式產(chǎn)生，而分裂算法則是以 自上而下的方式工作。雖然 分層 和分塊 的算法 用 凝聚 與 分裂的標(biāo)簽 來描述 ， 但 它通常 與分層 算法 聯(lián)系更緊密 。另一種描述標(biāo)簽 是指 是否 對(duì) 每個(gè)元素 一一 處理， 一系列 （有時(shí)稱為增量） 的一起處理 ，或 者 是否所有的項(xiàng)目都放在一起同步 研究 。如果一個(gè)特定的 數(shù)組被視為具有在該架構(gòu)中的所有屬性，然后可以用 不同聚類算法 進(jìn)行 屬性檢查。由于通常 用分層 分類 的 技術(shù)來完成， 有些算法分析屬性值每次只分析一個(gè) 。 Polythetic 算法考慮 的是每次的 所有 屬性值。最后，聚類算法 以 算法的數(shù)學(xué)公式 被表示出來：圖表或矩陣代數(shù)的理論基礎(chǔ)。這一章中，我們 采用圖形方式， 并且把聚類算法的輸入描述為鄰近距陣中距離變化。 我們?cè)谝韵赂鞴?jié)討論許多聚類算法。這 只是 已在文獻(xiàn)中提出了很多算法 中具有代表性的一個(gè) 。在這些算法 找到之前 ，我們首先研究 類似的處理 措施， 并研究 對(duì) 異常值的影響。 相似 性和距離 測(cè) 量 一個(gè) 特殊的聚類問題的 解決方案 可以產(chǎn)生很多理想的特性。 最重要的是，在 某個(gè)聚類中的一個(gè)數(shù)組比聚類外的數(shù)組 更像 聚類中的 。 至于 經(jīng)過 分類，那么， 假設(shè)我們 定義一個(gè) 近似度 ， sim( ,iltt)， ,ilt t D? 。 定義 更嚴(yán)格的定義和 可 替代 的 聚類。 除非另有說明，我們使用第一個(gè)定義而不是第二個(gè)。 在第二個(gè)定義 中的敘述的 相似關(guān)系是 可以獲得的特點(diǎn) ， 但是并不總 能獲得 。 距離量 dis( ,ijtt)，而不是相似 度 ，往往 被用于聚類分析。 根據(jù)這樣聚類 問題可以獲得jK, ,jl jm jt t K?? 和 , ( , ) ( , )i j jl jm jl it K sim t t d is t t??這兩個(gè)集合所表示的 特性。 一些聚類算法只看數(shù)字 型 數(shù)據(jù)，通常假定 度量 數(shù)據(jù)點(diǎn)。 度量屬性滿足三角不等式。 那么 聚類集合 可以使用多種特征值 來 描述。 給出一個(gè)聚類集合 ， N 點(diǎn) { 12, ,...,m m mNt t t }中的 mK ,我們提出以下定義 [ZRL96]： 這里的質(zhì)心是 聚類集合的 “中 心 ”，它不 一定 是一個(gè) 聚類集合中的實(shí)點(diǎn) 。一些聚類算法 可能 假設(shè)聚類集合是由位于聚類集合中心的中心點(diǎn)代替 。 半徑是 從集合中的中心點(diǎn)到聚類集合 中的任何點(diǎn) 間 的距離 的平方根，并且是對(duì)聚類集合中所有點(diǎn)而言的 。 我們使用符號(hào) mM 來表示聚類集合 mK 的中心點(diǎn)。 許多聚類算法要求 確定聚類集合（而不是元素）中的距離 。 這不是一件容易的事 ， 因?yàn)?聚類集合中的距離有很多解釋 。 已知聚類集合 iK 和 jK ，有幾個(gè)標(biāo)準(zhǔn)的 供選方案 來計(jì)算 聚類集合 之間的距離。 典型的 列表如下： ? 單鏈接 ：在一個(gè)聚類集合中的一個(gè)元素與另一個(gè)聚類集合中的一個(gè)元素之間的最小距離。這樣，我們可以得到dis( ,ijKK)= m i n( ( , ) )il jm il i jdi s t t t K K? ? ?and jm j it K K? ? ? 。 ? 完整的鏈接 ：在一個(gè)聚類集合中的一個(gè)元素與另一個(gè)聚類集合中的一 個(gè) 元 素 之 間 的 最 大 距 離 。 這 樣 我 們 可 以 得 到dis( ,ijKK)= m a x ( ( , ) )il jm il i jd is t t t K K? ? ?and jm j it K K? ? ? 。 ? 平均： 在一個(gè)聚類集合中的一個(gè)元素與另一個(gè)聚類集合中的一個(gè)元素 之 間 的 平 均 距 離 。 這 樣 我 們 可 以 得 到dis( ,ijKK)= ( ( , ) )il jm il i jm e a n d is t t t K K? ? ?and jm j it K K? ? ? 。 ? 質(zhì)心： 如果聚 類集合有具有代表性的質(zhì)心，那么中心距離可以定義為這些質(zhì)心之間的距離。這樣我們可以得到 dis( ,ijKK)=dis( ,ijCC)， iC 為 iK的質(zhì)心并且與jC類似。 ? 中心點(diǎn)： 使用中心點(diǎn)來代替每個(gè)聚類集合，集合之間的距離可以由中心點(diǎn)之間的距離來定義： dis( ,ijKK)= ( , )ijdis M M 異常數(shù)據(jù) 如前所述，離群點(diǎn)是 不同于集合里的剩余數(shù)據(jù)的采樣點(diǎn) 。 離群值 可能代表數(shù)據(jù)里的錯(cuò)誤值 （可能是一個(gè)傳感器故障記錄）或 者 可能是 與其余數(shù)據(jù)值差異過大的 正確數(shù)據(jù)。 一個(gè) 米高的人比大多數(shù)人都要高得多 。在分析個(gè)人 的 高度 時(shí) ，此值 就應(yīng)該被視為一個(gè)離群值。 一 些 聚類分析 技術(shù) 對(duì)于存在離群值的模型的分析表現(xiàn)的并不好 。 如 圖 描述的問題 所示 。 在這里，如果 發(fā)現(xiàn) 三 個(gè)聚類集合 （實(shí)線）， 異常 值 將某個(gè)集合自身內(nèi)發(fā)生 。但是，如果兩個(gè) 集合 被發(fā)現(xiàn)（虛線），兩個(gè)（顯然）不同的數(shù)據(jù) 集合 將被放置在 聚類集合中 ，因?yàn)?它 們比 離群值聯(lián)系更緊密 。 這個(gè)問題是復(fù)雜的事實(shí)，實(shí)際上有許多聚類算法作為輸入所需數(shù)目的簇被發(fā)現(xiàn)。 實(shí)際上許多聚類算法想找到理想聚類集合的輸入數(shù)目，這個(gè)做事實(shí)上是很復(fù)雜的 。 聚類算法實(shí)際上可能發(fā)現(xiàn)和消除異常點(diǎn)，以確保 其 有更好的表現(xiàn) 。 但是，在實(shí)際消除異常點(diǎn) 時(shí) 必須 要 注意。例如，假設(shè) 有 預(yù)測(cè)洪水 的 數(shù)據(jù)挖掘問題。水位值極高 非常不容易出現(xiàn) ， 與 正常水位值 相比可能就 是異常值。然而，刪除這些值可能 使 數(shù)據(jù)挖掘算法 不能有效的工作 ，因?yàn)閷⒉粫?huì)有數(shù)據(jù)表明 曾經(jīng) 發(fā)生過水災(zāi)。 異常檢測(cè)，或離群數(shù)據(jù)挖掘， 是在數(shù)據(jù)集合中確定離群值的過程。 聚類 分析 ， 或者其它的 數(shù)據(jù)挖掘， 便可以選擇算法刪除這些值或者賦上不同的其它值。一 些異常檢測(cè)技術(shù)是基于統(tǒng)計(jì)技術(shù) 基礎(chǔ)上的 。 這樣 通常假設(shè) 數(shù)據(jù)集合遵循 已知的分布 并且假設(shè) 離群值 可以被一個(gè)著名測(cè)試 檢測(cè) 出來 ，例如discordancy測(cè)試 。 不過， 對(duì)于現(xiàn)實(shí)來說 這些測(cè)試數(shù)據(jù) 并 不是 很 真實(shí)，因?yàn)檎鎸?shí)的數(shù)據(jù)值可能不遵循定義 好 的數(shù)據(jù)分布。 此外， 這些測(cè)試中大部分只設(shè) 了單一的屬性值 測(cè)試， 并且許多屬性涉及現(xiàn)實(shí)世界的數(shù)據(jù)庫 。 可替代的 檢測(cè)技術(shù) 可能 基于距離 測(cè)量 。