[發明專利]一種基于壓縮感知理論的文本數據流抽樣方法

有效

• 申請號: 201510024381.1
• 申請日: 2015-01-16
• 公開（公告）號: CN104504156B
• 公開（公告）日: 2017-07-11
• 發明（設計）人: 彭敏
• 申請（專利權）人: 武漢大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙)42222
• 代理人: 薛玲

技術領域

本發明屬于互聯網大數據文本檢索領域，涉及一種文本壓縮和抽樣技術，具體涉及一種基于壓縮感知理論的大規模文本數據流抽樣方法。

背景技術

隨著社交媒體的發展，越來越多的人喜歡分享最新的新聞熱點問題或對產品進行評論。這些諸如Twitter、Facebook、Blogger和亞馬遜等社交媒體或者電商網站的用戶產生的內容(UGC)形成了大規模的文本數據流。例如，超過80％的新浪微博用戶參與2014巴西世界杯的話題討論、超過76％的用戶在他們觀看比賽直播時發布微博。截至2011年1月，在YouTube上搜索奧巴馬就職典禮就有超過30000個視頻。2010年在YouTube上U2演唱會的直播在Twitter上產生了超過130000的帖子。UGC能夠以數據流的形式被連續收集，并且在各個領域也有廣泛的應用，如科學研究、系統管理、客戶調查、輿情分析等等。這些應用通?？梢猿橄蟪筛黝愐晕谋緸楹诵牡男畔⑼诰蛉蝿眨绮粩嗝嫦騎witter文本流，可以挖掘高質量的文本集或重要頻繁模式，以及檢測大規模數據流出現的新文檔或新主題。

然而，使用UGC文本流做挖掘任務存在兩個重要的挑戰：1)如何管理和儲存大量動態文本流，使之更有效的計算？2)在以文本為中心的挖掘任務中，例如主題探測或用戶興趣分析，是否需要使用的所有文本流？也就是說，是否所有的文本流在挖掘任務同等重要？

事實上，在信息檢索或新主題探測等以文本為中心的挖掘任務中，一方面，對于一個給定的計算量，減少其所需的機器或者磁盤數量可以節省計算資源消耗的成本。此外，減少數據規模能夠讓更多的數據存儲在內存中，從而提高計算效率；另一方面，UGC文本通常與各種現實世界的事件相關，對于特定分析目標，這些UGC文本中的一些可能包含有趣和有用的信息，而另一些則價值很小。根據研究，近36％的tweets值得一讀，其余tweets的可讀性一般甚至較差。也就是說，不同文本的內容質量有很大的不同，因此，從大規模文本流中識別出高質量的文本流，對于提高以文本為核心的挖掘任務的準確性和效率至關重要。此外，從時序分析來看，歷史數據通常比新到達的數據價值小。因此，根據文本內容的質量和新鮮度對文本加以區分至關重要，一般將內容質量高和新鮮度高的文本稱為有價值的文本。

社交媒體和電子商務的普及使得在線用戶原創內容文本UGC，如微博、博客和產品評論等，持續和快速地增長。這些大規模文本具有海量、暫時有序、快速變化和潛在無限的特點。如何使用更少的內存消耗、更快的計算時間，來處理不斷增加的文本流，是互聯網大數據文本檢索領域的迫切需要解決的問題。

發明內容

為了解決上述的技術問題，本發明面向互聯網海量的、不斷增加的文本流，提出了一種基于壓縮感知理論的文本數據流抽樣方法，通過更少的存儲消耗來實現更快的文本流抽樣和存儲，在大大降低抽樣文本流規模的情況下，確保能夠以全局視角獲得整個文本流中最有價值的那部分信息。

本發明所采用的技術方案是：一種基于壓縮感知理論的文本數據流抽樣方法，其特征在于，包括以下步驟：

步驟1：將文本數據流分割成固定大小的文本片段并通過向量空間模型表示成矩陣；

步驟2：使用壓縮感知理論對文本數據流進行空間降維抽樣；

步驟3：計算降維后每個文本的信息熵；

步驟4：基于文本的信息熵通過對數傾斜時間(LTT)模型壓縮存儲抽樣文本。

作為優選，步驟1中所述的固定大小的文本片段由TF或TF-IDF模型表示成矩陣其中P表示固定大小文本片段中文本的數量，n為向量空間的維數，L是當前文本數據流片段的數量。

作為優選，步驟2的具體實現過程是，對于給定的文本片段使用高斯隨機矩陣作為測量矩陣Ф，使用壓縮理論中的公式對X_l進行投影得到測量值實現空間降維，其中m≤n，計算如公式1所示：

Y_l＝ΦX_l(公式1)。

作為優選，步驟3的具體實現過程是，對于降維后每個文本，第l個文本片段中的第i個文本的內容質量由信息熵E(i,l)來衡量，其計算如公式2所示：

E(i,l)＝-Σp(t_j,l)logp(t_j,l)(公式2)；

其中p(t_j,l)是第i個文本中第j項在第l個片段中出現的頻率，t_j,l∈Y_iⁱ。

作為優選，步驟4的具體實現包括以下子步驟：