0

I require an efficient approach in R to identify clusters of points using the following rule sets:

  1. 2 or more points within 2 hours of each other should be clustered.
  2. Clusters that are within 150m each other (closest point to closest point) and within a 6 day time-window should be combined into larger clusters.

IndividualID represents unique individuals. Clusters between individuals should not be linked.

Ideal output would be a table with a "cluster" column identifying which cluster each point record is linked to.

I've figured out how to address rule set 1, albeit fairly long-winded, so can provide this if needed.

Example data set below:

structure(list(IndividualID = c("P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", "P_F_3071_40", 
"P_F_3071_40", "P_F_3071_40", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", 
"P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", 
"P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", 
"P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", 
"P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", "P_F_3071_65", 
"P_F_3071_65", "P_F_3071_65", "P_F_3071_65"), DateTime = structure(c(1460091660, 
1462683660, 1465426860, 1465434000, 1465462860, 1465470000, 1465491660, 
1465498800, 1465527660, 1465534800, 1465570860, 1465578000, 1465621260, 
1465628400, 1465765260, 1465772400, 1465902060, 1465909200, 1465945260, 
1465952400, 1465959660, 1465966800, 1465981260, 1465988400, 1466060460, 
1466067600, 1466089260, 1466096400, 1466118060, 1466125200, 1466132460, 
1466139600, 1466168460, 1466175600, 1466204460, 1466211600, 1466902860, 
1466910000, 1466938860, 1466946000, 1466974860, 1466982000, 1467075660, 
1467082800, 1467738060, 1467745200, 1467788460, 1467795600, 1467910860, 
1467918000, 1468177320, 1468184460, 1468220520, 1468227600, 1468429260, 
1468436400, 1468515660, 1468522800, 1468609320, 1468616400, 1468630860, 
1468638000, 1468789260, 1468796400, 1468947660, 1468954800, 1468969260, 
1468976400, 1468983660, 1468990800, 1469120460, 1469127600, 1469214060, 
1469221200, 1469322060, 1469329200, 1469358060, 1469365200, 1469458860, 
1469466000, 1469559660, 1469566800, 1469696460, 1469703600, 1469833200, 
1469840340, 1469934060, 1469941200, 1469984460, 1469991600), tzone = "", class = c("POSIXct", 
"POSIXt")), X = c(-122.3724041, -122.3733317, -122.3714029, -122.3715247, 
-122.3750655, -122.3708959, -122.3794764, -122.3829663, -122.4067149, 
-122.4112984, -122.409014, -122.408943, -122.4090122, -122.4107643, 
-122.4203011, -122.4092476, -122.4094697, -122.4089489, -122.4089616, 
-122.4088741, -122.408935, -122.4089612, -122.4086532, -122.4037183, 
-122.4201475, -122.4199123, -122.4204426, -122.4202226, -122.4199262, 
-122.4199871, -122.4199125, -122.4201827, -122.3938207, -122.3938583, 
-122.3918668, -122.3916721, -122.3529901, -122.354418, -122.340651, 
-122.3403595, -122.3409872, -122.3380352, -122.3035277, -122.3033569, 
-122.3746217, -122.3747383, -122.3770923, -122.3898683, -122.3840227, 
-122.3859436, -122.3708576, -122.363574, -122.3885722, -122.3745535, 
-122.3246823, -122.3409753, -122.3701529, -122.361142, -122.3611454, 
-122.3611205, -122.3428932, -122.3283405, -122.3245829, -122.3245331, 
-122.3144215, -122.3141788, -122.3372718, -122.3611578, -122.3611221, 
-122.3612322, -122.408749, -122.409146, -122.4087486, -122.3990234, 
-122.3866925, -122.3811472, -122.3754158, -122.3750234, -122.386714, 
-122.3874818, -122.3786127, -122.3831537, -122.3999038, -122.3986496, 
-122.3946552, -122.3944709, -122.394583, -122.3945822, -122.3937728, 
-122.3943946), Y = c(43.50910633, 43.50315059, 43.50424753, 43.50443729, 
43.50175542, 43.50423574, 43.50466981, 43.50695777, 43.50098758, 
43.50792655, 43.5341171, 43.53378358, 43.53429718, 43.53357688, 
43.53801069, 43.53427138, 43.53434456, 43.53444992, 43.53441397, 
43.53450356, 43.53460292, 43.53444999, 43.53431333, 43.53272097, 
43.48167926, 43.48170508, 43.48186084, 43.48158959, 43.48154307, 
43.48164243, 43.48168707, 43.48187753, 43.5027298, 43.50267598, 
43.50390799, 43.50481638, 43.45381077, 43.46481313, 43.47805195, 
43.47983312, 43.48238496, 43.48093622, 43.44715413, 43.44695499, 
43.45725372, 43.45673211, 43.45498911, 43.4665025, 43.47118042, 
43.47318071, 43.50434358, 43.48172953, 43.46630649, 43.45667707, 
43.46522666, 43.48347441, 43.50431268, 43.5036414, 43.50448782, 
43.50450569, 43.47423803, 43.4642037, 43.46527109, 43.46529781, 
43.50897145, 43.50854679, 43.51569729, 43.50448789, 43.50435262, 
43.50447029, 43.46999632, 43.4698543, 43.47003233, 43.49949772, 
43.53845663, 43.53727421, 43.53016573, 43.5334051, 43.51679257, 
43.51550008, 43.52736482, 43.53349428, 43.49303727, 43.49852329, 
43.50586771, 43.50574067, 43.50566923, 43.50575027, 43.50627723, 
43.50595637)), row.names = c(NA, -90L), groups = structure(list(
    IndividualID = c("P_F_3071_40", "P_F_3071_65"), .rows = structure(list(
        1:64, 65:90), ptype = integer(0), class = c("vctrs_list_of", 
    "vctrs_vctr", "list"))), row.names = c(NA, -2L), class = c("tbl_df", 
"tbl", "data.frame"), .drop = TRUE), class = c("grouped_df", 
"tbl_df", "tbl", "data.frame"))
Improve this question
5
  • I don't understand the two steps. Are they done sequentially? So Step 1 you could be clustering two points at any distance, and then Step 2 you do an essentially 3d clustering with spatial=150, time=6 distance, and you could end up with a "cluster" that's separated spatially by any distance because of step 1?
    – Spacedman
    Commented Jan 27, 2022 at 13:54
  • @Spacedman – They could be done sequentially, but they don't have to be done separately I guess. I just tried to explain the rules in a clear way.
    – Ross
    Commented Jan 27, 2022 at 16:45
  • Ok, suppose your data has two spatial clusters 10km apart, on roughly the same hour. By rule 1 you'd group that into one cluster? I think what you've got here is really an adjacency construction using those thresholds as the adjacency condition. So I think its the same as constructing the NxN binary adjacency matrix and then using maybe igraph to get connected components from the corresponding graph....
    – Spacedman
    Commented Jan 27, 2022 at 22:24
  • @Spacedman – Yes, by rule 1, those points would be grouped into one cluster. It's though very unlikely in a real-world scenario, since these data come from live large carnivores being tracked using GPS collars, and they shouldn't move such great distances within such short time spans. But, who knows, anything is possible I guess.
    – Ross
    Commented Jan 28, 2022 at 3:43
  • Code has to cope with anything :) In other words, you want to partition your data into a set X of subsets such that no point in subset A is within 2h of any point in subset B, or is within a space-time distance of (150m, 6day) of any point in subset B, for all pairs of subsets A,B in X (where A!=B).
    – Spacedman
    Commented Jan 28, 2022 at 9:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.