[發明專利]基于時間序列的話題發展聚類分析系統和方法

有效

• 申請號: 201710071763.9
• 申請日: 2017-02-09
• 公開（公告）號: CN108415910B
• 公開（公告）日: 2021-03-05
• 發明（設計）人: 殷復蓮;張貝貝;劉曉薇;蘇沛;王顏顏;白雪松
• 申請（專利權）人: 中國傳媒大學
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06F16/9536;G06Q50/00
• 代理公司: 北京鴻元知識產權代理有限公司 11327
• 代理人: 陳英俊;楊樺

本發明提供一種基于時間序列的話題發展聚類分析系統和方法，方法包括：采集話題形成累計閱讀量時間序列；對上述時間序列進行前向差分得到話題熱度時間序列；判斷話題是否處于衰退期；若不處于衰退期繼續話題采集；若處于衰退期，分別計算各話題間的S?Euc和S?DTW，對所有話題進行聚類。系統包括：數據采集部；數據處理部，對累計閱讀量時間序列進行前向差分處理，判斷話題是否處于衰退期，將不處于衰退期的話題存儲到第一話題存儲庫，將處于衰退期的話題存儲到第二話題存儲庫；時間序列距離計算部，分別計算各話題間的S?Euc和S?DTW；話題聚類部，對所有話題進行聚類。上述系統和方法精確度高、聚類效果好。

技術領域

本發明涉及輿情監控分析技術領域，更為具體地，涉及一種基于時間序列的話題發展聚類分析系統和方法。

背景技術

當前社交網絡新媒體迅猛發展，搜索引擎、社交網絡等得到大量廣泛使用，各種各樣的信息以驚人的速度在全球范圍內傳播，瞬息萬變的話題雨后春筍般在互聯網上層出不窮，深刻地影響著人們的生活和社會的方方面面。這些話題隨著時間不斷變化，形成了典型的時間序列數據。時間序列的聚類算法是分析預測互聯網熱點話題熱度隨時間變化趨勢的重要過程。

聚類分析，就是把對象按照性質上的親疏程度分成多個類或簇，使得類或簇內的數據相似度最大化，類或簇間的數據相似度最小化，目前聚類分析已成功應用到信息檢索、數據挖掘等多個領域。現有時間序列聚類研究中時間序列距離多用閔科夫斯基距離、動態時間彎曲距離、最長公共子序列和編輯距離等等。其中，動態時間彎曲距離支持時間軸上的形變，故常用在不等長時間序列距離度量上。當前熱點話題時間序列聚類算法應用較多的有K-means、FCM(模糊C均值)、層次聚類和基于基礎算法進行的各種改進算法如K_SC(K-spectral centroid)、WKSC(Wavelet-based K_SC)等。但是，這些聚類算法所用數據源均以“天”為單位，時效性不強。

歐式距離(Euclidean distance，Euc)是兩個序列距離度量的最簡單常用的方法，如時間序列x和y的歐式距離為：

如圖1a所示，該距離不能在時間軸上進行伸縮變換，不能計算不等長時間序列之間的距離，如對于{a,a,b,C}和{a,b,c,c}，盡管兩個序列相似性很高，但是其歐氏距離比較大。

動態時間彎曲距離(Dynamic time warping distance，DTW)相比于歐氏 距離支持時間軸上的彎曲，可以很方便地應用在不等長時間序列的距離度量上。

時間序列x和y之間的動態時間彎曲距離定義為：

D_tw(,)＝0，

D_tw(x,)＝_tw(,y)＝∞，

取δ(x_i,y_i)＝(x_i-y_i)²

DTW實際上就是確定序列x和y上每個點之間的對齊匹配關系，如圖2a所示，兩條曲線整體上的波形形狀很相似，但在時間軸上不對齊。如在t₂₀時，實線波形的a點會對應于虛線波形的b’點，傳統歐氏距離不能體現序列相似性，而實線的a點對應虛線的b點時序列相似性提高。圖2b中，DTW使兩個波形一一對齊，這是它們的最好匹配路徑，能夠使得兩條曲線相似性最高，但是，DTW距離使不同天的信息進行對齊，造成紊亂。

另外，傳統聚類算法為了能夠用于不等長時間序列聚類，所采用的樣本距離因損失了部分時間序列信息，導致精度下降。

發明內容

鑒于上述問題，本發明的目的是提供一種精確度高、聚類效果好的基于時間序列的話題發展聚類分析系統和方法。