Nonparametric approaches for discovering triggering events from spatio-temporal patterns

Abstract

Zamansal veya mekansal-zamansal sıralı desen keşfi, deprem bilimi, suç bilimi ve finans gibi birçok alanda tanınan önemli bir problemdir. Mevcut yaklaşımların çoğunluğu aday üretme yöntemine dayalı olup, bu adayların değerlendirilmesinde kullanılmak üzere, komşuluk, anlamlılık ve eşik değeri gibi parametrelerin belirlenmesine ihtiyaç duyar. Ancak, bu yöntemlerin performansı seçilen parametre değerlerinden oldukça etkilenmektedir. Bu tezde, farklı olay tiplerini içeren mekansal-zamansal nokta desenleri için parametrik olmayan stokastik ayrıştırma metodolojisine dayalı iki adet sıralı örüntü çıkarımı algoritması geliştirilmiştir. Yöntemler, çok değişkenli koşullu yoğunluk modeli kullanarak aynı ve farklı olay tipleri arasındaki ilişkileri modelleyip bu modelden anlamlı tetikleme ilişkilerini çıkarır. Öncelikle, tüm örnek ikilileri arasındaki tetikleme olasılıkları çok değişkenli Hawkes modeli ile tahmin edilir, daha sonra anlamlı ikililer rank yöntemi ile seçilerek örüntüler belirlenir. Her bir ikili bir olasılık değeri ile tanımlandığı için, önerilen yöntemler ile, tüm olay tipleri için olası ikili tetikleme örüntülerinin anlamlılığı değerlendirilebilir. Yöntem farklı özelliklere sahip sentetik veri setlerinde denenmiş ve literatürdeki aday üretme yaklaşımına dayalı yöntemler ile kıyasla iyi sonuçlar vermiştir. Yoğunluk fonksiyonunda kullanılan kesikleştirme parametreleri Diggle D fonksiyonu ile elde edilen anlamlı etkileşim mesafeleri kullanılarak tanımlandığında, benzer ölçekte etkileşim gösteren örüntülerin olasılık değerlerinin maksimuma ulaştığı gözlenmiştir. Önerilen metodoloji ODTÜ kampüsünde bulunan hız kasislerinin kampüs içinde kaydedilen trafik kazalarının sayısı üzerindeki etkisinin incelenmesi amacı ile gerçek bir veride test edilmiştir.

Temporal or spatio-temporal sequential pattern discovery is a well-recognized important problem in many domains such as seismology, criminology and finance. The majority of the current approaches are based on candidate generation which necessitates parameter tuning such as definition of a neighborhood, an interest measure and a threshold value to evaluate candidates. However, their performance is limited as the success of these methods relies heavily on parameter settings. In this thesis, two sequential pattern mining algorithms are developed for the multi-type spatio-temporal point patterns based on the nonparametric stochastic declustering methodology. The algorithms use multivariate conditional intensity model to define triggering relations within and among the event types and employs the estimated model to extract significant triggering patterns. They initially estimate pairwise triggering probabilities of all instances according to the multivariate Hawkes model, and then generate candidate patterns by using a rank selection method. Since a pair of instances is associated with a triggering probability, the proposed approaches also allow user to evaluate the significance of the pairwise pattern of any event type.The proposed methods are tested with synthetic data sets exhibiting different characteristics. The method gives good results that are comparable with the methods based on candidate generation in the literature. It is observed that the discretization of the density function based on the significant interaction ranges obtained by Diggle D-function maximizes the triggering probabilities of the patterns that exist at similar scales. The method is tested with real data to estimate the effects of the speed bumps on the number of accidents reported in METU Campus.