[發(fā)明專利]基于最大頻繁項(xiàng)集挖掘的微博炒作群體發(fā)現(xiàn)方法

有效

• 申請?zhí)枺?/td>: 201410188004.7
• 申請日: 2014-05-07
• 公開（公告）號: CN103927398A
• 公開（公告）日: 2014-07-16
• 發(fā)明（設(shè)計(jì)）人: 劉琰;張進(jìn);羅軍勇;羅向陽;董雨辰;陳靜;常斌
• 申請（專利權(quán)）人: 中國人民解放軍信息工程大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 鄭州天陽專利事務(wù)所(普通合伙) 41113
• 代理人: 聶孟民

1.一種基于最大頻繁項(xiàng)集挖掘的微博炒作群體發(fā)現(xiàn)方法，其特征在于，包括如下步驟：

(1)炒作微博樣本搜集：以炒作微博的相關(guān)性為線索，基于爬蟲技術(shù)或微博公共開放平臺獲取參與炒作微博傳播的賬戶集合；

(2)事務(wù)數(shù)據(jù)庫構(gòu)建：以單個(gè)微博為事務(wù)，參與微博傳播的賬戶為項(xiàng)，構(gòu)建炒作微博事務(wù)數(shù)據(jù)庫；

(3)最大頻繁項(xiàng)集挖掘：對待檢測微博組所對應(yīng)的事務(wù)數(shù)據(jù)庫中的每個(gè)事務(wù)，利用迭代交集法找出所有事務(wù)中包含的最大頻繁項(xiàng)集，得到若干最大頻繁項(xiàng)集集合；

由于炒作微博事務(wù)庫中每個(gè)事務(wù)包含的項(xiàng)目大都數(shù)以萬計(jì)，直接在原始事務(wù)數(shù)據(jù)庫中挖掘最大頻繁項(xiàng)集將會影響算法執(zhí)行的效率，利用二分查找法，快速剔除事務(wù)中的非頻繁項(xiàng)目，找出最大頻繁項(xiàng)集的候選集合，縮減事務(wù)數(shù)據(jù)庫規(guī)模；

(4)最大頻繁項(xiàng)集歸并：對每個(gè)最大頻繁項(xiàng)集，計(jì)算項(xiàng)集間的重疊率，對最大頻繁項(xiàng)集進(jìn)行合并，盡量將規(guī)模較小的項(xiàng)集歸并到較大項(xiàng)集中，并保證歸并后項(xiàng)集中的賬戶依然具有一定的關(guān)聯(lián)性；通過縮減事務(wù)數(shù)據(jù)庫規(guī)模，減少交集次數(shù)，事務(wù)間取交集時(shí)，采用二分查找法判斷事務(wù)中是否包含某項(xiàng)目，以提高挖掘最大頻繁項(xiàng)集的效率，從而發(fā)現(xiàn)微博炒作群體。

2.根據(jù)權(quán)利要求1所述的基于最大頻繁項(xiàng)集挖掘的微博炒作群體發(fā)現(xiàn)方法，其特征在于，包括炒作微博事務(wù)庫、最大頻繁項(xiàng)集挖掘以及最大頻繁項(xiàng)集歸并部分，炒作微博事務(wù)庫構(gòu)建模塊主要負(fù)責(zé)采集數(shù)據(jù)并進(jìn)行預(yù)處理，構(gòu)建事務(wù)數(shù)據(jù)庫D；最大頻繁項(xiàng)集挖掘模塊首先基于二分查找方法篩選候選最大頻繁項(xiàng)集，然后基于迭代交集方法從事務(wù)數(shù)據(jù)庫D中挖掘出最大頻繁項(xiàng)集MFS；最大頻繁項(xiàng)集歸并模塊主要對MFS進(jìn)行歸并處理，還原真實(shí)的炒作群體，具體步驟是：

1)、搜集炒作微博樣本

