移動(dòng)對象序列模式挖掘方法研究.pdf

1、數(shù)據(jù)挖掘技術(shù)能發(fā)現(xiàn)數(shù)據(jù)之間的潛在關(guān)系，從而提供決策支持，因此是數(shù)據(jù)庫研究中極具應(yīng)用前景的領(lǐng)域。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要工具之一，序列模式挖掘是對關(guān)聯(lián)規(guī)則的進(jìn)一步推廣。在傳統(tǒng)領(lǐng)域中，研究者對序列模式挖掘做了大量的研究，迄今為止已提出了許多高效的序列模式挖掘算法。
　　 而伴隨著網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，人們通過無線通信、位置感知及移動(dòng)計(jì)算等技術(shù)接入信息網(wǎng)獲取所需信息，因此，能夠收集大量的移動(dòng)對象的位置數(shù)據(jù)。如果對這些位置數(shù)據(jù)進(jìn)行挖掘，就

2、可以有效地發(fā)現(xiàn)移動(dòng)對象移動(dòng)的規(guī)律性。這些規(guī)律在智能交通管理和基于位置的服務(wù)等領(lǐng)域中都有廣泛的應(yīng)用。
　　 但是，在移動(dòng)計(jì)算環(huán)境中移動(dòng)對象序列模式的挖掘與傳統(tǒng)的序列模式挖掘不同，需要考慮序列項(xiàng)之間的空間約束關(guān)系，且移動(dòng)序列與傳統(tǒng)序列中的項(xiàng)具有的不同特點(diǎn)也應(yīng)考慮。因此在傳統(tǒng)的PrefixSpan算法和基于PrefixSpan算法改進(jìn)的PVS算法中都加入了空間結(jié)構(gòu)判斷，分別稱為Revised PrefixSpan和Revised PV

3、S算法。
　　 首先，本文提出的SMPM算法針對Revised PrefixSpan算法在挖掘數(shù)據(jù)集時(shí)需要產(chǎn)生大量重復(fù)投影和Revised PVS算法產(chǎn)生物理投影的不足進(jìn)行改進(jìn)。在SMPM算法中采用了前綴樹壓縮存儲(chǔ)序列模式，挖掘過程中利用前綴樹中每個(gè)節(jié)點(diǎn)記錄的支持度和后綴位置的信息來判斷前綴是否有相同的投影數(shù)據(jù)庫，如果有則直接將其指針指向前綴樹中的同一個(gè)節(jié)點(diǎn)，從而避免了原始算法中產(chǎn)生重復(fù)投影和產(chǎn)生物理投影的問題。此算法運(yùn)行的時(shí)間

4、效率與避免重復(fù)挖掘的次數(shù)有關(guān)，因此更適合挖掘相似度較高的序列。其次，本文又提出了SSMP算法，其針對RevisedPrefixSpan算法在挖掘空間數(shù)據(jù)時(shí)需要每次在k-序列擴(kuò)展為k+1-序列時(shí)進(jìn)行相鄰判斷的不足進(jìn)行改進(jìn)。SSMP算法將原始移動(dòng)序列根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)對不相鄰的項(xiàng)進(jìn)行劃分，從而避免了挖掘時(shí)進(jìn)行的多次網(wǎng)絡(luò)結(jié)構(gòu)判斷。最后，本文通過對比道路網(wǎng)與GSM網(wǎng)絡(luò)結(jié)構(gòu)的相似性，研究了SMPM算法及SSMP算法應(yīng)用到道路網(wǎng)的移動(dòng)對象序列模式挖掘模型