Python机器学习---2.聚类算法理论部分
文章目錄
- 1.聚類分析
- 1.1 無監督學習與聚類算法
- 1.1.1.旨在理解數據自然結構的聚類
- 1.1.2 用于數據處理的聚類
- 1.2 核心概念
- 1.2.1 聚類分析
- 1.2.2 簇
- 1.3 基于原型的聚類技術: K-Means
- 1.3.1 基于原型的簇
- 1.3.2. K-Means基本定義
- 1.3.3 算法執行細節
- 距離衡量方法
- 文本距離
- 1.3.4 誤差平方和SSE (Sum of the Squared Error, SSE)
- 1.3.5 聚類目標函數和質心計算方法
1.聚類分析
1.1 無監督學習與聚類算法
決策樹、線性和邏輯回歸都是比較常用的機器學習算法，他們雖然有著不同的功能，但卻都屬于“有監督學習”的一部分，即是說，模型在訓練的時候，即需要特征矩陣X，也需要真實標簽y。機器學習當中，還有相當一部分算法屬于“無監督學習”，無監督的算法在訓練的時候只需要特征矩陣X，不需要標簽。無監督學習的代表算法有聚類算法、降維算法。
聚類算法是無監督類機器學習算法中最常用的一類，其目的是將數據劃分成有意義或有用的組(也被稱為簇)。這種劃分可以基于我們的業務需求或建模需求來完成，也可以單純地幫助我們探索數據的自然結構和分布。如果目標是劃分成有意義的組，則簇應當捕獲數據的自然結構。然而，在某種意義下，聚類分析只是解決其他問題(如數據匯總)的起點。無論是旨在理解還是應用，聚類分析都在廣泛的領域扮演著重要角色。這些領域包括:心理學和其他社會科學、生物學、統計學、模式識別、信息檢索、機
器學習和數據挖掘。
聚類分析在許多實際問題上都有應用，下面是一些具體的例子，按聚類目的是為了理解數據自然結構還是用于數據處理來組織。
1.1.1.旨在理解數據自然結構的聚類
在對世界的分析和描述中，類，或在概念上有意義的具有公共特性的對象組，扮演著重要的角色。的確，人類擅長將對象劃分成組(聚類)，并將特定的對象指派到這些組(分類)。例如，即使很小的孩子也能很快地將圖片.上的對象標記為建筑物、車輛、人、動物、植物等。就理解數據而言,簇是潛在的類，而聚類分析是研究自動發現這些類的的技術。
1.1.2 用于數據處理的聚類
聚類分析提供由個別數據對象到數據對象所指派的簇的抽象。此外，-些聚類技術使用簇原型(即同一個簇中用于代表其他對象的數據對象，例如質心等)來刻畫簇特征。這些簇原型可以用作大量數據分析和數據處理技術的基礎。因此，就聚類用于數據處理層面而言，聚類分析是研究發現最有代表性的簇原型的技術。
- 數據降維
許多數據分析技術，如回歸和PCA,都具有O(m2 )或更高的時間或空間復雜度(其中m是對象的個數)。因此對于大型數據集，這些技術不切實際。然而，可以將算法用于僅包含簇原型的數據
集，即每一列只保留其原型，而不是整個數據集。依賴分析類型、原型個數和原型代表數據的精度，行匯總結果可以與使用所有數據得到的結果相媲美。 - 數據離散壓縮
簇原型可以用于數據列壓縮。例如，創建一個包含所有簇原型的表，即每個原型賦予-個整數值,作為它在表中的位置(索引)。 每個對象用于它所在的簇相關聯的原型的索引表示。這類壓縮稱作
向量量化(vector quantization)，并常常用于圖像、聲音和視頻數據。
無論是用于數據降維還是離散壓縮，都將損失-定的數據信息量，而能夠使用聚類進行信息濃縮的
數據的特點是:
(1) 許多數據對象之間高度相似
(2) 某些信息丟失是可以接受的
(3) 希望大幅度壓縮數據量 - 有效地發現最近鄰
很多機器學習算法都是基于距離的模型，即找出最近鄰可能需要計算所有點對點之間的距離，如之前介紹的KNN。通常我們可以使用簇原型減少發現對象最近鄰所需要計算的距離的數目。直觀地說，如果兩個簇原型相距很遠，則對應簇中的對象不可能互為近鄰。這樣，為了找出一個對象的最近鄰，只需要計算到鄰近簇中對象的距離，其中兩個簇的鄰近性用其原型之間的距離度量，從而大幅降低KNN類算法的計算量。
1.2 核心概念
在討論具體的聚類技術之前，還需要討論必要的背景知識。首先，我們就聚類分析中的核心概念展開討論。
1.2.1 聚類分析
聚類分析僅根據在數據中發現的描述對象及其關系的信息，將數據對象分組。其目標是，組內的對象相互之間是相似的(相關的)，而不同組中的對象是不同的(不相關的)。組內的相似性(同質性)越大，組間差別越大，聚類就越好。
1.2.2 簇
簡單來說，簇就是分類結果的類，但實際上簇并沒有明確的定義，并且簇的劃分沒有客觀標準，我們可以利用下圖來理解什么是簇。該圖顯示了20個點和將它們劃分成簇的3種不同方法。標記的形狀指示簇的隸屬關系。下圖分別將數據劃分成兩部分和六部分。然而，將2個較大的簇都劃分成3個子簇可能是人的視覺系統造成的假象。此外，說這些點形成4個簇可能也不無道理。該圖表明簇的定義是不精確的,而最好的定義依賴于數據的特性和期望的結果。聚類分析與其他將數據對象分組的技術相關。例如，聚類可以看作一種分類，它用類(簇) 標號創建對
象的標記。然而，只能從數據導出這些標號。相比之下，KN則是監督分類(supervisedclassfication)，即使用由類標號已知的對象開發的模型，對新的、無標記的對象賦予類標號。為此,有時稱聚類分析為非監督分類(unsupervised classification)。在數據挖掘中，不附加任何條件使用術語分類時，通常是指監督分類。
1.3 基于原型的聚類技術: K-Means
1.3.1 基于原型的簇
此時簇是對象的集合，并且其中每個對象到定義該簇的原型的距離比到其他簇的原型的距離更近(或更加相似)。 對于具有連續屬性的數據，簇的原型通常是質心，即簇中所有點的平均值。當質心沒有意義時(例如當數據具有分類屬性時)，原型通常是中心點，即簇中最有代表性的點。對于許多數據類型,原型可以視為最靠近中心的點;在這種情況下，通常把基于原型的簇看作基于中心的簇(center-basedcluster)。毫無疑問，這種簇趨向于呈球狀。下圖是一個基于中心簇的例子。
1.3.2. K-Means基本定義
K均值算法比較簡單，我們從介紹它的基本算法開始。首先，選擇K個初始質心，其中K是我們指定的參數，即所期望的簇的個數。每個點指派到最近的質心，而指派到一個質心的點集為一個簇。然后,根據指派到簇的點，更新每個簇的質心。重復指派和更新步驟，直到簇不發生變化，或等價地，直到質心不發生變化。
K-Means的核心任務就是根據我們設定好的K，找出K個最優的質心，并將離這些質心最近的數據分別分配到這些質心代表的簇中去。具體過程可以總結如下:
那什么情況下，質心的位置會不再變化呢?當我們找到一個質心，在每次迭代中被分配到這個質心上的樣本都是一致的，即每次新生成的簇都是一致的，所有的樣本點都不會再從一個簇轉移到另一個簇，質心就不會變化了。這個過程在可以由下圖來顯示，我們規定，將數據分為4簇(K=4) ，其中白色X代表質心的位置:
在數據集下多次迭代(iteration),就會有:
可以看見，第六次迭代之后，基本上質心的位置就不再改變了，生成的簇也變得穩定。此時我們的聚類就完成了，我們可以明顯看出，K-Means按照數據的分布， 將數據聚集成了我們規定的4類，接下來我們就可以按照我們的業務需求或者算法需求，對這四類數據進行不同的處理。
1.3.3 算法執行細節
聚類算法聚出的類有什么含義呢?這些類有什么樣的性質?我們認為，被分在同一個簇中的數據是有相似性的，而不同簇中的數據是不同的，當聚類完畢之后，我們就要分別去研究每個簇中的樣本都有什么樣的性質，從而根據業務需求制定不同的商業或者科技策略。聚類算法的目的就是追求“簇內差異小，簇外差異大”。而這個“差異”，由樣本點到其所在簇的質心的距離來衡量。
對于一個簇來說，所有樣本點到質心的距離之和越小，我們就認為這個簇中的樣本越相似，簇內差異就越小。而距離的衡量方法有多種，令x表示簇中的一個樣本點，μ表示該簇中的質心，n表示每個樣本點中的特征數目，表示組成點x的每個特征，則該樣本點到質心的距離可以由以下距離來度量。
距離衡量方法
常見距離衡量方法即對應公式如下所示:
● 數據距離
對于數據之間的距離而言，在歐式空間中我們常常使用歐幾里得距離，也就是我們常說的距離平方
和開平方，其基本計算公式如下:
除此之外，還有曼哈頓距離，也被稱作街道距離，該距離的計算方法相當于是歐式距離的1次方表示形式，其基本計算公式如下:
當然，不管是歐式距離還是曼哈頓距離，都可視為閔可夫斯基距離的-種特例，該距離計算公式如下:
當n為1時，就是曼哈頓距離，當n為2時即為歐式距離，當n趨于無窮時，即為切比雪夫距離 。
文本距離
而除了數據距離之外，距離的衡量還常見于文本數據之間，此時我們常用余弦相似性或杰卡德相似度來進行衡量，余弦相似性計算本質上就是計算余弦夾角，其基本計算公式如下:
而杰卡德相似度則主要以集合運算為主:
1.3.4 誤差平方和SSE (Sum of the Squared Error, SSE)
此處引入機器學習算法中非常重要的概念，誤差平方和，也被稱為組內誤差平方和。該概念在聚類和回歸算法中均有廣泛應用。在聚類算法中所謂誤差平方和是指每個數據點的誤差，即它到最近所屬類別質心的歐幾里得距離，然后求和匯總既得誤差平方和。在聚類算法中，SSE是我們判斷模型是否最優的重要指標，我們希望求得的模型是在給定K值得情況下SSE最小的模型，即在相同的K值情況下聚類模型SSE越小越好，這也是聚類算法最核心的優化條件。
1.3.5 聚類目標函數和質心計算方法
聚類算法中的目標函數是實現聚類這一目標所使用的函數，如最小化對象到其所屬類的質心距離等，這里需要注意，-般如果采用距離作為鄰近度衡量標準，則目標函數往往是利用最小距離來構建聚類類別，而若采用相似度作為鄰近度衡量標準，則目標函數就是利用最大化相似度和來構建聚類類別。
而質心是聚類類別的原型，-般可用均值或中位數來表示。但無論如何，在一旦確定距離衡量方法或鄰近度函數(如歐式距離等)，并 在模型優化條件(SSE最小) 的指導下，目標函數和質心選取方法都會隨之確定，常用鄰近度函數、質心和目標函數組合如下:
而這一切實際上是建立在嚴格的數學理論推導的基礎之上的，推導方法之一就是利用EM算法進行計算。首先，我們需要定義聚類算法中的符號集:
然后，誤差平方和可由下列計算公式表示:
其中，C; 是第i個簇，x是C;中的點，C是第i個簇的質心。我們這里驗證最常用的，當采用歐式距離時當且僅當質心為均值的時候才能夠保證在目標函數的聚類過程中SSE保持最小。要保證在給定K值情況”下總SSE最小，則用梯度下降理論工具可將問題轉化為為了保證總SSE最小，K的每一步取值，即K值每增加1,都要能夠最大程度降低SSE,即在給定K值步長為1的情況下去找SSE下降速度最快的坡度(詳見邏輯回歸)。即簇的最小化SSE的最佳質心是簇中各點的均值。同樣可類似證明采用曼哈頓距離時最佳質心選取方案是選取中位數，而當采用余弦夾角衡量相似度時，均值是最佳的質心計算方法。
總結
以上是生活随笔為你收集整理的Python机器学习---2.聚类算法理论部分的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python机器学习---何为机器学习？
- 下一篇： Python机器学习---2.聚类分析代