Colocation Pattern Discovery Zhe Jiang zjiang@cs.ua.edu 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 http://www.alamy.com/ Bar closing events and crimes 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 A, B, C Candidate Colocation (A, B), (B, C) … Spatial event instances Neighbor relationship (solid line) A.1, A.2, A.3, … ... (A.1, B.1), (A.1, C.2) … Table instance of (A, B) (A.1, B.1) (A.2, B.4) (A.3, B.4) 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.2 B.2 C.2 A.3 B.4 C.1 1 𝑝𝑟 (𝐴, 𝐵, 𝐶), 𝐴 = 4 A.3 B.3 C.3 1 A.4 B.4 𝑝𝑟 (𝐴, 𝐵, 𝐶), 𝐵 = 5 B.5 1 𝑝𝑟 (𝐴, 𝐵, 𝐶)

Lire le document entier