聚類分析讀書報告.doc
《聚類分析讀書報告.doc》由會員分享，可在線閱讀，更多相關(guān)《聚類分析讀書報告.doc（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。
聚類分析讀書報告 王晨 研數(shù)理1535 1152209008 基本原理 聚類問題實際上是將一組數(shù)據(jù)分成若干個組，每個組里的對象具有很大的相似性，不同的組之間存在盡量大的差異性。在這些組之間尋找數(shù)據(jù)之間內(nèi)在的聯(lián)系。這個過程實際上是一中在無監(jiān)督狀態(tài)下尋找最優(yōu)劃分的過程。聚類有效性的評價可以參考以下幾個指標(biāo)：聚類質(zhì)量的度量、聚類算法與某種數(shù)據(jù)集適合的程度、劃分的最佳聚類數(shù)目。聚類分析的內(nèi)容十分豐富，一般情況下按方法可以分為以下幾種：系統(tǒng)聚類法，調(diào)優(yōu)法(動態(tài)聚類法)，最優(yōu)分割法(有序樣品聚類法)，模糊聚類法，圖論聚類法，聚類預(yù)報法。按照分類對象的不同可以分為R型和Q型兩大類，R型是對變量進(jìn)行分類，Q型是對樣品進(jìn)行分類。 聚類分析就是用數(shù)學(xué)方法研究和處理給定對象的分類。聚類問題是一個久遠(yuǎn)的問題，是隨著人類的產(chǎn)生和社會的發(fā)展而不斷深化的一個問題。人們要認(rèn)知世界、改變世界就要區(qū)分不同的事物并感知存在于不同事物間的相似性。 經(jīng)典分類學(xué)是從單對象或有限的幾個對象出發(fā)，單憑經(jīng)驗或?qū)I(yè)知識對事物進(jìn)行分類。這種分類具有的優(yōu)點是界限非常清晰。但是，隨著人們認(rèn)識的加深，發(fā)現(xiàn)這種分類常常不適用于具有模糊性的分類問題。如把人按漂亮分為“漂亮的人，“不漂亮的人”。這就產(chǎn)生了經(jīng)典分類方法解決不了的問題一如何判定某個人的類別。由此產(chǎn)生了模糊聚類分析，應(yīng)用模糊聚類得到了對象屬于不同類別的不確定性程度，表達(dá)了樣本類屬的中介性，更能客觀地反映現(xiàn)實世界。我們把應(yīng)用普通數(shù)學(xué)方法進(jìn)行分類的聚類方法稱為普通聚類分析，而把應(yīng)用模糊數(shù)學(xué)方法進(jìn)行分析的聚類分析稱為模糊聚類分析。 1.1三種類的定義： 【定義一】設(shè)閾值是給定的正數(shù)，若集合中任何兩個元素的距離都滿足： ，則稱對于閾值組成一個類。 【定義二】設(shè)閾值是給定的正數(shù)，若集合中每個都滿足： ， 其中，是集合中元素的個數(shù)，則稱對于閾值組成一個類。 【定義三】設(shè)和是兩個給定的正數(shù)，如果集合中兩兩元素距離的平均滿足： ，， 其中是集合中元素的個數(shù)，則稱對于閾值，組成一個類。 1.2類的性質(zhì)特征： 設(shè)類包含的樣品為，其中為元總體的樣本，可以從不同角度來刻畫： （1）的重心（或稱均值）： （2）樣本離差陣及樣本協(xié)方差陣分別為： （3）類的直徑：用表示類的直徑，通常用以下來表示直徑 ， 距離與相似系數(shù)對樣品進(jìn)行分類，就需要研究它們之間的關(guān)系，現(xiàn)在用的較多的是距離和相似系數(shù)。 1.3距離 把個樣品看成是維空間中的個點，那么兩個樣品間的相似系數(shù)用度量。一般要求： ，對任意；當(dāng)； ，對任意； ，對任意。 1.3.1明氏（Minkowski）距離 ， 當(dāng)時的一階明氏距離為 即絕對距離 當(dāng)時，，即歐氏距離 當(dāng)趨于時， ，即為切比雪夫距離。 1.3.2馬氏（Mahalanobis)距離 馬氏距離是1936年印度的馬哈拉諾比斯提出的，具有很重要的作用。 為指標(biāo)的協(xié)方差陣，，其中， ， ， 當(dāng)存在時，則為馬氏距離。 樣品到總體的馬氏距離定義為，其中為總體的均值向量。 1.3.3蘭氏(Canberra)距離 蘭氏距離是由蘭思和威廉姆斯所給定的一種距離。其計算公式為：， 1.3.4杰氏距離 杰氏距離是由杰斐瑞和馬突斯塔提出的。計算公式為： 1.3.5斜交空間距離 由于變量之間往往存在著不同的相關(guān)關(guān)系，正交空間的距離計算樣本空間易變性，可以采用斜交空間距離。 1.4相似系數(shù) 為了將樣品進(jìn)行分類，研究樣品之間的關(guān)系，采用相似系數(shù)的方法；性質(zhì)接近的樣品，相似系數(shù)就越接近1或者-1，而無關(guān)系的樣品的相關(guān)系數(shù)就越接近0.比較相似的樣品歸為一類，不相似的樣品歸屬不同的類。 設(shè) （為常數(shù)）； ，對任意均成立； ，對任意均成立。 這里的絕對值越接近1，表示和越相似。反之，兩者關(guān)系疏遠(yuǎn)。 常用的相似系數(shù)有： 夾角余弦 當(dāng)和平行式，夾角，，說明這兩個向量完全相似；當(dāng)和正交時，夾角，，說明這兩個向量不相關(guān)。 相關(guān)系數(shù) 表示兩個向量線性相關(guān)。 指數(shù)相似系數(shù) 非參數(shù)方法 令 相似系數(shù)定義為 當(dāng)非負(fù)時，有三種相似系數(shù)： 聯(lián)列系數(shù) 1.5聚類分析的性質(zhì) 1.5.1單調(diào)性 設(shè)為系統(tǒng)聚類中第次并類時的距離。如果，則稱它具有單調(diào)性。在聚類方法當(dāng)中，可以證明的是只有重心法和中間距離法不具有單調(diào)性。 圖2為一個等角三角形，兩個腰長為1.1，底邊是1，則第一次A，B并為一類，并類的距離幾=l，第二次并類的距離是C至AB中點的距離，它是AB邊的高，它等于。所以重心法不能夠滿足單調(diào)性。 1.5.2空間的濃縮與擴(kuò)張 設(shè)兩個同階矩陣和。如果的每一個元素不小于相應(yīng)元素，則記為。特別的如果矩陣的元素非負(fù)，則有. 如果，，表示將的每一個元素平方，則。令，則 若有兩個系統(tǒng)聚類法，在第步距離陣記為和，若則稱比使空間擴(kuò)張或比使空間濃縮。這種性質(zhì)稱為最長距離法比最短距離法擴(kuò)張；或最短距離法比最長距離法濃縮。 基本方法 聚類方法主要有劃分聚類法、層次聚類法和密度聚類法、基于網(wǎng)格的方法和基于模型的方法等。 2.1層次聚類CURE算法 層次聚類方法是一種目前應(yīng)用較廣的聚類技術(shù)，是一種針對大型數(shù)據(jù)庫的高效的聚類算法，可為用戶提供多種可選的聚類結(jié)果，可以隨時完成聚類實施過程。CURE，ROCK和CHAMELEON算法是聚合聚類中最具代表性的三個方法。 Guha等人在1998年提出了CURE算法。該方法選擇數(shù)據(jù)空間中固定數(shù)目的、具有代表性的一些點共同來表示相應(yīng)的類，這樣就可以識別具有復(fù)雜形狀和不同大小的聚類，找到更合適的孤立點。ROCK算法是對CURE的改進(jìn)，適用于類別屬性的數(shù)據(jù)。 CHAMELEON算法是KaryPis等人于1999年提出來的，它在聚合聚類的過程中利用了動態(tài)建模的技術(shù)。例如在“自底向上”方案中，初始時每一個數(shù)據(jù)紀(jì)錄都組成一個單獨(dú)的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。它是一種分裂的層次聚類。CURE采用了用多個點代表一個簇的方法，可以較好的處理以上問題。并且在處理大數(shù)據(jù)量的時候采用了隨機(jī)取樣，分區(qū)的方法，來提高其效率，使得其可以高效的處理大量數(shù)據(jù)。算法分為以下六步： (1)從原始數(shù)據(jù)中抽取一個隨機(jī)樣本S。 (2)將樣本S分割為一組劃分。 (3)對每個劃分局部的聚類。 (4)通過隨機(jī)取樣剔除孤立點。如果一個類增長太慢，就去掉它。 (5)對局部的類進(jìn)行聚類。落在每個新形成的類中的代表點根據(jù)用戶定義的一個收縮因子收縮或向類中心移動。這些點代表和捕捉到了類的形狀。 (6)用相應(yīng)的類標(biāo)簽來標(biāo)記數(shù)據(jù)。 CURE算法的思想主要體現(xiàn)在如下幾個方面： (1)CURE算法采用的是聚結(jié)層次聚類。把每一個對象設(shè)立為一個類，隨即根據(jù)相似點對它們進(jìn)行合并。 (2)CURE算法采用分割方法，先把樣本分割為幾塊然后針對各個部分中的對象分別進(jìn)行局部聚類，形成子類。再對子類進(jìn)行聚類，形成新的類。 2.2 BIRCH方法 BIRCH(Balanced Iterative Reducing and clustering using Hierarchies)是專門針對大規(guī)模數(shù)據(jù)集提出的聚集型層次聚類算法，它綜合了層次凝聚和迭代的重定位方法。首先用自底向上的層次算法，然后用迭代的重定位來改進(jìn)結(jié)果。它的主要思想是：掃描數(shù)據(jù)庫，建立一個初始存放于內(nèi)存中的聚類特征樹，然后對聚類特征樹的葉結(jié)點進(jìn)行聚類。 聚類特征的定義(CF)：一個聚類特征(CF)是一個三元組(N，LS，SS)，其中N是簇中的點的數(shù)目，LS是N個點的線性和，SS是N個點的平方和。 聚類特征樹的定義(CF樹)：一顆CF樹是一個帶有分支因子B的平衡樹，每一個內(nèi)部結(jié)點對于每一個子結(jié)點都包含一個CF三元組。每個葉結(jié)點也代表一個簇，并且對于其中每一個子簇都包含一個CF條目。在葉結(jié)點中的子簇要有一個不超過給定閾值T的直徑。 合并假定：假定個簇進(jìn)行合并，個簇的聚類特征表示為，其中，那么合并后簇為，其聚類特征為 其中，，合并后簇的聚類特征精確地表示了兩個聚類合并后的漸增性。 在層次聚類方法中，要按照一定的相似性判斷標(biāo)準(zhǔn)合并最相似的部分，或者分割最不相似的兩個部分，判斷各個類之間的相似程度的準(zhǔn)則是：假設(shè)和是聚結(jié)過程中同一層次上的兩個類，和分別是和兩個類中的對象數(shù)目，為中的任意一個對象，為中的任意一個對象，為中對象的平均值，為中對象的平均值，下面的四種距離計算被廣泛地應(yīng)用于計算兩個類之間的差異度： 平均值距離：， 平均距離：， 最大距離： 最小距離： BIRCH聚類算法利用特征樹結(jié)構(gòu)對數(shù)據(jù)集進(jìn)行聚類，算法主要過程為：首先，將所有初始數(shù)據(jù)掃描，建立一個原始化聚集CF樹，盡最大可能使得特征樹包含所有信息；然后，用聚集特征代替原有數(shù)據(jù)集進(jìn)行聚類。在第一階段，CF樹是隨著原始數(shù)據(jù)的加入而自動形成的；一個對象被放入那個離它最近的葉子結(jié)點中去。如果放入以后這個簇的半徑大于閾值T的話，那么這個葉結(jié)點就會被分割。插入過程類似于B+樹構(gòu)建中的插入和結(jié)點分裂。 2.3 劃分法(Partitioning methods ) 劃分法(Partitioning methods)通常是指給定數(shù)據(jù)庫，其中有N個元素，采用分裂法將其構(gòu)造為K個組，每一個分組就代表一個聚類，K下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 聚類分析 讀書 報告
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://m.appdesigncorp.com/p-6523702.html