（計(jì)算機(jī)軟件與理論專業(yè)論文）基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn).pdf

摘要 隨著i n t e r n e t 技術(shù)的發(fā)展 各種網(wǎng)絡(luò)應(yīng)用服務(wù)越來越多 其中 網(wǎng)絡(luò)中廣 泛使用的電子郵件正成為一種快捷而經(jīng)濟(jì)的通信手段 如何面對(duì)每天各種各樣 種類繁多的郵件 就成為一個(gè)迫切要解決的問題 以前的郵件分類系統(tǒng) 由于郵件的主要部分是文本 因此研究方向主要是基 于數(shù)據(jù)挖掘中的文本分類技術(shù)的 但是 這類方法主要有兩點(diǎn)不足 第一就是分 類技術(shù)首先要指定各個(gè)分類的類別 同時(shí) 要形成準(zhǔn)確的結(jié)果 都需要事先進(jìn)行 大量的學(xué)習(xí)樣本用例的過程 第二就是現(xiàn)有的郵件分類系統(tǒng)只是考慮到郵件的正 文 而沒有考慮到郵件的其他特征 因此本文提出了基于文本聚類技術(shù)的郵件分類系統(tǒng) 它通過采用基于文本聚 類的算法來對(duì)郵件進(jìn)行分類 同時(shí) 本系統(tǒng)還結(jié)合了郵件的一些特性來提高聚類 效果 這樣就可以有效的改進(jìn)上面的兩種缺陷 在本文中 本文圍繞這種郵件聚 類模型來介紹其中的相關(guān)的關(guān)鍵技術(shù)與方法 其中主要的內(nèi)容有 通過使用改進(jìn) 的向量空間模型 v s m 方法在計(jì)算機(jī)中表示文本 在特征項(xiàng)的選擇上使用單詞 權(quán)技術(shù) 在郵件相似度計(jì)算中加入了非郵件正文文本信息的相似度 在聚類算法 選擇上 將兩種算法相結(jié)合以適應(yīng)郵件聚類等等 此外 本文還在此理淪基礎(chǔ)上 進(jìn)行了實(shí)際的實(shí)驗(yàn)分析 證明了這個(gè)理論的正確性 關(guān)鍵詞 郵件分類 文本聚類 向量空間模型 v s m 層次聚類法 k m e a n s a b s t r a c t w t ht h ed e v e l o p m e n to fi n t e r n e tt e c h n o l o g y v a r i o u sk i n d so fn e t w o r k a p p l i c a t i o ns e r v i c e sw e l l e du p a m o n g t h e m t h ee m a i lu s e de x t e n s i v e l yi nt h e n e t w o r ka n di ti s b e c o m i n g ak i n do fs w i f ta n de c o n o m i cc o m m u n i c a t i o n m e a n st h e p r o b l e ma b o u th o w t 0m a n a g ev a r i o u se m a i l si no u rd a i l yl i f eh a s t ob es o l v e du r g e n t l y b e c a u s et h em a i np a r to ft h ee m a i lw a sat e x t s ot h ec l a s s i f i c a t i o n s y s t e m o fe m a i li nt h ep a s ti s m a i n l yb a s e d o nt h et e c h n o l o g yo ft e x t c l a s s i f i c a t i o n h o w e v e r t h i sk i n do fm e t h o dl a s t st w oi n s u f f i c i e n t t h ef i r s ti st h e c l a s s i f i c a t i o nt e c h n o l o g ys h o u l da p p o i n te a c hc l a s s i f i c a t i o nf i r s t m e a n w h i l e i n o r d e rt of o r mt h ea c c u r a t er e s u l t s i ta l ln e e dt oc a r r yo nal a r g en u m b e r s a m p l e st os t u d y t h e s e c o n di st h a tt h ee x i s t i n gc l a s s i f i c a t i o n s y s t e mo f e m a i lo n l yc o n s i d e r st h et e x ta n dd i d n l tc o n s i d e ro t h e rc h a r a c t e r i s t i c so ft h e e m a i l s ow e p u tf o r w a r dt h ec l a s s i f i c a t i o ns y s t e mo fe m a i lb a s e do nc l u s t e r s t e c h n o l o g y o ft h et e x t t h i ss y s t e mu s et h ea l g o r i t h mb a s e do nt e x tc l u s t e r i n g t oc l a s s i f yt h ee m a i l m e a n w h i l e i ta l s oc o m b i n e ds o m ea d d i t i o n a lp r o p e r t i e s o ft h ee m a i lt o i m p r o v ec l u s t e r sr e s u l t 8 0t w ok i n d so fd e f e c t sm e n t i o n e d a b o v ec a nb ei m p r o v e d t h ep a p e ri n t r o d u c e dr e l e v a n tk e yt e c h n o l o g ya n d m e t h o da r o u n dl h i sk i n do fc l u s t e r sm o d e l a n dt h em a i nc o n t e n ta r e u s e i m p r o v e d v e c t o r s p a c em o d e l v s m m e t h o dt oe x p r e s st h e 培塒i nt h e c o m p u t e r u s et h ew o r ds t r e n g t h0 n s t e c h n o l o g yi nt h e f e a t u r es e l e c t i o n a d d t h ea d d i t i o n a li n f o r m a t i o no fo n ee m a i lw h i l e c a l c u l a t i n gt h es i m i l a r i t yb e t w e e n t h e s ee m a i l s c o m b i n et w ok i n d so fa l g o r i t h m si no r d e rt o a d a p tt oe m a i l c l u s t e r e t c i na d d i t i o n w eh a v ea l s oc a r r i e do nr e a j e x p e r i m e n t a la n a l y s i s o nt h eb a s i so ft h i st h e o r y t h er e s u l th a v ep r o v e dt h ee x a c t n e s so ft h i st h e o r y k e y w o r d s e m a i lc l a s s i f i c a t i o n t e x tc l u s t e r i n g v e c t o rs p a c em o d u l e v s m h i e r a r c h i c a lm e t h o d k m e a n s 河海大學(xué)碩士學(xué)位論文 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 第一章緒論 1 1 研究郵件分類的背景和意義 隨著i n t e m e t 技術(shù)的發(fā)展 各種網(wǎng)絡(luò)應(yīng)用服務(wù)越來越多 其中 網(wǎng)絡(luò)中廣泛 使用的電子郵件 e m a i l 正成為一種快捷而經(jīng)濟(jì)的通信手段 然而 面對(duì)每天各 種各樣 種類繁多的郵件 其中包括各種垃圾郵件 j u n ke m a i l 所謂垃圾郵件 就是那些接收者并不愿意收到的大量的無聊的郵件 垃圾郵件的來源主要有以下 幾個(gè)方面 商業(yè)廣告 站點(diǎn)宣傳 某些網(wǎng)絡(luò)雜志 連環(huán)信的e m a i l 版 還有一 些政治宣傳或者淫穢的內(nèi)容 如何有效的對(duì)這些郵件分類處理 是擺在人們眼前 的問題 如果處理不當(dāng) 會(huì)嚴(yán)重的浪費(fèi)了人力 物力 和財(cái)力 在以往 對(duì)電子郵件進(jìn)行過濾是以往常用的對(duì)付垃圾郵件的手段 市場(chǎng)上也 有一些商業(yè)化的軟件再進(jìn)行銷售 但是由于現(xiàn)在垃圾郵件的制造手段越來越狡 猾 隱蔽 一些傳統(tǒng)的郵件過濾手段已經(jīng)不能應(yīng)對(duì)這種新的垃圾郵件了 漏判 誤判的事情時(shí)有發(fā)生 同時(shí) 在日常的生活中 尤其是商業(yè)應(yīng)用中 人們對(duì)待郵 件的態(tài)度是寧可多閱讀垃圾郵件 也不能錯(cuò)過一封重要的郵件 如何與時(shí)俱進(jìn) 應(yīng)對(duì)這種新的形勢(shì) 本文提出了郵件分類的概念 1 2 問題描述 郵件分類的方法 可以將其分為人工分類和自動(dòng)分類兩大類 人工分類 組 織結(jié)構(gòu)清晰 分類精度高 服務(wù)質(zhì)量好 但是人工分類耗時(shí) 耗力 耗錢 難以 及時(shí)更新 尤其是隨著現(xiàn)代信息社會(huì)的發(fā)展 知識(shí)經(jīng)濟(jì)時(shí)代的到來 人工分類遠(yuǎn) 遠(yuǎn)不能滿足現(xiàn)代社會(huì)信息的需求 因此必須要發(fā)展自動(dòng)分類技術(shù) 郵件自動(dòng)分類是指計(jì)算機(jī)根據(jù)郵件的內(nèi)容 將其自動(dòng)歸到一個(gè)或者幾個(gè)類別 中去 這些郵件的來源是多種多樣的 有私人信件 新聞信件 娛樂信件 垃圾 信件等等 郵件的類別和數(shù)量可以是預(yù)先預(yù)定好的 也可以是不確定的 要經(jīng)過 郵件的自組織 聚類后才能得到 需要預(yù)先定義類別體系的郵件分類稱為有指導(dǎo) s u p e r v i s e d 的分類 也稱自動(dòng)歸類 類別體系不確定的郵件分類稱為無指導(dǎo) u n s u p e r v i s e d 的分類 也稱自動(dòng)聚類 自動(dòng)歸類的一般做法是 預(yù)先確定好郵 件類別 并且對(duì)每個(gè)郵件類別提供一批預(yù)先分好類的郵件 稱為訓(xùn)練文本集 類 系統(tǒng)先通過訓(xùn)練文本集學(xué) j l e a r n i n g 分類知識(shí) 在實(shí)際分類時(shí) 再根據(jù)學(xué)習(xí)到 的分類知識(shí)為需要分類的文本確定 個(gè)或者多個(gè)文檔類別 自動(dòng)聚類是指文本聚 類 c l u s t e r i n g 即對(duì)給定的待分類郵件集利用聚類方法將其劃分為多個(gè)類別 自 口j 薄大學(xué)壩士學(xué)位論文 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 動(dòng)聚類系統(tǒng)不需要訓(xùn)練郵件 劃分出的文檔類也是不確定的 本文研究的郵件自 動(dòng)分類是無指導(dǎo)的歸類 也就是對(duì)郵件進(jìn)行聚類 根據(jù)需要不同 標(biāo)準(zhǔn)不同 目 的不同 可以設(shè)計(jì)不同的類別體系 對(duì)于計(jì)算機(jī)進(jìn)行的郵件自動(dòng)分類 要求各類 郵件之間具有一定的區(qū)分度 類別體系確定以后 如何將郵件劃分到各個(gè)類別中呢 分類系統(tǒng)可以有兩 種 基于知識(shí)工程的分類系統(tǒng) 基于統(tǒng)計(jì)的分類系統(tǒng) 人在進(jìn)行分類時(shí) 可 以通過人腦所具有的抽象思維能力來理解文本內(nèi)容 達(dá)到郵件分類的目的 人類 所做的郵件分類是一種基于篇章理解的分類 知識(shí)工程的方法主要依賴語(yǔ)言學(xué)知 識(shí) 需要編制大量的推理規(guī)則作為分類知識(shí) 由于自然語(yǔ)言的復(fù)雜性以及知識(shí)庫(kù) 的嚴(yán)重不足 目前采用計(jì)算機(jī)來做篇章理解 還遠(yuǎn)遠(yuǎn)未能達(dá)到理解各種各樣真實(shí) 文本的水平 相比之下 統(tǒng)計(jì)方法由于其相對(duì)簡(jiǎn)單的機(jī)制 以及在實(shí)際環(huán)境中所 表現(xiàn)出來的良好性能 而為大多數(shù)文檔分類系統(tǒng)所采用 利用統(tǒng)計(jì)學(xué)方法實(shí)現(xiàn)文 檔分類具有速度快 實(shí)現(xiàn)簡(jiǎn)單等特點(diǎn) 且分類準(zhǔn)確度也較高 能夠滿足一般應(yīng)用 的要求 基于統(tǒng)計(jì)的分類方法具有如下特點(diǎn) 忽略郵件的語(yǔ)言學(xué)結(jié)構(gòu) 把郵 件文本作為特征項(xiàng)集合對(duì)待 利用加權(quán)特征項(xiàng)構(gòu)成向量作為郵件文本表示 根據(jù)詞頻信息對(duì)郵件文本特征進(jìn)行加權(quán) 因此 需要通過各種方法找出真實(shí)出口件 文本的一些可量化特性來描述各個(gè)郵件文本類別的特征 并以此作為分類的依 據(jù) 至此 郵件自動(dòng)分類問題可以被看作一種特定的模式識(shí)別問題 真實(shí)郵件文 本所反映出的文本類別特征可以看作一種待識(shí)別的模式 以郵件文本為研究對(duì)象 的模式識(shí)別所要研究的內(nèi)容主要有以下幾點(diǎn) 郵件可量化特征的選取 郵件特征 的量化以及對(duì)郵件特征的分類 聚類決策方法 或分類 聚類算法 1 3 郵件分類技術(shù)在國(guó)內(nèi)外的發(fā)展 1 3 1 特征表示與特征提取 特征表示是指以一定特征項(xiàng) 如詞條或描述 來代表文檔 在郵件文本挖掘時(shí) 只需對(duì)這些特征項(xiàng)進(jìn)行處理 從而實(shí)現(xiàn)對(duì)非結(jié)構(gòu)化的郵件文本的處理 這是 個(gè)非 結(jié)構(gòu)化向結(jié)構(gòu)化轉(zhuǎn)化的處理步驟 特征表示的構(gòu)造過程就是挖掘模型的構(gòu)造過 程 特征表示模型有多種 常用的有布爾邏輯型 b o o l e a nm o d e l 概率型 p r o b a b i l i s t i cm o d e l 向量空間型 v e c t o rs p a c em o d e l 簡(jiǎn)稱v s m 等 這些模型 從不同的角度出發(fā) 使用不同的方法處理特征加權(quán) 類別學(xué)習(xí)和相似計(jì)算等問題 其中應(yīng)用較多的則是向量空間模型 v e c t o rs p a c e m o d e l 在文本處理中 常用的文本特征提取方法有 文檔頻率 d o c u r n e n tf r e q u e n c y l 信思增益 i n f o r m a t i o ng a i n 互信息 m u t u a l i n f o r m a t i o n 單詞權(quán) 文本證據(jù)權(quán) 河海大學(xué)碩士學(xué)位論文基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 優(yōu)勢(shì)率等 1 3 2 分類決策方法 目前的分類決策方法 或分類算法 主要采用的是分類技術(shù) 而沒有使用聚類 技術(shù) 由于郵件的正文是非結(jié)構(gòu)化的文本文件 因此 目前郵件分類方法大部分 采用的就是文本分類方法 主要是現(xiàn)在常見的有貝葉斯分類法 1 和r o c c h i o a p p r o a c h b o o s t i n g z 等基于指導(dǎo)分類的方法 目前絕大部分的郵件分類器主要使 用的是基于文本數(shù)據(jù)挖掘的方法 而在其中大部分又是使用的貝葉斯分類法及其 改進(jìn)的算法 樸素貝葉斯分類器是一個(gè)簡(jiǎn)單 有效而且在實(shí)際使用中很成功的分 類器 其性能可以與判定樹與神經(jīng)網(wǎng)絡(luò)分類算法相媲美 3 在某些場(chǎng)合還優(yōu)于其 他分類器 然而 和其他的基于指導(dǎo)分類的郵件分類系統(tǒng)一樣 要形成準(zhǔn)確的結(jié) 果 都需要事先進(jìn)行大量的學(xué)習(xí)樣本用例的過程 由于郵件發(fā)送者以及郵件種類 的不停變化 為了保持分類的精度 系統(tǒng)還必須經(jīng)常學(xué)習(xí) 因此 就必須要尋找 一種靈活性的分類方法 采用文本聚類的方法來處理郵件 就可以達(dá)到這種目的 聚類不需要人們指定數(shù)據(jù)樣本和指定分類 它根據(jù)文檔內(nèi)容的相似度來自動(dòng)分 類 因此 使用了基于聚類方法的郵件處理系統(tǒng)后 能提高處理速度 縮短處理 時(shí)間 1 4 本文主要的工作內(nèi)容 本文對(duì)基于聚類技術(shù)的郵件分類系統(tǒng)中所涉及的各項(xiàng)技術(shù)進(jìn)行了全面的論 述 并根據(jù)電子郵件自身的特點(diǎn)提出了結(jié)合除了郵件正文外的相關(guān)信息與郵件正 文相結(jié)合的郵件聚類系統(tǒng) 以提高郵件聚類的效果 最后 本文通過對(duì)上述實(shí)現(xiàn)技術(shù)的闡述及其對(duì)試驗(yàn)結(jié)果的分析 提出了一些 關(guān)于郵件分類研究的見解 并對(duì)今后的研究工作進(jìn)行了展望 1 5 本文組織 第一章緒論 介紹了本文的研究背景以及主要工作和論文組織 第二章向量空間模型及相關(guān)技術(shù) 介紹本文采用的特征表示的方法一向量 空間模型以及特征項(xiàng)的抽取等相關(guān)技術(shù) 第三章聚類學(xué)習(xí)算法 對(duì)現(xiàn)有的聚類技術(shù)相關(guān)方面進(jìn)行了詳細(xì)的描述與研 究 第四章基于文本聚類技術(shù)的郵件分類技術(shù) 介紹了自己如何結(jié)合郵件的特 點(diǎn)來構(gòu)建基于文本聚類技術(shù)的郵件分類系統(tǒng) 河海人學(xué)碩士學(xué)位論文基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 第五章系統(tǒng)評(píng)測(cè) 介紹如何對(duì)自己的系統(tǒng)的實(shí)驗(yàn)結(jié)果的評(píng)測(cè)以及最后的實(shí) 驗(yàn)結(jié)果 最后 第六章對(duì)本文的工作做了總結(jié)與展望 河海大學(xué)碩士學(xué)位論文基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 第二章向量空間模型及相關(guān)技術(shù) 2 1 文本的表示 計(jì)算機(jī)并不具有人類的智能 人在閱讀文章后 根據(jù)自身的理解能力可以產(chǎn) 生對(duì)文章內(nèi)容的模糊認(rèn)識(shí) 而計(jì)算機(jī)并不能輕易地 讀懂 文章 從根本上說 它只認(rèn)識(shí)0 和1 所以必須將文本轉(zhuǎn)換為計(jì)算機(jī)可以識(shí)別的格式 根據(jù) 貝葉 斯假設(shè) 假定組成文本的字或詞在確定文本類別的作用上相互獨(dú)立 這樣可以 就使用文本中出現(xiàn)的字或詞的集合來代替文本 不言而喻 這將丟失大量關(guān)于文 章內(nèi)容的信息 但是這種假設(shè)可以使文本的表示和處理形式化 并且可以在文本 分類中取得較好的效果 目前 信息檢索的概念被提出后 出現(xiàn)了許多基于文檔 o c u r n e n t 平u 查詢 f q u e r y 之間的文本計(jì)算模型 具有代表性的有布爾模型 b o o l e a nm o d e l 向量 空間模型 v e c t o rs p a c em o d e l 簡(jiǎn)稱v s m 概率模型 p r o b a b i l i s t i cm o d e l 等 這些模型從不同的角度出發(fā) 使用不同的方法處理特征加權(quán) 類別學(xué)習(xí)和相似計(jì) 算等問題 這幾種模型中 向量空間模型是最簡(jiǎn)便有效的文本表示模型之一 向量空間 模型是s a l t o n 6 等人于6 0 年代末首先提出的 并在著名的s m a r t s y s t e m f o rt h e m a n i p u l a t i o na n dr e t r i e v a lo ft e x t 系統(tǒng)得到成功的應(yīng)用從此以后 該模型及其相 關(guān)技術(shù) 包括項(xiàng)的選擇 加權(quán)策略 以及采用相關(guān)反饋進(jìn)行優(yōu)化查詢等在文本分 類 自動(dòng)索引 信息檢索等許多領(lǐng)域得到廣泛的應(yīng)用 特別是隨著網(wǎng)上信息的迅 速膨脹 還被廣泛地應(yīng)用到搜索引擎 個(gè)人信息代理 網(wǎng)上新聞發(fā)布等信息檢索 領(lǐng)域新的應(yīng)用中 并且取得了較好的效果 2 2 向量空間模型 1 文檔 d o c u m e n t 泛指一般的文本或者文本中的片段 段落 句群或句子 一般指一篇文章 盡管文檔可以是多媒體對(duì)象 但是以下討論中本文只認(rèn)為是文 本對(duì)象 文本與文檔不加以區(qū)別 2 項(xiàng) t e r r a 文本的內(nèi)容特征常常用它所含有的基本語(yǔ)一言單位 字 詞 詞組或短語(yǔ)等 來表示 這些基本的語(yǔ)言單位被統(tǒng)稱為文本的項(xiàng) 即文本可以用 項(xiàng)集 t e r m l i s t 表示為d t l f 2 r 3 其中 是項(xiàng) 1 k 審n 3 項(xiàng)的權(quán)重 t e 皿w e i g h t 對(duì)于含有n 個(gè)項(xiàng)的文本d t 1 毛 屯 吒 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 項(xiàng) 常被賦予一定的權(quán)重 表示它們?cè)谖谋綿 中的重要程度 即d d r 簡(jiǎn)記為d d w 2 w 3 這時(shí)說項(xiàng) 的 權(quán)重為 l k n 4 向量空間模型 v s m 給定一文本d d w l 2 f 3 w 3 t 嵋 由于f 在文本中既可以重復(fù)出現(xiàn)又應(yīng)該又先后次序的關(guān)系分析起來仍有 定的 難度 為了簡(jiǎn)化分析 可以暫時(shí)不考慮k 在文檔中的先后順序并要求 互異 這 時(shí)可以把 乞 乞 看成一個(gè)n 維的坐標(biāo)系 而w 1 心 w 為相 應(yīng)的坐標(biāo)值 因而d d 心 m 被看成是n 維空間中的一個(gè)向量 稱d d m 為文本d 的向量表示 5 相似度 s i m i l a r i t y 兩個(gè)文本d 1 和d 2 之間的 內(nèi)容 相關(guān)程度 d e g r e eo f r e l e v a n c e 常常用它們之間的相似度s i r e d 1 d 2 來度量 當(dāng)文本被表示為向量 空間模型時(shí) 可以借助于向量之間的某種距離來表示文本間的相似度 常用向量 之間的內(nèi)積進(jìn)行計(jì)算 s i m d 1 d 2 w l t 4 w 2 t 2 1 t l 或者用夾角余弦值來表示 8 i 如圖 2 1 所示 s i m d 1 d 2 c o s 0 2 2 圖 2 1 文本的向量空間模型 v s m 以及文本間的相似度s i m d 1 d 2 6 一 河海人學(xué)碩士學(xué)位論文基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 2 3 項(xiàng)的選擇 如前所述 項(xiàng)可以是文本中的各種語(yǔ)言單位 特別是對(duì)中文來說有字 詞 短語(yǔ) 甚至是句子或旬群等更高單位 4 j 為了簡(jiǎn)便起見 本系統(tǒng)暫時(shí)不考慮中 文的項(xiàng)的情況 項(xiàng)也可以是相應(yīng)詞語(yǔ)或者短語(yǔ)的語(yǔ)義概念類 因此 項(xiàng)的選擇 只能由處理速度 精度 存儲(chǔ)空間等方面的具體要求來決定 選出的項(xiàng)越具有代 表性 語(yǔ)言層次越高 所包含的信息就越豐富 但是分析的代價(jià)就越大 而且受 分析精度 如句法分析的正確率 的影響就越大 由于詞匯是文本最基本的表示 項(xiàng) 在文本中的出現(xiàn)頻度較高 呈現(xiàn)一定的統(tǒng)計(jì)規(guī)律 再考慮到處理大規(guī)模真實(shí) 文本所面臨的困難 選擇詞或者短語(yǔ)作為特征項(xiàng)是比較合理的 常常被應(yīng)用于文 本檢索與分類領(lǐng)域 但是直接選用文本中的詞或者詞組作為文本特征項(xiàng)時(shí)也會(huì)出 現(xiàn)以下問顆 1 文本中存在一些沒有實(shí)在意義但使用頻率很高的虛詞和功能詞 如英語(yǔ) 中的 t h e a o f 等 常常把一些真正由分類作用的實(shí)詞淹沒掉 解決這 個(gè)問題的方法是把這些詞組織成一個(gè)禁用詞表 去除停用詞 合并數(shù)字和人名等 詞匯 把禁用詞表中的詞從特征集中濾掉 去除停用詞 合并數(shù)字和人名等詞匯 此外 還可以在文本預(yù)處理時(shí)進(jìn)行詞性標(biāo)注 從詞匯特征集中濾去那些對(duì)特 征區(qū)別貢獻(xiàn)極小的大部分虛詞和功能詞 2 一詞多義或詞匯變形問題 事實(shí)上 自然語(yǔ)言有著極為豐富的語(yǔ)言現(xiàn)象 例如詞匯之間的關(guān)系 就有同義關(guān)系 近義關(guān)系 從屬關(guān)系 關(guān)聯(lián)關(guān)系等等 在 使用短語(yǔ)等復(fù)合詞時(shí)關(guān)系就更加復(fù)雜了 另外詞匯的歧義和多義也很普遍 例如 c o n s o l eaf r i e n di ng r i e f c o n s o l e 意義為安慰 l o g i ni n t oo n ec o n s o l e 這里 的c o n s o l e 指的是計(jì)算機(jī)中的終端 因此 不同的詞義當(dāng)作不同的項(xiàng)來看待會(huì)更 合理 詞匯變形問題主要是指西文單詞有復(fù)雜地詞尾變化和派生現(xiàn)象 解決這些 問題常有兩種辦法 第一種是進(jìn)行概念語(yǔ)義標(biāo)注 以便把同義的或相似的特征項(xiàng) 合并為相應(yīng)的概念類 對(duì)于西文 可以通過特別的抽取詞千處理 把同源的詞用 同一個(gè)詞干來標(biāo)記 顯然 通過概念標(biāo)注并利用概念信息作為文本的特征項(xiàng)比單 純的詞匯信息更能反映文本的內(nèi)容 因此 詞義相同或者詳盡的詞匯往往被映射 為同一個(gè)概念 而同一詞匯所表示的詞義也是和上下文相關(guān)的 把詞匯在具體的 上下文中所對(duì)應(yīng)的概念作為文本的描述項(xiàng) 那么內(nèi)容相似而僅在用詞上有較大差 異的文章 彼此之間的相似度就會(huì)大大增加 所以采用概念作為特征項(xiàng)是比較合 理的 但是這樣做的同時(shí)勢(shì)必加大了文本處理的復(fù)雜程度 7 u 腳凡學(xué)砸卜學(xué)位論文 基于文本聚糞技術(shù)的郵件分類系寶覓的研究 j 實(shí)現(xiàn) 2 4 項(xiàng)的權(quán)重計(jì)算 在v s m 中 給每個(gè)項(xiàng)賦上權(quán)重時(shí) 應(yīng)使文本中越重要的項(xiàng)權(quán)重越大 種方 法是由專家或者用戶根據(jù)自己的經(jīng)驗(yàn)與所掌握的領(lǐng)域知識(shí)人為的賦上權(quán)值 這種 辦法隨意性很大 而且效率也很低 很難適用于大規(guī)模真實(shí)文本的處理 另一種 辦法是運(yùn)用統(tǒng)計(jì)的方法 也就是用文本的統(tǒng)計(jì)信息 如詞頻 詞之間的同現(xiàn)頻率 等 來計(jì)算項(xiàng)的權(quán)重 目前被廣泛采用的權(quán)重計(jì)算公式是t f i d f 公式 7 陽(yáng) 絲絲墮壘絲竺 望i 2 3 耐礦 孑 l o g n n 0 0 1 r 其中 f 廳 為詞 在文本孑中的權(quán)重 而t f t 孑 為詞f 在文本西 中的詞頻 為文本的總數(shù) 門 為文本集中出現(xiàn)f 的文本數(shù) 分母為歸一化因 子 這種公式是根據(jù)香農(nóng)信息學(xué)理論 如果項(xiàng)在所有文本中出現(xiàn)的頻率越高 那 么它所包含的信息嫡就越少 如果項(xiàng)的出現(xiàn)較為集中 只在少量文本中有較高的 出現(xiàn)頻率 那么它就會(huì)擁有較高的信息嫡 上述公式就是基于這個(gè)思想的一種實(shí) 現(xiàn) 同時(shí) 由于考慮到文本長(zhǎng)度的對(duì)權(quán)值的影響 這個(gè)公式還對(duì)項(xiàng)權(quán)值公式做歸 一化處理 這樣就可以將各項(xiàng)權(quán)值規(guī)范到 o 1 之問 另外 對(duì)于特征較為明顯的文本類別 往往有少數(shù)項(xiàng)的出現(xiàn)頻率數(shù)遠(yuǎn)遠(yuǎn)大于 其他項(xiàng) 根據(jù)上述計(jì)算公式計(jì)算出的權(quán)值會(huì)很高 如果個(gè)別項(xiàng)的權(quán)值很高 在分 類過程中往往會(huì)抑制其他項(xiàng)的作用 因此在計(jì)算各項(xiàng)權(quán)重時(shí) 應(yīng)對(duì)統(tǒng)計(jì)出的詞頻 做適當(dāng)?shù)木馓幚?較為簡(jiǎn)單的均衡處理方法是對(duì)統(tǒng)計(jì)出的權(quán)值進(jìn)行開平方 經(jīng) 過詞頻均衡處理的權(quán)值計(jì)算公式為 w t d 絲絲 塑絲 竺蘭 塑 24 2 2 l q j 撇孑 1 0 9 n 氌 0 0 1 丁 該公式中參數(shù)的含義與上式相同 權(quán)重的計(jì)算只能視具體情況而定 至今仍沒有普遍使用的 最優(yōu)公式 另 外 前面的討論中項(xiàng)的權(quán)值一般為正 其實(shí)權(quán)值也可以取負(fù)值 用來描述某用戶 厭棄某特征 t f i d f 公式是一種經(jīng)驗(yàn)公式 并沒有堅(jiān)實(shí)的理論基礎(chǔ) 但是 多 年的實(shí)驗(yàn)表明 上述公式是文本處理中的一個(gè)有效工具 事實(shí)上 這一公式不僅 在信息檢索中得到了成功應(yīng)用 它對(duì)子其他文本處理領(lǐng)域 如信息分發(fā) 信息過 濾和文本分類也有很好的借鑒意義 本文研究的郵件自動(dòng)聚類系統(tǒng)也是以它作為 文本表示模型而實(shí)現(xiàn)的 河海大學(xué)碩士學(xué)位論文 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 2 5 特征項(xiàng)的抽取 特征抽取是從一組特征中選出一部分最有代表性的特征 5 特征抽取在文本 分類中起著重要的作用 能夠起到降低向量空間維數(shù) 簡(jiǎn)化計(jì)算 防止過分?jǐn)M合 等作用 1 0 由于特征子集的數(shù)量和特征數(shù)量之間是指數(shù)的關(guān)系 枚舉幾乎是不可 能的 因此本文中假設(shè)特征之間是獨(dú)立的 這樣特征子集的抽取就轉(zhuǎn)化特征項(xiàng)的 抽取 及根據(jù)某個(gè)特征評(píng)估函數(shù)計(jì)算各個(gè)特征的評(píng)分值 然后按評(píng)分值排序 選 取若干個(gè)評(píng)分最高的作為特征詞 這就是特征提取 國(guó)際上在特征選擇方面進(jìn)行了大量的工作 其中c 州的y a n gy i m i n g 教授和 s t a n f o r d 的m e h r as a h a m i 的論點(diǎn)較具代表性和總結(jié)性 特別在y a n g 的論文中 她對(duì)現(xiàn)有的許多特征選擇方法做了總結(jié)和歸納 她的實(shí)驗(yàn)表明 特征選擇的主要 功能是在不損傷分類精度的情況下盡量減少要處理的單詞數(shù) 以此來降低向量空 間維數(shù) 從而提高分類工作的速度和效率 因此 特征選擇對(duì)提高分類精度來說 即使是有幫助 但是對(duì)不同的分類器所起的效果不同 在文本處理中 常用的文本特征選擇方法有 文檔頻率 d o c u m e n t f r e q u e n c y 信息增益 i n f o r m a t i o ng a i n 互信息 m u t u a li n f o r m a t i o n z 2 統(tǒng)計(jì)量 c h i 期望交叉熵 文本證據(jù)權(quán) 單詞權(quán)等1 1 1 1 2 1 3 2 9 這些方法的基 i 本思想都是對(duì)每一個(gè)特征 在這里是詞 計(jì)算某種統(tǒng)計(jì)度量值 然后設(shè)定一個(gè)閾 值t 把度量值小于t 的那些特征過濾掉 剩下的即認(rèn)為是有效特征 下面簡(jiǎn)單 的介紹一下文檔頻率 信息增益 互信息 單詞權(quán)的計(jì)算方法 對(duì)于特征詞t 各種選擇標(biāo)準(zhǔn)的含義如下 1 文檔頻數(shù) d o c u m e n tf r e q u e n c y 即是特征t 在文本集中出現(xiàn)的文檔數(shù) 它是最簡(jiǎn)單的評(píng)估函數(shù) 其值為 訓(xùn)練集合中該單詞發(fā)生的文本數(shù) d f 的缺點(diǎn)是稀有單詞可能在某一類文本中 并不稀有 也可能包含著重要的判斷信息 簡(jiǎn)單地舍棄 可能影響分類器的 精度 因此 在實(shí)際運(yùn)用中一般并不直接使用d f 2 信息增益 i n f o r m a ti o ng a i n 信息增益 i n f o r m a t i o ng a i n 在機(jī)器學(xué)習(xí)領(lǐng)域被廣泛使用 f 4 i g 考察c 中出現(xiàn)和不出現(xiàn)t 的文檔頻數(shù)來衡量t 對(duì)于c 的信息增益 可以采用如下 的定義式 三一旦 一一 i g t 2 尸0 乞p c jj t l o g p c rir p f p qi t l o g p c l f 2 5 其中戶 c f 表示c 類文檔在語(yǔ)料中出現(xiàn)的概率 p 表示語(yǔ)料中包含詞條 t 的文檔的概率 p qi t 表示文檔包含訶條t 時(shí)屬于c 類的條件概率 河海大學(xué)顧 卜學(xué)位論文 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) p n 表示語(yǔ)料中不包含詞條t 的文檔的概率 j d c jf 表示文檔不包含詞條t 時(shí)屬于c 的條件概率 m 表示類別數(shù) 3 互信息 m u t u a l i n f o r m a ti o n 在統(tǒng)計(jì)學(xué)中 互信息用于表征兩個(gè)變量的相關(guān)性 常被用來作為文本特 征相關(guān)的統(tǒng)計(jì)模型及其相關(guān)的應(yīng)用標(biāo)準(zhǔn) 文本特征t 與類別c 的互信息 m i t c 定義如下 m i t c 1 g 等 26 如果用a 表示包含詞條t 且屬于類別c 的文檔頻數(shù) b 為包含t 但是 不屬于c 的文檔頻數(shù) c 表示屬于c 但是不包含t 的文檔頻數(shù) n 表示語(yǔ) 料中文檔總數(shù) t 和c 的互信息可由下式計(jì)算 m i t c l 8 酉而a x n 2 7 4 單詞權(quán) t s 它和其它的評(píng)估函數(shù)完全不同 與類別信息無關(guān) 首先利用文本向量 間的余弦夾角找出相似度大于 f 限值的文本對(duì) 令 x v 是任意一個(gè)這樣 的文本對(duì) 定義 t s w p y i w x 2 6v s m 的總結(jié) 2 8 向量空間模型的最大優(yōu)點(diǎn)在于它在知識(shí)表示方法上的巨大優(yōu)勢(shì) 在該模型 中 文本內(nèi)容被形式化為多維空間中的一個(gè)點(diǎn) 通過向量的形式給出 把對(duì)文本 內(nèi)容的處理簡(jiǎn)化為向量空間中向量運(yùn)算 使問題的復(fù)雜性大為降低 而權(quán)重的計(jì) 算既可以用規(guī)則的方法手工完成 又可以通過統(tǒng)計(jì)的辦法自動(dòng)完成 便于融合統(tǒng) 計(jì)和規(guī)則兩種方法的優(yōu)點(diǎn) 也正是因?yàn)榘盐谋疽韵蛄康男问蕉x到實(shí)數(shù)域中 才 使得模式識(shí)別和其他領(lǐng)域中的各種成熟的計(jì)算方法得以應(yīng)用 極大提高了自然語(yǔ) 言文本的可計(jì)算性和可操作性 所以說 文本的形式化表示方法一向量空間模型 是基于文本處理的各種應(yīng)用得以實(shí)現(xiàn)的基礎(chǔ)和前提 向量空間模型是一種不考慮特征項(xiàng)出現(xiàn)順序的詞袋 b a go fw o r d s 文本表示 模型 3 2 l 這種模型雖然帶來了計(jì)算和操作上的方便 但是卻損失了大量的文本結(jié) 構(gòu)信息 而這些信息在自然語(yǔ)言中是至關(guān)重要的 如句子中詞序信息等 另外 在權(quán)重和相似度的計(jì)算中也做了許多簡(jiǎn)化工作 一是對(duì)不同的語(yǔ)言單位構(gòu)成的特 河海火學(xué)碩 e 學(xué)位論文基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與宴現(xiàn) 征項(xiàng)大都只考慮其統(tǒng)計(jì)信息并采用統(tǒng)一的權(quán)重計(jì)算方法 而這種計(jì)算只是經(jīng)驗(yàn)公 式并沒有很好的理論基礎(chǔ) 所以計(jì)算出的權(quán)重未必能真實(shí)反映各項(xiàng)的重要性 二 是向量空間模型是建立在所有項(xiàng)兩兩正交這一假設(shè)基礎(chǔ)之上的 沒有考慮特征項(xiàng) 之間的相關(guān)性 對(duì)于自然語(yǔ)言這種有著非常豐富語(yǔ)言現(xiàn)象的研究對(duì)象來說 這種 假設(shè)顯然是過于嚴(yán)格的 不能很好地反映自然語(yǔ)言的特征 目前已經(jīng)有許多改進(jìn) 項(xiàng)權(quán)重計(jì)算的方法 但是效果并不明顯 原因在于語(yǔ)義關(guān)系實(shí)際上是一個(gè)很復(fù)雜 的運(yùn)算 采用簡(jiǎn)單的初等運(yùn)算代替它 誤差勢(shì)必存在 目前 自然語(yǔ)言理解領(lǐng)域的多項(xiàng)試驗(yàn)表明 在以自然語(yǔ)言為研究對(duì)象的知識(shí) 處理和知識(shí)獲取問題中 知識(shí)表示始終是其處理的主要瓶頸 如何確定和彌補(bǔ)現(xiàn) 有文本內(nèi)容映射到特征項(xiàng)時(shí)出現(xiàn)的大量有效信息的損失是自然語(yǔ)言處理領(lǐng)域今 后需要關(guān)注和解決的問題之一 河海大學(xué)顧七學(xué)位論文 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 第三章聚類學(xué)習(xí)算法 聚類 分類是人類認(rèn)識(shí)未知世界的一種重要的認(rèn)知手段 在生產(chǎn)和生活中 人們往往面對(duì)非常復(fù)雜的事和物 如果能夠把相似的東西歸為一類 有明顯區(qū)別 的事物分屬在不同的類別中 處理起來就大為簡(jiǎn)便 所謂 物以類聚 人以群分 說的就是這個(gè)道理 譬如人們將生物分為動(dòng)物和植物 又根據(jù)不同的生理特點(diǎn)將 生物分為不同的門 綱 目 科 屬 種 在化學(xué)理論中 人們根據(jù)不同的化學(xué) 性質(zhì)將各種元素劃分為不同的類別 比如鹵族元素 惰性氣體等等 進(jìn)而總結(jié)出 元素周期率 在社會(huì)學(xué)中 人們還根據(jù)不同的信仰劃分出不同的黨派 宗教等 在原始的分類學(xué)中 人們的分類依據(jù)是經(jīng)驗(yàn)和專業(yè)知識(shí)來進(jìn)行定性分析 很 少使用數(shù)學(xué)工具 隨著人類對(duì)自然和社會(huì)的認(rèn)識(shí)不斷深入 要處理的數(shù)據(jù)量規(guī)模 越來越大 相互關(guān)系也越來越復(fù)雜 分類越來越細(xì) 對(duì)分類的要求也越來越高 這時(shí)僅僅依靠定性分析就不能滿足要求 于是數(shù)學(xué)這個(gè)得力工具被引入 形成了 數(shù)值分類學(xué) 對(duì)分析對(duì)象進(jìn)行定量的研究 由于數(shù)值分類學(xué)中的方法不僅能夠用 于分類 還能用于其他領(lǐng)域 于是人們覺得使用 聚類分析 這個(gè)名稱更為恰當(dāng) 聚類分析的目的是揭示樣本點(diǎn)之間最本質(zhì)的 抱團(tuán)一隆質(zhì) 要想定量地處理 一批樣本點(diǎn) 首先必須對(duì)這些樣本點(diǎn)的性質(zhì)進(jìn)行定量的表示 領(lǐng)域?qū)＜掖_定采用 哪些指標(biāo)特征變量來精確刻畫樣本的性質(zhì) 以及如何定義樣本之間的相似性測(cè) 度 3 1 什么是聚類分析 聚類分析是數(shù)據(jù)挖掘的一項(xiàng)重要功能 而聚類算法是目前研究的核心 聚類 是把一組個(gè)體按照相似性劃分成若干類別 即 物以類聚 它的目的是使得屬 于同一類別的個(gè)體之間的距離盡可能的小 而不同類別的個(gè)體間的距離盡可能的 大 聚類分析就是使用聚類算法來發(fā)現(xiàn)有意義的聚類 它的主要依據(jù)是把相似的 樣本歸為一類 而把差異大的樣本區(qū)分開來 這樣所生成的簇是一組數(shù)據(jù)對(duì)象的 集合 這些對(duì)象與同一個(gè)簇中的對(duì)象彼此相似 而與其他簇中的對(duì)象彼此相異 在許多應(yīng)用中可以把一個(gè)簇中的數(shù)據(jù)對(duì)象當(dāng)作一個(gè)整體來對(duì)待 聚類分析是一種重要的人類行為 很小的時(shí)候人就可以通過不斷的改進(jìn)下意 識(shí)中的聚類模式來學(xué)會(huì)如何區(qū)分不同的動(dòng)物或動(dòng)物和植物 聚類分析已經(jīng)廣泛的 應(yīng)用在許多應(yīng)用中 包括模式識(shí)別 數(shù)據(jù)分析 圖象處理以及市場(chǎng)研究 通過聚 類人們能夠識(shí)別密集和稀疏的區(qū)域 因而發(fā)現(xiàn)全局的分布模式以及數(shù)據(jù)屬性之間 河海大學(xué)碩士學(xué)位論文基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 的有趣的相互聯(lián)系 作為一個(gè)數(shù)據(jù)挖掘的功能聚類分析能作為一個(gè)獨(dú)立的工具來 獲得數(shù)據(jù)分布的情況 觀察每個(gè)簇的特點(diǎn) 集中對(duì)特定的簇做進(jìn)一步的分析 而 且聚類分析可以作為其他算法 如特征和分類等 的預(yù)處理步驟 雖然聚類也可以起到分類的作用 但是它和大多數(shù)分類方法不同 大多數(shù)分 類方法都是演繹的 即人們事先確定某種事物分類的準(zhǔn)則或各類別的標(biāo)準(zhǔn) 分類 的過程就是比較分類的要素與各類別標(biāo)準(zhǔn) 然后將各要素劃歸于各類別中 確定 事物的分類準(zhǔn)則或各類別的標(biāo)準(zhǔn)或多或少帶有主觀的色彩 而聚類分析是歸納 的 不需要事先確定分類的準(zhǔn)則 不知道它們的分類 甚至連分成幾類也不知道 它通過一些計(jì)算來把觀測(cè)進(jìn)行合理的分類 使得同 類的觀測(cè)比較接近 不同類 的觀測(cè)相差較多 這是無指導(dǎo)的學(xué)習(xí) 本文中討論的聚類分析依賴于對(duì)觀測(cè)間的接近程度 距離 或相似程度的理 解 定義不同的距離量度和相似性量度可能產(chǎn)生不同的聚類結(jié)果 3 2 聚類算法涉及的各類型數(shù)據(jù)及預(yù)處理 數(shù)據(jù)挖掘的一個(gè)重要步驟是數(shù)據(jù)準(zhǔn)備 這包括對(duì)選定的數(shù)據(jù)進(jìn)行規(guī)范化 整 合和預(yù)處理等等 這是進(jìn)行數(shù)據(jù)挖掘的前提也同樣是聚類算法能正常實(shí)施的必要 前挺 要對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類 基于統(tǒng)計(jì)方法 其最重要的前提是要計(jì)算各個(gè)數(shù) 據(jù)對(duì)象之間的距離一即文中相異度 聚類算法最常使用的兩種有代表性的數(shù)據(jù)結(jié)構(gòu)為數(shù)據(jù)矩陣和相異度矩陣 數(shù) 據(jù)矩陣一般用p 個(gè)變量 也稱為度量和屬性 來表現(xiàn)n 個(gè)對(duì)象 這種數(shù)據(jù)結(jié)構(gòu)是關(guān) 系表的形式 或看成 p n 個(gè)對(duì)象 p 個(gè)變量 的矩陣 陣 圖 3 1 數(shù)據(jù)矩陣 相異度矩陣存儲(chǔ)n 個(gè)對(duì)象兩兩之間的近似性 表現(xiàn)形式為一個(gè)n n 的矩 一l p p p 加 易 島 一 一 曠 曠 乃 一 一 五 五 瓦 一 一 河海人學(xué)顧 l 學(xué)位論義基于文本聚類技術(shù)的郵件分類系統(tǒng)的酬究與實(shí)現(xiàn) 墊1 od 3100d n2 1 d 2 f d o 2 i d m 1 d j 矩陣中的d i j 表示對(duì)象i 和對(duì)象j 之間的相異性 通常它是一個(gè)非負(fù)的數(shù) 值 當(dāng)對(duì)象i 和對(duì)象j 越相似或接近時(shí)其值越接近0 兩個(gè)對(duì)象越不同其值就越 大 因此有d i j d j f d i f 0 數(shù)據(jù)矩陣通常被稱為二模矩陣 而相異度矩陣稱為單模矩陣 這是因?yàn)榍罢?的行和列代表不同的實(shí)體而后者的行和列代表相同的實(shí)體 實(shí)際中很多聚類算法 是以相異度矩陣為基礎(chǔ)的 相異度是聚類算法的基礎(chǔ) 對(duì)于相異度的估算不同的變量類型有不同的計(jì)算 方式 詳細(xì)的計(jì)算方式在第四章中會(huì)闡述 3 3 現(xiàn)存重要的代表性聚類算法的分析與研究 目前 已經(jīng)提出的聚類算法有很多口 可以在此仔細(xì)分析研究它們的具體性 能 優(yōu)勢(shì)與缺點(diǎn) 明確它們所適合的具體情形 當(dāng)然 這些算法一般都存在這樣 或那樣的不足 對(duì)于一些情況無能為力 因此 在使用這些聚類算法的時(shí)候 必 然要與具體情況相結(jié)合 做出一些相應(yīng)的調(diào)整 一般來說這些算法可以分為如下 的幾類 3 3 1 劃分方法 p a r t i t i o n i n gu e t h o d 給定一個(gè)n 個(gè)對(duì)象或元組的數(shù)據(jù)庫(kù) 一個(gè)劃分方法構(gòu)建數(shù)據(jù)的k 個(gè)劃分 每 個(gè)劃分表示一個(gè)聚簇 并且k 墨n 也就是說它將數(shù)據(jù)劃分為k 個(gè)組 同時(shí)滿足 如下的要求 i 每個(gè)組至少包含一個(gè)對(duì)象 i i 每個(gè)對(duì)象必須屬于且只屬于一個(gè) 組 給定要構(gòu)建的劃分的數(shù)目k 劃分方法首先創(chuàng)建一個(gè)初始劃分 然后采用一 種迭代的重定位技術(shù) 嘗試通過對(duì)象在劃分間的不斷移動(dòng)來改進(jìn)劃分 一個(gè)好的 劃分的一般準(zhǔn)則是 在同一個(gè)類中的對(duì)象之間盡可能的接近或相關(guān) 而不同類中 的對(duì)象之間盡可能的遠(yuǎn)離或不同 實(shí)際上絕大多數(shù)應(yīng)用采用了以下比較流行的啟發(fā)式算法 i k 平均算法 1 在該算法中每個(gè)簇用該簇中對(duì)象的平均值來表示 i i k 中心點(diǎn)算法 在 河海人學(xué)碩上學(xué)位論文 基于文本聚婁技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 該算法中 每個(gè)簇用接近聚類中心的一個(gè)對(duì)象來表示 這些啟發(fā)式聚類方法對(duì)在 中小規(guī)模的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)球狀簇很適用 而且其實(shí)現(xiàn)相對(duì)的簡(jiǎn)單 但是它不能發(fā) 現(xiàn)任意形狀的簇 其參數(shù)k 對(duì)聚類結(jié)果有很大的影響 很影響聚類的質(zhì)量而且這 類算法不具有很好的伸縮性 要對(duì)大規(guī)模的數(shù)據(jù)集進(jìn)行聚類以及處理復(fù)雜形狀的 聚類就要對(duì)基于劃分的方法做進(jìn)一步的擴(kuò)展 如下為當(dāng)前最常用最流行的兩個(gè)經(jīng)典算法的詳細(xì)闡述 1 k 一平均算法 k m e a n s 的具體步驟如下 輸入 簇的數(shù)目k 和包含n 個(gè)對(duì)象的數(shù)據(jù)庫(kù) 輸出 k 個(gè)簇并且使平方誤差準(zhǔn)則最小 i 假設(shè)要聚成k 個(gè)類 由人為決定k 個(gè)類中心z l 1 z 2 1 互 1 2 在第k 次疊代中 樣本集 z 用如下方法分類 對(duì)所有i l 2 k i 若忙一弓 七 i l l z z 硎i 則z 邑 忌 3 令由 2 得到的s 的新的類的平準(zhǔn)值為z 克 1 令 l i z z j k 1 1 2 最小 j 1 2 k c 6 t 則z j k 1 爭(zhēng) z 量 七 中的樣本數(shù) z s 對(duì)于所有的j 1 2 k 若z j 七 1 z 尼 則終止 否則繼續(xù)再?gòu)?第二步開始 圖 3 3 k 平均值法迭代圖例 o 這個(gè)算法嘗試找出使平方誤差函數(shù)值最小的k 個(gè)劃分 當(dāng)結(jié)果簇是密集的 而簇與簇之間區(qū)別明顯時(shí)它的效果很好 但是k 一平均方法只有在簇的平均值被 河海人學(xué)碩士學(xué)位論文基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 定義的情況下才能使用 這可能不適用于某些應(yīng)用 例如涉及分類屬性的數(shù)據(jù) 要求用戶必須事先給出k 要生成的簇的數(shù)目 可以說是該方法最大的缺點(diǎn) 而且 k 一平均方法不適合于發(fā)現(xiàn)非凸面形狀的簇 或者大小差別很大的簇 與此同時(shí)它 對(duì)于 噪聲 和孤立點(diǎn)數(shù)據(jù)很敏感 少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生大的影響 此算法不僅對(duì)參數(shù)k 的選擇很敏感而且對(duì)最初始簇中心的選擇也具有很大的依 賴性 不同的初始類中心選擇可能會(huì)產(chǎn)生不同的聚類結(jié)果 它的流行主要在于它 的實(shí)現(xiàn)很簡(jiǎn)單 針對(duì)k 一平均算法對(duì) 噪聲 和孤立點(diǎn)數(shù)據(jù)的敏感性 對(duì)其進(jìn)行改進(jìn)出現(xiàn) k 一中心點(diǎn)方法 2 k 一中心點(diǎn)算法具體步驟如下 輸入 結(jié)果簇的數(shù)目k 包含n 個(gè)對(duì)象的數(shù)據(jù)庫(kù) 輸出 k 個(gè)簇 使得所有對(duì)象與其最近中心點(diǎn)的相異度總和最小 1 假設(shè)要聚成k 個(gè)類 由人為決定k 個(gè)類中心z i 1 z 2 1 五 1 2 若l i z z i i l l z z 川 n z 墨 s 為以z f 為中心點(diǎn)的簇 對(duì)所有的 i 1 2 k i 3 在每次疊代中 樣本集 z 用如下方法分類 對(duì)所有i i 2 k 隨機(jī)從咀z 為中心點(diǎn)的簇中取z 若 忙一乙j l e i i z z i i 其中z 為簇中的每一個(gè)對(duì)象 則用匆代替互 z z e 為中心點(diǎn) 4 由 3 得到的新的類的中心點(diǎn) k 令 l i z 一圳最小 i l 2 k i 1z e 0 z 為以互為中心點(diǎn)的簇中的對(duì)象 5 若j 已經(jīng)達(dá)到最小或不在變化 則終止 否則再轉(zhuǎn)到第三步 河海大學(xué)煩士學(xué)位論文 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) 4 g 蜘m 岬 l j h 上 工 秈 葉 a g n e s d i v i s i 仰 m a h a 圖 3 5 數(shù)據(jù)對(duì)象 a b c d e 的凝聚與分裂 現(xiàn)在算法研究主要集中在凝聚層次聚類方面 分裂方面的很少 其中凝聚方面 可以按照的思路就是 尋找 距離 最近的兩個(gè)樣本結(jié)合 這個(gè)算法步驟如下 有n 個(gè)樣本的集合邑 fz l z 2 乙 若想要聚成k 個(gè)類 其中k 要預(yù)先指定 1 k n e 互 i l 2 n 2 i fk k t h e ne n d 3 找到c 與c 之間的距離d e c 最小的一對(duì) 4 c 與c j 合并成一個(gè)類g 并計(jì)算新的c 的中心 5 去除c k k 一1 然后轉(zhuǎn)到第二步 類間距離d g c 的度量可以有以下四種 1 中心間距 a i i i m 一螞 其中m z 一是屬于c 的樣本數(shù) t l z e c 2 距離最近的樣本 吐 乏i 蠆藕f z f 一弓 f 3 距離最近的樣本 吐 z j c i z c 硼互一乙 l 4 類間平均距離 吐 1 4 x x q l z 一乙4 河海大學(xué)碩士學(xué)位論文 基于文本聚類技術(shù)的郵件分類系統(tǒng)的研究與實(shí)現(xiàn) c ic 2c 3c 4c 5c 6 相似性尺度 6 0 7 0 8 0 9 0 1 0 0 圖 3 6 層次方法圖例 層次聚類方法雖然很簡(jiǎn)單 但是它經(jīng)常的遇到合并或分裂點(diǎn)選擇的困難 合 并和分裂點(diǎn)的選擇是非常關(guān)鍵的 因?yàn)橐坏?組對(duì)象被合并或者分裂 下一步的 處理將在新生成的簇上進(jìn)行 已做的處理不能被撤消 聚類之間也不能交換對(duì)象 這樣做不用擔(dān)心組合數(shù)目的不同選擇 相對(duì)來說計(jì)算代價(jià)會(huì)較小 但另一方面造 成的后果是如果在某一步?jīng)]有很好的選擇合并和分裂點(diǎn) 剛可能會(huì)導(dǎo)致低質(zhì)量的 聚類結(jié)果 而且由于合并和分裂的決定需要檢查和估算大量的對(duì)象或簇 這種聚 類方法不具有很好的可伸縮性 改進(jìn)層次方法聚類質(zhì)量的一個(gè)很有前途的方向是把層次聚類和其他聚類方 法相結(jié)合起來 形成多階段的聚類 下面將討論的b i r c h 算法就是其中有代表性 的一種 它首先用數(shù)結(jié)構(gòu)對(duì)對(duì)象進(jìn)行層次劃分 然后采用其他的聚類算法對(duì)聚類 結(jié)果進(jìn)行求精 它采用最多的聚類算法是劃分方法方面的 b i r c h 算法口l 的核心是用一個(gè)聚類特征三元組c f 總結(jié)了一個(gè)簇個(gè)體的有關(guān)