炒作微博樣本搜集實(shí)現(xiàn)本發(fā)明的最初步驟，微博樣本的選擇應(yīng)具有相關(guān)性，若某個(gè)炒作賬戶曾經(jīng)參與的若干微博，或與某個(gè)主題相關(guān)的若干微博，微博樣本的判定應(yīng)借鑒已有的成熟判別方法或?qū)＜蚁到y(tǒng)，炒作微博樣本搜集有兩種方法：一種方法是選擇爬蟲技術(shù)，從微博網(wǎng)頁下載網(wǎng)頁、解析頁面結(jié)構(gòu)并提取微博傳播賬戶的信息；另一種方法是調(diào)用微博公共開放平臺，調(diào)用微博官方對外提供的API函數(shù)獲取微博傳播賬戶的信息；

按照待挖掘炒作賬戶的算法分析條件，樣本搜集的內(nèi)容應(yīng)包括微博標(biāo)識號、微博賬戶標(biāo)識號、微博賬戶的基本信息；

2)構(gòu)建事務(wù)數(shù)據(jù)庫

將炒作群體發(fā)現(xiàn)問題轉(zhuǎn)化為數(shù)據(jù)挖掘中的最大頻繁項(xiàng)集挖掘，在炒作微博樣本搜集的基礎(chǔ)上，將炒作微博對應(yīng)事務(wù)，參與微博轉(zhuǎn)發(fā)的賬戶對應(yīng)事務(wù)中的項(xiàng)，構(gòu)建事務(wù)數(shù)據(jù)庫，如圖2所示；

3)基于二分查找的候選最大頻繁項(xiàng)集篩選

由于炒作微博事務(wù)庫中每個(gè)事務(wù)包含的項(xiàng)目大都數(shù)以萬計(jì)，直接在原始事務(wù)庫中挖掘最大頻繁項(xiàng)集將會影響算法執(zhí)行的效率，基于二分查找的方法，能夠快速剔除事務(wù)中的非頻繁項(xiàng)目，找出最大頻繁項(xiàng)集的候選集合，縮減事務(wù)庫規(guī)模，給定事務(wù)數(shù)據(jù)庫D，最小支持?jǐn)?shù)S，進(jìn)行候選最大頻繁項(xiàng)集篩選，方法是：

(1)將事務(wù)庫D中的事務(wù)按項(xiàng)目個(gè)數(shù)從大到小排序

(2)記頻繁項(xiàng)目集合，非頻繁項(xiàng)目集合；從i＝1開始，按順序遍歷D中的每個(gè)事務(wù)T_i(1≤i≤|D|)，對事務(wù)T_i中的每個(gè)項(xiàng)目u：

a)若u∈FI，則保留u；

b)若u∈NFI，則從T_i中剔除u；

c)若，則轉(zhuǎn)到下一步判斷u是否是頻繁項(xiàng)目；

(3)、從j＝i+1開始遍歷剩余的事務(wù)，并利用二分查找法判斷T_j，i<j≤|D|中是否包含u，終止條件為：

a)當(dāng)包含u的事務(wù)個(gè)數(shù)達(dá)到S時(shí)，說明u是頻繁項(xiàng)目，將u加入到FI中；

b)當(dāng)剩余的事務(wù)個(gè)數(shù)與包含了u的事務(wù)個(gè)數(shù)之和小于S時(shí)，說明u是非頻繁項(xiàng)目，從T_i中剔除u，若此時(shí)包含了u的事務(wù)個(gè)數(shù)大于1，說明u還出現(xiàn)在T_i之外的事務(wù)中，則將u加入到NFI中；

(4)剔除完D中所有事務(wù)中的非頻繁項(xiàng)目后，即可得到縮減后的事務(wù)庫D₁；

4)基于迭代交集的最大頻繁項(xiàng)集挖掘：

通過對事務(wù)迭代取交集的方式挖掘最大頻繁項(xiàng)集，給定縮減后的事務(wù)庫D₁，最小支持?jǐn)?shù)S，最大頻繁項(xiàng)集挖掘的方法如下：

