Co-location pattern mining (for CSCI 5715) Charandeep Parisineti

Co-location pattern mining
(for CSCI 5715)
Charandeep Parisineti,
Bhavtosh Rath
Chapter 7: Spatial Data Mining
[1]Yan Huang, Shashi Shekhar, Hui Xiong. Discovering Co-location patterns from Spatial
Datasets: A General Approach. IEEE Transactions on Knowledge and Data Engineering, 2004.
[2]Sajib Barua, Jörg Sander. Mining Statistically Significant Co-location and Segregation
Patterns. IEEE Transactions on Knowledge and Data Engineering, 26(5), 2014.
[3] Shashi Shekar, et al., Trends in Spatial Data Mining
Where do we find Co –location?
In ecology
Symbiotic species : Ox-pecker and giraffe
Public Safety
To determine possible causes of disease outbreak
(London cholera)
In cities
{‘auto dealers’, ‘auto repair shops’}
{‘departmental stores’, ’gift stores’}
Other domains: Earth science, public
safety, transportation, tourism etc.
What are association rules?
Association rules vs Co-location rules
Class Exercise:
Co-location rule mining approaches
b) Reference feature centric approach c) Data partition approach d) Event centric model
• Co-location (A,B) will not be found in (b) since it does not involve the reference feature
• Data partition approach can have many distinct ways of partitioning the data, each yielding
a distinct set of transactions and hence support.
 In (c) support of (A,B) is different for different partitions
 Event centric model finds the subsets of spatial features likely to occur in a neighborhood
around instances of given subsets of event types
Event Centric model
Drawbacks of event centric model
• In (a) there are only a few instances of A but B is abundant.
 As many Bs are without As B’s participation ratio will be small which results the
participation index of {A,B} to be low
• In (b) A and B are abundant in a spatial area but randomly distributed
 We might see enough instances of {A,B} even without true spatial dependency
• In (c) both features A and B are spatially auto-correlated. A cluster of A and a cluster of B
happen to overlap by chance.
 Enough instances of {A,B} will falsely report a spatial co-location
Statistical approaches
Similar problems as above in association rule mining are handled using Interest
measures such as phi coefficient for a 2x2 contingency table
~Coffee means the transactions which
don’t contain coffee
The absence of an item doesn’t make sense in spatial data as boolean spatial
features are embedded in continuous space
Hence phi coefficient, odds ratio etc, used in traditional data mining don’t work for
Spatial data
The basic idea in Spatial statistical approach is comparing the observed PI value to a
PI value under no spatial relationship instead of a global threshold
The process is repeated over several spaces with CSR using Monte Carlo simulation
Computing co-location patterns using cross k function for all possible co-location
patterns can be computationally expensive

similar documents