一種基於主題詞條的跨類型數據的概率聚類方法

2023-09-18 15:44:55 2

專利名稱：一種基於主題詞條的跨類型數據的概率聚類方法
技術領域：
本發明屬於資料庫領域，特別涉及一種基於主題詞條的跨類型數據的概率聚類方法。

背景技術：
在過去的幾十年裡，傳統的關係資料庫管理系統發揮了非常重要的作用。可是，隨著計算機應用技術，特別是Web信息技術的不斷發展，當今的數據呈現出「海量」和「數據無處不在」這兩大特點，而且數據特徵紛繁複雜。因此傳統的某種資料庫管理系統已經無法滿足這樣一種資料庫管理的需求，而且當今的很多數據或信息根本就沒有存儲在資料庫管理系統中，正如Serge Atiteboul等在他們發表在ACM通信(48卷第5期)上的報告和Homman在DASFAA2007的大會報告中指出的那樣，目前只有20％左右的數據或信息被存儲在資料庫中。這就意味著傳統的資料庫系統已經無法滿足當今數據管理的需求，於是數據空間這一概念應運而生。
在數據空間中，需要管理跨類型(cross-type)數據，即從類型上劃分，包含結構化數據(structured data)、半結構化數據(semi-structured data)和無結構化數據(unstructured data)。在結構化數據中，主要有資料庫表，Excel表以及從各種無結構化和半結構化數據中提取出來的結構信息等；在半結構化數據中，主要指XML數據、word文檔、ppt文檔、Latex數據以及個人E-mail數據等；在無結構化數據中，主要包括txt文檔、pdf文檔、ps文檔以及圖像等。如何在跨類型數據中根據數據語義進行聚類，以提供給用戶高級語義層面的查詢是一個亟待解決的問題。
目前，針對數據的聚類問題已提出很多聚類算法。如基於劃分的K-means方法，基於密度的DBSCAN方法。但是現有的聚類算法沒有考慮到聚類過程中的不確定性(uncertainty)問題。同時，以往的這些聚類方法在處理數據的相似性關係時，處理手段過於簡單，例如K-means方法僅僅是將數據在詞條空間下的距離作為數據間的相似度。由於以上原因，基於概率的聚類方法和考慮語義信息的基於數據主題的聚類方法得到了廣泛應用。其中，基於數據主題的聚類方法是實現聚類的方法之一，而用詞條表示數據主題又是相似性計算的前提，因此首先需要解決詞條對數據主題的描述問題。其次，由於詞條與主題之間的描述關係具有不確定性，即一個詞條可以描述不同的主題，而一個主題也可以由不同的詞條集合來表示，這就導致了數據間基於不確定主題詞條的聚類問題。此外，數據間基於主題詞條的相似關係，既包含直接相似關係(direct similarity relationship)，也包含間接相似關係(indirect similarityrelationship)，如何利用這些相似關係來更全面地聚類數據是需要解決的另一個關鍵問題。


