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