背景：

在實際工作中，會遇到這樣的問題，給機器輸入大量的特征數(shù)據(jù)，并希望機器希望學(xué)習(xí)找到某種共同的特征或者結(jié)構(gòu)，亦或是數(shù)據(jù)之間存在的某種關(guān)聯(lián)，例如，視頻網(wǎng)站根據(jù)用戶的觀看行為進行分組，從而建立不同的推薦策略，或是找到視頻是否流暢與用戶是否退訂之間的關(guān)系等。屬于無監(jiān)督學(xué)習(xí)算法。

無監(jiān)督學(xué)習(xí)：

包括兩大類，一：數(shù)據(jù)聚類，此類方案往往是通過數(shù)次迭代找到數(shù)據(jù)的最優(yōu)分割。二：特征變量的關(guān)聯(lián)規(guī)則，此類方法利用各種相關(guān)性分析找到變量之間的關(guān)系。

K-means 算法步驟

Kmeans的核心是將給定的數(shù)據(jù)集劃分成K個簇，并給出每個數(shù)據(jù)對應(yīng)的中心點。算法具體步驟如下：

1：數(shù)據(jù)預(yù)處理，如歸一化、離散點處理等

2：隨機選取K個簇中心，記為 $\mu _{1}^0, \mu _{2}^0, ,...\mu _{K}^0,$ 。

3：定義代價函數(shù)： $J(c,\mu )=\min_{\mu} \min_{c}\sum_{i=1}^M\vert \vert x_{i} -\mu _{c_{i}} \vert \vert ^2$ 。

4：令 $t=0,1,2...$ 為迭代步數(shù)，重復(fù)下面過程直到 $J$ 收斂

4.1 對于每一個樣本將其分到距離最近的簇

$c_{i}^t \leftarrow argmin_{\mu}\vert \vert x_{i} -\mu _{k}^t \vert \vert$

4.2 對于每一個類簇k，重新計算類簇的中心

$\mu _{k}^{t+1}\leftarrow argmin_{\mu}\sum_{i:\mu _{c_{i}}=k}\vert \vert x_{i} -\mu _{} \vert \vert ^2$

K均值在迭代時，交替方向法求解，假設(shè)當(dāng)前 $J$ 沒有達到最小值，那么首先固定簇中心 $\left\{ \mu _{k} \right\}$ ,調(diào)整樣本 $x_{i}$ 所屬的類別 $c_{i}$ 來讓 $J$ 函數(shù)減小，然后再固定 $\left\{ c_{i} \right\}$ ,調(diào)整中心 $\left\{ \mu _{k} \right\}$ 使 $J$ 減小，這兩個過程交替循環(huán)， $J$ 單調(diào)遞減，當(dāng) $J$ 遞減到最小時， $\left\{ \mu _{k} \right\}$ 和 $\left\{ c_{i} \right\}$ 同時收斂。

K-means缺點以及如何調(diào)優(yōu)

缺點：

1：受初始值的影響

2：異常值的影響

3：當(dāng)簇分布相差很大時，不適合

優(yōu)點：

大數(shù)據(jù)集， $K$ 均值聚類相對是可伸縮和高效的，計算復(fù)雜度 $O(NKt)$ ,其中 $N$ 是數(shù)據(jù)對象的數(shù)目， $K$ 是聚類簇數(shù)， $t$ 是迭代的輪數(shù)。盡管算法經(jīng)常局部最優(yōu)結(jié)束，一般情況下局部最優(yōu)已經(jīng)滿足要求

調(diào)優(yōu)方向

1：數(shù)據(jù)歸一化和離散點處理

2：合理選擇 $K$ 值

一：手肘法：選擇若干個K畫均方誤差的折線圖肉眼查看拐點二：Gap Statistic方法的基本思路是：引入?yún)⒖嫉臏y度值，其可以通過Monte Carlo采樣的方法獲得。?

3：采用核函數(shù)

利用kmeans假設(shè)各個數(shù)據(jù)簇的數(shù)據(jù)具有一樣的先驗概率，并呈現(xiàn)高緯球形分布，但是實際生活中是不常見的。面對非凸的數(shù)據(jù)分布時，引入核函數(shù)來優(yōu)化。核心：利用非線性核函數(shù)將樣本映射到高緯空間，并在新的特征空間中進行聚類。非線性映射增加了數(shù)據(jù)的線性可分的概率。

針對K-Means算法的缺點進行改進