發明內容
針對現有的數據聚類方法沒有考慮到聚類過程中的不確定性(uncertainty)問題。同時，以往的這些聚類方法在處理數據的相似性關係時，處理手段過於簡單，本發明提供了一種基於主題詞條的跨類型數據的概率聚類方法，利用與主題相關的詞條項的相似性來對數據空間中的跨類型數據進行聚類，該模型稱作PTSM(Probabilistic Term Similarity Model)。本發明的具體步驟如下 步驟1定義主題詞條的類型 對於任意一個跨類型數據d，將其表示為詞條的集合d(t1，t2，...tn)，其中ti(1≤i≤n)表示數據d的第i個詞條。按照TF□IDF原則給集合中的每一個詞條賦予權重。TF□IDF公式如公式(1)-(4)所示。
tf(t)＝1+ln(1+ln(1+f(t))(1) 其中，f(t)表示詞條t在數據d中出現的頻率，N和Nt分別表示數據空間內數據的總量以及含有詞條t的數據的數量，tld表示數據d中詞條的總量，avgtl表示所有數據內詞條數量的平均數，而s是一個參數，一般取值為0.2。公式SCORE(t)用於計算詞條的權重，它從三方面考慮1)將較小的權重值分賦給在較多數據中出現的詞條；2)將較大的權重值賦給在一個數據中多次出現的詞條；3)從數據集合的整體特性考慮詞條的權重，而不是從某一個數據出發。
按照上面的權重公式對詞條分配權重後，能夠保證具有較大權重的詞條能較好地將數據區分開，從而達到理想的聚類效果。在給每個詞條賦權重後，按照權重大小分為三類詞條主題相關詞條(related term)、主題半相關詞條(semi-related term)和主題不相關詞條(unrelatedterm)，分別用r、s和u表示。權重大於某個閾值θs的詞條稱為主題相關詞條；權重小於某個閾值θu的詞條稱為主題不相關詞條；權重介於θs和θu之間的詞條稱為主題半相關詞條。此處，θs＝αθmax，其中θmax為某一個數據d中權重最大的詞條的TF□IDF權重，而α是一個參數，取值在0到1之間，我們通過實驗確定α的取值，α在0.2至0.5之間。θu則採用一種啟發式原則來確定。在確定了主題相關詞條r之後，對剩餘的詞條項按權重大小進行排序。如果令w[i]表示排名第i位的詞條的權重值，則啟發式思想是尋求相鄰兩個權值差最大的詞條所在位置k，並將位置k所對應的詞條的權值作為θu的值，即k滿足公式(5)，其中m表示剩餘詞條(即除主題相關詞條外的詞條)個數，這時θu＝w[k]。
w[k]-w[k+1]＝max1≤i≤m-1(w[i]-w[i+1]) (5) 步驟2給主題詞條分配概率 給上述每類詞條t賦予一個概率值p，則p(t)稱作詞條t的主題相關概率。p(t)表示詞條t能夠以概率p表示數據d的主題。ri的主題相關概率p(ri)＝1，ui的主題相關概率p(ui)＝0，而si的主題相關概率p(si)＝wsi/wmax，其中wsi為半相關詞條si的權重，wmax為d中所有詞條的權重的最大值，p(si)介於(0，1)之間。
步驟3用概率表示數據主題 根據步驟1和2，首先，將跨類型數據d表示成主題相關詞條r的一個確定集合，記作d(r1，r2，...，rn)，其中ri表示第i個相關主題詞條。然後，再將所有的主題半相關詞條s追加到d的確定集合中。我們稱這樣的每一個集合為跨類型數據d的一種「描述形式」。由於任意一個si是以一定的概率來表示數據的主題，那麼數據的一個確定的表示集合就演化成多個帶概率值的「描述形式」。我們希望這種「描述形式」能夠完全表示數據的主題，而主題半相關詞條只能以一定的概率表示數據的主題，因此，每一個主題半相關詞條有可能別加入到數據的的集合中，從而產生一個數據的描述形式，又或者不會被加入到數據的集合中，從而產生另一種「描述形式」。而半相關詞條被加入到集合中的概率既是p(si)，不被加入到集合中的概率為1-p(si)。換句話說，「描述形式」是不確定的，且具有一定的概率，概率值依賴於每個集合中的主題半相關詞條si，即其中k表示一個數據中主題半相關詞條的數量，m＝1，2，...，2k，dm是d的第m個「描述形式」中。如果某個si出現在dm中，則Pi＝p(si)，否則Pi＝1-p(si)。對於任意一個數據，假設它有m個主題半相關詞條，那麼存在2m個「描述形式」表示它的主題。例如，數據d有2個半相關詞條s1和s2，其描述主題的概率分別為p(s1)和p(s2)，那麼d能夠被表示為4種集合形式d1(r1，r2，...，rn)，d2(r1，r2，...，rn，s1)，d3(r1，r2，...，rn，s2)和d4(r1，r2，...，rn，s1，s2)。這四種集合存在的概率分別為(1-p(s1))(1-p(s2))，p(s1)(1-p(s2))，(1-p(s1))p(s2)和p(s1)p(s2)。
步驟4構建數據的主題詞條概率相似性矩陣M 對步驟(3)中跨類型數據d的任意兩個數據dx和dy，計算dx和dy任意兩種描述形式的相似度，假設dxi是dx的第i種描述形式，dyj是dy的第j種描述形式，則dxi和dyj的相似度計算如公式(6)所示。
假設dx含有m個半相關詞條，dy含有n個半相關詞條，那麼如果要計算dx和dy的任意兩種描述形式的相似度，共需2m+n次相似性計算，這種計算方式導致計算量極具增加。由於這種相似性計算的計算代價很大，因此採用基於位圖(bitmap)的增量計算方法進行求解，可以大大降低計算代價。
首先，針對數據d的每一種「描述形式」給出對應的位圖。例如，假設d有m個主題半相關詞條，則d的每一種「描述形式」被分配m位比特位。該位圖的每一位對應數據d的每一個主題半相關詞條。如果第i個半相關詞條出現在d的某一個描述形式中，那麼這個描述形式的相對應的第i位比特位為1，否則為0。
其次，為每個數據的所有表示形式建立一個鄰接樹，構建方法如下 1.將比特位全為0的描述形式作為樹的根節點； 2.其比特位與當前節點僅有一位不同的描述形式作為當前節點的子節點； 3.按照廣度優先遍歷方式，遍歷當前的鄰接樹；重複步驟2，直到所有的節點都被插入到樹中。
接下來，根據每個數據對應的鄰接樹，可以確定計算任意兩條數據的每一種描述形式的相似性計算次序以及增量計算的方式，對鄰接樹的兩個根節點之間的相似度利用公式(6)計算，除了兩個根節點之外的相似度用公式(7)計算；其計算步驟如算法1所示。
算法1SimCal(Tx，Ty) 輸入dx的鄰接樹Tx，dy的鄰接樹Ty 輸出dx和dy的任意兩個表達形式之間的相似度 步驟 1)Begin 2)計算sim(dx0，dy0)； //dx0和dy0分別為Tx和Ty的根節點 3)For(dx的每一種描述形式dyj) 4)sim(dx0，dyp)通過公式(3)求解sim(dx0，dyj)；//dxp為dyj的父節點 5)Endfor 6)For(dx的每一種描述形式dxi) 7)For(dy的每一種描述形式dyj) 8)sim(dxi，dyj)可以通過sim(dxp，dyj)求解；//dxp為dxi的父節點 9)Endfor 10)Endfor 11)End 在算法1中，沒有必要為每一條數據都建立一個鄰接樹，因為含有相同個數的半相關詞條的數據可以共享同一棵鄰接樹。如果dyp為dyj的父節點，s為在dyp基礎上追加到dyj中的一個主題半相關詞條，則(其中，p為集合dxi與dyp交集的大小，q為集合dxi與dyp併集的大小)，那麼，公式(7)給出了遞增計算相似度的公式。
由於參加相似性計算的「描述形式」是帶有概率的，那麼，由這兩種「描述形式」計算的得到的相似性也是帶有概率的，這個概率既是這兩種「描述形式」的概率的乘積。接下來，將這兩個數據的所有描述形式的相似度大於某一閾值θsim的相似度的概率相加，θsim∈(0.3，0.7)，該概率和表示了這兩個數據具有相同主題的概率。這個概率被稱之為「直接相關概率」。至此，數據空間內任意兩個數據dx和dy的直接相關概率已經被求出，數據空間中的其他數據間的直接相關概率同樣可以通過我們上面提到的方法求解。最後，將任意兩個數據的直接相關概率存儲在一個N×N大小的矩陣M中，其中N代表數據空間內數據的數量。
步驟5基於M構建聚類模型Mc M僅僅存儲了任意兩個數據之間的直接相似性聯繫(direct relationship)，而沒有考慮他們之間可能存在的間接相似性聯繫(indirect relationship)。如果考慮數據間的間接聯繫，將使數據之間的相似性表達更為準確。對於存儲矩陣M，可以將其中的相似性信息以圖的形式表示出來。假設G＝{V，E}是一個完全圖(complete graph)，其中V是節點集合，代表數據空間中的所有數據；E是節點間邊的集合，代表任意兩個數據對象間具有直接相似性聯繫的概率。如果考慮數據間的間接相似性聯繫，則計算圖G中兩節點的相似性概率需要考慮這兩個節點中間含有多個中間節點的情況。下面，通過一些定義來介紹要構建的聚類模型。
定義1.n-連接路徑(n-connection path)。設v0，v1，...，vn∈V，e1，e2，...，en ∈E，其中ei(1≤i≤n)的端點為vi-1和vi，這時，一條n-連接路徑pathn(v0，vn)就是由v0，e1，v1，...，en，vn構成的一個長度為n的有序序列，其中v0是第一個頂點，vn是最後一個頂點，且v0≠vn。
定義2.n-連接概率(n-connection probability)。

