语音识别学习日志 2019-7-14 语音识别基础知识准备3 {Kmean算法分析与HMM(Hidden Markov Model)模型}
Kmean算法
聚類算法
對(duì)于"監(jiān)督學(xué)習(xí)"(supervised learning)，其訓(xùn)練樣本是帶有標(biāo)記信息的，并且監(jiān)督學(xué)習(xí)的目的是：對(duì)帶有標(biāo)記的數(shù)據(jù)集進(jìn)行模型學(xué)習(xí)，從而便于對(duì)新的樣本進(jìn)行分類。而在“無監(jiān)督學(xué)習(xí)”(unsupervised learning)中，訓(xùn)練樣本的標(biāo)記信息是未知的，目標(biāo)是通過對(duì)無標(biāo)記訓(xùn)練樣本的學(xué)習(xí)來揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律，為進(jìn)一步的數(shù)據(jù)分析提供基礎(chǔ)。對(duì)于無監(jiān)督學(xué)習(xí)，應(yīng)用最廣的便是"聚類"(clustering)。
??“聚類算法”試圖將數(shù)據(jù)集中的樣本劃分為若干個(gè)通常是不相交的子集，每個(gè)子集稱為一個(gè)“簇”(cluster)，通過這樣的劃分，每個(gè)簇可能對(duì)應(yīng)于一些潛在的概念或類別。
kmeans算法又名k均值算法。其算法思想大致為：先從樣本集中隨機(jī)選取?k?個(gè)樣本作為簇中心，并計(jì)算所有樣本與這?k?個(gè)“簇中心”的距離，對(duì)于每一個(gè)樣本，將其劃分到與其距離最近的“簇中心”所在的簇中，對(duì)于新的簇計(jì)算各個(gè)簇的新的“簇中心”
算法的算法過程如下:
D為訓(xùn)練集，K為聚類簇的個(gè)數(shù)，maxIter最大迭代次數(shù) KMeans(D， K， maxIter):隨機(jī)選取K個(gè)中心點(diǎn)for j in range(m):計(jì)算每個(gè)樣本Xj到各個(gè)簇中心的距離根據(jù)最近距離，篩選樣本歸屬于哪個(gè)簇for i in range(k):計(jì)算新的簇的中心，利用均值如果簇中心改變，則更新該簇中心，否則不變?nèi)绻總€(gè)簇的中心都沒更新則退出算法算法分析：
kmeans算法由于初始“簇中心”點(diǎn)是隨機(jī)選取的，因此最終求得的簇的劃分與隨機(jī)選取的“簇中心”有關(guān)，也就是說，可能會(huì)造成多種?k個(gè)簇的劃分情況。這是因?yàn)閗means算法收斂到了局部最小值，而非全局最小值。
二分k-means算法
??基于kmeans算法容易使得結(jié)果為局部最小值而非全局最小值這一缺陷，對(duì)算法加以改進(jìn)。使用一種用于度量聚類效果的指標(biāo)SSE(Sum of Squared Error)，即對(duì)于第?ii?個(gè)簇，其SSE為各個(gè)樣本點(diǎn)到“簇中心”點(diǎn)的距離的平方的和，SSE值越小表示數(shù)據(jù)點(diǎn)越接近于它們的“簇中心”點(diǎn)，聚類效果也就越好。以此作為劃分簇的標(biāo)準(zhǔn)。
??算法思想是：先將整個(gè)樣本集作為一個(gè)簇，該“簇中心”點(diǎn)向量為所有樣本點(diǎn)的均值，計(jì)算此時(shí)的SSE。若此時(shí)簇個(gè)數(shù)小于?k，對(duì)每一個(gè)簇進(jìn)行kmeans聚類(k=2) ，計(jì)算將每一個(gè)簇一分為二后的總誤差SSE，選擇SSE最小的那個(gè)簇進(jìn)行劃分操作。
算法的算法過程如下:
D為訓(xùn)練集，K為聚類簇的個(gè)數(shù)，maxIter最大迭代次數(shù) KMeans(D， K， maxIter):將所有點(diǎn)看做一個(gè)簇，計(jì)算此時(shí)“簇中心”向量while “簇中心”個(gè)數(shù)h<k ：for i=1,2,...,h do將第 i 個(gè)簇使用 kmeans算法進(jìn)行劃分，其中 k=2計(jì)算劃分后的誤差平方和 SSEi比較 k 種劃分的SSE值，選擇SSE值最小的那種簇劃分進(jìn)行劃分更新簇的分配結(jié)果添加新的“簇中心”until 當(dāng)前“簇中心”個(gè)數(shù)達(dá)到 k二分k-means算法分析：
二分k-means算法不再隨機(jī)選取簇中心，而是從一個(gè)簇出發(fā)，根據(jù)聚類效果度量指標(biāo)SSE來判斷下一步應(yīng)該對(duì)哪一個(gè)簇進(jìn)行劃分，因此該方法不會(huì)收斂到局部最小值，而是收斂到全局最小值。
HMM模型
隱馬爾可夫模型（Hidden Markov Model，以下簡稱HMM）。
1、什么樣的問題需要HMM模型
使用HMM模型的問題一般有一下兩個(gè)特征：
? ? ? 1)問題是基于序列的，比如時(shí)間序列或者狀態(tài)序列。
? ? ? 2)問題中有兩類數(shù)據(jù)，一列序列數(shù)據(jù)是可以觀測的，即觀測序列；而另一類數(shù)據(jù)是不能觀測到的，即隱藏狀態(tài)序列，簡稱狀態(tài)序列。
有這兩個(gè)特征，那么問題一般可以用HMM模型解決。這樣的問題在實(shí)際生活中是很多的。比如：打字的過程，在鍵盤上敲出來的一系列字符就是觀測序列，而實(shí)際想輸入的句子就是隱藏序列，輸入法的任務(wù)就是根據(jù)敲入的一系列字符盡可能的猜測我要輸入的詞語，并把最可能的詞語放在最前面，這就可以看做一個(gè)HMM模型。
2、HMM模型的定義
HMM模型詳細(xì)介紹:http://www.52nlp.cn/hmm-learn-best-practices-two-generating-patterns
http://www.52nlp.cn/hmm-learn-best-practices-three-hidden-patterns
http://www.52nlp.cn/hmm-learn-best-practices-four-hidden-markov-models
對(duì)于HMM模型，假設(shè)Q是所有可能的隱藏狀態(tài)的集合，V是所有可能的觀測狀態(tài)的集合，即：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
其中，N是可能的隱藏狀態(tài)數(shù)，M是所有的可能的觀察狀態(tài)數(shù)。
對(duì)于一個(gè)長度為T的序列，I對(duì)應(yīng)的狀態(tài)序列,?O是對(duì)應(yīng)的觀察序列，即：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
其中，任意一個(gè)隱藏狀態(tài)∈Q, 任意一個(gè)觀察狀態(tài)∈V。
HMM模型做了兩個(gè)很重要的假設(shè)如下：
1）齊次馬爾科夫鏈假設(shè)。即任意時(shí)刻的隱藏狀態(tài)只依賴于它前一個(gè)隱藏狀態(tài)。當(dāng)然這樣假設(shè)有點(diǎn)極端，因?yàn)楹芏鄷r(shí)候我們的某一個(gè)隱藏狀態(tài)不僅僅只依賴于前一個(gè)隱藏狀態(tài)，可能是前兩個(gè)或者是前三個(gè)。但是這樣假設(shè)的好處就是模型簡單，便于求解。如果在時(shí)刻t的隱藏狀態(tài)是,在時(shí)刻t+1的隱藏狀態(tài)是?, 則從時(shí)刻t到時(shí)刻t+1的HMM狀態(tài)轉(zhuǎn)移概率可以表示為:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
這樣可以組成馬爾科夫鏈的狀態(tài)轉(zhuǎn)移矩陣A:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?
2）觀測獨(dú)立性假設(shè)。即任意時(shí)刻的觀察狀態(tài)只僅僅依賴于當(dāng)前時(shí)刻的隱藏狀態(tài)，這也是一個(gè)為了簡化模型的假設(shè)。如果在時(shí)刻t的隱藏狀態(tài)是, 而對(duì)應(yīng)的觀察狀態(tài)為, 則該時(shí)刻觀察狀態(tài)在隱藏狀態(tài)下生成的概率為,滿足：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
這樣可以組成觀測狀態(tài)生成的概率矩陣B:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
除此之外，我們需要一組在時(shí)刻t=1的隱藏狀態(tài)概率分布Π:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ?, 其中?
一個(gè)HMM模型，可以由隱藏狀態(tài)初始概率分布Π, 狀態(tài)轉(zhuǎn)移概率矩陣A和觀測狀態(tài)概率矩陣B決定。Π, A決定狀態(tài)序列，B決定觀測序列。因此，HMM模型可以由一個(gè)三元組λ表示如下：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
3、一個(gè)HMM模型實(shí)例
一個(gè)簡單的實(shí)例來描述上面抽象出的HMM模型。這是一個(gè)盒子與球的模型，例子來源于李航的《統(tǒng)計(jì)學(xué)習(xí)方法》。
假設(shè)我們有3個(gè)盒子，每個(gè)盒子里都有紅色和白色兩種球，這三個(gè)盒子里球的數(shù)量分別是：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
按照下面的方法從盒子里抽球，開始的時(shí)候，從第一個(gè)盒子抽球的概率是0.2，從第二個(gè)盒子抽球的概率是0.4，從第三個(gè)盒子抽球的概率是0.4。以這個(gè)概率抽一次球后，將球放回。然后從當(dāng)前盒子轉(zhuǎn)移到下一個(gè)盒子進(jìn)行抽球。規(guī)則是：如果當(dāng)前抽球的盒子是第一個(gè)盒子，則以0.5的概率仍然留在第一個(gè)盒子繼續(xù)抽球，以0.2的概率去第二個(gè)盒子抽球，以0.3的概率去第三個(gè)盒子抽球。如果當(dāng)前抽球的盒子是第二個(gè)盒子，則以0.5的概率仍然留在第二個(gè)盒子繼續(xù)抽球，以0.3的概率去第一個(gè)盒子抽球，以0.2的概率去第三個(gè)盒子抽球。如果當(dāng)前抽球的盒子是第三個(gè)盒子，則以0.5的概率仍然留在第三個(gè)盒子繼續(xù)抽球，以0.2的概率去第一個(gè)盒子抽球，以0.3的概率去第二個(gè)盒子抽球。如此下去，直到重復(fù)三次，得到一個(gè)球的顏色的觀測序列:?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O={紅，白，紅}.
注意在這個(gè)過程中，觀察者只能看到球的顏色序列，卻不能看到球是從哪個(gè)盒子里取出的。
那么按照我們上一節(jié)HMM模型的定義，我們的觀察集合是:?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?V={紅，白}，M=2
我們的狀態(tài)集合是：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Q={盒子1，盒子2，盒子3}，N=3
而觀察序列和狀態(tài)序列的長度為3.
初始狀態(tài)分布為：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
狀態(tài)轉(zhuǎn)移概率分布矩陣為：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
觀測狀態(tài)概率矩陣為：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
從上一節(jié)的例子，可以抽象出HMM觀測序列生成的過程。
輸入的是HMM的模型,觀測序列的長度T
輸出是觀測序列
生成的過程如下：
1）根據(jù)初始狀態(tài)概率分布Π生成隱藏狀態(tài)
2) for t from 1 to T
a. 按照隱藏狀態(tài)it的觀測狀態(tài)分布生成觀察狀態(tài).
? ? ? ? ? ?b. 按照隱藏狀態(tài)it的狀態(tài)轉(zhuǎn)移概率分布產(chǎn)生隱藏狀態(tài).
所有的一起形成觀測序列
HMM模型一共有三個(gè)經(jīng)典的問題需要解決：
1） 評(píng)估觀察序列概率。即給定模型λ=(A,B,Π)和觀測序列，計(jì)算在模型λ下觀測序列O出現(xiàn)的概率P(O|λ)。這個(gè)問題的求解需要用到前向后向算法。
2）模型參數(shù)學(xué)習(xí)問題。即給定觀測序列，估計(jì)模型λ=(A,B,Π)的參數(shù)，使該模型下觀測序列的條件概率P(O|λ)最大。這個(gè)問題的求解需要用到基于EM算法的Baun-Welch算法。這個(gè)問題是HMM模型三個(gè)問題中最復(fù)雜的。
3）預(yù)測問題，也稱為解碼問題。即給定模型λ=(A,B,Π)和觀測序列，求給定觀測序列條件下，最可能出現(xiàn)的對(duì)應(yīng)的狀態(tài)序列，這個(gè)問題的求解需要用到基于動(dòng)態(tài)規(guī)劃的維特比（Viterbi）算法。這個(gè)問題是HMM模型三個(gè)問題中復(fù)雜度居中的算法。
Baun-Welch算法，Viterbi解碼算法將在下一篇學(xué)習(xí)日志中介紹。
?
總結(jié)
以上是生活随笔為你收集整理的语音识别学习日志 2019-7-14 语音识别基础知识准备3 {Kmean算法分析与HMM(Hidden Markov Model)模型}的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 最大最小距离算法(K-MEANS K-m
- 下一篇： html中contentEditable