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

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

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

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

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

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