pathn(v0，vn)上的每條邊ei，p(ei)為邊ei的概率，.則p稱作n-連接概率。
定義3.n-連接失敗概率矩陣Mn。Mn的每一個元素為其中，pl為節點i和j的第l種n-連接概率，N為數據空間中數據的個數。n-連接失敗概率矩陣存儲的是任意兩條數據在所有n-連接路徑都失敗的情況下的概率。
定義4.全關係矩陣Mc(complete-connection matrix)。Mc的每一個元素其中，Mijn為節點i和j的n-連接失敗概率。
由於Mc記錄了任意兩個節點將所連接這兩個節點的路徑都考慮的情況下的相似性概率，因此，任意兩個節點間的相似性概率可以用矩陣Mc內的元素表示。矩陣Mc即為我們構建出來的聚類模型，矩陣中的每一個元素表示了對應的兩個數據間的主題相似性概率。這個主題相似概率不僅考慮了數據間的直接相關概率，而且也考慮了數據間通過其他對象產生關係的概率。根據Mc，並利用已知的聚類算法，如編網聚類算法，就可以實現基於主題詞條的相似性聚類。本發明的一種優選方式，當n-連接概率的n的取值為2時，聚類效果最好。
步驟6基於聚類模型Mc的聚類方法 基於聚類模型Mc採用聚類方法，對數據進行聚類。我們的模型適用於多種不同的聚類方法，這裡我們只選取幾種代表性的聚類方法加以闡述。此模型可以採用一種名為「編網」法的聚類算法，對數據進行聚類。將矩陣Mc中元素值大於某一閾值θpar的元素值置為「·」，將小於這一閾值的元素值修改為null。將取值為「·」的元素稱為「結點」。從結點出發向對角線引經線(豎線)和緯線(橫線)。編網法就是在結點處將經過的經、緯線捆綁起來以實現分類，而通過打結能相互連接的點屬於同一類。
其他的聚類方法，例如K-means方法仍然可以應用於這個模型。我們可以隨機的選取若干個數據點，即將模型Mc中的每一行元素數值作為一個高維向量。將這些高維向量作為K-means方法的起始點，以這個數據點與其他所有數據的相似概率作為迭代空間。而後按照K-means的步驟進行聚類分析，得到聚類結果。
本發明的有益效果 這裡主要通過實驗測試提出的概率模型在聚類方面的應用效果。
(1)對聚類精度的評價 實驗中，應用提出的PTSM並藉助編網聚類算法對數據空間中的數據進行聚類。為驗證聚類精度，如F-measure、Entropy以及NMI等指標，將PTSM編網算法同經典的K-means和CP聚類算法進行了比較。圖2～4從三種不同的測試角度分別考察了這些算法的聚類精度。從圖2～4中，可以看出基於PTSM的聚類算法的聚類精度要好於其他兩種經典算法。PTSM的精度之所以會高出其他算法，首先是因為模型充分考慮了詞條與數據主題之間的相似性，並且對那些重要的詞條賦予了較高的權重，這使得數據的主題表達更加準確。另一個原因是，當計算任意兩個數據對象間相似性的概率時，不僅考慮了直接相似性聯繫，而且還考慮了間接相似性聯繫，從而使得數據間的相似性概率計算更為準確。CP算法面向的數據主要是文檔數據，類型單一。在不考慮數據類型的情況下，CP算法的聚類精度介於PTSM編網算法和K-means之間。CP算法好於K-means，是因為CP也考慮了聚類過程中的概率問題，比如詞條屬於某一個詞條簇的概率以及文檔屬於某一個文檔簇的概率。而CP算法不如PTSM編網算法，是因為CP算法沒有考慮數據之間更為複雜的間接相似性聯繫問題。對於K-means而言，它僅僅在詞條向量空間內比較兩條數據的相似性，並且只是一種能夠得到局部最優的聚類方法，因此，其聚類效果是最差的。
(2)對聚類執行時間的評價 圖5顯示了這三種算法的執行時間，從圖5中可以看出PTSM編網算法的執行時間遠遠小於K-means，而與CP的執行時間相似。這是因為，K-means是一種迭代方法，這種迭代方法往往非常費時，而PTSM編網算法由於忽略了大量不重要的詞條，起到了降維(reduction ofdimensionality)作用，從而使得PTSM編網算法的執行時間遠遠小於K-means。相比之下，由於PTSM編網算法與CP算法都是利用矩陣作為處理聚類的手段，因此在執行時間上兩者相差無幾。
(3)對聚類敏感度的評價 首先，評價了模型參數的設置對PTSM及聚類效果的影響。圖6(a)表明了參數α和θsim的設置對模型的影響。用F-measure作為衡量聚類效果的標準。從圖6(a)可以看出，當θsim＝0.3時，PTSM的聚類效果最佳。當然，θsim的最佳設置取決於數據集中數據的特性。通過大量的試驗，我們發現通常情況下，θsim∈(0.3，0.7)時，PTSM的聚類效果較好。在對α進行測試時，當α的值從0.9下滑至0.3時，聚類的效果不斷提升。但是當α＜0.3時，聚類的效果變得越來越差。這是因為當新的詞條被加入到主題相關詞集合中時，數據的主題會被描述的越來越精確，因此聚類效果越來越好。但是，隨著詞條的不斷加入，會導致大量與主題無關的詞條被加入到主題相關詞條集合中，而這些詞條原本屬於主題半相關詞條或主題不相關詞條，從而使聚類效果下降。因此，我們認為α＝0.3對於PTSM而言是比較合適的。
其次，評價連接失敗概率矩陣中，連結路徑的長度n對聚類效果的影響。n的取值不僅僅影響聚類效果，而且還會影響聚類精度。n越大，PTSM的複雜度越高，即需要更多的聚類計算時間，但PTSM的聚類精度被提高了。相反，n越小，聚類時間越少，但聚類效果更差，圖6(b)證明了上述結論。當n增加時，PTSM的聚類效果越來越好。然而，當n＞2後，PTSM聚類精度的提高越來越不明顯，並且趨於穩定。因此，n的取值為2對模型較為合適。



