Đang tạo bản xem trước...
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.
Hiển thị 13 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!