版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
第九章聚類算法
無監(jiān)督學習(UnsupervisedLearning)是指在樣本標記信息未知的情況下,通過對樣本的學習來找到數(shù)據(jù)本身的內(nèi)在性質(zhì)和規(guī)律。無監(jiān)督學習可以用于數(shù)據(jù)分析或者監(jiān)督學習的前處理,主要包含聚類(Clustering)、降維(DimensionalityReduction)、概率估計(ProbabilityEstimation)等。
其中聚類應(yīng)用最為廣泛,其基本思想是將樣本中“相似”的樣本聚為相同的類或簇,“不相似”的樣本聚為不同的類。19.1聚類概述相似或者不相似的定義和標準不是固定的,而是根據(jù)數(shù)據(jù)本身的性質(zhì)決定。依據(jù)形狀聚類依據(jù)顏色聚類
依據(jù)不同的策略,可以設(shè)計不同的聚類算法,主要包括原型聚類、層次聚類以及密度聚類。29.1.1相似度1.樣本相似度
常用的有距離(Distance)(閔可夫斯基距離(MinkowskiDistance)、馬哈拉諾比斯距離(MahalanobisDistance))、相關(guān)系數(shù)(CorrelationCoefficient)、夾角余弦等。
聚類的核心概念是相似度,其度量方式有很多種,并直接影響聚類結(jié)果的好壞,具體哪一種更好取決于問題本身的特性。39.1.1相似度(1)閔可夫斯基距離(MinkowskiDistance)
49.1.1相似度
(2)馬哈拉諾比斯距離(MahalanobisDistance)59.1.1相似度
(3)相關(guān)系數(shù)(相關(guān)系數(shù)絕對值越接近1表示樣本越相似;越接近0表示樣本越不相似)
(4)夾角余弦(夾角余弦的數(shù)值越接近1表示樣本越相似;越接近0表示樣本越不相似)69.1.1相似度(5)VDM(ValueDifferenceMetric)距離
79.1.1相似度(6)加權(quán)距離(WeightedDistance)
89.1.1相似度2.類(或簇)的相似度或距離
99.1.2
性能度量
聚類算法的性能度量是一種“有效性指標(ValidityIndex)”,評估類內(nèi)樣本的相似度,不同類別之間的相似度,用以評價聚類結(jié)果以及聚類算法的好壞。
109.1.2
性能度量
顯然,DBI指數(shù)越小越好,DI指數(shù)越大越好119.2
原型聚類
129.2
原型聚類
算法流程:139.2
原型聚類
149.3
密度聚類
假設(shè)聚類結(jié)構(gòu)可以通過樣本分布的緊密程度確定,以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進行聚類。
此類算法無需預先設(shè)定類別數(shù)量,因此適合于未知內(nèi)容的數(shù)據(jù)集,代表算法有DBSCAN、OPTICS、DENCLUE等(本節(jié)只討論DBSCAN)主要思想:
逐步檢查數(shù)據(jù)集中的每個樣本,如果其鄰域內(nèi)的樣本點總數(shù)小于某個閾值,那么定義該點為低密度點;反之,如果大于該閾值,則稱其為高密度點。如果一個高密度點在另外一個高密度點的鄰域內(nèi),就直接把這兩個高密度點劃分為一個類別;如果一個低密度點在一個高密度點的鄰域內(nèi),則將該低密度點加入距離它最近的高密度點的類別中;不在任何高密度點鄰域內(nèi)的低密度點,被劃入異常點類別,直到最終處理整個數(shù)據(jù)集?;靖拍睿?59.3
密度聚類DBSCAN算法
其核心是找到樣本點的全部密集區(qū)域,并把這些密集區(qū)域當作不同的類別。如下圖所示:
利用“鄰域”(Neighborhood)的半徑和最少點數(shù)(Minpoints,簡記為Minpts)兩個參數(shù)刻畫樣本分布的緊密程度。169.3
密度聚類將樣本點分為以下三類:
179.3
密度聚類非密度相連(Non-densityConnected):如果兩個點不屬于密度相連關(guān)系,則兩個點非密度相連。進一步定義四種樣本點的關(guān)系:
189.3
密度聚類
任意選擇一個沒有類別的核心對象作為種子,然后找到所有這個核心對象能夠密度可達的樣本集合,即為一個類別。接著繼續(xù)選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合,這樣就得到另一個聚類簇,這樣的得到都肯定是密度相連的,一直運行到所有核心對象都有類別為止。DBSCAN方法199.3
密度聚類
20
例:如下圖所示:
9.3
密度聚類
219.3
密度聚類
229.3
密度聚類
239.3
密度聚類
249.3
密度聚類
259.3
密度聚類(2)可以在聚類的同時發(fā)現(xiàn)異常點,對數(shù)據(jù)集中的異常點不敏感。主要優(yōu)點:主要缺點:(1)如果樣本集的密度不均勻、聚類間距差相差很大時,聚類質(zhì)量較差,這時DBSCAN聚類一般不適合。
269.4
層次聚類(假設(shè)類別之間存在層次結(jié)構(gòu),將樣本聚到層次化的類別中)聚合(Agglomerative)/自下而上(Bottom-up)聚類——本節(jié)重點分裂(Divisive)/自上而下(Top-down)聚類
每個樣本各分到一個類,之后將距離相近的兩類合并,建立一個新的類別,重復此操作直到滿足停止條件,得到層次化的類別。
將所有的樣本分到一個類,之后將已有類中相距最遠的樣本分到兩個新的類,重復此操作直到滿足停止條件,得到層次化的類別。279.4
層次聚類Agglomerative聚類算法基本流程:
距離尺度:最短距離、最長距離、平均距離、Ward方差等對應(yīng)算法:“單鏈接(Single-linkage)”、“全鏈接(Complete-linkage)”、“單鏈接(Average-linkage)”
、“Ward鏈接(Ward-linkage)”等289.4
層次聚類例:單鏈接Agglomerative聚類算法步驟:
299.4
層次聚類
309.4
層次聚類圖解示例:Agglomerative聚類算法可在不同層次上對數(shù)據(jù)集進行劃分,形成一個樹狀的聚類結(jié)構(gòu),可以指定類別數(shù)也可不指定。但Agglomerative聚類算法的時間和空間復雜度較高,不適合解決大型數(shù)據(jù)集聚類問題。319.5
本章小結(jié)
DBSCAN算法,不需要指定類別的數(shù)量,聚類的形狀可以是任意的,能找出數(shù)據(jù)中的噪音,對噪音不敏感,算法應(yīng)用參數(shù)少。但對于密度不均勻的樣本集、聚類間距差相差很大的樣本集,聚類質(zhì)量較差,一般不適合。Agglomerative聚類算法可在不同層次上對數(shù)據(jù)集進行劃分,形成一個樹狀的聚類結(jié)構(gòu),可以指定類別數(shù)也可不指定。但Agglomerative聚類算法的時間和空間復雜度較高,不適合解決大型數(shù)據(jù)集聚類問題。其次,對于三種算法,通過不同案例,分別介紹了手工實現(xiàn)和調(diào)包實現(xiàn)兩種代碼實現(xiàn)方式。32第十章數(shù)據(jù)降維
數(shù)據(jù)降維是緩解維數(shù)災(zāi)難常用方法之一,是將原始數(shù)據(jù)映射到低維子空間,以達到降低維度的目的,這個過程中數(shù)據(jù)的特征發(fā)生了本質(zhì)的變化,新的子空間的特征不再是原來的特征,因此不存在完全無損的降維方法,區(qū)別只是損失多少的問題.
針對研究對象,我們通常會收集一系列特征屬性,對研究對象進行分析,屬性越多,越有利于細致研究分析。但是隨著屬性增多,也會增加后續(xù)數(shù)據(jù)處理的運算量,帶來較大的處理負擔。3310.1
數(shù)據(jù)降維概述
數(shù)據(jù)降維方法從不同角度可以分為不同的類別,根據(jù)數(shù)據(jù)的特性劃分,有線性降維和非線性降維;根據(jù)是否利用數(shù)據(jù)的監(jiān)督信息劃分,有無監(jiān)督降維、有監(jiān)督降維和半監(jiān)督降維;根據(jù)是否保持數(shù)據(jù)的結(jié)構(gòu)劃分,有全局保持降維、局部保持降維和全局與局部保持一致降維等。需要根據(jù)特定的問題選擇合適的數(shù)據(jù)降維方法.
本章主要介紹常見的兩種數(shù)據(jù)降維技術(shù):主成分分析(PrincipalComponentAnalysis,簡稱PCA)、線性判別分析(LinearDiscriminantAnalysis,簡稱LDA)。3410.2
主成分分析35
主成分分析(PrincipalComponentAnalysis,PCA)主要用于發(fā)現(xiàn)數(shù)據(jù)中變量之間的關(guān)系,是數(shù)據(jù)分析的有力工具,是一種常用的無監(jiān)督學習方法,其原理是通過通過正交變換將一組可能存在相關(guān)性的變量轉(zhuǎn)換為一組線性不相關(guān)的變量,轉(zhuǎn)換后的這組變量叫主成分,它是原特征的線性組合,其個數(shù)通常小于原始變量的個數(shù)。10.2
主成分分析PCA算法原理:(1)由于樣本的屬性特征維數(shù)較高,相互之間存在關(guān)聯(lián)關(guān)系.為了消除相關(guān)性,對原始屬性進行線性線性組合,找到一組彼此不相關(guān)的屬性特征;(2)在新的屬性特征中,刪除一些不重要的特征,保留較少特征數(shù),同時保證損失較小.利用線性代數(shù)的知識對此進行解釋:
3610.2.1
PCA算法原理
37
10.2.1
PCA算法原理38
對于二維降一維問題,只需要找到一個基向量就夠了,即方差最大化就夠了。但對于更高維的問題,還有其他基向量需要求解.10.2.1
PCA算法原理39
例如,三維降二維,第一個基向量通過方差找到,第二個如果也利用方差,那么它與第一個基向量幾乎重合.我們希望第二個基向量與第一個線性無關(guān),而協(xié)方差可以表示樣本某兩個屬性的相關(guān)性.當協(xié)方差為0時,表示樣本的某兩個屬性獨立。
由上述討論知,我們希望單個屬性上方差最大,兩兩屬性間協(xié)方差為0。為將二者統(tǒng)一,我們考慮協(xié)方差矩陣。10.2.1
PCA算法原理
那么同樣地,可以推廣至更高維。40
10.2.1
PCA算法原理若要找到一組新的正交基,使得在這組基下的樣本集的協(xié)方差矩陣為對角陣,并且為了找到最大方差,對角線上元素應(yīng)從大到小排列。
4110.2.1
PCA算法原理
利用特征值分解利用奇異值(SVD)分解
4210.2.1
PCA算法原理那么此時
SVD降維與特征值降維雖然原理一致,但不需要計算協(xié)方差矩陣,節(jié)省了計算量。4310.2.1
PCA算法原理貢獻率
對于利用SVD實現(xiàn)的降維,我們可以利用奇異值衡量,將上面兩個公式中的特征值替換為對應(yīng)的奇異值即可。
4410.2.2
特征值分解降維利用特征值和特征向量實現(xiàn)PCA算法基本步驟:
4510.2.3
奇異值分解降維利用SVD實現(xiàn)PCA算法基本步驟:
4610.3線性判別分析(LinearDiscriminantAnalysis,簡稱LDA)LDA是一種經(jīng)典的線性學習方法、分類算法,也是一種有監(jiān)督降維方法?;舅枷雽?shù)據(jù)投影到低維空間上,并且希望投影后的數(shù)據(jù)點滿足:同一類別盡可能“接近”,不同類別盡可能“遠離”。4710.3線性判別分析(LinearDiscriminantAnalysis,簡稱LDA)算法原理(以二分類問題為例):
4810.3線性判別分析
4910.3線性判別分析二分類問題(1)廣義Rayleigh商
5010.3線性判別分析(2)類內(nèi)散度
5110.3線性判別分析
那么投影后的兩類樣本的方差和為
定義類內(nèi)散度矩陣為5210.3線性判別分析(3)類間散度
(4)LDA模型(
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 新冠患者的早期活動
- 2023-2024學年重慶市九年級(上)月考數(shù)學試卷(10月份)
- 滬科版八年級數(shù)學上冊第15章軸對稱圖形與等腰三角形15-1軸對稱圖形第1課時軸對稱圖形與軸對稱課件
- 七年級英語重點語法專練(附答案)
- 七年級下冊期中語法與作文英語復習
- 九年級英語語法學案(三)
- 2024-2025學年版塊9 壓強 專題9-4 不規(guī)則容器中液體壓強、壓力比較 (含答案) 初中物理尖子生自主招生培優(yōu)講義83講
- DB1410T 065-2024冬小麥滴灌生產(chǎn)技術(shù)規(guī)程
- 江蘇省宿遷市2024年中考數(shù)學試卷(含答案)
- 【四年級】上冊道德與法治-7.2 健康看電視 第二課時 別讓它搶走太多 課件
- 國開2023秋《人文英語4》第1-4單元作文練習參考答案
- 探秘微觀世界課件
- 人教版九年級上冊化學默寫總復習
- 螺旋鋼管的安裝施工方案
- 《足球傳接球》教學反思簡短 足球傳接球教案反思
- 初中信息技術(shù)高效課堂構(gòu)建策略之探究
- 科學論文中的學術(shù)不端案例分析
- 胸大肌斜方肌帶蒂皮瓣移植術(shù)后護理查房
- 信用社(銀行)工作會議精神貫徹落實情況的匯報
- 《配送中心運營管理實務(wù)》 教案 第13課 流通加工作業(yè)管理
- 江蘇省南京市玄武區(qū)南京理工大學附屬中學2023-2024學年上學期七年級英語國慶檢測(月考)
評論
0/150
提交評論