2
$\begingroup$

I have a big dataset of M sequences of [1 - N] events, where each event has multiple properties (start date, end date, location, and more contextual features).

For each sequence of [1-N] events I want to find up to K (1<=K<=N) subsequences (clusters) based on events similarity.

For example, the sequence of the following events: [A B C D]

EVENT     START_DATE     END_DATE       LON      LAT

A         2018-01-01     2018-01-02     10       15
B         2018-01-02     2018-01-03     10       15
C         2018-02-01     2018-01-08     20       30
D         2018-03-01     2018-03-03     10       15

can be split into:

[[A] [B] [C] [D]],[[A B] [C] [D] ], [[A][B C][D]], [[A] [B] [C D]], [[A B] [C D]], [[A B C][D]],[[A] [B C D]], [[A B C D]]

Where the obvious split is [[A B][C][D]] since A and B are consecutive in same location with similar time-span, C happens a month after in a different location and D happens in the same location but 2 month later.

Some assumptions/special treatment might apply:

  • Same clusters appear sequentially in terms of time ([[A C] [B] [D]] is not possible)
  • Different features might have different weights (time proximity might be more important that date proximity
  • Number of clusters is unknown
  • Ground truth is unknown, but can be determined in a quite accurate way by human labelling.
  • The calculation needs to be realtime (<1s for M<100), but can be calculated incrementally (recalculated after addition of a new event)

Any suggestions of what algorithm can be useful for this problem? Classical clustering here is not suitable and I'm looking for other options.

$\endgroup$
0
$\begingroup$

Try generalized DBSCAN.

Define two thesis:

  1. Distance, points sold be "near" each other
  2. Time, events should be close in time

Don't use a standard implementation. Instead exploit that you can sort the data by time, and only need to consider the events within the time threshold.

$\endgroup$
  • $\begingroup$ I'm sorry but I can't see how it relates to frequent subsequence. I'm not looking for the popular subsequences (they probably won't repeat at all), but looking how to group events in the sequence into clusters. (reference for FS - ai.ms.mff.cuni.cz/~sui/sequential_mining.pdf) $\endgroup$ – Dimgold Mar 27 at 8:11
  • $\begingroup$ Then you need to explain your problem better, what kind of patterns you are looking for. $\endgroup$ – Anony-Mousse Mar 27 at 16:00
  • 1
    $\begingroup$ So give examples of the actual input and output, not A B C if these aren't items in a sequence, and how a cluster is supposed to be defined. $\endgroup$ – Anony-Mousse Mar 28 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.