【正文】 與基于分布的方法相比，基于距離的孤立點(diǎn)檢測(cè)包含并擴(kuò)展了基于分布的思想，當(dāng)數(shù)據(jù)集不滿足任何標(biāo)準(zhǔn)分布時(shí)，基于距離的方法仍能有效地發(fā)現(xiàn)孤立點(diǎn)。2. 基于距離的方法基于距離（Distancebased ，DB）的孤立點(diǎn)的概念是由 Knorr 和 Ng 在 1998 年提出的。目前，已經(jīng)研究出若干種檢測(cè)孤立點(diǎn)的方法，大多數(shù)方法建立在統(tǒng)計(jì)學(xué)的基礎(chǔ)上，這些方法大致可以分為 4 類：基于分布的、基于深度的、基于距離的和基于密度的，每種方法都給出了相應(yīng)的孤立點(diǎn)的定義。但是，并非所有的孤立點(diǎn)都是錯(cuò)誤的數(shù)據(jù)，所以，在檢測(cè)出孤立點(diǎn)后還應(yīng)結(jié)合領(lǐng)域知識(shí)或所存儲(chǔ)的元數(shù)據(jù)，從中找出相應(yīng)的錯(cuò)誤數(shù)據(jù)。Hawkins 給出了孤立點(diǎn)本質(zhì)性的定義：孤立點(diǎn)是在數(shù)據(jù)源中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制。2. 通過(guò)檢測(cè)字段之間以及記錄之間的關(guān)系來(lái)發(fā)現(xiàn)錯(cuò)誤數(shù)據(jù)這種方法主要是通過(guò)在大量數(shù)據(jù)中發(fā)現(xiàn)特定的數(shù)據(jù)格式，如幾個(gè)字段之間的關(guān)系，從而得到字段之間的完整性約束，如采用函數(shù)依賴或特定應(yīng)用的業(yè)務(wù)規(guī)則來(lái)檢測(cè)并改正數(shù)據(jù)源中的錯(cuò)誤數(shù)據(jù)。簡(jiǎn)單地說(shuō)，數(shù)據(jù)錯(cuò)誤是指數(shù)據(jù)源中記錄字段的值和實(shí)際的值不相符。5) 估算值替代法估算值替代法是最復(fù)雜，也是最科學(xué)的一種處理方法。2) 常量值替代法常量替代法就是對(duì)所有缺失的字段值用同一個(gè)常量來(lái)填充，比如用“Unknown”或“Miss Value”，這種方法最簡(jiǎn)單。判斷記錄的可用性也就是根據(jù)每一條記錄的不完整程度及其它因素，來(lái)決定該記錄是保留還是刪除。所以，該方法能較好地完成不完整數(shù)據(jù)的清理工作。3. 推斷缺失字段的值推斷缺失字段的值是指對(duì)那些要保留的記錄，要采取一定的方法來(lái)處理該記錄中缺失的字段值。不完整數(shù)據(jù)的清理方法對(duì)于數(shù)據(jù)源中不完整數(shù)據(jù)的清理，可分成以下三步來(lái)處理：1. 檢測(cè)數(shù)據(jù)源中的不完整數(shù)據(jù)要清理數(shù)據(jù)源中的不完整數(shù)據(jù)，首先要做的就是把數(shù)據(jù)源中的不完整數(shù)據(jù)檢測(cè)出來(lái)，以便于下一步的處理。故必須要解決數(shù)據(jù)源中的數(shù)據(jù)不完整問(wèn)題。因此，為了提高相似重復(fù)記錄的檢測(cè)效率，有一種優(yōu)化相似重復(fù)記錄檢測(cè)效率的方法，該方法采用長(zhǎng)度過(guò)濾方法減少不必要的編輯距離計(jì)算。然后，在記錄相似檢測(cè)過(guò)程中對(duì)不同字段指定不同的權(quán)重，這樣可提高相似重復(fù)記錄的檢測(cè)精度，從而更好地識(shí)別重復(fù)記錄。等級(jí)法是一種計(jì)算記錄字段權(quán)重的方法，它是讓用戶根據(jù)數(shù)據(jù)表中各個(gè)字段的重要程度來(lái)劃分等級(jí)，即最重要字段的等級(jí)指定為 1，第二重要的字段等級(jí)指定為 2，等等。由此可見各個(gè)字段所賦予的權(quán)重對(duì)檢測(cè)精度影響很大，合適的賦值能提高記錄相似檢測(cè)的精度。于是，目的就是合并一組重復(fù)記錄，產(chǎn)生一個(gè)具有更完整信息的新記錄。5) 實(shí)用規(guī)則因?yàn)橹貜?fù)率越高的信息可能越準(zhǔn)確一些，比如，如果三條記錄中兩個(gè)供應(yīng)商的電話號(hào)碼是相同的，那么重復(fù)的電話號(hào)碼可能是正確的。3) 最新規(guī)則在很多情況下，最新的記錄能更好地代表一組相似重復(fù)記錄。對(duì)于一組相似重復(fù)記錄，一般有兩種處理方法：1. 第一種處理方法第一種處理方法是把一組相似重復(fù)記錄中的一個(gè)記錄看成是正確的，其它記錄看成是含有錯(cuò)誤信息的重復(fù)記錄。因此，從實(shí)用的角度考慮，在實(shí)際應(yīng)用中，對(duì)于小批量數(shù)據(jù)，如記錄總數(shù)小于 5 萬(wàn)時(shí)，沒有必要采用復(fù)雜的記錄排序算法，可以直接進(jìn)行記錄的比較，從而提高相似重復(fù)記錄的查全率。按以上方法重排記錄后，相似記錄被放在較接近的位置，從而可以在相對(duì)集中的范圍內(nèi)作記錄的相似檢測(cè)。序值表的大小只有幾十 K，可以存放在內(nèi)存中。對(duì)于漢字各種不同的排序方式，分別建立對(duì)應(yīng)于 GB231280 漢字基本集的序值表。在國(guó)標(biāo) GB231280 中共收集漢字 6763 個(gè)，分成兩級(jí)，一級(jí)漢字字庫(kù)包括漢字 3755 個(gè)，按拼音字母排序，二級(jí)漢字字庫(kù)包括漢字 3008 個(gè)，按部首排序。對(duì)于記錄排序方法，使用某種應(yīng)用相關(guān)的鍵來(lái)將相似記錄聚類到鄰近位置。比如，在整個(gè)分類后的數(shù)據(jù)表中通過(guò)移動(dòng)一個(gè)固定大小的窗口，比較附近的記錄。其清理過(guò)程可描述如下：首先，把數(shù)據(jù)源中需要清理的數(shù)據(jù)通過(guò) JDBC（Java DataBase Connectivity,Java 數(shù)據(jù)庫(kù)連接）接口調(diào)入到系統(tǒng)中來(lái)；然后，執(zhí)行數(shù)據(jù)清理，記錄排序模塊從算法庫(kù)中調(diào)用排序算法，執(zhí)行記錄之間的排序；在記錄已排序的基礎(chǔ)上，記錄相似檢測(cè)模塊從算法庫(kù)中調(diào)用相似檢測(cè)算法，作鄰近范圍內(nèi)記錄間的相似檢測(cè)，從而計(jì)算出記錄間的相似度，并根據(jù)預(yù)定義的重復(fù)識(shí)別規(guī)則，來(lái)判定是否為相似重復(fù)記錄。先計(jì)算各記錄的 NGram 值，然后以各記錄的 NGram 值為排序鍵進(jìn)行排序，再通過(guò)采用一種高效的應(yīng)用無(wú)關(guān)的 Pairwise 比較算法，通過(guò)計(jì)算兩記錄中單詞間的編輯距離來(lái)判斷記錄的相似與否，并采用一種改進(jìn)的優(yōu)先隊(duì)列算法來(lái)準(zhǔn)確地聚類相似重復(fù)記錄,該算法使用固定大小的優(yōu)先隊(duì)列順序掃描已排序的記錄,通過(guò)比較當(dāng)前記錄和隊(duì)列中記錄的距離來(lái)聚類相似重復(fù)記錄；提出一種檢測(cè)多語(yǔ)言數(shù)據(jù)重復(fù)記錄的綜合方法。記錄排序：用第一步生成的排序鍵對(duì)記錄排序。完全重復(fù)記錄不管以記錄的哪一個(gè)部分進(jìn)行分類，在分類排序后，都能保證互相相鄰。為了減少數(shù)據(jù)源中的冗余信息，重復(fù)記錄的清理是一項(xiàng)重要的任務(wù)。數(shù)據(jù)源中的重復(fù)記錄可分成完全重復(fù)記錄和相似重復(fù)記錄。對(duì)于數(shù)據(jù)清理應(yīng)該滿足：數(shù)據(jù)清理應(yīng)該能檢測(cè)和消除所有主要的錯(cuò)誤和不一致，包括單數(shù)據(jù)源和多數(shù)據(jù)源集成時(shí)；數(shù)據(jù)清理方法能被這樣的工具支持，人工檢測(cè)和編程工作要盡可能少，并具有可擴(kuò)展性。一般說(shuō)來(lái)，數(shù)據(jù)清理包括以下幾個(gè)步驟：1) 數(shù)據(jù)分析數(shù)據(jù)分析是指從數(shù)據(jù)中發(fā)現(xiàn)控制數(shù)據(jù)的一般規(guī)則，比如字段域、業(yè)務(wù)規(guī)則等。數(shù)據(jù)清理在不同的應(yīng)用領(lǐng)域其要求不完全相同，如在數(shù)據(jù)倉(cāng)庫(kù)環(huán)境下，數(shù)據(jù)清理是 ETL（ Extraction 抽取、Transition 轉(zhuǎn)換、Load 加載，ETL）過(guò)程的一個(gè)重要部分，要考慮數(shù)據(jù)倉(cāng)庫(kù)的集成性與面向主題的需要，包括數(shù)據(jù)的清理及結(jié)構(gòu)轉(zhuǎn)換；在 KDD 中，數(shù)據(jù)清理主要是提高數(shù)據(jù)的可利用性，如去除噪聲、無(wú)關(guān)數(shù)據(jù)、空值，考慮時(shí)間順序和數(shù)據(jù)的變化等，但主要內(nèi)容還是一樣的。在以上這些問(wèn)題中，前三種問(wèn)題在數(shù)據(jù)源中出現(xiàn)的最多。2) 不完整的數(shù)據(jù)由于錄入錯(cuò)誤等原因，字段值或記錄未被記入數(shù)據(jù)庫(kù)，造成信息系統(tǒng)數(shù)據(jù)源中應(yīng)該有的字段或記錄缺失。一般說(shuō)來(lái)，評(píng)價(jià)數(shù)據(jù)質(zhì)量最主要的幾個(gè)指標(biāo)是：1) 準(zhǔn)確性（Accuracy）：準(zhǔn)確性是指數(shù)據(jù)源中實(shí)際數(shù)據(jù)值與假定正確數(shù)據(jù)值的一致程度；2) 完整性（Completeness）完整性是指數(shù)據(jù)源中需要數(shù)值的字段中無(wú)值缺失的程度；3) 一致性（Consistency）一致性是指數(shù)據(jù)源中數(shù)據(jù)對(duì)一組約束的滿足程度；4) 唯一性（Uniqueness ）唯一性是指數(shù)據(jù)源中記錄以及編碼是否唯一；5) 適時(shí)性（Timeliness）適時(shí)性是指在所要求的或指定的時(shí)間提供一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的程度；6) 有效性（Validity）有效性是指維護(hù)的數(shù)據(jù)足夠嚴(yán)格以滿足分類準(zhǔn)則的接受要求。所謂動(dòng)態(tài)的評(píng)估方式，是指從數(shù)據(jù)產(chǎn)生機(jī)制上對(duì)數(shù)據(jù)質(zhì)量進(jìn)行評(píng)估，而靜態(tài)方式只考慮數(shù)據(jù)本身。數(shù)據(jù)質(zhì)量的描述通?？梢苑譃椴煌膶哟?，不過(guò)到目前為止，還沒有形成專門用于表示這種層次性的統(tǒng)一術(shù)語(yǔ)，例如，有的用類和域表示這種層次，而 ISO TC211 則用數(shù)據(jù)質(zhì)量元素及子元素來(lái)表達(dá)。在數(shù)據(jù)生產(chǎn)過(guò)程中形成的質(zhì)量維度，如準(zhǔn)確性(Accuracy)、完整性(Completeness)、一致性(Consistence)等，已經(jīng)成為數(shù)據(jù)質(zhì)量評(píng)估的基本要求。20 世紀(jì) 80 年代以來(lái)，國(guó)際上普遍認(rèn)為，數(shù)據(jù)質(zhì)量的標(biāo)準(zhǔn)基本上是圍繞著以提高數(shù)據(jù)準(zhǔn)確性為出發(fā)點(diǎn)和原則的。如，在我校圖書館的資源的網(wǎng)頁(yè)中，包含對(duì)象期刊網(wǎng)，而其具體的的題目等內(nèi)容在另一個(gè)頁(yè)面，這樣對(duì)象中國(guó)期刊網(wǎng)與鏈接所指頁(yè)面就是源與目標(biāo)對(duì)象的關(guān)系。由于沒有強(qiáng)制性模式限制，使半結(jié)構(gòu)化數(shù)據(jù)具有很大靈活性，能夠滿足網(wǎng)絡(luò)這種復(fù)雜分布式環(huán)境需要，但同時(shí)也給數(shù)據(jù)描述和處理帶來(lái)了很大困難。沒有嚴(yán)格的類型約束：由于沒有一個(gè)預(yù)先定義的模式，以及數(shù)據(jù)在結(jié)構(gòu)上的不規(guī)則性，導(dǎo)致缺乏對(duì)數(shù)據(jù)的嚴(yán)格約束。半結(jié)構(gòu)化是上數(shù)據(jù)的最大特點(diǎn)。? 半結(jié)構(gòu)化數(shù)據(jù)的定義半結(jié)構(gòu)化數(shù)據(jù)有兩層含義，一種是指在物理層上缺少結(jié)構(gòu)的數(shù)據(jù)，另一種是指在邏輯層上缺少結(jié)構(gòu)的數(shù)據(jù)。其次，還要解決 Web 上的數(shù)據(jù)查詢問(wèn)題，因?yàn)槿绻璧臄?shù)據(jù)不能很有效地得到，對(duì)這些數(shù)據(jù)進(jìn)行分析、集成、處理就無(wú)從談起。而Inter 上的數(shù)據(jù)非常復(fù)雜，沒有特定的模型描述，每一站點(diǎn)的數(shù)據(jù)都各自獨(dú)立設(shè)計(jì)，并且數(shù)據(jù)本身具有自述性和動(dòng)態(tài)可變性，其結(jié)構(gòu)也不可琢磨，是一種我們稱之為半結(jié)構(gòu)化數(shù)據(jù)。一些單位每年要花費(fèi)上百萬(wàn)元來(lái)查找數(shù)據(jù)錯(cuò)誤，手工清理是勞累的、費(fèi)時(shí)的和易出錯(cuò)的。對(duì)此，提出一個(gè)可擴(kuò)展的數(shù)據(jù)清理軟件平臺(tái)，該軟件平臺(tái)具有開放的規(guī)則庫(kù)和算法庫(kù)，通過(guò)在規(guī)則庫(kù)中定義清理規(guī)則以及從算法庫(kù)中選擇合適的清理算法，可使該軟件平臺(tái)適用于不同的數(shù)據(jù)源，從而使其具有較強(qiáng)的通用性和適應(yīng)性；5) 目前，對(duì)數(shù)據(jù)清理的研究主要集中在結(jié)構(gòu)化數(shù)據(jù)上。然而，由于數(shù)據(jù)清理本身的一些特點(diǎn)，比如：1) 數(shù)據(jù)清理是具體應(yīng)用問(wèn)題，經(jīng)常要具體問(wèn)題具體分析，難于歸納出通用方法；2) 數(shù)據(jù)清理問(wèn)題的數(shù)學(xué)建模困難。但是，由于各種原因，如數(shù)據(jù)錄入錯(cuò)誤、不同來(lái)源數(shù)據(jù)引起的不同表示方法、數(shù)據(jù)間的不一致等，導(dǎo)致企業(yè)現(xiàn)有系統(tǒng)數(shù)據(jù)庫(kù)中存在這樣或那樣的臟數(shù)據(jù)，主要表現(xiàn)為：不正確的字段值、重復(fù)的記錄、拼寫問(wèn)題、不合法值、空值、不一致值、縮寫詞的不同，不遵循引用完整性等。收集到的數(shù)據(jù)在時(shí)間和空間上的相關(guān)性可以用來(lái)更好地評(píng)估數(shù)據(jù)的正確性。我們希望計(jì)算機(jī)能夠做類似的事情。但是，還是存在一些個(gè)人有其他的動(dòng)機(jī)和角色，有些人出于某種原因故意提供錯(cuò)誤的信息以誤導(dǎo)別人。一個(gè)大數(shù)據(jù)分析系統(tǒng)應(yīng)該支持來(lái)自多個(gè)專家的輸入，并共享分析的結(jié)果。理想的方案是，大數(shù)據(jù)分析并不完全是計(jì)算機(jī)算法，而是設(shè)計(jì)成明確地把人放到分析的環(huán)路中。另外，實(shí)際中的數(shù)據(jù)不是靜態(tài)的，而是會(huì)隨著時(shí)間的推移發(fā)生變化并且變得更大。這是因?yàn)樵诨谖恢玫姆?wù)中，為了成功的數(shù)據(jù)訪問(wèn)和數(shù)據(jù)收集，就需要用到用戶的位置信息，而用戶的身份信息就可以不需要。一段時(shí)間后，用戶就會(huì)留下一些蹤跡，這些蹤跡可以和特定的住所以及辦公地點(diǎn)相關(guān)聯(lián)，從而可以確定用戶的身份。這些新的架構(gòu)要求用戶把他們的位置信息共享給業(yè)務(wù)提供商，這是一個(gè)很明顯的隱私性問(wèn)題。對(duì)于其他的數(shù)據(jù)，就沒有那么硬性的規(guī)定，特別是在美國(guó)。這里的問(wèn)題是，因?yàn)槊總€(gè)索引結(jié)構(gòu)是按照一些類型的準(zhǔn)則來(lái)設(shè)計(jì)的。給定一個(gè)大的數(shù)據(jù)集，通常需要找到滿足一個(gè)特定準(zhǔn)則那些數(shù)據(jù)。現(xiàn)實(shí)中有很多情況需要立刻得到分析得結(jié)果。? 及時(shí)性數(shù)據(jù)大小的另一面是速度。硬盤的隨機(jī)訪問(wèn) I/O 性能比順序 I/O 性能要慢很多，通常數(shù)據(jù)處理引擎通過(guò)格式化數(shù)據(jù)，以及查詢處理方法的設(shè)計(jì)來(lái)克服這些限制。依靠用戶驅(qū)動(dòng)的程序優(yōu)化有可能導(dǎo)致較差的群的整體性能。這些變化要求我們重新思考如何設(shè)計(jì)，搭建以及運(yùn)行數(shù)據(jù)處理組件。在過(guò)去，大型的數(shù)據(jù)處理系統(tǒng)需要避免在計(jì)算機(jī)群中跨節(jié)點(diǎn)的并行機(jī)制；現(xiàn)在，則需要處理在一個(gè)節(jié)點(diǎn)內(nèi)的并行機(jī)制。多年來(lái)，對(duì)大數(shù)據(jù)并且快速增長(zhǎng)的數(shù)據(jù)的管理一直是很具有挑戰(zhàn)的問(wèn)題。在數(shù)據(jù)分析得過(guò)程中應(yīng)該有效地管理這種不完整性以及這些錯(cuò)誤。很多的數(shù)據(jù)分析系統(tǒng)都要求好的數(shù)據(jù)結(jié)構(gòu)?？梢园研袠I(yè)研究報(bào)告的總結(jié)放在這里）2 面臨的挑戰(zhàn)大數(shù)據(jù)分析面臨巨大的挑戰(zhàn)，以下我們從 5 方面來(lái)討論：? 異構(gòu)性和非完整性當(dāng)用戶使用信息時(shí)，可以容忍大量的異構(gòu)性。實(shí)際上，自然語(yǔ)言的豐富性和微妙可以提供有價(jià)值的深度。少一些的結(jié)構(gòu)化設(shè)計(jì)對(duì)于一些目的可能更加有效，但是計(jì)算機(jī)系統(tǒng)的有效性則有賴于多個(gè)數(shù)據(jù)的大小和結(jié)構(gòu)的一致性。這是一個(gè)非常大的挑戰(zhàn)。在過(guò)去，這些挑戰(zhàn)都是通過(guò)更快的處理器來(lái)應(yīng)對(duì)的。不幸的是，過(guò)去應(yīng)用于跨節(jié)點(diǎn)數(shù)據(jù)處理的并行數(shù)據(jù)處理技術(shù)并不能直接用于節(jié)點(diǎn)內(nèi)的并行處理，因?yàn)榧軜?gòu)看上去非常不同。第二個(gè)巨大的轉(zhuǎn)變是向云計(jì)算的遷移，云計(jì)算將多個(gè)分離的計(jì)算任務(wù)匯聚到非常大的計(jì)算機(jī)群中，每個(gè)計(jì)算任務(wù)具有不同的性能目標(biāo)。系統(tǒng)驅(qū)動(dòng)的整體優(yōu)化要求程序是足夠透明的，比如在關(guān)系型數(shù)據(jù)庫(kù)中，說(shuō)明式的查詢語(yǔ)言就是這樣設(shè)計(jì)的。如今，硬盤正在逐步被固態(tài)驅(qū)動(dòng)器取代，其他的技術(shù)如相變內(nèi)存正在出現(xiàn)。需要處理的數(shù)據(jù)集越大，分析所需要的時(shí)間就越長(zhǎng)。比如，如果懷疑一個(gè)欺詐性信用卡交易，在交易完成之前我們就應(yīng)該標(biāo)識(shí)出這樣的交易，這樣可以從根本上防止欺詐性交易的發(fā)生。在數(shù)據(jù)分析得過(guò)程中，這種類型的搜索有可能重復(fù)地發(fā)生。當(dāng)需要使用大數(shù)據(jù)時(shí)，有可能定義新型的準(zhǔn)則，這時(shí)就需要設(shè)計(jì)新的索引結(jié)構(gòu)來(lái)支持新的準(zhǔn)則。然而，公眾還是很擔(dān)心個(gè)人數(shù)據(jù)的不正當(dāng)使用，特別是通過(guò)鏈接多個(gè)數(shù)據(jù)源的數(shù)據(jù)。如果只是隱藏用戶的身份信息，而沒有隱藏他的位置信息，這并不是一個(gè)好的解決方案。其他幾種個(gè)人信息如關(guān)于個(gè)人健康（比如在癌癥治療中心去過(guò)）或者宗教偏好（比如去過(guò)教堂）等也可以通過(guò)觀察匿名用戶的移動(dòng)和使用模式推理獲得。還有很多其他的具有挑戰(zhàn)性的研究課題。還有一個(gè)重要方向是重新思考在大數(shù)據(jù)中信息共享的安全性研究。新的可視化分析嘗試按照這種原理去做，至少是在整個(gè)管道中建模和分析得環(huán)節(jié)。這些專家有可能在空間和時(shí)間上是分離的，數(shù)據(jù)系統(tǒng)應(yīng)該接受這種分布式的專家輸入，并支持多個(gè)專家之間的協(xié)作。雖然大部分這種錯(cuò)誤會(huì)被其他的人發(fā)現(xiàn)并且糾正，我們需要技術(shù)來(lái)支撐。在一種特定類型的眾包，即參與感測(cè)中不確定性和錯(cuò)誤的問(wèn)題更加顯著。 數(shù)據(jù)采集 數(shù)據(jù)清洗隨著信息化建設(shè)的不斷深入，企事業(yè)單位積累了大量的電子數(shù)據(jù)，這些數(shù)據(jù)非常重要。根據(jù)“進(jìn)去的是垃圾，出來(lái)的也是垃圾（garbage in，garbage out）”這條原理，若不進(jìn)行清理，這些臟數(shù)據(jù)會(huì)扭曲從數(shù)據(jù)中獲得的信息，影響信息系統(tǒng)的運(yùn)行效果，也為企業(yè)構(gòu)建數(shù)據(jù)倉(cāng)庫(kù)、建立決策支