【文章內(nèi)容簡介】 統(tǒng)計分析方法 在數(shù)據(jù)庫字段項之間存在兩種關(guān)系：函數(shù)關(guān)系 (能用函數(shù)公式表示的確定性關(guān)系 )和相關(guān)關(guān)系 (不能用函數(shù)公式表示，但仍是相關(guān)確定性關(guān)系 )，對它們的分析可采用統(tǒng)計學(xué)方法，即利用統(tǒng)計學(xué)原理對數(shù) 據(jù)庫中的信息進行分析。可進行常用統(tǒng)計 (求大量數(shù)據(jù)中的最大值、最小值、總和、平均值等 )、回歸分析 (用回歸方程來表示變量間的數(shù)量關(guān)系 )、相關(guān)分析 (用相關(guān)系數(shù)來度量變量間的相關(guān)程度 )、差異分析 (從樣本統(tǒng)計量的值得出差異來確定總體參數(shù)之間是否存在差異 )等。 ⑺模糊集方法 即利用模糊集合理論對實際問題進行模糊評判、模糊決策、模糊模式識別和模糊聚類分析。系統(tǒng)的復(fù)雜性越高，模糊性越強，一般模糊集合理論是用隸屬度來刻畫模糊事物的亦此亦彼性的。有人在傳統(tǒng)模糊理論和概率統(tǒng)計的基礎(chǔ)上，提出了定性定量不確定性轉(zhuǎn)換模型云模型，并形成 了云理論。 聚類分析算法介紹 聚類分析研究有很長的歷 史，幾十年來，其重要性及與其他研究方向的交叉特性得到人們的肯定。 聚類是數(shù)據(jù)挖掘、模式識別等研究方向的重要研究內(nèi)容之一，在識別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有極其重要的作用，聚類主要應(yīng)用于模式識別中的語音識別、字符識別等，機器學(xué)習(xí)中的聚類算法應(yīng)用于圖像分割和機器視覺，圖像處理中聚類用于數(shù)據(jù)壓縮和信息檢索，聚類的另一個主要應(yīng)用是數(shù)據(jù)挖掘 (多關(guān)系數(shù)據(jù)挖掘 )、時空數(shù)據(jù)庫應(yīng)用 (GIS 等 )、序列和異類數(shù)據(jù)分析等，此外，聚類還應(yīng)用于統(tǒng)計科學(xué)，值得一提的是，聚類分析對生物學(xué) 、心理學(xué)、考古學(xué)、地質(zhì)學(xué)、地理學(xué)以及市場營銷等研究也都有重要作用。 8 聚類概念 迄今為止，聚類還沒有一個學(xué)術(shù)界公認(rèn)的定義，這里給出 EverittIs 在 1974 年關(guān)于聚類所下的定義：一個類簇內(nèi)的實體是相似的，不同類簇的實體是不相似的；一個類簇是測試空間中點的會聚，同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離；類簇可以描述為一個包含密度相對較高的點集的多維空間中的連通區(qū)域，它們借助包含密度相對較低的點集的區(qū)域與其他區(qū)域 (類簇 )相分離 。 聚類過程： 1) 數(shù)據(jù)準(zhǔn)備：包括特征標(biāo)準(zhǔn)化和降 維， 2) 特征選擇：從最初的特征中選擇最有效的特征，并將其存儲于向量中， 3) 特征提?。和ㄟ^對所選擇的特征進行轉(zhuǎn)換形成新的突出特征， 4) 聚類 (或分組 )：首先選擇合適特征類型的某種距離函數(shù) (或構(gòu)造新的距離函數(shù) )進行接近程度的度量； 5) 聚類結(jié)果評估：是指對聚類結(jié)果進行評估，評估主要有 3種：外部有效性評估、內(nèi)部有效性評估和相關(guān) 性測試評估。 聚類 分析 算法的類別 沒有任何一種聚類技術(shù) (聚類算法 )可以普遍適用于揭示各種多維數(shù)據(jù)集所呈現(xiàn)出來的多種多樣的結(jié)構(gòu)，根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則以及應(yīng)用這些規(guī) 則的方法，有多種聚類算法 。 聚類算法有多種分類方法， 聚類算法可以分為以下幾大類：分割聚類方法 (Partitioning Method)、層次聚類方法 (Hierarchical Method)、基于密度 (DensityBased)的聚類方法、基于網(wǎng)格 (GridBased)的聚類方法、基于模型 (ModelBased)的聚類方法等等。 [1]基于劃分的方法 : 所謂基于劃分的方法 (Partitioning Method)是指給定一個包含 n 個數(shù)據(jù)對象的數(shù)據(jù)集，以及要生成的簇的數(shù)目 K，采用一個劃分準(zhǔn)則（稱為相似度函 數(shù)）將數(shù)據(jù)對象組織為 K 個劃分 (k=n)，每個劃分代表一個簇，使同一個簇中的對象是“相似的”，而不同簇中的對象是“相異的”。為了達到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。 為了使該方法適用于大規(guī)模數(shù)據(jù)集，以及處理復(fù)雜形狀的聚類，出現(xiàn)了若干基于劃分方法的擴展方法。 9 該類方法的典型代表是 KMeans 方法，其次有 KMedoids 方法， PAM 方法， CLARA方法， CLARANS 方法等。 [2]基于層次聚類的方法 : 基于層次的聚類方法將數(shù)據(jù)對象在不同的階段組成不同粒度的簇，在簇的分裂和合并過程中不斷 改善聚類的效果，以達到逐步求精的目的。根據(jù)層次分解是自底向上還是自頂向下形成，層次的聚類方法可以進一步分為凝聚的 (Agglomeration)和分裂的 (Divisive)層次聚類。 凝聚的層次聚類：這種自底向上的策略首先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者某個終結(jié)條件被滿足。絕大多數(shù)層次聚類方法屬于這一類，它們只是在簇間相似度的定義上有所不同。 分裂的層次聚類：這種自頂向下的策略與凝聚的層次聚類相反，它首先將所有對象置于一個簇中，然后逐漸細(xì)分為越來越小 的簇，直到每個對象自成一簇．或者達到了某個終結(jié)條件，例如達到了某個希望的簇數(shù)目，或者兩個最近的簇之間的距離超過了某個閾值。例如， DIANA 方法的處理過程中，所有的對象初始都放在一個簇中。根據(jù)一些原則（如簇中最臨近對象的最大歐氏距離），將該簇分裂。簇的分裂過程反復(fù)進行，直到最終每個新的簇只包含一個對象。 四個廣泛采用的簇間距離度量方法如下： 最小距離： ||m i n),( 39。39。,m in ppCCd CjpCpji i ?? ?? 最大距離： ||m a x),( 39。39。,m a x ppCCd CjpCpji i ?? ?? 平均值的距離： ||),( jijim ean mmCCd ?? 平均距離： ? ?? ? ?? i jCp Cpjijiav g ppnnCCd ||1),( , 這里 |pp,|兩個對象 p 和 p,之間的距離， m是簇 Ci的平均值，而 ni是簇 Ci中對象的數(shù)目。 [3]基于密度的方法 基于密度的聚類方法是為了發(fā)現(xiàn)任意形狀的聚類結(jié)果而提出的。這類方法將簇看作是數(shù)據(jù)空間中被低密度區(qū)域分割開的高密度對象區(qū)域。 DBSCAN(Density Based Spatial Clustering of Applications with Noise)就是一個基于密度的聚類算法。該算法將具有足夠高密度的區(qū)域劃分為簇 ，并可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。它定義簇為密度相連的點的最大集合。 基于密度的聚類的基本想法涉及一些新的定義。 10 給定對象半徑內(nèi)的區(qū)域稱為該對象的 ε 鄰域 。 如果一個對象的 ε 鄰域 至少包含最小數(shù)目 MinPts 個對象，則稱該對象為核心對象。 給定一個對象集合 D，如果 p 是在 q的 ε 鄰域 內(nèi)，而 q是一個核心對象，我們說對象 p從對象 q出發(fā)是直接密度可達的。 如果存在對象鏈 npppp ,..., 321 ， ppqp n ?? ,1 ,對 )1(, niDpi ??? , 1?ip 是從 ip 關(guān)于 ε 和 MinPts 直接密度可達的，則對象 p 是從對象 q 關(guān)于 ε 和 MinPts 密度可達的(DensityReachable)。 如果對象集合 D 中存在一個對象 O，使得對象 p 和 q 是從 O關(guān)于 ε 和 MinPts 密 度可達的，那么對象 p和 q是關(guān)于 ε 和 MinPts 密度相連的 (DensityConnected）。 密度可達是直接密度可達的傳遞閉包，這種關(guān)系是非對 稱的。只有核心對象之間是相互密度可達的。然而，密度相連性是一個對稱的關(guān)系。 一個基于密度的簇是基于密度可達性的最大的密度相連對象的集合。不包含在任何簇中的對象被認(rèn)為是“噪聲”。 DBSCAN 通過檢查數(shù)據(jù)庫中每個點的ε 鄰域來尋找聚類。如果一個點 p 的ε 鄰域包含多于 MinPts 個點，則創(chuàng)建一個以 p 作為核心對象的新簇。然后， DBSCAN 反復(fù)地尋找從這些核心對象直接密度可達的對象。這個過程可能涉及一些密度可達簇的合并。當(dāng)沒有新的點可以被添加到任何簇時，該過程結(jié)束。 如果采用空間索引 ,DBSCAN的計算復(fù)雜度是 O(nlogn)，這里 n是數(shù)據(jù)庫中對象的數(shù)目。否則，計算復(fù)雜度是 O(n2),另外，該算法對用戶定義的參數(shù)是敏感的。 盡管 DBSCAN 能根據(jù)給定輸入?yún)?shù)ε和 MinPts 對對象進行聚類，但它仍將選擇能產(chǎn)生可接受的聚類結(jié)果的參數(shù)值的責(zé)任留給了用戶。事實上，這也是許多其它聚類算法的共性問題。對于實際中的高維數(shù)據(jù)集合而言，參數(shù)的設(shè)置通常是依靠經(jīng)驗，難以確定。絕大多數(shù)算法對參數(shù)值是非常敏感的：設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類結(jié)果。而且，實際中的高維數(shù)據(jù)集合經(jīng)常分布不均，全局密度參數(shù)不能刻畫其內(nèi)在的聚類結(jié)構(gòu)。 [4]基于 網(wǎng)格的方法 基于網(wǎng)格的聚類方法采用一個多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)。它將空間量化為有限數(shù)目的單元，這些單元形成了網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在網(wǎng)格上進行。這種方法的主要優(yōu)點是處理速度快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，僅依賴于量化空間中每一維上的單元數(shù)目。 基于網(wǎng)格方法的有代表性的例子包括： STING，它利用存儲在網(wǎng)格單元中的統(tǒng)計信息； 11 WaveCIuster，它用一種小波轉(zhuǎn)換方法來聚類對象； CLIQUE，它是在高維數(shù)據(jù)空間中基于網(wǎng)格和密度的聚類方法。 STING(Statistical Information Grid)是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結(jié)構(gòu)：高層的每個單元被劃分為多個低一層的單元。關(guān)于每個網(wǎng)格單元屬性的統(tǒng)計信息（例如平均值、最大值和最小值）被預(yù)先計算和存儲。高層單元的統(tǒng)計參數(shù)可以很容易地從低層單元的計算得到。 當(dāng)這些統(tǒng)計信息用于回答查詢時，統(tǒng)計參數(shù)的使用可以按照自頂向下的基于網(wǎng)格的方法。首先，在層次結(jié)構(gòu)中選定一層作為查詢處理的開始點。通常，該層包含少量的單元。對當(dāng)前層次的每個單元，我們計算置信度區(qū)間（或者估算其概率范圍），用以反映該單元與給定查詢的關(guān)聯(lián)程度。不相關(guān)的單元就不再考慮。低一層的處理就只檢查剩余的相關(guān)單元。這個處理過程反復(fù)進行，直到達到底層。此時，如果查詢要求被滿足，那么返回相關(guān)單元的區(qū)域。否則，檢索和進一步的處理落在相關(guān)單元中的數(shù)據(jù)，直到它們滿足查詢要求。 由于 STING 采用了一個多分辨率的方法來進行 聚類分析， STING 聚類的質(zhì)量取決于網(wǎng)格結(jié)構(gòu)的最低層的粒度。如果粒度比較細(xì)，處理的代價會顯著增加；但是，如果網(wǎng)格結(jié)構(gòu)最低層的粒度太粗，將會降低聚類分析的質(zhì)量。而且， STING 在構(gòu)建一個父親單元時沒有考慮孩子單元和其相鄰單元之間的關(guān)系。因此，結(jié)果所有的聚類邊界或者是水平的，或者是豎直的，沒有對角的邊界。盡管該技術(shù)有快速的處理速度，但可能降低簇的質(zhì)量和精確性。 WaveCluster 也是一種多分辨率的聚類算法，它首先通過在數(shù)據(jù)空間上強加一個多維網(wǎng)格結(jié)構(gòu)來匯總數(shù)據(jù)，然后采用一種小波變換來變換原特征空間，在變換后的 空間中找到密集區(qū)域。 WaveC1uster 是一個基于網(wǎng)格和密度的算法。它符合一個好的聚類算法的許多要求：它能有效地處理大數(shù)據(jù)集合，發(fā)現(xiàn)任意形狀的簇，成功地處理孤立點，對于輸入的順序不敏感，不要求指定諸如結(jié)果簇的數(shù)目或鄰域的半徑等輸入?yún)?shù)。在實驗分析中， WaveCluster在效率和聚類質(zhì)量上優(yōu)于 BIRCH， CLARANS和 DBSCAN。實驗分析也發(fā)現(xiàn) WaveCluster 能夠處理多達 20 維的數(shù)據(jù)。 [5] 基于模型的聚類方法 基于模型的聚類方法試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性。這樣的方法經(jīng)常 是基于這樣的假設(shè)：數(shù)據(jù)是根據(jù)潛在的概率分布生成的?；谀Ｐ偷姆椒ㄖ饕袃深悾航y(tǒng)計學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。下面分別討論之。 12 統(tǒng)計學(xué)方法 概念聚類是機器學(xué)習(xí)中的一種聚類方法，給出一組未標(biāo)記的對象，它產(chǎn)生對象的一個分類模式。與傳統(tǒng)的聚類不同，概念聚類除了確定相似對象的分組外，還向前走了一步，為每組對象發(fā)現(xiàn)了特征描述，即每組對象代表了一個概念或類。因此，概念聚類是一個兩步的過程：首先進行聚類，然后給出特征描述。在這里，聚類質(zhì)量不再只是單個對象的函數(shù)，而且加入了如導(dǎo)出的概念描述的簡單性和一般性等因素。 概念聚類的絕 大多數(shù)方法采用了統(tǒng)計學(xué)的途徑，在決定概念或聚類時使用概率度量。概率描述用于描述導(dǎo)出的概念。 COBWEB 是一種流行的簡單增量概念聚類算法。它的輸入對象用分類屬性 值對來描述。 COBWEB 以一個分類樹的形式創(chuàng)建層次聚類。它采用了一個啟發(fā)式估算度量 — 分類效用來指導(dǎo)樹的構(gòu)建。 COBWEB 的工作過程： COBWEB 將對象增量地加入到分類樹中。給定一個新的對象，COBWEB 沿著一條適當(dāng)?shù)穆窂较蛳?，修改計?shù)，尋找可以分類該對象的最好節(jié)點。這個判定基于將對象臨時置于每個節(jié)點，并計算結(jié)果劃分的分類效用。產(chǎn)生最高分類效用的位置應(yīng)當(dāng)是對象節(jié)點一個好的選擇。 如果對象不屬于樹中現(xiàn)有的任何概念， COBWEB 就計算為給定對象創(chuàng)建一個新的節(jié)點所產(chǎn)生的分類效用。它與基于現(xiàn)存節(jié)點