2
$\begingroup$

I am trying to find a good distance function for sequential data that is all binary. For now, I am using Edit distance however I have some more domain-specific knowledge that I would like to incorporate. Unlike data in a standard Euclidean space, we can think of my measurements as a time-series such that it makes sense to assume that entries at neighboring indices should be close to each other, as an example:

$$\mathbf{x} = \{0,0,0,0,0,0,0,1 \}$$ $$\mathbf{y} = \{0,0,0,0,0,0,1,1 \}$$ $$\mathbf{z} = \{1,0,0,0,0,0,0,1 \}$$

Here $\mathbf{x}, \mathbf{y}, \mathbf{z}$ all have the same pairwise edit distance, but for me, it would seem more logical to rank $\mathbf{x}$ and $\mathbf{y}$ to be closer to each other. I read some threads here that mentioned other classic similarities like Jaccard distance or Dice-dissimilarity, but they are not localized either. I also found some articles about string metrics based on Kernels, but it seemed quite involved and I am not sure if they can do what I expect. My sequences are all rather short (<= 10), so computational efficiency is not a big concern. Also, I don't mind the similarity measure not being a metric from a mathematical standpoint.

Thank's for your help, Max

$\endgroup$
1
$\begingroup$

Edit distances measure the cost of transforming one input into another via a sequence of operations. Their behavior depends on the allowed set of operations and the costs assigned to these operations. Based on your example, it sounds like you might be using an edit distance that only allows bit flip operations (making it equivalent to the Hamming distance). One way to gain location sensitivity is to allow 'move' operations as well.

Here, you could think of each binary sequence as a collection of objects located at particular positions. Each '1' represents an object whose position is the corresponding index within the sequence. The allowed operations are:

  • Move an object (by changing the position of a '1'). The cost of this operation is the distance moved.

  • Create an object (by flipping a '0' to a '1') or destroy an object (by flipping a '1' to a '0'). This has a cost of $c$, which is a free parameter governing the relative cost of creating/destroying vs. moving.

The distance between two sequences is the minimum cost of transforming one sequence into the other using these operations. Computing the distance requires solving an optimization problem (e.g. using dynamic programming). This form of edit distance can also be seen as a generalized earth mover's distance where mass can be created/destroyed.

Notice that an object can effectively be moved a distance of $d$ using either the move operation (with a cost of $d$), or by destroying the original object and creating another object at the new location (with a cost of $2 c$). The move operation is cheaper (and therefore contributes to the final cost) when $d < 2c$. So, the choice of $c$ can be seen as determining the length scale over which moves are relevant.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I like this approach, it captures this idea of localized distance, which I found hard to define precisely in the first place and it is pretty easy to interpret. I'll implement it and see how this works, thanks a lot. $\endgroup$ – Maximal Jan 16 '19 at 12:00
0
$\begingroup$

A simple suggestion with the idea to still take the edit distance but add a value <1 based on how close the 1s and 0s are in the two strings:

1) Determine the edit distance: N_edit

2) For String X (having X_0 0s and X_1 1s) and Y do:

  1. Create all permutations of X_0 0s and X_1 1s naming it X'.
  2. Create all permutations of Y_0 0s and Y_1 1s naming it Y'.
  3. Define dist_local(X,Y) as the absolute value of the sum of differences between the positions of all 0's in X AND Y PLUS the sum of differences between the positions of all 1's in X AND Y.
  4. Be MAX_LOCAL_DIST the maximum over all dist_local(Xi,Yi) where Xi in X' and Yi in Y'.
  5. Your final distance is: N_edit + dist_local(X,Y) / MAX_LOCAL_DIST
| cite | improve this answer | |
$\endgroup$

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.