[發(fā)明專利]一種基于時空密度波與同步的大型時空數(shù)據(jù)聚類算法GRIDWAVE

在審

• 申請?zhí)枺?/td>: 201711063170.4
• 申請日: 2017-11-02
• 公開（公告）號: CN107704891A
• 公開（公告）日: 2018-02-16
• 發(fā)明（設(shè)計）人: 鄧超;陳智斌;郭曉惠;農(nóng)英雄;楊振宇;孫忱;梁東;陸瑛;鐘征燕
• 申請（專利權(quán)）人: 廣西中煙工業(yè)有限責(zé)任公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京三聚陽光知識產(chǎn)權(quán)代理有限公司11250
• 代理人: 李紅團(tuán)

技術(shù)領(lǐng)域

本發(fā)明涉及時空數(shù)據(jù)挖掘和大數(shù)據(jù)分析領(lǐng)域，具體涉及一種基于時空密度波與同步的大型時空數(shù)據(jù)聚類算法GRIDWAVE。

背景技術(shù)

空間數(shù)據(jù)聚類被廣泛的應(yīng)用于許多信息技術(shù)領(lǐng)域，例如數(shù)據(jù)挖掘、模式識別、機(jī)器學(xué)習(xí)、人工智能、可視分析、地理信息系統(tǒng)等。在大數(shù)據(jù)時代，它可用來探索與發(fā)現(xiàn)數(shù)據(jù)中潛在的模式及價值，可應(yīng)用于許多學(xué)科領(lǐng)域，例如天文學(xué)、生物信息學(xué)、文獻(xiàn)計量學(xué)、社會網(wǎng)絡(luò)分析、經(jīng)濟(jì)網(wǎng)絡(luò)分析、交通網(wǎng)絡(luò)分析、氣象分析、智慧城市發(fā)展等。傳統(tǒng)的空間數(shù)據(jù)聚類方法主要有四種：1)、基于劃分的聚類；2)、基于密度的聚類；3)、層次聚類；4)、基于網(wǎng)格的聚類。時空聚類是在空間數(shù)據(jù)聚類的基礎(chǔ)上增加了時序維度的聚類，用來分析空間受限變量的時序規(guī)律與模式，以及挖掘數(shù)據(jù)中隱藏的時空事件。

傳統(tǒng)的時空聚類算法主要是引入了時序距離的概念，將時序數(shù)據(jù)納入空間距離計算，再基于密度進(jìn)行聚類，如ST-DBSCAN，因此其聚類效果近似于空間聚類，其特點(diǎn)是其時空聚類一定是空間上連續(xù)或者近鄰的點(diǎn)的集合。但是在一些領(lǐng)域，例如經(jīng)濟(jì)學(xué)、社會學(xué)、網(wǎng)絡(luò)媒體等，時空數(shù)據(jù)不一定是空間連續(xù)或者近鄰的。同時，由于ST-DBSCAN是基于點(diǎn)與點(diǎn)之間的時空距離計算，其算法的時間復(fù)雜度為O(N²)。所以它不能用于處理海量時空數(shù)據(jù)，當(dāng)N不斷增大時，其運(yùn)算時間是不可接受的。

同時，我們都處于一個4維時空中，在日常生活工作學(xué)習(xí)中存在大量的時空事件，這些時空事件被廣泛的存儲于數(shù)據(jù)中，因此，設(shè)計一款能夠進(jìn)行無監(jiān)督時空聚類、挖掘時空事件的算法是具有現(xiàn)實(shí)意義的。

發(fā)明內(nèi)容

本發(fā)明采用了一種新穎的時空聚類理念，設(shè)計了一款能夠無監(jiān)督的發(fā)現(xiàn)時空類和時空噪聲，并且能夠挖掘時空事件的大型時空數(shù)據(jù)聚類算法。

本發(fā)明提供如下技術(shù)方案：

一種基于時空密度波與同步的大型時空數(shù)據(jù)聚類算法GRIDWAVE，包括以下步驟：

步驟1，根據(jù)預(yù)設(shè)空間邊長L、時序間隔I及D維時空數(shù)據(jù)集P創(chuàng)建D維時空數(shù)據(jù)網(wǎng)格G；

步驟2，根據(jù)D維時空數(shù)據(jù)集P中的空間受限變量V、最小近鄰參數(shù)MinPts，計算核心空間格子的時空密度波；

步驟3，根據(jù)每個核心空間格子的時空密度波及預(yù)設(shè)時空同步率R計算每一對核心空間格子之間的時空同步率，并根據(jù)該所述時空同步率進(jìn)行無監(jiān)督的時空網(wǎng)格聚類，并根據(jù)數(shù)據(jù)點(diǎn)所在D維時空格子的聚類結(jié)果對整個D維時空數(shù)據(jù)集P進(jìn)行分類標(biāo)注。

優(yōu)選地，上述基于時空密度波與同步的大型時空數(shù)據(jù)聚類算法GRIDWAVE中，所述構(gòu)建時空網(wǎng)格的方法具體包括：

時序間隔I是大于1的正整數(shù)，且空間邊長L大于0，D為正整數(shù)；

首先根據(jù)所述邊長L對所述D維空間數(shù)據(jù)集P中的每個空間維度的數(shù)值范圍進(jìn)行平均切分，創(chuàng)建一個D-1維空間數(shù)據(jù)網(wǎng)格G’，其次根據(jù)所述時序間隔I對所述D-1維空間數(shù)據(jù)網(wǎng)格G’再進(jìn)行時序切分，創(chuàng)建D維時空數(shù)據(jù)網(wǎng)格G；

所述D-1維空間數(shù)據(jù)網(wǎng)格G’中的每個格子為各邊相等的超方格子；

根據(jù)所述D維空間數(shù)據(jù)集P中每個點(diǎn)的D維時空信息將數(shù)據(jù)點(diǎn)映射到相應(yīng)的所述D維時空數(shù)據(jù)網(wǎng)格G中的時空格子，并進(jìn)行數(shù)據(jù)點(diǎn)數(shù)量累加與記錄。

優(yōu)選地，上述的基于時空密度波與同步的大型時空數(shù)據(jù)聚類算法GRIDWAVE中，所述核心空間格子是所述D-1維空間數(shù)據(jù)網(wǎng)格G’中的格子中數(shù)據(jù)點(diǎn)數(shù)量大于或等于所述最小近鄰參數(shù)MinPts的格子，并為每個核心空間格子設(shè)置一個獨(dú)立的時空類標(biāo)。

優(yōu)選地，上述的基于時空密度波與同步的大型時空數(shù)據(jù)聚類算法GRIDWAVE中，所述核心空間格子的時空密度波的計算方法具體包括：

計算每個核心空間格子中I個時空格子的時空密度值，計算方法為：對所述時空格子中所有數(shù)據(jù)點(diǎn)所關(guān)聯(lián)的空間受限變量V進(jìn)行累加與記錄；

所述空間受限變量V為關(guān)系型數(shù)據(jù)庫中用戶指定屬性的值。

第一個時空格子的時空密度波值固定為0，之后的I-1個時空格子的時空密度波值的計算方法為：當(dāng)本時序時空格子的時空密度值大于上一時序時空格子的時空密度值時，其時空密度波值計為1；當(dāng)本時序時空格子的時空密度值小于上一時序時空格子的時空密度值時，其時空密度波值計為-1；當(dāng)本時序時空格子的時空密度值等于上一時序時空格子的時空密度值時，其時空密度波值計為0；

所述核心空間格子的時空密度波即為其按時序依次排列的時空格子的時空密度波值的I個數(shù)字序列的集合，如{0,1，-1，…，1}。