聚類分析讀書報告王晨研數理15351152209008基本原理聚類問題實際上是將一組數據分成若干個組，每個組里的對象具有很大的相似性，不同的組之間存在盡量大的差異性。在這些組之間尋找數據之間內在的聯系。這個過程實際上是一中在無監督狀態下尋找最優劃分的過程。聚類有效性的評價可以參考以下幾個指標：聚類質量的度量、聚類算法與某種數據集適合的程度、劃分的最佳聚類數目。聚類分析的內容十分豐富，一般情況下按方法可以分為以下幾種:系統聚類法，調優法(動態聚類法)，最優分割法(有序樣品聚類法)，模糊聚類法，圖論聚類法，聚類預報法。按照分類對象的不同可以分為R型和Q型兩大類，R型是對變量進行分類，Q型是對樣品進行分類。聚類分析就是用數學方法研究和處理給定對象的分類。聚類問題是一個久遠的問題，是隨著人類的產生和社會的發展而不斷深化的一個問題。人們要認知世界、改變世界就要區分不同的事物并感知存在于不同事物間的相似性。經典分類學是從單對象或有限的幾個對象出發，單憑經驗或專業知識對事物進行分類。這種分類具有的優點是界限非常清晰。但是，隨著人們認識的加深，發現這種分類常常不適用于具有模糊性的分類問題。如把人按漂亮分為“漂亮的人，“不漂亮的人”。這就產生了經典分類方法解決不了的問題一如何判定某個人的類別。由此產生了模糊聚類分析，應用模糊聚類得到了對象屬于不同類別的不確定性程度，表達了樣本類屬的中介性，更能客觀地反映現實世界。我們把應用普通數學方法進行分類的聚類方法稱為普通聚類分析，而把應用模糊數學方法進行分析的聚類分析稱為模糊聚類分析。1.1三種類的定義：【定義一】設閾值T是給定的正數，若集合G中任何兩個元素的距離%都滿足：氣<T(i,jeG)，則稱G對于閾值T組成一個類。【定義二】設閾值T是給定的正數，若集合G中每個ieG都滿足：上&<Tlim，"-1jeG"x*其中，n是集合G中元素的個數，則稱G對于閾值T組成一個類。【定義三】設T和H(HT)是兩個給定的正數，如果集合G中兩兩元素距離的平均滿足：一1一EEd<T，d..<H(i,jeG)，n(n—1)可ijieGjeG其中n是集合G中元素的個數，則稱G對于閾值T，H組成一個類。1.2類的性質特征：設類G包含的樣品為X⑴,X(2),...,X(.)，其中X(/=1,2,...,n)為m元總體的樣本，可以從不同角度來刻畫G.g的重心(或稱均值)：xg=nXx(t)t=1樣本離差陣氣及樣本協方差陣SG分別為：4=￡(X(t)-~XGy,SG=土氣t=1類的直徑：用dg表示類G的直徑，通常用以下來表示直徑D=X(X-X^)(X-XC)=tr(A)G(t)G(t)GGt-1D=maxd，Gi,jeGi,j距離與相似系數對樣品進行分類，就需要研究它們之間的關系，現在用的較多的是距離和相似系數。1.3距離把n個樣品看成是m維空間中的n個點，那么兩個樣品間的相似系數用di,j度量。一般要求:對任意i,j;當d=00X(.)=X(.)；d=d，對任意i,j；d<dk+d，對任意i,j,k。明氏(Minkowski)距離1/qd(q)=Xx-xq(i,j=1,2,...,n)，ij.itjt當q=1時的一階明氏距離為d⑴=|x.-x.(i,j=1,2,...,n)即絕對距離t=1當q=2時，d(2)=Xx-x2"%,j=1,2,...,n)，即歐氏距離司L=1"打」當趨于s時，d(8)=maxx.-x.(i,j=1,2,...,n)，即為切比雪夫距離。馬氏(Mahalanobis)距離馬氏距離是1936年印度的馬哈拉諾比斯提出的，具有很重要的作用。X為指標的協方差陣，X=(七)肋，其中，

1項，一、，&=1項，一、，&=乙(x-x.)(x?n—1ai1,a=1aj-xj),(i,j=1,2,...,p)x-1?x-云、a=1x=1命jnaja=1當￡-1存在時，則dj(M)=(X.—X.)'￡-1(X.—X.)為馬氏距離。樣品X到總體G的馬氏距離定義為d2(X,G)=(X-日)'￡-1(X-日)，其中|1為總體的均值向量。蘭氏(Canberra)距離蘭氏距離是由蘭思和威廉姆斯所給定的一種距離。其計算公式為：d(L)=—Y--，i,j=1,2,...,nijm.](x+x.)1.3.4杰氏距離杰氏距離是由杰斐瑞和馬突斯塔提出的。計算公式為:1.3.5斜交空間距離由于變量之間往往存在著不同的相關關系，正交空間的距離計算樣本空間易變性，可以采用斜交空間距離。r1一1ld=一空(x—x)(x—x)rijp2ihjhikjkhkLn=1k=1-1.4相似系數為了將樣品進行分類，研究樣品之間的關系，采用相似系數的方法；性質接近的樣品，相似系數就越接近1或者-1，而無關系的樣品的相關系數就越接近0.比較相似的樣品歸為一類，不相似的樣品歸屬不同的類。設C=±10X=aX(a。0為常數);C^<1，對任意i,j均成立；C=C，對任意i,j均成立。這里C的絕對值越接近1，表示X,和x.越相似。反之，兩者關系疏遠。常用的相似系數有:夾角余弦C(1)=cosaijijkikj［乙2ki、k=11「▽\￡X2L*)k=1當X和X平行式，夾角a.=00，C⑴=1，說明這兩個向量完全相似；當X和X正交時，相關系數夾角a=900，ijC⑴=0，說明這兩個向量不相關。Cj(2)=E/一、/一、(x,.-X,)(x^-X,)-k=1￡(Xf)2