(1)將事務(wù)庫D₁中的事務(wù)按項(xiàng)的個(gè)數(shù)從大到小排序，以盡早發(fā)現(xiàn)最大頻繁項(xiàng)集，為縮減事務(wù)庫規(guī)模，合并事務(wù)庫中重復(fù)的事務(wù)，并對事務(wù)個(gè)數(shù)計(jì)數(shù)；

(2)為減少取交集的次數(shù)，對于事務(wù)T_i，1≤i≤|D₁|-S+1，從i＝1開始，首先找出包含了T_i中任意項(xiàng)的事務(wù)集合，T_j|T_j至少包含了T_i中的一個(gè)項(xiàng)目；j>i)，T_i依次與T_j取交集，將兩者的交集移入新的事務(wù)庫D₂，同時(shí)剔除T_j，；

(3)對于新事務(wù)庫D₂中的事務(wù)T，如果T是由不小于S個(gè)事務(wù)取交集而得，則將T移入最大頻繁候選項(xiàng)集集合MFCS中，同時(shí)剔除T在D₂中的子事務(wù)；

(4)如果新事務(wù)庫D₂中的剩余事務(wù)個(gè)數(shù)小于S，則結(jié)束對事務(wù)庫D₂的處理，返回到上層事務(wù)庫；否則，對D₂從第1步開始再進(jìn)行此過程；

(5)當(dāng)事務(wù)庫D₁中剩余的事務(wù)數(shù)小于S時(shí)，即i>|D₁|-S+1，結(jié)束對當(dāng)前事務(wù)庫D₁的處理；

(6)對MFCS中的項(xiàng)集進(jìn)行合并同時(shí)剔除非最大頻繁項(xiàng)集，最后的結(jié)果即為所求的最大頻繁項(xiàng)集集合MFS；

5)最大頻繁項(xiàng)集歸并：

由于最小支持?jǐn)?shù)的限制，使得MFS中最大頻繁項(xiàng)集規(guī)模較小，而且有些項(xiàng)集之間存在大量的重疊項(xiàng)，這些項(xiàng)集代表的賬戶群很可能從屬于同一個(gè)炒作群體，為解決這一問題，使用重疊率來反映兩個(gè)項(xiàng)集之間的相似性，設(shè)項(xiàng)集X₁,X₂∈MFS，將X₁和X₂的重疊率記為：

ORate(X1,X2)=|X1∩X2|Min(|X1|,|X2|)]]>

上式中，|X₁∩X₂|表示X₁與X₂重疊項(xiàng)目的個(gè)數(shù)，Min(|X₁|,|X₂|)表示規(guī)模較小的項(xiàng)集中項(xiàng)目的個(gè)數(shù)，項(xiàng)集歸并的方法是：

(1)將MFS中的最大頻繁項(xiàng)集按項(xiàng)目的個(gè)數(shù)從大到小排序；

(2)遍歷MFS中的每個(gè)最大頻繁項(xiàng)集，從i＝1開始，對，若ORate(X_i,X_j)≥minOR，i<j≤|MFS|，則將X_i和X_j的并集添加到新的集合MMFS中，同時(shí)剔除X_j；

(3)對MMFS中的項(xiàng)集重復(fù)執(zhí)行以上兩個(gè)步驟；

(4)當(dāng)MMFS中任意兩個(gè)項(xiàng)集的重疊率小于minOR時(shí)，結(jié)束。

3.根據(jù)權(quán)利要求2所述的基于最大頻繁項(xiàng)集挖掘的微博炒作群體發(fā)現(xiàn)方法，其特征在于，所述的步驟1)中，搜集炒作微博樣本應(yīng)符合如下條件：

a、選取轉(zhuǎn)發(fā)數(shù)相對較高的熱門微博；

b、微博發(fā)布時(shí)間跨度<180天；以利于對炒作群體的發(fā)現(xiàn)。