Colocation Pattern and Examples • Colocation: a set of spatial features that frequently occur in together • Example: • Ecology: symbiotic relationship in animals or plants • Public health: environmental factors and cancers • Public safety: crime generators and crime events Nile Crocodiles and Egyptian Plover Bar closing events and crimes http://www.alamy.com/ http://www.startribune.com/
Basic Concepts • Spatial event type • Example: Bar closing, drunk driving • Spatial event instance • Belong to an event type, associated with a location • Example: one specific drunk driving event • Colocation pattern 𝑐: • A subset of spatial event types: (bar closing, drunk driving) • Instances of these event types frequently occur together
Basic Concepts • Neighbor relationship 𝑅 • Binary relationship on two event instances • Determined by adjacency or a distance threshold • 𝑅-proximity neighborhood • A clique of multiple event instances • Any pair of instances are neighbors under 𝑅 • Row instance of a colocation pattern 𝑐 • An 𝑅-proximity neighborhood • Each event type in 𝑐 appear only once • Table instance of a colocation pattern 𝑐 • Collection of all row instances of 𝑐
Basic Concept Example Spatial event types Candidate Colocation Table instance of (A, B) A, B, C (A, B), (B, C) … (A.1, B.1) (A.2, B.4) Spatial event instances Neighbor relationship (solid line) (A.3, B.4) A.1, A.2, A.3, … ... (A.1, B.1), (A.1, C.2) … Q: Table instance of (A, B, C)?
Interestingness Measure • Participation ratio 𝑝𝑟 • Given colocation pattern 𝑐 = 𝑓1,𝑓2,…,𝑓𝑘 |𝜋𝑓 𝑇𝑎𝑏𝑙𝑒.𝐼𝑛𝑠𝑡𝑎𝑛𝑐𝑒(𝑐)| • 𝑝𝑟 𝑐,𝑓𝑖 = 𝑖 |𝑇𝑎𝑏𝑙𝑒.𝐼𝑛𝑠𝑡𝑎𝑛𝑐𝑒(𝑓𝑖)| • Participation index 𝑝𝑖 • 𝑝𝑖 𝑐 = 𝑚𝑖𝑛𝑖{𝑝𝑟 𝑐,𝑓𝑖 } • Example: T1 T2 T3 T7 A B C ABC A.1 B.1 C.1 A.3 B.4 C.1 A.2 B.2 C.2 1 𝑝𝑟 (𝐴,𝐵,𝐶),𝐴 = A.3 B.3 C.3 4 A.4 B.4 1 𝑝𝑟 (𝐴,𝐵,𝐶),𝐵 = 5 B.5 1 𝑝𝑟 (𝐴,𝐵,𝐶),𝐶 = 1 3 𝑝𝑖 (𝐴,𝐵,𝐶),𝐶 = 5
Problem Definition • Input: • A set of spatial event types 𝑓1,𝑓2,…,𝑓𝑘 • A table instance for each event type • Spatial neighbor relationship across instances 𝑅 • A participation index threshold 𝛿 • Find: • All colocation patterns 𝑐 such that 𝑝𝑖(𝑐) ≥ 𝛿
Colocation Mining Algorithm: Baseline • Starting with 𝑘 = 1 k=1 A B C • Iterative until no prevalent pattern • Generate size 𝑘 colocation patterns {𝑐𝑘} k=2 AB AC BC • Generate table instance of each 𝑐𝑘 • Compute each 𝑝𝑖(𝑐 ), add to result if prevalent k=3 ABC 𝑘 • 𝑘 = 𝑘 + 1 T1 T2 T3 T4 T5 T6 T7 A B C A B A C B C A B C A.1 B.1 C.1 A.1, B.1 A.1, C.2 B.2, C.1 A.3, B.4, C.1 A.2 B.2 C.2 A.2, B.4 A.3, C.1 B.4, C.1 𝑝𝑖 = 0.2 A.3 B.3 C.3 A.3, B.4 B.5, C.3 A.4 B.4 𝑝𝑖 = 0.4 𝑝𝑖 = 0.5 𝑝𝑖 = 0.6 B.5
Colocation Mining Algorithm: Filter-Based Symbol Description 𝑐𝑘 candidate colocation of size k 𝐶𝑘 all candidate colocation of size k • Starting with 𝑘 = 1 𝑃𝑘 all prevalent colocation of size k • Iterative until no prevalent pattern • Generate size 𝑘 candidate patterns 𝐶𝑘 from prevalent patterns 𝑃𝑘−1 • For each candidate 𝑐𝑘 ∈ 𝐶𝑘 • Check all subset patterns • If any subset pattern not prevalent, prune out 𝑐𝑘 • Generate coarse table instance of each remaining 𝑐𝑘 ∈ 𝐶𝑘 • Compute each 𝑝𝑖(𝑐𝑘) • If 𝑝𝑖(𝑐𝑘) based on coarse resolution below threshold, prune out 𝑐𝑘 • Generate table instance of each remaining 𝑐𝑘 ∈ 𝐶𝑘 • Compute each 𝑝𝑖(𝑐𝑘), if above threshold, add 𝑐𝑘to set 𝑃𝑘 • 𝑘 = 𝑘 + 1
Prevalence-based Pruning • Lemma (apriori property): • If a colocation pattern 𝑐𝑘 is not prevalent, then any superset of 𝑐𝑘 is also not prevalent • Example T1 T2 T3 T4 T5 T6 k=1 A B C A B C A B A C B C A.1 B.1 C.1 A.1, B.1 A.1, C.2 B.2, C.1 k=2 AB AC BC A.2 B.2 C.2 A.2, B.4 A.3, C.1 B.4, C.1 A.3 B.3 C.3 A.3, B.4 B.5, C.3 A.4 B.4 𝑝𝑖 = 0.4 𝑝𝑖 = 0.5 𝑝𝑖 = 0.6 B.5 Don’t need to check (A,B,C)
Multi-resolution Pruning • Key idea: • Overlay a grid of size h • Each grid cell is a coarse instance of event types inside it • Neighbor relationship is imposed on the same cell or touching cells • Property • Participation index 𝑝𝑖 based on coarse resolution is upper bound of true value • Candidate pattern can be pruned if 𝑝𝑖 based on coarse resolution is below the threshold
Reference [1] Huang, Yan, Shashi Shekhar, and Hui Xiong. "Discovering colocation patterns from spatial data sets: a general approach." IEEE Transactions on Knowledge and data engineering 16.12 (2004): 1472-1485.
显示前 13 页。下载资料查看完整内容。
暂无评论。快来抢沙发吧！
评论 (0)
暂无评论。快来抢沙发吧！