ki-k=1￡(X/X)2kjjLk=1C(2)=1表示兩個向量線性相關。指數相似系數C(3)=1欄amk=13(&_偵)24S2

k非參數方法=X.-Xjn=X'X',k=1,...,m中大于0的個數+ikjkn=X'X',k=1,…,m中小于0的個數--ikjk相似系數定義為c(4)=氣—n司n—n當j非負時，有三種相似系數:￡min(x,X)c..⑸=^m~￡ma乂x,x)k=1￡min(x,x)C(6)=k=12￡(、+x/k=1工min(x,x)%(7)=汶狄已k=1聯列系數I1x2c(8)=.\；——j\x2+n1.5聚類分析的性質1.5.1單調性設氣為系統聚類中第k次并類時的距離。如果D1<D2<D3<…，則稱它具有單調性。在聚類方法當中，可以證明的是只有重心法和中間距離法不具有單調性。圖2為一個等角三角形，兩個腰長為1.1，底邊是1，則第一次A，B并為一類，并類的距離幾二1，第二次并類的距離是C至AB中點的距離，它是AB邊的高，它等于J1.12-0.52=0.98=D2Y只。所以重心法不能夠滿足單調性。1.5.2空間的濃縮與擴張設兩個同階矩陣D(A)和D(B)。如果D(A)的每一個元素不小于D(B)相應元素，則記為D(A)>D(B)。特別的如果矩陣D的元素非負，則有D>0.如果D(A)>0，D(B)>0，D2(A)表示將D(A)的每一個元素平方，則D(A)>D(B)=D2(A)>D2(B)。令D(A,B)=D2(A)-D2(B)，則D(A,B)>00D(A)>D(B)若有兩個系統聚類法A,B，在第k步距離陣記為D(A「和D(B)(k=0,1,2,...,n-1)，若D(A.,B)>0則稱A比B使空間擴張或B比A使空間濃縮。這種性質稱為最長距離法比最短距離法擴張；或最短距離法比最長距離法濃縮。基本方法聚類方法主要有劃分聚類法、層次聚類法和密度聚類法、基于網格的方法和基于模型的方法等。2.1層次聚類CURE算法層次聚類方法是一種目前應用較廣的聚類技術，是一種針對大型數據庫的高效的聚類算法，可為用戶提供多種可選的聚類結果，可以隨時完成聚類實施過程。CURE，ROCK和CHAMELEON算法是聚合聚類中最具代表性的三個方法。Guha等人在1998年提出了CURE算法。該方法選擇數據空間中固定數目的、具有代表性的一些點共同來表示相應的類，這樣就可以識別具有復雜形狀和不同大小的聚類，找到更合適的孤立點。ROCK算法是對CURE的改進，適用于類別屬性的數據。CHAMELEON算法是KaryPis等人于1999年提出來的，它在聚合聚類的過程中利用了動態建模的技術。例如在“自底向上”方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。它是一種分裂的層次聚類。CURE采用了用多個點代表一個簇的方法，可以較好的處理以上問題。并且在處理大數據量的時候采用了隨機取樣，分區的方法，來提高其效率，使得其可以高效的處理大量數據。算法分為以下六步：從原始數據中抽取一個隨機樣本S。將樣本S分割為一組劃分。對每個劃分局部的聚類。通過隨機取樣剔除孤立點。如果一個類增長太慢，就去掉它。對局部的類進行聚類。落在每個新形成的類中的代表點根據用戶定義的一個收縮因子收縮或向類中心移動。這些點代表和捕捉到了類的形狀。用相應的類標簽來標記數據。CURE算法的思想主要體現在如下幾個方面：CURE算法采用的是聚結層次聚類。把每一個對象設立為一個類，隨即根據相似點對它們進行合并。CURE算法采用分割方法，先把樣本分割為幾塊然后針對各個部分中的對象分別進行局部聚類，形成子類。再對子類進行聚類，形成新的類。2.2BIRCH方法BIRCH(BalancedIterativeReducingandclusteringusingHierarchies)是專門針對大規模數據集提出的聚集型層次聚類算法，它綜合了層次凝聚和迭代的重定位方法。首先用自底向上的層次算法，然后用迭代的重定位來改進結果。它的主要思想是：掃描數據庫，建立一個初始存放于內存中的聚類特征樹，然后對聚類特征樹的葉結點進行聚類。聚類特征的定義(CF)：一個聚類特征(CF)是一個三元組(N，LS，SS)，其中N是簇中的點的數目，LS是N個點的線性和，SS是N個點的平方和。聚類特征樹的定義(CF樹)：一顆CF樹是一個帶有分支因子B的平衡樹，每一個內部結點對于每一個子結點都包含一個CF三元組。每個葉結點也代表一個簇，并且對于其中每一個子簇都包含一個CF條目。在葉結點中的子簇要有一個不超過給定閾值T的直徑。合并假定：假定n(心2)個簇七進行合并，n個簇的聚類特征表示為CF=(N,LS,SS,T)，其中i=1,2,,n，那么合并后簇為W，其聚類特征為iiiiiCF=(N,LS,SS,T)

N=￡nii=1LS=2lSIi=1SS=ESSii=1T=max(dist(w.mean,c.mean)+T)Elsw.mean-，=1i=1Elsw.mean-，=1i=1LS其中c.mean=~^~i寸，合并后簇的聚類特征精確地表工Ni示了兩個聚類合并后的漸增性。在層次聚類方法中，要按照一定的相似性判斷標準合并最相似的部分，或者分割最不相似的兩個部分，判斷各個類之間的相似程度的準則是：假設C和七是聚結過程中同一層次上的兩個類，n和七分別是c和C,兩個類中的對象數目，p(i)為C中的任意一個對象，p(J)為C.中的任意一個對象，f為C中對象的平均值，f為c中對象的平均值，下面的四種距離計算被廣泛地應用于計算兩個類之間的差異度：平均值距離：d(c,c)=d(f,f)，meanijij、.1p(「)￡cP(j)8c.平均距離：d(c,c)=Ed(p,p)，avenageijnnijp()8c.-p(j)8c.最大距離：d(c,c)=niaxjd(p(i),p(j))p(i)8c.-p(j)8c.最小距離：d.(c,c)=riimjd(p(i),p(j))BIRCH聚類算法利用特征樹結構對數據集進行聚類，算法主要過程為：首先，將所有初始數據掃描，建立一個原始化聚集CF樹，盡最大可能使得特征樹包含所有信息；然后，用聚集特征代替原有數據集進行聚類。在第一階段，CF樹是隨著原始數據的加入而自動形成的；一個對象被放入那個離它最近的葉子結點中去。如果放入以后這個簇的半徑大于閾值T的話，那么這個葉結點就會被分割。插入過程類似于B+樹構建中的插入和結點分裂。劃分法(Partitioningmethods)劃分法(Partitioningmethods)通常是指給定數據庫，其中有N個元素，采用分裂法將其構造為K個組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：(1)每一個分組至少包含一個數據紀錄；(2)每一個數據紀錄屬于且僅屬于一個分組；對于給定的K,算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好。我們通常使用的K一MEANS算法、K一MEDO工DS算法、CLARANS算法基本上都采用這中思想。K一MEANS算法首先是輸入量為K；然后將N個數據對象劃分為K個聚類使得到的聚類滿足：（1）同一聚類中的數據相似度較高，（2）而不同聚類中的數據相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”來進行計算的。CLARA算法的思想就是用實際數據的抽樣來代替整個數據，然后再在這些抽樣的數據上利用K一medoids算法得到最佳的medoids。CLRAR算法從實際數據中抽取多個采樣，在每個采樣上都用K一medoids算法得到相應的（01,02,...,0Z,???0k），然后在這當中選取E最小的一個作為最終的結果。K_means算法K_means算法是劃分聚類中較流行的一種算法，它是一種迭代的聚類算法，迭代過程中不斷移動簇集中的對象，直至得到理想的簇集為止，每個簇用該簇中對象的平均值來表示。利用k_means算法得到的簇，簇中對象的相似度很高，不同簇中對象之間的相異度也很高。算法的主要步驟為：從n個數據對象隨機選取k個對象作為初始簇中心；計算每個簇的平均值，并用該平均值代表相應的簇；根據每個對象與各個簇中心的距離，分配給最近的簇；轉第二步，重新計算每個簇的平均值。這個過程不斷重復直到滿足某個準則函數不再明顯變化或者聚類的對象不再變化才停止。一般，K_means算法的準則函數采用平方誤差準則，定義為：E=￡：￡\p-m『其中，E是數據集中所有對象與相應類聚中心的均方差之和，p為給定的數據對象，m,為七聚類的均值（p和m均是多維的）。2.5基于密度的DBSCAN算法DBSCAN算法屬于基于密度的方法當中的一個。密度聚類法是指只要一個區域中的點的密度大于某個值，就把它添加到與之相鄰的類中。DBS以N算法是密度聚類法中一個具有代表的算法，它將簇定義為密度相連的點的最大集合，只要臨近區域的密度（對象或數據點的數目）超來控制簇的增長。基本定義：點的8鄰域，以選定點為中心，以8為半徑的區域：核心點：如果一個點的8領域包含最小數目個點，則稱該點為核心點。直接密度可達：如果點p在點q的8領域內，而q是一個核心點，則稱該點p是從點q直接密度可達。間接密度可達：給定一個點集M，如果存在一個點鏈p1,p2,...,pn,pl=1,pn=n，對pieM，1<i<n，p+1是從pi關于8和f,f直接密度可達的，則點p是從點q關于8和minps間接密度可達。密度相連：如果點集M中存在一個點o,使得點p和q,是從o關于￡和minps間接密度可達，則稱點p和q是關于e和minps密度相連。噪聲：不屬于密度可達或密度相連集合的點（即孤立點），稱為噪聲。CLARANS算法CLARANS算法是一種分割聚類方法。它首先隨機選擇一個點作為當前點，然后隨機檢查它周圍不超過參數Maxneighbor個的一些鄰接點，若能找到一個更適合的點，把它移入該臨近點。然后再隨機選擇一個點來尋找另一個局部最小量，直至所找到的局部最小量數目達到用戶要求為止。該算法要求聚類的對象必須都預先調人內存，并且需多次掃描數據集，這對大數據量而言，無論時間復雜度還是空間復雜度都相當大。CLIQUE算法CLIQUE算法為自動子空間聚類算法。該算法利用自頂向上方法求出各個子空間的聚類單元。CLIQUE算法主要用于找出在高維數據空間中存在的低維聚類。為了求出d維空間聚類，必須組合給出所有d-1維子空間的聚類，導致其算法的空間和時間效率都較低，而且要求用戶輸入兩個參數：數據取值空間等間隔距離和密度閾值。這兩個參數與樣木數據緊密相關，用戶一般難以確定。優缺點及解決方法優點缺點層次法識別形狀復雜、大小不一的聚類，過濾孤立點。一旦一組對象合并，下一步將在新生成的類上進行；因為合并或分裂的決定需要檢查和估算大量的對象或類。劃分法計算時間段，速度快；容易解釋；聚類效果好。結果好壞依賴對初始聚類中心的選擇；容易陷入局部最優解；對K值的選擇沒有準則可依循；對異常數據較為敏感；只能處理數值屬性的數據；聚類結構可能不平衡。基于密度的方法有較強的抗“噪聲”的能力若原始數據庫中有較大的聚類，則難解決存儲核心對象信息的問題；輸入參數敏感；當數據分布不均勻時聚類質量較差。對于層次法的改進：聚集特征樹的大小可以通過調節參數來改變，如果要存儲樹需要的內存大于主存，可以定義一個較小的閉值，然后通過提升閉值重新建立一個聚類CF樹，這個重建過程并不需要將整個記錄掃描一次，而是建立在原有樹的葉子結點的基礎之上的，因此，建立一個樹數據記錄只需要被掃描一次。當樹建好以后，可以在第二階段用其他的聚類算法對聚類特征進行聚類。對于劃分法的改進：l）并行化。針對數據分布不均，可以對數據進行劃分，參照每個劃分中的數據的分布密度選取EPs值，這樣可以降低全局變量EPs值的影響。也降低了DBSCAN算法對內存的較高要求。2）增量式處理。當要考察的較大的數據有變化的時候，我們只需考慮其增加或刪除的數據所影響到的那些類.就不必重新對數據庫中的所有數據進行聚類。只需要對類進行漸進性地更新，修正和加強己發現的類。3）由于高維數據的復雜性，使聚類分析的效率和實用性都很差。通過確定聚類空間中和聚類主題相關性較強的數據維，來降低聚類空間的維度。利用數據降維可以降低數據結構上的復雜性。聚類分析的應用聚類分析是一個極富挑戰性的研究領域，是近年來迅速發展起來的一種新興的數據處理技術，它在氣象分析、圖像處理、模糊控制、計算機視覺、天氣預報、模式識別、生物醫學、化學、食品檢驗、生物種群劃分、市場細分、業績評估等諸多領域有著廣泛的應用，并在這些領域中取得了長足的發展。4.1聚類分析在文本中的應用文本聚類是將文本集中相似的文本分為一組的全自動處理過程，根據對象的某種聯系或相關性，對文檔進行有效的摘要、組織，以便從文本集中發現內在相關的信息。同類的文本相似程度較大。文本聚類方法通常先通過向量空間模型把文檔轉換成高維空間中的向量，然后對這些向量進行聚類。中文文檔轉換成向量，需要先有分詞軟件對中文文本分詞后轉換成向量，再通過特征抽取形成樣本矩陣，最后進行聚類，文本聚類的輸出一般為文檔集合的一個劃分。由于聚類不需要訓練，也不需要預先對文檔手工標注類別，具有一定的靈活性和自動化處理能力，目前已經成為對文本信息進行處理的的重要手段。4.2聚類分析在市場營銷客戶細分中的應用市場營銷業利用數據挖掘技術進行市場定位和消費分析，輔助制定營銷方案。通過對客戶數據庫不同消費者消費同一類商品或服務的眾多不同數據進行聚類分析，爭取潛在的客戶，制定有利于市場運行的策略。目前企業都己經意識到“客戶就是上帝”，在這種經營理念的指引下，對現有客戶和潛在客戶的培養和挖掘正成為企業成功的關鍵。例如，客戶的需求傾向一般有內因和外因共同局決定的，內因一般包括對某種產品的需要，認知，而影響外因的元素相對較多，比如文化，社會，小群體，參考群體等等。把這些因素作為分析變量，把所有潛在客戶的每一個分析變量的指標值量化出來，用聚類分析法進行分類。除此之外，戶滿意度和重復購買的機率都可以作為屬性進行分類。根據這些分析得到的歸類，可以為企業制定市場運營決策提供參考和保障。4.3聚類分析在金融領域中的應用隨著世界經濟的快速發展，金融業面臨的考驗與日俱增。在分析市場和預測發展、各類客戶的歸類、銀行及各類擔保公司的擔保和信用評估等工作上需要收集和處理大量的數據，這些數據不可能通過人工或