圖1本發明的聚類方法流程圖， 圖2本發明的一種實施例PTSM編網算法、K-means和CP聚類算法的調和率比較圖； 圖3本發明的一種實施例PTSM編網算法、K-means和CP聚類算法的熵比較圖； 圖4本發明的一種實施例PTSM編網算法、K-means和CP聚類算法的規範化互信息比較圖。
圖5本發明的一種實施例PTSM編網算法、K-means和CP聚類算法的執行時間比較圖； 圖6(a)本發明的聚類模型Mc參數的取值α和θsim的設置對模型的影響圖； 圖6(b)本發明的評價連接失敗概率矩陣中，連結路徑的長度n對三種聚類方法的聚類效果比較圖； 圖7(a)本發明的一個數據詞條按照權重大小進行排序示意圖； 圖7(b)本發明的另一個數據詞條按照權重大小進行排序示意圖； 圖8本發明的一種實施例的鄰接樹示意圖； 圖9本發明的一種實施例的數據空間中對象間的直接與間接關係示意圖； 圖10(a)本發明中的一種實施例編網法聚類法中數據在模型Mc中的表示示意圖； (b)本發明中的一種實施例編網法聚類法選取「結點」元素的示意圖； (c)本發明中的一種實施例編網法聚類法的結果示意圖。

