面向圖流和文本數(shù)據(jù)分類的哈希方法研究.pdf

1、隨著信息社會(huì)的快速發(fā)展和網(wǎng)絡(luò)的廣泛應(yīng)用，每天從社交網(wǎng)絡(luò)、業(yè)務(wù)交易以及傳感器等應(yīng)用中產(chǎn)生的數(shù)據(jù)難以計(jì)數(shù)。盡管傳統(tǒng)的哈希技術(shù)能夠很大程度上壓縮數(shù)據(jù)并提高數(shù)據(jù)管理性能，但是壓縮后的數(shù)據(jù)往往會(huì)丟失很多重要的信息，也因此失去了相應(yīng)的挖掘價(jià)值。為了解決這一問(wèn)題，本文以圖流及文本數(shù)據(jù)的分類問(wèn)題為背景，研究有效的哈希方法，在實(shí)現(xiàn)對(duì)數(shù)據(jù)壓縮的同時(shí)，盡可能保證數(shù)據(jù)信息的完整性，以此為基礎(chǔ)實(shí)現(xiàn)有效的數(shù)據(jù)分類。
　　針對(duì)圖流的應(yīng)用場(chǎng)景，本文提出了基于區(qū)分

2、性圖團(tuán)特征的哈希方法（DICH）用于對(duì)圖流數(shù)據(jù)進(jìn)行快速分類。其主要思想是采用快速算法將圖分解成若干圖團(tuán)，然后順序地提取圖團(tuán)模式作為圖特征。該方法利用兩個(gè)隨機(jī)哈希方案壓縮圖流數(shù)據(jù)中原始的邊集信息，并將無(wú)限增加的圖團(tuán)模式映射到一個(gè)固定大小的特征空間中。這些已經(jīng)被映射的圖團(tuán)信息被用于實(shí)時(shí)更新一個(gè)存放于內(nèi)存中并且大小固定的模式類別表，該表最終將被用于構(gòu)建一個(gè)基于規(guī)則的分類器。實(shí)驗(yàn)結(jié)果表明，DICH方法在盡可能保留數(shù)據(jù)信息的同時(shí)，解決了圖流挖掘問(wèn)

3、題中圖團(tuán)模式信息的無(wú)限擴(kuò)大問(wèn)題、加快了圖流數(shù)據(jù)的分類過(guò)程并且提高了分類效率。
　　針對(duì)圖流數(shù)據(jù)中概念漂移的問(wèn)題，在 DICH方法的基礎(chǔ)上，本文進(jìn)一步提出了一個(gè)面向?qū)崟r(shí)圖流分類的自適應(yīng)哈希方法（ARC-GS）。首先，為了有效地識(shí)別圖流數(shù)據(jù)中的概念漂移數(shù)據(jù)，整個(gè)圖流數(shù)據(jù)被劃分成若干個(gè)含有相同圖數(shù)量的數(shù)據(jù)塊。對(duì)于每個(gè)數(shù)據(jù)塊，采用隨機(jī)哈希方案壓縮圖流中原始的節(jié)點(diǎn)信息。然后，基于之前數(shù)據(jù)塊的特征信息，探測(cè)出當(dāng)前塊中的新舊圖團(tuán)特征，以便及時(shí)地

4、發(fā)現(xiàn)概念漂移數(shù)據(jù)。之后采用差分哈希方案，將新舊圖團(tuán)特征映射到各自大小固定的特征空間中，該特征空間被用來(lái)增量學(xué)習(xí)一個(gè)實(shí)時(shí)塊分類器。最后，采用塊級(jí)加權(quán)機(jī)制建立一個(gè)集成的圖流分類器。實(shí)驗(yàn)結(jié)果表明，面向?qū)崟r(shí)圖流分類的自適應(yīng)哈希方法不僅更好地保留了數(shù)據(jù)的信息，并且一定程度上加快了圖特征提取的過(guò)程，解決了圖特征的無(wú)限增加問(wèn)題，有效地適應(yīng)了帶有概念漂移數(shù)據(jù)的圖流分類問(wèn)題。
　　在 DICH哈希方法的基礎(chǔ)上，針對(duì)快速圖流分類問(wèn)題，進(jìn)一步提出了一個(gè)

5、圖分解方法。該方法的主要目的是使用區(qū)分性圖團(tuán)的線性組合表示圖并用于圖流分類。這種圖分解方法不僅確保信息損失盡可能小，同時(shí)也避免了耗時(shí)的子圖同構(gòu)驗(yàn)證過(guò)程。基于這種思想，本文提出了一個(gè)基于圖分解的細(xì)粒度表示模型用于快速圖流分類。實(shí)驗(yàn)結(jié)果表明，這種基于細(xì)粒度的圖表示模型能夠更好地保留圖的信息并實(shí)現(xiàn)高效的圖流分類。
　　針對(duì)文本數(shù)據(jù)的分類問(wèn)題，本文提出了一個(gè)遞歸最小哈希方法（RMH）。該方法的目標(biāo)是快速計(jì)算文本之間的相似度，同時(shí)盡可能保留