文本分類與聚類-資料下載頁
2025-07-19 18:03本頁面
【正文】 文本分類的應(yīng)用 ? 新聞出版按照欄目分類 ? 類別 {政治 ,體育 ,軍事 ,… } ? 網(wǎng)頁分類 ? 類似于 Yahoo的分類 ? 個性化新聞 ? 智能推薦 ? 垃圾郵件過濾 ? 類別 {spam, notspam} 文本聚類 Text Clustering 聚類式搜索 聚類式搜索 聚類 ? 將無標(biāo)記的樣本劃分到聚類的各個子集中 : ? 類內(nèi)樣本非常相似 ? 類間樣本非常不同 ? 無監(jiān)督方法發(fā)現(xiàn)新類別 . 聚類樣例 . . . . . . . . . . . . . . . 層次聚類 ? 在無標(biāo)注的樣本集合中建立 樹狀層次分類結(jié)構(gòu) ? 遞歸的標(biāo)準(zhǔn)層次聚類算法應(yīng)用生成層次聚類 . animal vertebrate fish reptile amphib. mammal worm insect crustacean invertebrate 會聚 vs. 分裂聚類 ? 會聚 (bottomup) 以每個樣本獨自一類開始，迭代合并到越來越大的類中 ? 分裂 (partitional, topdown) 將所有樣本不斷劃分到類別中 會聚層次聚類 (HAC) ? 設(shè)定相似度函數(shù)確定任意兩個實例的相似度 ? 開始每個實例獨自一類 ? 然后重復(fù)合并最相似的類別，直到成為一類： ? 在當(dāng)前的類別中，確定最近的兩類 ci 和 cj ? 用單一的類別 ci ? cj取代 ci 和 cj ? 合并的過程成為層次結(jié)構(gòu) 聚類相似度 ? 設(shè)定一個相似度函數(shù)確定兩個實例的相似程度 ? 文本向量的余弦相似度 ? 如何計算包含多個樣例的兩個類別的相似度？ ? Single Link: 兩個類別中最近成員的相似度 ? Complete Link: 兩個類別中最遠(yuǎn)成員的相似度 ? Group Average: 成員間的平均相似度 計算復(fù)雜度 ? 在第一次迭代中， HAC方法需要計算所有樣例的每一對的距離 ? 在合并迭代中，需要計算新形成的類與其他類的距離 ? 為了維持 O(n2)的性能，計算類與類之間的相似度需要 常數(shù)時間 計算類別間相似度 ? 合并 ci,cj后，計算該類和其他類的相似度可以如下計算： ? Single Link: ? Complete Link: )),(),(m a x ()),(( kjkikji ccs i mccs i mcccs i m ??)),(),(m i n ()),(( kjkikji ccs i mccs i mcccs i m ??平均連通凝聚聚類 ? 單連通容易導(dǎo)致狹長聚類，全連通的算法復(fù)雜度為 O(n3) ? 用合并后的類中所有對平均相似度度量兩個類的相似度 ? 是全連通和單連通的折中 . ? ??? ???????)( :)(),()1(1),(ji jiccx xyccyjijiji yxs i mccccccs i m ? ?????計算平均連通相似度 ? 設(shè)定余弦相似度及單位長度歸一化向量 . ? 總是維持每個類別的向量和 . ? 計算類別相似度在常數(shù)時間內(nèi) : ???jcxj xcs ??? )(( ( ) ( ) ) ( ( ) ( ) ) ( | | | |)( , )( | | | |) ( | | | | 1 )i j i j i jiji j i js c s c s c s c c cs i m c cc c c c? ? ? ? ??? ? ?非層次聚類 ? 需要確定期望的類別數(shù) k ? 隨機選擇 k個種子 ? 進行初始聚類 ? 迭代，將樣例重新劃分 ? 直到樣例所屬的類別不再改變 KMeans ? 設(shè)定樣例是一個實值向量 ? 基于質(zhì)心或類 c中樣本的均值聚類 ? 根據(jù)樣例與當(dāng)前類別質(zhì)心的相似度重新劃分類別 ???cxxc???||1( c)μ距離矩陣 ? 歐式距 (L2 norm): ? L1 norm: ? 余弦相似度 (轉(zhuǎn)換成距離 ): 212 )(),( imii yxyxL ?? ????????miii yxyxL11 ),(??yxyx?????? ?1KMeans 算法 令 d為兩個實例的距離度量 . 選擇 k 個隨機樣例 {s1, s2,… sk} 作為種子 . 直到聚類收斂或滿足停止策略 : 對每個樣例 xi: 將 xi 分配到 cj ， d(xi, sj) 是最小的 . (Update the seeds to the centroid of each cluster) 對每個類 cj sj = ?(cj) K Means 舉例 (K=2) Pick seeds Reassign clusters Compute centroids x x Reasssign clusters x x Compute centroids Reassign clusters Converged! 種子的選擇 ? 聚類結(jié)果與隨機種子的選擇是相關(guān)的 ? 隨機選擇的種子可能會導(dǎo)致收斂很慢或者收斂到局部最優(yōu) ? 采用啟發(fā)式方法或其他方法選擇好的種子 Buckshot 算法 ? 層次聚類和 K均值 ? 首先隨機選擇 n1/2 大小的語料 ? 在這些樣例上運行 HAC ? 利用 HAC的結(jié)果做為 K均值的種子 ? 該方法避免了不良種子的選取 文本聚類 ? HAC 和 KMeans可以直接應(yīng)用于文本中 . ? 典型的使用歸一化、基于 TF/IDF權(quán)重的向量以及余弦相似度 . ? 應(yīng)用 : ? 在檢索階段，加入同一類別的其他文本作為初始檢索結(jié)果，提高召回率 . ? 檢索結(jié)果進行聚類，可以提供給用戶更好的組織形式 ? 自動生成的層次聚類結(jié)果為用戶提供方便，根據(jù)聚類結(jié)果生成文摘等 半監(jiān)督學(xué)習(xí) ? 對于有監(jiān)督的分類，生成標(biāo)注的訓(xùn)練語料代價很大 . ? Idea: 用無標(biāo)記的數(shù)據(jù)幫助有監(jiān)督分類 . ? 通過用標(biāo)注和未標(biāo)注的語料訓(xùn)練 EM，在半監(jiān)督模式中應(yīng)用 . ? 用已標(biāo)注的數(shù)據(jù)子集訓(xùn)練初始的模型 . ? 用戶已標(biāo)注的數(shù)據(jù)在迭代過程中不再改變 . ? 無指導(dǎo)的數(shù)據(jù)標(biāo)注在迭代過程中被重新標(biāo)注 . 半監(jiān)督學(xué)習(xí)舉例 ? 假設(shè) “ quantum” 出現(xiàn)在標(biāo)為物理的文檔中，但是 “ Heisenberg”（海森堡） 沒有出現(xiàn)在標(biāo)注的數(shù)據(jù)中 . ? 從標(biāo)注的數(shù)據(jù)中學(xué)到 “ quantum” 是物理文檔的標(biāo)示 . ? 標(biāo)注無監(jiān)督數(shù)據(jù)時，將出現(xiàn) “ quantum” 和 “ Heisenberg”的文檔標(biāo)為物理類 . ? 在進行訓(xùn)練時，可以學(xué)到 “ Heisenberg” 也是物理類文檔的標(biāo)示 . ? 最后學(xué)到的模型可以正確地將僅包含 “ Heisenberg” 的文檔劃為物理類 . 本章小結(jié) ? 介紹了文本分類和聚類的概念 ? 介紹了幾種特征提取的方法 ? 介紹了貝葉斯， KNN及決策樹分類方法 ? 介紹了層次聚類和非層次聚類的方法
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1