具體實施例方式 本發明的一個實施例 (1)定義主題詞條的類型，詞條權重排序 假設d1和d2為數據空間中的兩個數據，T(d1)和T(d2)分別表示每個數據包含的詞條項，此處T(d1)＝{數據，索引，搜索，精度，會議，聚類，查找，相似，摘要，包含，版本}，T(d2)＝{數據，搜索，精度，會議，圖像，測量，不確定}。T(d1)和T(d2)中每個詞條都被賦予了一個權重值，並按照權重值大小從高到低排序，如圖7(a)和(b)所示。
(2)用概率表示數據主題 在d1中，取「數據」、「索引」、「搜索」和「精度」為主題相關詞條，「會議」和「聚類」為主題半相關詞條，其餘是主題不相關詞條。「會議」和「聚類」的權重分別為4和3，而d1中詞條的最大權重為10，那麼，「會議」和「聚類」的相關概率分別為而在d2中，「數據」，「搜索」和「精度」是主題相關詞條，「聚類」是主題半相關詞條，其餘是主題不相關詞條，而「聚類」相對於d2的主題相關概率為這樣，我們將主題相關詞條和主題半相關詞條加入到描述d的主題的詞條集合中，其中主題半相關詞條按照主題相關概率加入，而主題不相關詞條被忽略。因此，d1的主題可以被表示為以下4種形式，d2可被表示為兩種形式，且每種表達方式都有一個概率值。






