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