【摘要】：在現(xiàn)今社會的信息發(fā)展過程中,各種來源的數(shù)據(jù)不斷累積,但是原始累積的數(shù)據(jù)往往含有臟數(shù)據(jù),例如錯誤的、相似重復的和缺失的數(shù)據(jù)等,對于臟數(shù)據(jù)進行清洗的一個關鍵點在于去除數(shù)據(jù)集中的重復數(shù)據(jù)。本文主要對相似重復記錄檢測的相關算法進行了研究與創(chuàng)新。相似重復記錄檢測是指準確地檢測出源數(shù)據(jù)集中的重復數(shù)據(jù),以達到清洗數(shù)據(jù)的目的。在真實情景中,數(shù)據(jù)規(guī)模龐大,數(shù)據(jù)來源多樣,這都增加了重復數(shù)據(jù)檢測的難度。雖然存在一些解決這類問題的優(yōu)秀算法,例如近鄰排序算法和多趟近鄰排序算法等,但是已有的算法在解決實際應用中的重復記錄檢測問題時,仍存在不足之處。本文首先研究了傳統(tǒng)的多趟近鄰排序算法,并對該算法的缺點進行改進,提出了優(yōu)化的多趟近鄰排序算法(OMPN),以適用于實際問題;然后,通過研究基于遺傳神經(jīng)網(wǎng)絡求解重復檢測問題的算法,將OMPN算法與神經(jīng)網(wǎng)絡相結合,得到準確度更高的A-OMPN算法和BP-OMPN算法;最后,將本文提出的OMPN算法應用于“航天情報信息管理系統(tǒng)”的數(shù)據(jù)清洗模塊,該算法在實際應用中得到了較好的效果。本文的主要內容如下:1.優(yōu)化的多趟近鄰排序算法(OMPN)。傳統(tǒng)的多趟近鄰排序算法首先對數(shù)據(jù)集中的記錄依據(jù)預先選取的排序關鍵字進行排序,使得相似重復記錄排序后位置相近,然后使用固定大小的滑動窗口對排序后的數(shù)據(jù)進行判等。但是,該過程不僅需要依賴專家經(jīng)驗知識進行關鍵字的選取,而且需要人工選擇判等字段,也沒有考慮真實數(shù)據(jù)可能存在數(shù)據(jù)缺失的問題,同時,固定大小的滑動窗口不僅會導致對重復數(shù)據(jù)的檢測不全面的問題,而且會導致對非重復數(shù)據(jù)的冗余檢測。本文在多趟近鄰排序算法的基礎上,提出基于字段區(qū)分度的關鍵字選取方法,根據(jù)數(shù)據(jù)的統(tǒng)計特點進行關鍵字的選取,同時,在判等過程中,同樣根據(jù)字段區(qū)分度為字段賦予不同權值,避免了人為干擾;然后,采用自適應大小的滑動窗口對排序后的記錄進行檢測,減少了漏檢記錄數(shù)量和冗余操作;最后,對源數(shù)據(jù)中存在缺失值的記錄進行標記和單獨檢測。通過實驗驗證,本文所提出的改進的多趟近鄰排序算法具有較高的查全率,且更適用于真實問題場景。2.基于神經(jīng)網(wǎng)絡的多趟近鄰排序算法(A-OMPN和BP-OMPN)�；谶z傳神經(jīng)網(wǎng)絡進行相似重復記錄檢測的算法效果較好,但是該算法時間復雜度較大,耗時嚴重。本文將多趟近鄰排序算法與遺傳神經(jīng)網(wǎng)絡相結合,提出了基于遺傳神經(jīng)網(wǎng)絡的增強的多趟近鄰排序算法,記作A-OMPN,使得神經(jīng)網(wǎng)絡可以僅對同一個滑動窗口內的記錄進行判等,避免了傳統(tǒng)的遺傳神經(jīng)網(wǎng)絡對數(shù)據(jù)全集上的任意兩個不同的記錄進行判等,極大地提高了算法的運行效率。同時,考慮到遺傳神經(jīng)網(wǎng)絡訓練速度慢的缺點,本文嘗試使用單一的神經(jīng)網(wǎng)絡執(zhí)行判等操作,得到了基于單一神經(jīng)網(wǎng)絡的多趟近鄰排序算法,記作BP-OMPN。作為OMPN算法和傳統(tǒng)遺傳神經(jīng)網(wǎng)絡算法的結合,實驗結果表明,A-OMPN算法和BP-OMPN算法能得到比OMPN算法更高的查準率,并且比傳統(tǒng)的遺傳神經(jīng)網(wǎng)絡算法的運行效率更高。3.本文所提出的OMPN算法在“航天情報信息管理系統(tǒng)”中的應用。本文主要完成了該系統(tǒng)的數(shù)據(jù)清洗模塊和移動端模塊的開發(fā)。在真實業(yè)務場景中,航天情報管理系統(tǒng)的數(shù)據(jù)清洗模塊需要實現(xiàn)對源數(shù)據(jù)的去重和清洗,因為該系統(tǒng)所使用的數(shù)據(jù)是真實的不帶標簽的數(shù)據(jù),且數(shù)據(jù)規(guī)模相對較小,所以綜合分析OMPN算法、A-OMPN算法與BP-OMPN算法的優(yōu)勢與適用場景,最終采用OMPN算法實現(xiàn)該系統(tǒng)的數(shù)據(jù)清洗模塊。
【圖文】：

驗證流程示意圖

圖 2.4 Merkle 樹哈希值計算示意圖樹進行完整性證明時，需要獲取目的節(jié)點的遍歷路徑e 樹的根節(jié)點的哈希值，并與存儲的根節(jié)點的哈希值整性[52]。遍歷路徑是指由根節(jié)點到達目的節(jié)點的路徑路徑是指由根節(jié)點到目的節(jié)點的路徑上所有節(jié)點的兄示，，每一個葉子節(jié)點存儲對應數(shù)據(jù)塊的哈希值，M確性。以2h ( x)節(jié)點為例，該葉子節(jié)點的認證路徑為{徑和節(jié)點存儲的哈希值的關系來計算 MHT 的根節(jié)2)|| h ( x ))|| h ( D )|| h ( B))成立。根據(jù) Hash 函數(shù)的單向性儲的根節(jié)點 Root 值就可以判斷 MHT 結構的正確性需要更新該節(jié)點的遍歷路徑上的所有節(jié)點值即可。性檢測方法[52]是為了獲得數(shù)據(jù)完整性證明中所需要歷路徑和認證路徑。用 flag 表示當前節(jié)點的訪問狀還未被訪問；若 flag=1，則表示該節(jié)點已被訪問過
【學位授予單位】：西安電子科技大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP311.13

【參考文獻】

相關博士學位論文 前1條

1 杜紅珍;數(shù)字簽名技術的若干問題研究[D];北京郵電大學;2009年

本文編號：2622258