【文章內(nèi)容簡(jiǎn)介】 式計(jì)算類標(biāo)記的期望值。 ? 四、 M步驟：利用 E步驟計(jì)算出的期望值，按下式用已標(biāo)記樣本和未標(biāo)記樣本重新估計(jì)新的分類器參數(shù)。 )(/)|()()|(1XPHxPHPHXPnkk?????||)|()()()|()|(HHXPHPHPHXPXHP? K最近鄰分類 ? K近鄰（ KNN）分類是 基于范例 的分類方法，它的基本思想是：給定待分類樣本后，考慮在訓(xùn)練樣本集中與該待分類樣本距離最近（最相似）的K 個(gè)樣本，根據(jù)這 K 個(gè)樣本中大多數(shù)樣本所屬的類別判定待分類樣本的類別。 ? 它的特例是 1 NN，即分類時(shí)選出待分類樣本的最近鄰，并以此最近鄰的類標(biāo)記來(lái)判斷樣本的類。 ? KNN算法的優(yōu)點(diǎn)在于它有較高的精確程度，研究表明， KNN的分類效果要明顯好于樸素貝葉斯分類、決策樹(shù)分類。 ? K最近鄰分類（續(xù)） ? 最近鄰分類的算法步驟如下： ? 一、以向量空間模型的形式描述各訓(xùn)練樣本。 ? 二、在全部訓(xùn)練樣本集中選出與待分類樣本最相似的 K個(gè)樣本。 K值的確定目前沒(méi)有很好的方法，一般采用先定一個(gè) 100左右的初始值，然后再調(diào)整。 ? 三、將待分類樣本標(biāo)記為其 K個(gè)鄰居中所屬最多的那個(gè)類別中。 ? 遺傳算法 ? 遺傳算法易于并行處理，其依據(jù)是自然界進(jìn)化和適者生存的原則。遺傳學(xué)習(xí)開(kāi)始如下：創(chuàng)建若干個(gè)由隨機(jī)產(chǎn)生的個(gè)體組成的初始 群體 。每個(gè)個(gè)體用一個(gè)二進(jìn)位串表示。 ? 形成由當(dāng)前群體中最適合的個(gè)體組成新的群體，以及這些規(guī)則的子女。個(gè)體的 適合度 用某一目標(biāo)函數(shù)來(lái)評(píng)估。 ? 子女通過(guò)使用諸如交叉和變異等遺傳操作來(lái)創(chuàng)建。在 交叉 操作中，來(lái)自個(gè)體對(duì)的子串交換，形成新的個(gè)體對(duì)。在 變異 操作中，個(gè)體中隨機(jī)選擇的位被反轉(zhuǎn)。 ? 遺傳算法（續(xù)） ? Fitness：適應(yīng)度評(píng)分函數(shù)，為給定假設(shè)賦予一個(gè)評(píng)估得分。 ? Fitness_threshold：指定終止判據(jù)的閾值。 ? p：群體中包含的假設(shè)數(shù)量。 r：每一步中通過(guò)交叉取代群體成員的比例。 m：變異率。 ? 初始化群體： P?隨機(jī)產(chǎn)生的 p個(gè)假設(shè) ? 評(píng)估： 對(duì)于 P中的每一個(gè) h，計(jì)算 Fitness(h) ? 當(dāng) [Fitness(h)]Fitness_threshold，做： ? 產(chǎn)生新的一代 PS： ? 遺傳算法（續(xù)） ? 選擇： 用概率方法選擇 P的 (1r)p個(gè)成員加入 PS。從 P中選擇假設(shè) hi的概率 P(hi)通過(guò)下面公式計(jì)算： ? 交叉： 根據(jù)上面給出的 P(hi)，從 P中按概率選擇r?p/2對(duì)假設(shè)。對(duì)于每一對(duì)假設(shè) h1, h2應(yīng)用交叉算子產(chǎn)生兩個(gè)后代。把所有的后代加入 PS。 ? 變異： 使用均勻的概率從 PS中選擇 m百分比的成員。對(duì)于選出的每個(gè)成員，在它的表示中隨機(jī)選擇一個(gè)位取反。 ? 更新： P?PS。 ? 評(píng)估： 對(duì)于 P中的每一個(gè) h計(jì)算 Fitness(h) ? 從 P中返回適應(yīng)度最高的假設(shè)。 ? 聚類分析 ? 為達(dá)到全局最優(yōu)，基于劃分的聚類會(huì)要求窮舉所有可能的劃分。聚類技術(shù)將數(shù)據(jù)元組視為對(duì)象。它將對(duì)象劃分為群或聚類，使得在一個(gè)聚類中的對(duì)象 “ 類似 ” ，但與其它聚類中的對(duì)象 “ 不類似 ” 。 ? 絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的 基于劃分的方法 ，這些基于劃分的聚類方法對(duì)在中小規(guī)模的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)球狀簇很適用。 ? （ 1） kmeans算法 ，在該算法中，每個(gè)簇用該簇中對(duì)象的平均值來(lái)表示。 ? （ 2） kmedoids算法 ，在該算法中，每個(gè)簇用接近聚類中心的一個(gè)對(duì)象來(lái)表示。 ? 聚類分析（續(xù)） ? 常用的相似程度度量 ? 余弦?jiàn)A角： Dice系數(shù)： Jaccard系數(shù)： ? ??? ????nknkjkiknkjkikjiWWWWddC os1 1221))((),(? ??? ????? nknkjkiknkjkikjiWWWWddD i c e1 1221)(),(? ???? ???????? nknkjkiknkjkiknkjkikjiWWWWWWddJ a c c a r d1 11221),(? 聚類分析（續(xù)） ? 基于層次的方法： 層次的方法對(duì)給定數(shù)據(jù)集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以被分為凝聚或分裂方法。 （ Chameleon ， CURE， BIRCH） ? 基于密度的方法： 只要臨近區(qū)域的密度超過(guò)某個(gè)閾值，就繼續(xù)聚類。避免僅生成球狀聚類。（ DBSCAN， OPTICS， DENCLUE） ? 基于網(wǎng)格的方法： 基于網(wǎng)格的方法把對(duì)象空間量化為有限數(shù)目的單元，所有的聚類操作都在這個(gè)量化的空間上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度很快。（ STING， CLIQUE，WaveCluster） ? 基于模型的方法： 為每個(gè)簇假設(shè)一個(gè)模型，發(fā)現(xiàn)數(shù)據(jù)對(duì)模型的最好匹配。（ COBWEB， CLASSIT，AutoClass） ? 隱馬爾可夫模型 ? 對(duì)于一個(gè)隨機(jī)事件，有一個(gè)觀察值序列： O1, ..., OT。該事件隱含著一個(gè)狀態(tài)序列： X1, ..., XT ? 假設(shè) 1：馬爾可夫性， P(Xi| Xi1… X1) = P(Xi| Xi1) ? 假設(shè) 2：不動(dòng)性， P(Xi+1| Xi) = P(Xj+1| Xj)，對(duì)任意 i,j成立 ? 假設(shè) 3：輸出獨(dú)立性， P(O1,..., OT | X1,..., XT) = ΠP(Ot | Xt) ? 一個(gè)隱馬爾可夫模型是一個(gè)五元組： (ΩX, ΩO, A, B, π) ? 其中： ΩX = {Q1,..., QN}：狀態(tài)的有限集合； ? ΩO = {V1,..., VM}：觀察值的有限集合； ? A = {aij}， aij = P(Xt+1 = Qj |Xt = Qi)：轉(zhuǎn)移概率； ? B = {bik}， bik = P(Ot = Vk | Xt = Qi)：輸出概率； ? π = {πi}， πi = P(X1 = Qi)：初始狀態(tài)分布。 ? 隱馬爾可夫模型（續(xù)） ? 令 λ = {A, B,π} 為給定 HMM的參數(shù)， ? 令 σ = O1,...,OT 為觀察值序列， ? 隱馬爾可夫模型的三個(gè)基本問(wèn)題： ? 評(píng)估問(wèn)題 ：對(duì)于給定模型，求某個(gè)觀察值序列的概率 P(σ|λ) 。 向前 /向后算法 ：定義向前 /向后變量。采用動(dòng)態(tài)規(guī)劃算法，復(fù)雜度 O(N2T) ? 解碼問(wèn)題 ：對(duì)于給定模型和觀察值序列，求可能性最大的狀態(tài)序列。 Viterbi算法 ：采用動(dòng)態(tài)規(guī)劃算法，復(fù)雜度 O(N2T) ? 學(xué)習(xí)問(wèn)題 ：對(duì)于給定的一個(gè)觀察值序列，調(diào)整參數(shù) λ，使得觀察值出現(xiàn)的概率 P(σ|λ)最大。向前 EM算法的一個(gè)特例，帶隱變量的最大似然估計(jì)。BaumWelch算法 。 ? 隱馬爾可夫模型（續(xù)） ? 向前 /向后算法：定義向前 /向后 變量： ? 初始化： ? 遞歸： ? 終結(jié)： TtqOOOPi ittt ???? 1)/,()( 21 　　　??? ?TtObi ii ??? 1)()( 11 　　　??NjTtObaij tjijNiit ?????? ??? ? 1,11)(])([)( 111 　　　????? NiT iP1)()/( ???11)/,()( 21 ????? ?? TtqOOOPi itTttt 　　　??? ?TtiT ??? 11)( 　　　?NiTTtjObai ttNijijt ?????? ???? 1,1,...,2,1)()()( 111　????? NiiP11 )()/( ???? 隱馬爾可夫模型（續(xù)） ? Viterbi算法 ? 初始化： ? 遞歸： ? 終結(jié)： ? 求 S序列： Ni1,0)(Ni1),()(111??????　　　　iObi ii???NjTtaijNjTtObaijijtNitijijtNit????????????????1,2],)([m a xa r g)(1,2),(])([m a x)(1111　　　　????)]([m a xa r g) ] )([m a x1*1*iqiPTNiTTNi????????1,. .. ,2,1),( * 11* ???? ?? TTtqq ttt 　　?1 2 1 1 2 1 1 , 2 , , , . . .( ) m a x [ . . . , , | ]tt t t tq q qi P q q q q i O O O??? ??? …? 隱馬爾可夫模型（續(xù)） ? BaumWelch算法 ? 主要步驟： 1. 初始模型（待訓(xùn)練模型） ?0, 2. 基于 ?0 以及觀察值序列 ?，訓(xùn)練新模型 ?； 3. 如果 log P(X|?) log(P(X|?0) Delta， 說(shuō)明訓(xùn)練已經(jīng)達(dá)到預(yù)期效果， 算法結(jié)束。 4. 否則，令 ?0 ＝ ? ， 繼續(xù)第 2步工作 ? 支持向量機(jī) ? 支持向量機(jī)基本模型是針對(duì)線性可分情況下的最優(yōu)分界面提出的。在這一條件下，正類和反類訓(xùn)練樣本可用 超平面 完全正確地分開(kāi)。 ? 設(shè)線性可分樣本集合為 ( xi , yi )， i = 1,… , n；x∈ R