文章目錄
- 前言
- 聚類
- 聚類定義
- 什麼是簇
- 聚類分類
- 離群點
- 聚類算法執行個體
- K-Means算法(k-均值算法)
- 尋找質心最佳位置
- 關于均值
- 關于距離函數
- 次元災難
- 定義
- 産生的問題
- 解決辦法
- 總結
前言
聚類
聚類是在無标記樣本的條件下将資料進行分組，進而發現天然的結構。
聚類是無監督學習的主要任務，分類是監督學習的主要任務。
聚類主要應用在：
-
發現資料的潛在結構
-
對資料進行自然分組
-
對資料進行壓縮
這幾個方面的功能使聚類既可以作為預處理程式，又可以作為獨立的資料分析工具。
聚類定義
資料聚類（或聚類分組）的目标是在一個對象（模式、資料點）的集合中發現其自然的分組。
關于聚類目前尚無統一的定義，比較常用的定義如下：
聚類是把一個資料對象的集合劃分成簇（子集），使簇内對象彼此相似，簇間對象不相似的過程。
什麼是簇
回答什麼是簇這個根本性問方面，人們已經做了大量努力。
給定一個資料集X，距離函數d，考慮一個聚類函數F,Kleinbreg描述了以下3個屬性：
- 尺度不變性：對于任意距離函數d和任意常數a>0，有F（d）=F（αd）
- 劃分豐富性：聚類函數F輸出的資料簇劃分集合包含資料所有可能的簇劃分結果（标記一下）
- 距離一緻性：令d和d是兩個距離函數，如果d在的基礎上縮小同一簇中資料之間的距離，擴大不同簇中資料之間的距離，則F（d）= F（d`）
簡單地說就是：
簇：資料點分布為一團的資料集合為一簇，如下紅色圈。
聚類分類
聚類方法大體可以分為3個階段：
- 經典算法：它是2000年以前，而向早期的資料庫及相關應用開發的算法。比如基于模型的算法，基于劃分的算法，基于密度的算法，基于網格的算法，層次聚類算法，
- 進階算法：它是2000年以來，在經典算法的基礎上，針對更為複雜的資料和任務開發的算法。比如譜聚類，高維資料聚類，基于非負數矩陣分解的聚類，不确定資料聚類：
- 多源資料算法：它是針對多源相關資料開發的算法。比如：多角度聚類，多任務聚類，多任務多視角聚類，遷移聚類，多模聚類。
離群點
簡單了解為噪聲點 或者 離各個簇都很遠，如下綠色圈中的
聚類算法執行個體
這裡，我們以
經典算法
——
基于劃分的聚類算法
——
k-均值算法
為例，對聚類進行初步探索。
備注：基于劃分的方法是一種被廣泛研究和應用的資料聚類方法，這類方法的大部分算法都有着簡潔易懂，易于實作等優點，在許多領域都發揮巨大作用，基于劃分的方法通過一個最優化的目标函數發掘資料中包含的類别資訊結構，通常以疊代的方式逐漸提高聚類的效果。
這裡首先需要引入一個
原型點
的概念，
即可以展現出某一類别特性的代表的點
，是以，基于劃分的算法通常需要設定某種确定的參數來選取可以代表對應簇的原型點.
原型點：可以展現出某一類别特性的代表的點
是以，基于劃分的方法也稱為基于原型的方法。
基于劃分算法的基本流程：
K-Means算法(k-均值算法)
k-均值算法在許多學科科領域内得到了大量的研究和應用，具體如：
- 資料壓縮、
- 資料分類、
- 密度估計等方面，
因為其算法思想較為
簡潔易懂
，且
花費較小的計算代價
可以獲得不錯的聚類結果等原因，k-均值算法成為各種聚類算法中較為常用的算法之一。
算法實作k-means是最大分離和最大内聚的最簡單實作.
基本步驟是：
- 尋找質心最佳位置
尋找質心最佳位置
假設我們有一個資料集
，要分成K個聚類和一組K質心，則經由k-均值算法進行聚類分析後，産生的類别集合為C={C1，C2，，Ck}，其聚類中心為：
其中，
集合M和質心有一個附加索引 t（作為上标）表示疊代次數，從最開始的
開始，K-means試圖最小化目标函數，我們可以使用誤差平方和SSE作為度量聚類品質的目标函數：
如果SSE（t+1）<SSE（t），則表示質心正在接近一個最佳位置。尋找最佳位置的過程就是一個疊代的過程，這個疊代過程也叫做勞埃德算法Lloyd’s Algorithm，通過給M0初始化随機值開始，下一步是給xi∈X的每個樣本配置設定質心與x；距離最小的聚類：
完成所有配置設定後，新的質心将重新被指派：
重複該過程直到質心停止變化。
有上述步驟可知，最初我們選擇的質心對計算時間具有很大影響：
- 如果
- 非常接近
- 那麼，我們隻需疊代幾次就可以得到最佳位置
- 但是 如果
- 純粹是随機的時候，無效的初始選擇的機率接近于1.
同時，我們需要注意的是，勞埃德算法雖然計算簡單且易于了解，但是算法易陷入局部最優解而不是全局最優解，對于這個問題，我們可以在同一個資料及上多運作幾次k-均值算法，然後選取SSE（temd）最小的那次作為最終聚類結果。
關于均值
關于距離函數
次元災難
我們可以了解到，傳統的聚類算法在高維資料上的性能通常很差，
故我們在訓練模型時，要特别注意
次元災難（curse of dimensionality）現象
。
定義
次元災難，即當我們模型的特征個數不斷增加時，模型性能可能會有提升，但是超過了某個值後，其性能不升反降。
舉例，發生資料聚類有重疊的情況，說明可能是不同次元的重疊，雖然是仍然是兩個簇，但平面上相交，三維為正常簇，引起的聚類分劃問題。
産生的問題
次元災難同時引發了
過拟合問題
，即模型在訓練集上表現的良好，但在非訓練集上表現一般，此時模型可能因為特征維數過多，進而學習了過多細節，泛化能力差。
在此，引用納特·西菲爾的一句話：資訊越多，問題越多。
在這個時代，我們的資訊量增長速度過快，人們應該從幹憂他們的噪聲中分辨出有用的信号。但是由于人工篩選特征成本過大，再加上人們本身對所研究的事物不夠了解，難以人工篩選出"有用的"特征，是以此時，我們就可以考慮，讓模型自己去提取特征。
解決辦法
為此，人們廣泛研究了
降維
和
特征變換
方法，将原始資料映射到一個新的特征空間，生成的資料更容易被現有的分類器分離。
一般來說，現有的資料變換方法有主成分分析（PCA）等線性變換和核方法、譜方法等非線性變換。
然而，高度複雜的資料隐藏結構仍然挑戰着現有聚類方法的有效性。
随着深度學習的發展，深度神經網絡由于其高度非線性轉換的固有特性，可以用于将資料轉換為更有利于聚類的表示。