針對對初始值敏感的改進

K-means++算法：

起步

由于 K-means 算法的分類結(jié)果會受到初始點的選取而有所區(qū)別，因此有提出這種算法的改進:?K-means++?。

算法步驟

其實這個算法也只是對初始點的選擇有改進而已，其他步驟都一樣。初始質(zhì)心選取的基本思路就是，初始的聚類中心之間的相互距離要盡可能的遠。

算法描述如下：

步驟一：隨機選取一個樣本作為第一個聚類中心；

步驟二：

計算每個樣本與當(dāng)前已有類聚中心最短距離（即與最近一個聚類中心的距離）這個值越大，表示被選取作為聚類中心的概率較大；

最后，用輪盤法選出下一個聚類中心；

步驟三：重復(fù)步驟二，知道選出 k 個聚類中心。

選出初始點后，就繼續(xù)使用標(biāo)準(zhǔn)的 k-means 算法了。

針對K值不容易確定引入了ISODATA算法

??????ISODATA的聚類個數(shù)是可變的，因為在聚類的過程中，對類別數(shù)有一個“合并”和“分裂”的操作。合并是當(dāng)聚類結(jié)果某一類中樣本數(shù)太少，或兩個類間的距離太近時，將這兩個類別合并成一個類別；分裂是當(dāng)聚類結(jié)果中某一類的類內(nèi)方差太大，將該類進行分裂，分裂成兩個類別。

ISODATA分類的過程和K-Means一樣，用的也是迭代的思想：先隨意給定初始的類別中心，然后做聚類，通過迭代，不斷調(diào)整這些類別中心，直到得到最好的聚類中心為止。

注：

初始簇個數(shù) $K_{0}$ ，最終簇大小范圍 $K_{0} /2=<K<=2*K_{0}$

分裂和合并的標(biāo)準(zhǔn)

每個簇的樣本數(shù)最小 $N_{min}$ ，小于這個值不進行分裂

每個簇樣本的最大方差 $\delta$ ，大于這個則進行分裂

兩個簇之間的最小距離圍 $D_{min}$ ，小于這個則進行合并

EM算法

EM算法是一種迭代算法，用于含有隱變量的概率模型的極大似然估計，或者說是極大后驗概率估計。

算法步驟

輸入：觀測變量數(shù)據(jù)Y，隱變量Z，聯(lián)合分布 $P(Y,Z|\theta )$ ，條件分布 $P(Z|Y,\theta )$

輸出：模型參數(shù) $\theta$

1：選擇參數(shù)的初始值 $\theta^{0}$

2：E步：記 $\theta ^i$ 為第 $i$ 次迭代參數(shù) $\theta$ 的估計值，在第 $i+1$ 次迭代的E步，計算 $Q$ 函數(shù) $Q(\theta ,\theta ^i )=E_{z} [logP(Y,Z|\theta)|Y ,\theta ^i )]=\sum_{z}logP(Y,Z|\theta)P(Z|Y,\theta^i)$ ，其中， $P(Z|Y,\theta^i)$ 是再幫給定Y和 $\theta^i$ 下隱變量數(shù)據(jù)Z的條件概率分布；

3：M步：求使 $Q(\theta ,\theta ^i )$ 極大化的 $\theta$ ，確定第 $i+1$ 次迭代的參數(shù)的估計值 $\theta ^{i+1}$ , $\theta ^{i+1}=arg\max_{a}Q(\theta ,\theta ^i)$

4：重復(fù)2，3步，直到收斂

EM算法推導(dǎo)

通過不斷求解下界的極大化逼近求解對數(shù)似然函數(shù)的極大化的算法

含有隱變量的概率模型的極大似然估計 $L(\theta )=logP(Y|\theta )=log\sum_{z} P(Y,Z|\theta )=log\sum_{z} P(Y|Z,\theta )P(Z,\theta )$

下面證明 $L(\theta )>L(\theta ^i)$

$L(\theta )-L(\theta ^i)=log\sum_{z} P(Y|Z,\theta )P(Z,\theta )-logP(Y|\theta ^i )$

利用Jensen不等式

$L(\theta )-L(\theta ^i)=log\sum_{z} P(Y|Z,\theta )P(Z,\theta )-logP(Y|\theta ^i )$

$>=\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )} -logP(Y|\theta ^i )=\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )}$

令 $B(\theta ,\theta^i)=L(\theta ^i )+\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )}$

