一種社交網絡文本數據的索引方法與流程
2023-06-10 17:19:46
本發明涉及索引技術領域，尤其涉及一種社交網絡文本數據的索引方法。
背景技術：
自網際網路的發展從web1.0步入web2.0的新時代後，各種各樣的由用戶主導而生成的內容網際網路產品隨之發展起來，如博客、rss等。在線社交網絡服務(socialnetworkingservice，sns)發展成為網絡上最受歡迎的應用。各種在線社交網絡服務網站都出現在人們眼前，如twitter，facebook，新浪微博等。在現實世界中，人們通過結識更多的人以擴展自己的社交圈，更優更廣的社交關係往往是一個人自身價值與自我發展的關鍵。而在這些在線社交網絡中，用戶可以發布自己的狀態或者了解最近的好友狀態，或者分享給他人生活體驗，與好友互發消息、照片及視頻等。這彌補了由於身在異地或者其他原因無法面對面溝通交流的遺憾，在線社交網絡現在提供一種新興又非常普適的交友方式，依靠其真實性、便利性、可玩性以及穩定性、方便熟人朋友間的溝通、也為陌生人之間提供了認識的橋梁等特點得到了人們的認可和青睞。定位技術的發展應用，並且又結合gis地理信息系統，確定用戶是基於地理的位置服務(locationbasedservice，lbs)也快速發展開來。社交網站引入用戶主動籤到機制，並適當整合用戶位置信息與社交信息，可在籤到行為的基礎上提供後續有價值的服務。
儘管社交網站實現了各種各樣技術特點的功能，但是它們主要的「骨幹」是一組組可見的個人文本或者圖片等信息。這些信息是用戶唯一可以自己輸入的。一個人加入一個社交網絡後，會被要求填寫包含一系列問題的表單，通常包含一些特有的描述，如年齡、地址、興趣和自我介紹。大多數網站還鼓勵用戶上傳個人照片。有些網站允許用戶提交一些多媒體文件或者修改個人基本信息來提升個人帳號的形象。不同的社交網站的用戶能見度情況也是不一樣的。默認情況下，這些用戶信息都可以被查看，但是也存在一些社交網站是收費查看，或者是只對好友開放查看，或者是只允許其他人查看部分的信息。由於在可見性和訪問方式的區別下，社交網站也相互區別開來。
當用戶在加入一個社交網站時，識別系統會推薦與其有關係的其他用戶。這些關係的標籤主要分為朋友，聯繫人，粉絲等。大多數社交網站需要雙向確認友誼。單向的關係則會被貼上粉絲的標籤。而朋友的標籤也可能會誤導人，因為這種連接不一定意味著日常關係上的友誼，因為人們聯繫的原因是多種多樣的。除了用戶的個人信息之外，社交網絡還提供結識朋友、發表評論和發送私人消息等功能。有的社交網站會提供照片分享或者視頻分享的功能，或者是內置博客和即時消息傳遞功能。許多社交網站的目標用戶會是特定的地理區域或者特定語言使用團體，儘管實際上可能並不是特定的目標用戶。
隨著位置服務(locationbasedservice，lbs)與社交網絡逐漸融合，形成了基於位置的社交網絡(location-basedsocialnetworks，lbsn)，它通過移動用戶的位置籤到功能，把線上虛擬社會與線下真實世界關聯在一起，實現用戶位置定位的同時，還實現了位置信息在虛擬網絡世界的共享和傳播，從而衍生出多種多樣的位置服務，其中，推薦系統作為目前解決信息過濾和個性化服務問題的重要技術手段之一，在位置服務中發揮著越來越重要的作用。
社交網絡的快速崛起和廣泛應用，讓更多的人加入到社交網絡中進行信息交流活動。人們產生，傳播和使用信息的方式被社交網絡所改變。社交網絡與傳統的網際網路不同：傳統網際網路中的用戶只是信息的接收者，他們只能通過網站瀏覽信息；在社交網絡中，用戶除了作為信息消費者，又是信息的發布者和傳播者。用戶可以在社交網絡中發布信息，並且被發布出來的信息通過社交網絡平臺在用戶群體之間傳播。例如，用戶在facebook上分享自己的觀點，關注那些自己會感興趣的信息，並將這些信息分享給好友。又如，在twitter和新浪微博上，用戶可以發表自己的微博，添加好友，也可以向粉絲們分享自己的興趣愛好信息等。
目前，社交網絡中的用戶規模和用戶發布的信息增量迅猛，而包含著地理位置信息的內容也在被越來越多的人所關注。社交網絡所提供的信息是很豐富的。一般情況下，人們使用社交網絡平臺與朋友保持聯繫和尋求各種不同的社會信息。現在，廣泛採用了的全球定位系統的移動終端和基於位置的移動服務(lbs)的成功使得社交媒體數據能夠獲取到地理位置信息。地理位置標記微博在分享言論和意見、獲取新聞和了解現實世界的真實事件上發揮了重要的作用。因此基於位置的社交網絡成為了豐富的含有地理信息的資源。
但是，當前的傳統主流搜尋引擎大多在從含有豐富的關鍵詞的長文本中獲取相關的信息，這種方式並不適合包含一些關鍵字信息的短文本社交媒體數據。當前流行的微博它們自身也提供了一些實時搜索服務，搜索返回與用戶輸入的關鍵字相關的高排名的微博，然而這種搜索並沒有包含所發微博的空間信息，對於用戶來說，用戶可能希望自己的搜索結果是結合了微博的空間信息之後，獲取到的最合適的信息。並且，現有的技術在進行相關信息的索引時，都是根據單一的關鍵字或者單一的信息點進行搜索，使得搜索準確性降低，搜索的工作量增大，降低了用戶的體驗，為用戶進行有效信息的查找帶來不便。
技術實現要素：
針對上述問題，本發明的目的在於提供一種社交網絡文本數據的索引方法，在顧及關鍵詞相關性的同時，考慮地理位置的相關性。
為了解決背景技術中所存在的問題，本發明的技術方案為：
一種社交網絡文本數據的索引方法，包括以下步驟：
1)、獲取需求用戶的地理位置，根據需求用戶輸入的需求，對社交網絡中的文本數據進行分詞處理，獲取與需求用戶的需求相匹配的關鍵詞組；
2)、根據所獲取的關鍵詞組，建立索引樹dlir-tree，所述索引樹dlir-tree的每個節點包含一系列的社交網絡文本的發送用戶，每個節點的發送用戶都是由該節點的下一層的子樹所包含的發送用戶的集合；
3)、根據需求用戶的需求、地理位置及區域半徑查詢索引樹dlir-tree，得到相應的文本數據。
所述步驟1)具體包括：
1.1、對待處理的文本數據進行分詞停用詞、標點符號、表情處理，得到處理後的文本數據；
1.2、利用正向匹配策略與逆向匹配策略對處理後的文本數據對文本數據分詞，通過相互的信息比對，以及歧義詞語對的互信值比較，以互信值高一組為最終的分詞結果，輸出分詞集合。
所述步驟2)具體包括：
定義dlir-tree葉子節點對象，其中每個實體對象都包含了地理位置信息l，λ為存在一個與該地理位置對應的最小邊界矩形mbr屬性，與地理位置相關聯的文本關鍵詞ψ，並且存在集合f代表一組發送用戶，這組發送用戶在該地理位置上籤到過的；
定義dlir-tree非葉子節點對象，其中，r表示了孩子節點對象的集合，λ為其孩子節點的地理位置所組成的對應的最小邊界矩形mbr屬性，最小邊界矩形對所要查詢的區域用戶做相應的匹配計算，ψ對應了所有的孩子節點所包含的文本關鍵詞，f為對象中一組在該區域做過籤到行為且發表過文本的發送用戶。
所述步驟3)具體包括：
給定一個查詢需求q、給出一個非葉子節點實體e，以及它的最小邊界矩形e.λ，用trq(p)表示對象實體p對應的關聯倒排文本與查詢q的關鍵詞的相關度，對於任意屬於節點e的對象實體p，均有對於文本籤到位置與需求用戶發起查詢的地理位置之間的社會距離相關性的公式：
在上述公式中，sdq(p)表示對象實體p對於用戶u發起的查詢的社會距離相關性，其中，α∈[0，1)，常量1保證了計算的相關性永遠不會等於零。
與現有技術相比較，本發明的有益效果為：
本發明提供了一種社交網絡文本數據的索引方法，同時考慮文本數據和地理位置的混合索引結構，簡稱dlir-tree，以便於根據用戶的需求快速搜索得到符合需求及在區域範圍內與關鍵詞組相關的文本信息，並且能夠通過邊界評分方式提供搜索空間的剪枝能力，通過利用地理位置已經查詢的需求建立索引，增大了索引能力，減低了索引的數據處理量，提供了工作效率。
附圖說明
圖1是本發明社交網絡文本數據的索引方法流程圖；
圖2是本發明社交網絡文本數據的索引方法dlir-tree結構圖；
圖3是本發明實施例微博倒排索引結構圖；
圖4是本發明實施例地理位置圖；
圖5是本發明實施例倒排文件圖。
具體實施方式
下面結合附圖對本發明做詳細描述。
用戶可能通過移動終端發表一條文本的時候，該移動終端支持位置定位服務，那麼用戶可以選擇是否標記地理位置進行籤到，但是並不是所有的移動終端都支持位置定位服務，也可能用戶不讓別的用戶或者好友看見自己在何地發表微博而故意不籤到。針對這種情況，本發明對帶有地理位置信息的社交網絡數據節點進行處理。
如圖1所示，本發明提供了一種社交網絡文本數據的索引方法，包括以下步驟：
1)、獲取需求用戶的地理位置，根據需求用戶輸入的需求，對社交網絡中的文本數據進行分詞處理，獲取與需求用戶的需求相匹配的關鍵詞組；
1.1、對待處理的文本數據進行分詞停用詞、標點符號、表情處理，得到處理後的文本數據；
定義漢字字符集合∑＝{c1，…，ci，…，cn}，其中c1表示漢字的字符，∑*表示在字符集∑上的字符串集合。
定義分詞規則為κ表示在某種語境下，對於w∈∑*，k∈κ，符合seg(w，k)＝1說明w是一個詞語，seg(w，k)＝0就表示w不是詞語。一般來說，當把κ退化為一個詞庫v時，seg(w，k)＝1(w∈v)，或者
定義針對應用d(applicationdomain)的詞彙及(詞庫)：
vd＝{w1，…，wi，…，wv|wi∈∑*}，並且應用d滿足segd(wi)＝1。
不考慮對d的限制，認為任何詞庫都可以作為參考，vd簡記為v。於是v*表示在v的詞彙串集合。
定義tail(s)＝tail(c0c1…ck)＝ck，head(s)＝c0，vcat(ci，cj)＝cicj，ci，cj∈s。
定義如果存在字符串s∈s，是s＝c1c2…cn的一種分詞結果，記為
定義將分詞規則定義為k，中文分詞問題就成為了利用計算機解決式子：
中文分詞方法中，常用的方法主要有正向最大匹配分詞法(forwardmaximummatchingmethod，fmm)和逆向最大匹配分詞法(reversemaximummatchingmethod，rmm)。
正向最大匹配分詞法fmm主要依據了分詞詞典來進行詞語切分，它的思想是：假定如果分詞詞典中最大長度詞條的長度為n即該詞條由n個字符組成，首先獲取文檔的中文短語，然後讀取當前中文短語中的前n個字符，這些字符就是需要匹配的字符串，然後開始分詞操作，與分詞詞典中的詞語進行匹配，如果詞典中有這個字符串形成的詞語，那麼匹配成功，這個字符串就是一個詞語被切分出來；如果詞典中找不到對應這樣的一個詞語，就認為匹配失敗，此時去掉字符串最後一個字符，繼續進行匹配，直到匹配成功出一個詞或者字符串只剩下一個字符結束匹配。以偽代碼的形式在下面給出正向最大匹配分詞法的描述：
逆向最大匹配分詞方法rmm與正向最大匹配分詞方法fmm的基本原理相同，但是不同的地方在於分詞切分掃描的方向與fmm方法是相反的。逆向最大匹配分詞法從文檔的末尾處進行匹配，使用逆序詞典作為分詞詞典，其中每個詞語都是正常詞語的逆序形式。在算法中，首先要對被處理文檔進行逆序的操作，生成逆序文檔。接著採用逆序詞典對逆序文檔進行匹配。由於中文語句大多是偏正結構的形式，從後向前的匹配策略能夠使得分詞的準確率得到提升。以偽代碼的形式在下面給出逆向最大匹配分詞法的描述：
歧義詞語是中文分詞中經常會出現的問題。中文歧義是對於一個中文句子進行分詞，可能會得到不同的分詞的結果。中文歧義有三種形式，交集型歧義(oas)，覆蓋型歧義(cas)和真歧義：oas歧義，設a，b，c分別代表一個或多個連續的漢字，則句子abc中，ab和bc分別可以組合成詞，那麼就被成為交集型歧義；cas歧義，設a，b各為一個或多個連續的漢字，若a，b自身分別是詞語，則稱作覆蓋型歧義；真歧義就是對於分詞結果必須根據上下文其他句子去進行判斷。
需要說明的是，在對文本內容進行分詞預處理時，需要去考慮對於停用詞的處理。在中文語句中，停用詞基本上是對這句話沒有語義上的貢獻，沒有意義。然而，這種詞語會大量出現在文本中，因此處理好停用詞能夠提高詞語切分效率以及提升後續算法處理的準確性。詞語切分時，必須對這些詞進行處理。要正確的處理好停用詞，那麼停用詞表的使用和停用詞的識別是非常重要的。
1.2、利用正向匹配策略與逆向匹配策略對處理後的文本數據對文本數據分詞，通過相互的信息比對，以及歧義詞語對的互信值比較，以互信值高一組為最終的分詞結果，輸出分詞集合。
對文本進行分詞預處理，這其中要對停用詞和標點符號進行處理，停用詞庫的獲取很方便，將文本與停用詞庫以及標點符號做比對處理。用「#」進行替換，從而可獲取到待分詞文本數據。接下來就是具體分詞算法核心處理部分，對待分詞文本進行詞語切分處理，最後得到分詞結果集合。
文本分詞處理算法中，歧義詞的處理時分詞不可避免的階段，採用計算互信來進行歧義的消除。互信的公式如下所示：
在公式(4.1)中，xy表示中文有序字符串，x、y分別是其中兩個詞。
示例性的，本發明以偽代碼的形式在下面給出微博文本分詞處理算法的描述：
該算法首先通過對文檔x與停用詞集合的處理獲取到處理後的文檔x1，那麼文檔x1經過停用詞處理後，實際上將其變成了由一句短語構成的文本。之後讀取文檔x1，首先獲取一個中文短語s，如果中文短語s長度小於分詞詞典最長詞語長度，則直接對中文短語進行分詞，如果中文短語s長度大於分詞詞典最長詞語長度，則就需要進一步截取字符串進行分詞，算法中採用字符串term1與正向分詞詞典匹配進行正向分詞的操作，採用term2與逆向分詞詞典匹配進行逆向分詞的操作。當獲取到正向分詞集合fw和逆向分詞集合rw後，首先將逆序分詞集合rw詞語進行逆向操作獲取正確的詞語集合，然後比較正向與逆向分詞集合，判斷是否出現了歧義詞語，當出現歧義詞語的時候，就記錄這些歧義詞語存入集合aw中。算法中對消除歧義的做法採取的是，先參照集合c1中的詞語出現次數，然後統計歧義詞語出現的概率，並根據公式(4.1)進行互信計算，互信的分高的那組為最終的分詞結果。算法最終生成輸出分詞集合r。
2)、根據所獲取的關鍵詞組，建立索引樹dlir-tree，所述索引樹dlir-tree的每個節點包含一系列的社交網絡文本的發送用戶，每個節點的發送用戶都是由該節點的下一層的子樹所包含的發送用戶的集合；如圖2所示，圖2為dlir-tree結構圖，在這個樹中，葉子節點由一組實體對象構成。給出該對象的形式化定義：
定義dlir-tree葉子節點對象定義表明每個實體對象都包含了地理位置信息l，並且存在一個與該地理位置對應的最小邊界矩形mbr屬性λ，與地理位置相關聯的文檔即用戶在該地理位置籤到時所發的微博文本關鍵詞ψ，並且存在集合f代表一組用戶，這組用戶都是在該地理位置上籤到過的。
對於dlir-tree索引樹的每個葉子節點來說，每個葉子節點映射一個相應的倒排文件。
倒排文件又被稱作倒排索引，它的含義是用記錄的非主屬性值(也叫副鍵)來查找記錄而組織的文件叫倒排文件，即次索引。倒排文件中包含了所有的非主屬性值，並且列出了與之有關的所有記錄的主鍵值，倒排文件主要用於複雜查詢處理。
對於搜尋引擎而言，它需要一個特別有效的數據結構處理收集到的數據，並在這個基礎上給用戶提供搜索服務。現在大量的搜尋引擎都採用倒排文件的索引方式處理數據。根據倒排文件的特徵可以看到，倒排文件簡單地認為是一種用文檔的關鍵詞作為索引，而文檔自身作為索引目標的結構。
針對葉子節點關聯的倒排文件，如圖3所示，由兩個主要的部分構成：
(1)一個關鍵詞詞彙表，這些關鍵詞均在某些微博文本中出現過。
(2)對於每一個單詞來說，它對應的一組微博文本集合，以鍊表形式表現。例如對於一個關鍵詞w來說，一篇微博文本中出現了這個關鍵詞w，那麼將這樣的微博文本放在同一個集合中。
對於dlir-tree中的每一個非葉子節點，給出了形式化的定義：
定義dlir-tree非葉子節點對象定義中r表示了它的孩子節點對象的集合，並且其孩子節點的地理位置所組成的對應的最小邊界矩形mbr屬性λ，這個最小邊界矩形可以對所要查詢的區域用戶做相應的匹配計算，ψ對應了它所有的孩子節點所包含的微博文本關鍵詞，對象中的f也是一組在該區域做過籤到行為且發表過微博的用戶，同時這些用戶也是該節點的孩子節點對應的用戶集合。
對於dlir-tree索引樹的每個非葉子節點來說，每個非葉子節點也始終會映射一個相應的倒排文件。
如圖4所示，圖4是對於圖2dlir-tree樹中各個節點的一個地理位置圖。如圖所示，位置l1和位置l2形成了一個mbr即r1，位置l3和位置l4形成了一個mbr即r2，位置l5、位置l6和位置l7形成了一個mbr即r3，位置l8和位置l9形成了一個mbr即r4，接著r1與r2形成上一層的mbr即r5，r3與r4形成上一層的mbr即r6，與圖2dlir-tree相對應。
示例性的，如圖5所示，是對於圖2dlir-tree樹中各個節點的一個倒排文件圖。圖中左側為節點r5的倒排文件，文件中包含六個關鍵詞，其中每一個關鍵詞對應了構成r5的r1與r2的實體對象，可以看到價格對應r1與r2，牛排對應r1，餐廳對應r1與r2，電影院對應r1，酒店對應r2，商場對應r2。圖中中間部分是r1對應的倒排文件，右側部分是r2對應的倒排文件。因為r1對應的孩子節點已經是葉子節點，因此其對應的倒排文件內容關聯的是具體的微博文本，已在圖中表示。
所定義的dlir-tree繼承了典型的ir-tree所具有的一個重要特徵，即每一個非葉子節點都有一個對應的關聯倒排文本，該關聯文本就是對以該節點為根節點的子樹的查詢的關聯倒排文本的上界。
3)、根據需求用戶的需求、地理位置及區域半徑查詢索引樹dlir-tree，得到相應的文本數據。
定義dlir-tree倒排文本單調性給定一個查詢q，再給出一個非葉子節點實體e，以及它的最小邊界矩形e.λ。用trq(p)表示對象實體p對應的關聯倒排文本與查詢q的關鍵詞的相關度。那麼對於任意屬於節點e的對象實體p，均有
例如對於圖2中數據，給定一個查詢q，那麼就有trq(r5)≥trq(r1)≥trq(p1)
對於微博籤到位置與用戶發起查詢的地理位置之間的社會距離相關性的如下列公式(4.2)所示：
在上述公式中，sdq(p)表示對象實體p對於用戶u發起的查詢的社會距離相關性。其中，α∈[0，1)，常量1保證了計算的相關性永遠不會等於零。α||uqu||s也經常會被用於其他的一些社交網絡評分計算以及pagerank，考慮對其進行合適的處理，應用在dlir-tree的查詢算法中。
基於以上定義與公式，給出下列定義：
定義給定一個查詢q，再給出一個非葉子節點實體e，並且它擁有孩子節點，孩子節點包含了n個實體對象，有e＝{ei，1≤i≤n}，那麼對於任意的孩子節點對象實體，都有
因為ei是e的孩子節點中的一個對象，ei一定是e的一個子集，有對於定義4.10可以給出以下證明：
dlir-tree查詢算法：
對於給定的一個微博文本p與用戶需求q關鍵詞組的相似度，可以用下列公式(4.3)計算：
根據對微博文本分詞處理後，可將微博文本看作是由一組關鍵詞組成的，即微博文本自身也是一個關鍵詞組。那麼通過對公式(4.3)的分析可知，當wp，i*wq，i的結果為零時，是不影響相似度的，而只有當p或者q其中任意一方的關鍵詞不能匹配時，wp，i*wq，i的結果為零。當p或者q中的關鍵詞不完全匹配時，也就是其中有一方不存在該關鍵詞，但是這種情況出現的比較少，那麼可以考慮以關鍵詞存在較多的一方作為參考對象，而不考慮關鍵詞存在較少的一方。相反，當p或者q中的關鍵詞匹配度非常低的時候，也就是wp，i和wq，i存在非常多的零項時，那麼就考慮以關鍵詞存在較少的一方作為參考對象，而不考慮關鍵詞存在較多的一方。公式(4.4)是改進的餘弦相似度計算公式，其中k為選擇的關鍵詞的索引集合，去掉了不考慮的關鍵詞組中的關鍵詞。
改進的餘弦相似度計算公式能夠保證當匹配度高的情況下，給與其一定的權值挑選出來，匹配度過低的情況下，賦予其較低的權值，使得相似度的區分更加快速更加合理。結合dlir-tree以及改進的餘弦相似度計算公式，可以獲取到微博plist。
以偽代碼的形式在下面給出dlir-tree查詢算法的描述：
上述算法首先初始化一個優先隊列u，該隊列存放的是對dlir-tree進行最佳優先搜索的結果。首先將dlir-tree的根節點存入優先隊列中，對優先隊列u進行while循環操作，當優先隊列u為非空隊列時，則表明此隊列中存在符合條件的節點或對象，那麼判斷出隊列的是否是一個實體對象，如果是一個實體對象，那麼判斷這個對象對應的微博文本是否已經存入plist中，若plist中沒有，就將該對象添加入plist中。當出隊列的不是一個實體對象時，那麼它就對應了dlir-tree中的一個非葉子節點，那麼此時遍歷這個節點e的所有孩子節點e′，如果存在孩子節點e′的社交距離小於給定的查詢半徑社交距離即sdq(e′)＜sdq(r)，並且它所對應的倒排文件關鍵詞與給定查詢關鍵詞組有交集即那麼就計算這個孩子節點與給定關鍵詞組的相似度，作為優先級別將這個孩子節點e′存入優先隊列中，然後算法繼續執行while循環，直到優先隊列為空隊列結束。
對於本領域技術人員而言，顯然能了解到上述具體實施例只是本發明的優選方案，因此本領域的技術人員對本發明中的某些部分所可能作出的改進、變動，體現的仍是本發明的原理，實現的仍是本發明的目的，均屬於本發明所保護的範圍。