數(shù)據(jù)挖掘畢業(yè)論文

數(shù)據(jù)挖掘畢業(yè)論文

數(shù)據(jù)挖掘畢業(yè)論文題目異常數(shù)據(jù)挖掘研究系別：計算機(jī)科學(xué)與技術(shù)系專業(yè)：計算機(jī)科學(xué)與技術(shù)摘要摘要粗糙集理論，它是一種分析處理數(shù)據(jù)的理論，在20世紀(jì)80年代由波蘭科學(xué)家Pawlak建立。一開始由于語言交流上的問題，建立該理論的時候只有一些東歐學(xué)者會研究和應(yīng)用它，后來隨著該理論的發(fā)展才慢慢受到全球上知名數(shù)學(xué)學(xué)者和計算機(jī)學(xué)者的重視。知識粒度的基本思想在許多領(lǐng)域都有體現(xiàn)，如粗糙集、數(shù)據(jù)庫、聚類分析、模糊集、證據(jù)理論、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等。自從1979年L.A.Zadeh在世界上首次提出并討論了知識粒度問題之后，知識粒度獲得了人們越來越多的關(guān)注。經(jīng)過多年的發(fā)展，知識粒度已在知識發(fā)現(xiàn)、數(shù)據(jù)挖掘、軟計算中扮演越來越重要的角色。在本論文中，本人引入知識粒度這一個方法作為一個統(tǒng)一的框架去理解和實(shí)施異常點(diǎn)挖掘。此外，還給出了基于知識粒度的異常點(diǎn)挖掘算法。該算法結(jié)合粗糙集與數(shù)據(jù)挖掘技術(shù)研究異常數(shù)據(jù)。理論研究和實(shí)驗(yàn)結(jié)果表明，知識粒度方法對評定異常是有效且適用的。關(guān)鍵詞：粗糙集；異常檢測；數(shù)據(jù)挖掘；知識粒度IAbstractABSTRACTRoughsettheory,itisatheoryofdataanalysisandprocessing,80inthe20thcenturybyPolishscientistsPawlakestablished.Thebeginningoftheproblemsduetolanguageexchanges,theestablishmentofthetheory,whenonlyafewEasternEuropeanscholarswouldstudyandapplyit,andlaterwiththedevelopmentofthetheoryslowlybytheglobalcomputeronthewell-knownscholarsandscholarsinmathematicsseriously.Thebasicideaofknowledgegranulationinmanyareas,suchasroughsets,database,clusteringanalysis,fuzzysets,evidencetheory,dataminingandmachinelearning.1979L.A.Zadehthefirsttimeintheworldanddiscussedaftertheknowledgegranulationoffuzzy,theknowledgegranulationobtainedpeoplemoreandmoreattention.Afteryearsofdevelopment,knowledgegranularityinknowledgediscovery,datamining,softcomputingplaysanincreasinglyimportantrole.Inthispaper,weintroducethismethodofknowledgegranularityasaunifiedframeworktounderstandandimplementoutliermining.Inaddition,wealsogivethesizeofknowledge-basedalgorithmforminingoutliers.Thealgorithmcombinesroughsetsanddataminingofabnormaldata.Theoreticalandexperimentalresultsshowthatthemethodofassessmentofknowledgegranularityisaneffectiveandappropriateexception.KeyWords:roughsets;outlierdetection;datamining;knowledgegranulationII目錄目錄第1章引言(1)1.1概述(1)1.2研究的目的和意義(2)1.3國內(nèi)外研究現(xiàn)狀(3)1.3.1數(shù)據(jù)挖掘的研究現(xiàn)狀(3)1.3.2粗糙集的研究現(xiàn)狀(3)1.3.3知識粒度的研究現(xiàn)狀(4)第2章數(shù)據(jù)挖掘(6)2.1數(shù)據(jù)挖掘的定義(6)2.2數(shù)據(jù)挖掘的有趣故事(7)2.3數(shù)據(jù)挖掘的幾種知識表示方法與模式(8)2.3.1廣義知識挖掘(8)2.3.2關(guān)聯(lián)知識挖掘(8)2.3.3類知識挖掘(8)2.3.4預(yù)測型知識挖掘(9)2.3.5特異型知識挖掘(9)2.3.6粗糙集知識挖掘(9)2.4數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(9)2.4.1把KDD看成數(shù)據(jù)挖掘的一個特例(10)2.4.2數(shù)據(jù)挖掘存在于KDD過程中(10)2.4.3數(shù)據(jù)挖掘與知識發(fā)現(xiàn)相近似(11)第3章粗糙集理論(12)3.1粗糙集理論的基本概念(12)3.1.1信息集(12)3.1.2集合的上近似，下近似與邊界值(13)III目錄3.2粗糙集理論的優(yōu)點(diǎn)(14)3.3屬性約簡(14)3.3.1屬性依賴(15)3.3.2屬性約簡(15)3.4信息熵(16)3.5知識粒度(17)3.5.1基于粗糙集理論的知識粒度表示(17)3.5.2知識粒度在知識約簡中的應(yīng)用(18)3.5.3應(yīng)用實(shí)例(19)第4章基于知識粒度的異常檢測(20)4.1知識粒度的異常檢測(20)4.1.1基于知識粒度異常點(diǎn)的定義(20)4.1.2基于知識粒度異常點(diǎn)的例子(22)4.2基于知識粒度的異常檢測算法(26)4.2.1基于知識粒度異常點(diǎn)檢測的算法流程圖(26)4.2.2基于知識粒度異常點(diǎn)檢測的算法描述(26)第5章實(shí)驗(yàn)與分析(29)5.1實(shí)驗(yàn)結(jié)果(29)5.2實(shí)驗(yàn)分析(31)5.2.1淋巴數(shù)據(jù)的檢測(31)5.2.2漏檢和誤檢(32)第6章結(jié)論與展望(34)6.1結(jié)論(34)6.2進(jìn)一步工作的方向(34)致謝(35)參考文獻(xiàn)(36)IV第1章引言第1章引言1.1概述相較于傳統(tǒng)的數(shù)據(jù)挖掘的問題，其主要目的是通過建立一個普遍的模式映射到大多數(shù)的數(shù)據(jù)，而異常檢測[1]的目標(biāo)則是挖掘那些與大多數(shù)常規(guī)的數(shù)據(jù)相比，行為較特殊的稀有數(shù)據(jù)?；诰嚯x的挖掘算法是現(xiàn)今最流行的方法之一，是由Knorr和Ng提出的。一個數(shù)據(jù)集中的某個異常數(shù)據(jù)是指該數(shù)據(jù)的距離與其它普通常規(guī)數(shù)據(jù)的距離大于dmin。這個概念總結(jié)概括了許多以分布為基礎(chǔ)的研究方法，且它擁有較好的檢測精度。假設(shè)一個對象在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則我們認(rèn)為該對象也屬于這個類別，稱之為KNN算法[2]。換句話說，在不依賴于統(tǒng)計檢驗(yàn)的情況下，我們可以將通過距離計算出那些沒有“足夠多”鄰居的對象看作是異常點(diǎn)，這里的對象是根據(jù)給定對象的距離來定義的，這是一種研究挖掘異常點(diǎn)K的高效算法。然而，因?yàn)镵NN異常檢測算法是要計算點(diǎn)到其他點(diǎn)的所有空間的距離，所以如果可用的對象數(shù)量非常多的話，那么這是很費(fèi)時的。而且，使用KNN算法來進(jìn)行數(shù)據(jù)挖掘則將會產(chǎn)生很大的空間，這樣很有可能導(dǎo)致性能和質(zhì)量成本上的問題。異常檢測可以粗略的分成五大類[3]，除了之前講到的基于距離的異常檢測方法外，還有基于統(tǒng)計的方法、基于深度的方法、基于聚類的方法和基于密度的檢測方法。利用統(tǒng)計學(xué)的方法處理數(shù)據(jù)異常點(diǎn)的問題已經(jīng)有很長的歷史，并且它已經(jīng)有了一套完整的理論和方法。統(tǒng)計學(xué)的方法就是對給定的數(shù)據(jù)集假設(shè)了一個分布或者稱為概率模型（例如正態(tài)分布），然后再根據(jù)模型通過不一致性檢驗(yàn)來確定數(shù)據(jù)異常點(diǎn)，所以不一致性檢驗(yàn)要求我們事先知道數(shù)據(jù)集模型的參數(shù)（如正態(tài)分布）、分布的參數(shù)（如均值等）和預(yù)期異常點(diǎn)的數(shù)目。它最大缺點(diǎn)就在于測量的數(shù)據(jù)分布在實(shí)際中是很難被發(fā)現(xiàn)的。基于深度的方法是通過計算幾何和計算不同層的k-d凸殼和標(biāo)記外層的對象作為異常點(diǎn)。然而，眾所周知的是該算法采用維數(shù)，不能應(yīng)付大量的對象集。聚類分類對輸入數(shù)據(jù)進(jìn)行分類。它檢測異常點(diǎn)作為副產(chǎn)品。由于主要目的是分類歸并，它不適合用于異常檢測。1第1章引言基于密度的方法[4]最初是由Breunig提議的。它采用局部異常因子來確定異常數(shù)據(jù)的存在與否。它的主要思想是，計算出對象的局部異常因子（LOF）。高局部異常因子（LOF）就認(rèn)為它更可能異常。這種解決方案的缺點(diǎn)是，它對鄰居的參數(shù)定義非常敏感的。粗糙集理論（RoughSetTheory）[5]，是由波蘭數(shù)學(xué)家Z.Pawlak教授在1982年提出，用于研究不完整性數(shù)據(jù)和不精確的知識表達(dá)，學(xué)習(xí)歸納的數(shù)學(xué)分析理論，并成功的應(yīng)用于機(jī)器學(xué)習(xí)、模式識別和數(shù)據(jù)挖掘等領(lǐng)域上。其算法特點(diǎn)是簡單，無需提供數(shù)據(jù)以外的任何先驗(yàn)信息，可直接根據(jù)給定問題的描述集合出發(fā)，然后通過不可分辨關(guān)系和等價類來確定問題的近似域，再找出該問題的規(guī)律。為了評估粗糙集理論在分辨不確定性知識上的能力，L.A.Zadeh首次推出粒度。它提出了關(guān)于領(lǐng)域劃分的描述，更直觀和更具有結(jié)構(gòu)性。許多知識上的檢測在信息系統(tǒng)上有提出。這些測量包括粗糙集，知識粒度和信息熵。這些測量應(yīng)用于屬性約簡，分類，特征選擇與不確定性的推理。然而，這些年很少有基于知識粒度檢測異常數(shù)據(jù)的文章發(fā)表出來。本文提出了一種異常檢測的新方法，是基于知識粒度的。它采用了基于知識粒度的距離度量，研究不確定信息。有些在UCI數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)分析。結(jié)果表明，該檢測系統(tǒng)可以把大部分異常點(diǎn)檢測出來。1.2研究的目的和意義隨著計算機(jī)和網(wǎng)絡(luò)等信息技術(shù)的飛速發(fā)展，對信息的處理在整個社會乃至世界規(guī)模上已經(jīng)迅速產(chǎn)業(yè)化。隨著信息的慢慢堆積，人們所積累的數(shù)據(jù)已經(jīng)越來越多，以至數(shù)據(jù)和信息系統(tǒng)中的不確定性問題更加的明顯了。海量雜亂的信息數(shù)據(jù)背后隱藏著很多我們不知道的，但對我們來說又非常重要的信息，所以人們希望能夠通過對其進(jìn)行深入的分析，方便我們能更好的利用并使用這些隱藏中的數(shù)據(jù)信息[6]。現(xiàn)在的數(shù)據(jù)庫系統(tǒng)雖然可以實(shí)現(xiàn)對數(shù)據(jù)的增刪改查及統(tǒng)計等功能，但它卻無法發(fā)現(xiàn)數(shù)據(jù)間存在的關(guān)系和規(guī)則，它沒法根據(jù)數(shù)據(jù)中所變現(xiàn)出來的隱藏信息來預(yù)測未來的發(fā)展趨勢。缺少挖掘數(shù)據(jù)背后隱藏的信息手段就造成了我們所說的“數(shù)據(jù)豐富卻知識貧乏”的現(xiàn)象。自從20世紀(jì)90年代中期以來，數(shù)據(jù)挖掘一直引起人們的廣泛興趣，以至它得到了迅猛的發(fā)展。通常，數(shù)據(jù)挖掘被人們劃分成四種類型[7]：類別的判定、2第1章引言類別的描述、相關(guān)依賴關(guān)系的發(fā)現(xiàn)、粗糙或異常(Outlier)數(shù)據(jù)挖掘。前三個類型主要針對的是數(shù)據(jù)集中服從的數(shù)據(jù)模式的大部分?jǐn)?shù)據(jù)記錄，而異常檢測的目的則在于找出隱藏在海量數(shù)據(jù)中的相對稀疏而又孤立的異常數(shù)據(jù)模式，這也造就了異常檢測與傳統(tǒng)面向數(shù)據(jù)主體的數(shù)據(jù)挖掘間的區(qū)別。早期，在對數(shù)據(jù)集進(jìn)行預(yù)處理時，我們通常把異常點(diǎn)當(dāng)作噪聲，或者干脆修正異常點(diǎn)的值，讓其減少對正常數(shù)據(jù)的影響。雖然異常檢測是以發(fā)現(xiàn)數(shù)據(jù)集中的隱藏數(shù)據(jù)為主要目的，但是異常數(shù)據(jù)挖掘常常能比其他類型的挖掘來得更有價值，更有研究意義，因?yàn)槭f個正常的記錄里很可能只覆蓋了一條規(guī)則，而十個異常記錄里則很可能就意味著擁有十條不同的規(guī)則。實(shí)際生活中，異常檢測是有著很廣泛的應(yīng)用，比如信用卡惡意透支、貸款證明的審核、網(wǎng)絡(luò)入侵檢測等。1.3國內(nèi)外研究現(xiàn)狀1.3.1數(shù)據(jù)挖掘的研究現(xiàn)狀知識發(fā)現(xiàn)（KDD：KnowledgeDiscoveryinDatabases）[8]是指從數(shù)據(jù)集中辨別出新穎的、有效的、潛在有用的且最終可理解的模式的一個非平凡過程。知識發(fā)現(xiàn)就是將信息變?yōu)橹R，從數(shù)據(jù)的海洋中找到蘊(yùn)藏的知識石油，它為知識的創(chuàng)新和知識經(jīng)濟(jì)的發(fā)展做出了偉大貢獻(xiàn)。知識發(fā)現(xiàn)的術(shù)語是在1989年美國底特律召開的第一屆KDD國際學(xué)術(shù)會議上出現(xiàn)的。隨后KDD得到了廣泛的發(fā)展。1995年第一屆知識發(fā)現(xiàn)與數(shù)據(jù)挖掘國際學(xué)術(shù)會議在加拿大召開。1998年，在美國紐約召開了第四屆知識發(fā)現(xiàn)與數(shù)據(jù)挖掘國際學(xué)術(shù)會議，其中有30多家國際公司陳列出了他們的研究產(chǎn)品，其中的一些產(chǎn)品都已廣泛的在發(fā)達(dá)國家中應(yīng)用了。至此數(shù)據(jù)挖掘和知識發(fā)現(xiàn)成為當(dāng)前數(shù)學(xué)界與計算機(jī)科學(xué)研究界的一大研究的熱點(diǎn)。1.3.2粗糙集的研究現(xiàn)狀隨著《粗糙集—關(guān)于數(shù)據(jù)推理的理論》這篇文章的發(fā)表，國際上掀起了一場粗糙集的學(xué)習(xí)熱潮。在1992年，眾多知名學(xué)者齊聚波蘭，召開了第1屆國際粗糙集理論的研討會，這次會議主要討論了數(shù)據(jù)集合近相似的基本思想和應(yīng)用，3第1章引言其中在粗糙環(huán)境下的機(jī)器學(xué)習(xí)的研究是這次會議的重點(diǎn)之一。20世紀(jì)90年代第2屆國際粗糙集與知識發(fā)現(xiàn)研討會在加拿大召開了，這次會議極大的推動了全球?qū)Υ植诩碚摰难芯?。一些著名的學(xué)者參加了這次會議，并且介紹和演示了許多基于粗糙集理論的數(shù)據(jù)挖掘方法和系統(tǒng)。在1995年ACMCommunication將粗糙集理論列為“新興的計算機(jī)科學(xué)”的研究課題。1996年在日本的東京召開了第5屆國際粗糙集研究會?！暗谝粚么植诩陀嬎愕漠?dāng)前趨勢”學(xué)術(shù)會議于1998年在波蘭華沙召開了。1999年，在日本召開了“第七屆粗糙集、Fuzzy集、數(shù)據(jù)挖掘和粒度一軟計算的國際學(xué)術(shù)研討會”，闡明了目前粗糙集、模糊集的研究現(xiàn)狀和未來發(fā)展趨勢，最終指出將著重在數(shù)據(jù)庫、AI、軟計算的近似推理理論和應(yīng)用方面發(fā)展。目前，美國、日本、波蘭、加拿大都建立了粗糙集研究的專門機(jī)構(gòu)。粗糙集理論的研究雖然在我國起步晚，但發(fā)展迅速?！暗谝粚弥袊浻嬎銓W(xué)術(shù)與粗糙集研討會”于2001年在重慶的郵電大學(xué)開辦了。主辦方還邀請了粗糙集理論的始祖——Z.Pawlak教授。這次研討會的舉行大大推動了我國乃至亞洲地區(qū)對粗糙集的應(yīng)用及其理論的研究。粗糙集與軟計算專業(yè)委員會于2003年由中國人工智能學(xué)會組建。加拿大的粗糙集研討會議于2005年9月舉辦時，我國研究者的論文已經(jīng)超過了會議采用論文總數(shù)的1/4。2006年7月在重慶舉行了第一屆粗糙集與知識技術(shù)國際研討會議。如今，國內(nèi)學(xué)者從事粗糙集理論研究的人員越來越多越來越強(qiáng)大，已形成了一支較為穩(wěn)定且實(shí)力強(qiáng)大的學(xué)術(shù)隊(duì)伍，中國學(xué)者在粗糙集這一領(lǐng)域的影響力也越來越巨大，儼然成為了這一領(lǐng)域的重要科研力量。在對大型數(shù)據(jù)庫中不完整數(shù)據(jù)的分析和學(xué)習(xí)方面都取得了顯著的成果，使得粗糙集理論以及數(shù)據(jù)挖掘的研究成為熱點(diǎn)領(lǐng)域。1.3.3知識粒度的研究現(xiàn)狀粒度計算[9]是信息處理的一種全新的概念和計算范式，它覆蓋了所有關(guān)于粒度的理論、技術(shù)、方法和工具的研究，現(xiàn)已成為了人工智能界的研究熱門之一。在美國知名學(xué)者L.A.Zadeh的模糊集理論合集的基礎(chǔ)上，人們在1979年第一次發(fā)表并且討論了關(guān)于模糊集粒度化信息的問題，雖然這推動了邏輯的模糊的應(yīng)用以及理論的進(jìn)一步研究，但在當(dāng)時卻沒有吸引人們的眼球。直到“詞計算理論”這一演說于1996年被L.A.Zadeh提出，才宣告著模糊集粒度化信息理4第1章引言論的誕生。它的主要思想在于通過我們的自然語言，進(jìn)行模糊的判斷和推理，以便實(shí)現(xiàn)模糊智能控制的方法。隨后，美國多特蒙德大學(xué)的HelmutThiele教授于1998年發(fā)表了“粒計算理論的語義模型”，促進(jìn)了粒度計算理論的發(fā)展。粒度計算理論對Internet上的海量信息資源的利用有著深遠(yuǎn)的影響。基于L.A.Zadeh的模糊集理論的粒度計算的研究，已成為“粒度計算”方面的重要研究方向之一。在國內(nèi)，著名學(xué)者張鈴教授和張鈸院士曾提出了一個模型是基于商空間的粒度計算。其主要思想是通過子集來表示概念，然后我們把不同粒度的概念可以認(rèn)為是不同粒度的子集，一簇的概念我們就當(dāng)成了空間的一個劃分（商空間），叫知識基[10]，不一樣的概念也就簇成了不同的知識基。而粒度計算問題，也可以把它看作是研究在給定知識基上的各種不同子集合之間的關(guān)系與轉(zhuǎn)換。對同一問題，我們可以采取不同的粒度。通過對不同的粒度進(jìn)行分析，綜合獲取對所提問題的求解。在此基礎(chǔ)上，學(xué)者張鈸和張鈴在2003年提出了關(guān)于模糊商空間的理論。總的來說，粒度計算的研究在我國還屬于剛起步階段，尚未引起廣泛的關(guān)注。但我們相信，在不久的將來會有更多的學(xué)者加入到我們的隊(duì)伍中來，一起對該領(lǐng)域的研究做出偉大的貢獻(xiàn)。5第2章數(shù)據(jù)挖掘第2章數(shù)據(jù)挖掘我們先對數(shù)據(jù)挖掘的定義進(jìn)行講解，然后通過一個故事來了解數(shù)據(jù)挖掘在我們生活中的應(yīng)用，在介紹幾種知識表示方法與模式，最后在討論數(shù)據(jù)挖掘與知識發(fā)現(xiàn)之間的關(guān)系。2.1數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘（DataMining）[11]是一個多學(xué)科交叉研究領(lǐng)域，它融合了數(shù)據(jù)庫（Databa