(3)構建數據的主題詞條概率相似性矩陣M 在計算d1和d2的主題詞條相似性概率時，要先建立它們的鄰接樹。首先，給數據主題的每一種表達方式建立位圖。在集合d11中，由於沒有出現主題半相關詞條，因此位圖為00；以此類推，d12、d13和d14的位圖分別為10(比d11增加了一個主題半相關詞條「會議」)、01(比d11增加了一個主題半相關詞條「聚類」)和11(比d11增加了兩個主題半相關詞條，即「會議」和「聚類」)，而d2的位圖分別為0(沒出現主題半相關詞條「聚類」和1(比d21增加了一個主題半相關詞條「聚類」)。然後，以00作為d1的根結點，將與它只有一個bit位不同的位圖集合，即01和10作為它的兒子節點，重複執行上述過程，直到d1的所有位圖都被插入到樹中，如圖8左側所示。對於d2，執行上述相同操作，對應的樹如圖8右側所示。於是，在圖8中，存在以00和0為根節點的兩棵樹，分別對應著d1和d2。樹中每個節點表示數據的一種主題詞條表現形式，節點中的編號對應著該形式的位圖。相鄰節點間的有向實線邊表示在一個數據對象中具有的父子關係的主題詞條表現形式，比如d1中的01位圖(對應著d13)比其00位圖(對應著d11)多一個主題半相關詞條「聚類」。箭頭虛線則表示需要計算兩個數據間一對主題詞條表達形式間的相似度。
在圖8中，d1和d2的主題詞條表示集合的位圖的鄰接樹在計算相似度時，首先計算d1(00)和d2(0)的相似度，即d11和d21的相似度。根據相似性計算的定義，即公式(2)，求得sim(d1(00)，d2(0))＝3/4，而sim(d1(01)，d2(0))只需在已計算過的sim(d1(00)，d2(0))之上進行修改就能得到。例如，

與

相比只多出一個半相關詞條「聚類」，而換句話說，「聚類」不是集合


中的詞條，因此，根據公式(7)推導出sim(d1(01)，d2(0))＝3/(4+1)＝3/5。同理，sim(d1(10)，d2(0))＝3/(4+1)＝3/5，sim(d1(11)，d2(0))＝3/(5+1)＝3/6。而d11和d21基於主題詞條的相似性概率為其他形式間的概率計算以此類推。接下來，計算d22與d1的各種主題表達方式之間的相似性。由於d2(0)是d2(1)的父節點，所以有關於d2(1)的相似度都可以通過d2(0)推導出來。例如，sim(d1(01)，d2(1))＝(3+1)/4＝4/4。類似地，sim(d1(00)0，d2(1))＝3/(4+1)＝3/5，sim(d1(10)，d2(1))＝3/(5+1)＝3/6，sim(d1(11)，d2(1))＝(3+1)/6＝4/6。至此，d1和d2的每種主題表達方式都已經通過這種增量計算方式得到。在表1中，我們詳細列出了這些相似度的數值以及它們的概率。
表1d1和d2的各種主題詞條表達形式間的相似度及概率
如果設相似度閾值θsim＝0.65，那麼我們將大於該閾值的概率值相加求和來作為d1和d2的主題相似概率。這樣，最終求得的矩陣M如公式(8)所示。
(4)基於M構建聚類模型 M是在不考慮其他對象情況下，d1和d2在0.41概率下是主題相似的，但該概率只能表明d1和d2間較為簡單的直接聯繫，如果存在另外一個對象dx，三者的關係就比較複雜了，圖9給出了它們之間的一種間接聯繫。
在圖9中，任意兩個數據間的相似性概率已被求出，P(d，dx)＝0.3，P(dx，d』)＝0.5。那麼，在僅考慮沒有中間節點的情況下，d1和d2的1-連接失敗概率為1-P(d，dx)＝0.59。在含有一個中間節點的情況下，d1和d2的2-連接失敗概率為1-P(d1，dx)*P(dx，d2)＝0.85。上述已論及，含有一個中間節點是較好的情況，因此在該情況下，d1和d2的相似性概率為1-(1-P(d1，dx))*(1-P(d1，dx)*P(dx，d2))＝1-0.59*0.85＝0.4985。在該例中，數據空間中只有3個數據，依據上述方法，可以計算出這3個數據間所有的1-連接失敗概率矩陣M1、2-連接失敗概率矩陣M2和全概率矩陣Mc，公式(9)～(11)分別給出了最終結果。
(5)基於聚類模型的聚類方法 這裡我們只介紹基於編網法的聚類實例。假設由數據空間中的數據構建出的矩陣Mc，由圖10(a)所示。我們取閾值θpar＝0.5。將元素值大於0.5的元素置為「·」，如圖10(b)所示。從「結點」處引出經、緯線，將落在從同一個「結點」出發的經、緯線上的元素放入同一個聚類中，如圖10(c)所示。這樣1、2、3三個元素被聚為兩個類{1}，{2，3}。
權利要求
1、一種基於主題詞條的跨類型數據的概率聚類方法，其特徵在於該方法包括以下步驟
(1)定義主題詞條的類型；
對一個跨類型數據d，將其表示為詞條的集合，對每個詞條賦權重後，按照權重大小分為三類詞條主題相關詞條r、主題半相關詞條s和主題不相關詞條u；
(2)對每類詞條分配概率；
主題相關詞條的主題概率為1，主題不相關詞條的主題概率為0，主題半相關詞條的主題概率p(si)＝wsi/wmax，其中wsi為半相關詞條si的權重，wmax為跨類型數據d中所有詞條的權重的最大值；
(3)用概率表示數據主題；
將跨類型數據d表示成主題相關詞條r的一個確定集合，記作d(r1，r2，...，rn)，其中ri表示第i個主題相關詞條，再將所有的主題半相關詞條s追加到跨類型數據d的確定集合中，跨類型數據d的確定集合在加入主題半相關詞條s後，轉換成多種描述形式，而每一種描述形式有一個概率其中k表示一條數據中主題半相關詞條的數量，m＝1，2，...，2k，dm是d的第m個描述形式，如果si出現在dm中，則Pi＝p(si)，否則Pi＝1-p(si)；
(4)構建數據的主題詞條概率相似性矩陣M；
對步驟(3)中跨類型數據d的任意兩個數據dx和dy，計算dx和dy任意兩種描述形式的相似度，將相似度大於某一閾值θsim的相似性的概率相加，θsim∈(0.3，0.7)，該概率和為直接相關概率，將任意兩個數據的直接相關概率存儲在矩陣M中；
(5)基於矩陣M構建聚類模型Mc；
聚類模型Mc的每一個元素其中，Mijn為節點i和j的n-連接失敗概率，其中，N為數據空間內數據的個數，pl為節點i和j的第l種n-連接概率，對於任意一條n連接路徑上的每一條邊ei，p(ei)為邊ei的概率，
(6)基於聚類模型Mc的聚類方法
基於聚類模型Mc採用聚類方法，對數據進行聚類。
2、按照權利要求1所述的基於主題詞條的跨類型數據的概率聚類方法，其特徵在於步驟(1)中所述的定義主題詞條的類型，步驟如下
對於任意一個跨類型數據d，將其表示為詞條的集合d(t1，t2，...tn)，其中ti(1≤i≤n)表示跨類型數據d的第i個詞條，按下面的公式給集合中的每一個詞條賦予權重，如公式(1)-(4)所示
tf(t)＝1+ln(1+ln(1+f(t))(1)
其中，f(t)表示詞條t在跨類型數據d中出現的頻率，N和Nt分別表示數據空間內數據的總量以及含有詞條t的數據的數量，tld表示跨類型數據d中詞條的總量，avgtl表示所有數據內詞條數量的平均數，而s是一個參數，公式SCORE(t)用於計算詞條的權重，按照權重大小分為三類詞條主題相關詞條、主題半相關詞條和主題不相關詞條，分別用r、s和u表示；權重大於某個閾值θs的詞條稱為主題相關詞條；權重小於某個閾值θu的詞條稱為主題不相關詞條；權重介於θs和θu之間的詞條稱為主題半相關詞條；此處，θs＝αθmax，其中θmax為某一個跨類型數據d中權重最大的詞條的權重，而α是一個參數，α在0.2至0.5之間；在確定了主題相關詞條r之後，對剩餘的詞條項按權重大小進行排序，令w[i]表示排名第i位的詞條的權重值，尋求相鄰兩個權值差最大的詞條所在位置k，並將位置k所對應的詞條的權值作為θu的值，即k滿足公式(5)，其中m是除主題相關詞條外的詞條個數，θu＝w[k]
w[k]-w[k+1]＝max1≤i≤m-1(w[i]-w[i+1])(5)。
3、按照權利要求1所述的基於主題詞條的跨類型數據的概率聚類方法，其特徵在於步驟(4)中所述的構建數據的主題詞條概率相似性矩陣M，步驟如下
dxi是dx的第i種描述形式，dyj是dy的第j種描述形式，首先，針對跨類型數據d的每一種描述形式給出對應的位圖，該位圖的每一位對應跨類型數據d的每一個主題半相關詞條；如果該主題半相關詞條沒有出現在這個描述形式中，對應的比特位為1，否則為0；
其次為每個數據的所有描述形式建立一個鄰接樹，構建方法如下將比特位全為0的描述形式作為樹的根節點；其比特位與當前節點僅有一位不同的描述形式作為當前節點的子節點；
按照廣度優先遍歷方式，遍歷當前的鄰接樹；直到所有的節點都被插入到樹中；
對鄰接樹的兩個根節點之間的相似度利用公式(6)計算，除了兩個根節點之外的相似度用公式(7)計算；
dyp為dyj的父節點，s為在dyp基礎上追加到dyj中的一個主題半相關詞條，則其中，p為集合dxi與dyp交集的大小，q為集合dxi與dyp併集的大小，那麼，公式(7)給出了遞增計算相似度的公式
將相似度大於某一閾值θsim的描述形式的概率相加，θsim∈(0.3，0.7)，該概率和為直接相關概率，將任意兩個數據的直接相關概率存儲在一個N×N大小的矩陣M中，其中N代表數據空間內數據的數量。
4、按照權利要求1所述的基於主題詞條的跨類型數據的概率聚類方法，其特徵在於步驟(5)中所述的n-連接概率的n的取值為2。
5、按照權利要求1所述的基於主題詞條的跨類型數據的概率聚類方法，其特徵在於步驟(6)中所述的基於聚類模型Mc的聚類方法，採用編網法的聚類方法或者K-means方法的聚類方法，其中編網法的聚類方法的步驟如下將矩陣Mc中元素值大於某一閾值θpar的元素值置為「·」，將小於這一閾值的元素值修改為null，將取值為「·」的元素稱為結點，從結點出發向對角線引經線和緯線，編網法就是在結點處將經過的經、緯線捆綁起來以實現分類，而通過打結能相互連接的點屬於同一類；
其中K-means方法的聚類方法的步驟如下隨機的選取若干個數據點，即將模型Mc中的每一行元素數值作為一個高維向量，將這些高維向量作為K-means方法的起始點，以這個數據點與其他所有數據的相似概率作為迭代空間，而後按照K-means的步驟進行聚類分析，得到聚類結果。
全文摘要
一種基於主題詞條的跨類型數據的概率聚類方法，屬於資料庫領域，包括以下步驟(1)定義主題詞條的類型；將跨類型數據分為主題相關詞條、主題半相關詞條和主題不相關詞條；(2)對每類詞條分配概率；(3)用概率表示數據主題；(4)構建數據的主題詞條概率相似性矩陣M；對步驟(3)中跨類型數據的任意兩個數據dx和dy，計算dx和dy任意兩種描述形式的相似度，將相似度大於某一閾值的相似性的概率相加，將任意兩個數據的直接相關概率存儲在矩陣M中；(5)基於矩陣M構建聚類模型Mc；(6)基於聚類模型Mc的聚類方法。本發明利用與主題相關的詞條項的相似性來對跨類型數據進行聚類，提高了數據聚類的精度，減少了聚類時間。
文檔編號G06F17/30GK101408901SQ20081022904
公開日2009年4月15日 申請日期2008年11月26日 優先權日2008年11月26日
發明者王國仁, 於亞新, 王波濤, 丁國輝, 斌 王, 趙相國, 趙宇海, 信俊昌, 喬百友, 韓東紅, 張恩德, 淼 李 申請人:東北大學