則 $L(\theta )>=B(\theta ,\theta^i)$ 即函數(shù) $B(\theta ,\theta^i)$ 增大 $\theta$ ，也可以使得 $L(\theta )$ 有盡可能的增大，選擇 $\theta^{i+1}$ 使得 $B(\theta ,\theta^i)$ 達到極大，即 $\theta^{i+1}=arg\max_{a} {B(\theta ,\theta^i)}$ 現(xiàn)在求 $\theta^{i+1}$ 的表達式 $\theta^{i+1}=arg\max_{\theta }( L(\theta ^i )+\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )})$ = $arg\max_{\theta }(\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )})$ = $arg\max_{\theta }(\sum_{z}P(Z|Y,\theta^i ) logP(Z|\theta )P(Y|Z,\theta ))$ = $arg\max_{\theta }(\sum_{z} P(Z|Y,\theta^i )logP(Y,Z|,\theta ))$ = $arg\max_{\theta }Q(\theta ,\theta^i)$

K-means和EM算法的關(guān)系****

假設(shè)有m個觀察樣本，模型的參數(shù) $\theta$ ，最大化對數(shù)似然函數(shù)可以寫成如下的形式

$\theta =argmax\sum_{i=1}^mlogP(y^i,\theta)$

當(dāng)概率模型含有無法觀測的隱變量時，參數(shù)的最大似然估計

$\theta =argmax\sum_{i=1}^m\sum_{z^i} logP(y^i,z^i|\theta)$

因為含有不可觀測的隱變量，無法通過極大似然估計求解參數(shù)，這時可以通過EM算法求解。假設(shè) $z^i$ 對應(yīng)的分布 $Q_{i} (z^i)$ ，并滿足 $\sum_{z^i} Q_{i} (z^i)=1$ 。利用Jensen不等式，可以得到，

$\sum_{i=1}^m\sum_{z^i} logP(y^i,z^i|\theta)=\sum_{i=1}^m log\sum_{z^i}Q_{i}(z^i)\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)} >=\sum_{i=1}^m \sum_{z^i}Q_{i}(z^i)log\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)}$

$Q_{i}(z^i)=\frac{P(y^i,z^i|\theta)}{\sum_{z^i}P(y^i,z^i|\theta)} =P(z^i|y^i,\theta)$ 。不等式右側(cè)，即為 $r(x\vert \theta )$ 。當(dāng)?shù)仁匠闪r，我們相當(dāng)于優(yōu)化的函數(shù)找到了一個逼近的下界，然后最大化這個下界

EM算法和k-means關(guān)系

1：E步驟 $Q_{i}(z^i)=\frac{P(y^i,z^i|\theta)}{\sum_{z^i}P(y^i,z^i|\theta)} =P(z^i|y^i,\theta)$

2：M步驟：最大化 $\argmax_{\theta } \sum_{i=1}^m \sum_{z^i}Q_{i}(z^i)log\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)}$

K均值算法等價于以下隱變量求最大似然問題

$P(y,z|\mu_{1},\mu_{2},...\mu_{k})=exp(-||y-\mu_{z}||^2)【 if 】||y-\mu_{z}||^2=min ||y-\mu_{k}||^2 else【 0】$

$Q_{i}(z^i)==P(z^i|y^i,\theta) 「1」 if ||x-\mu_{z}||^2=min ||x-\mu_{k}||^2 【 else「 0」$

相當(dāng)于E步找到x當(dāng)前最近的簇

在M步驟 $\theta =\argmax_{\theta } \sum_{i=1}^m \sum_{z^i}Q_{i}(z^i)log\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)} =const -\sum_{i=1}^m \vert \vert x^i-\mu_{z^i} \vert \vert ^2$ 來更新簇中心

#####引用葫蘆書和李航機器學(xué)習(xí)

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

EM算法和K-Means算法

EM算法和K-Means算法

背景：

無監(jiān)督學(xué)習(xí)：

K-means 算法步驟

K-means缺點以及如何調(diào)優(yōu)

針對K-Means算法的缺點進行改進

針對K值不容易確定引入了ISODATA算法

EM算法

K-means和EM算法的關(guān)系****

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

EM算法和K-Means算法

背景：

無監(jiān)督學(xué)習(xí)：

K-means 算法步驟

K-means缺點以及如何調(diào)優(yōu)

針對K-Means算法的缺點進行改進

針對K值不容易確定引入了ISODATA算法

EM算法

K-means和EM算法的關(guān)系****

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av