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

驗(yàn)證流程示意圖

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

【參考文獻(xiàn)】

相關(guān)博士學(xué)位論文 前1條

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

本文編號(hào)：2622258