Search in net for the concept of "Levenshtein distance between vectors"

Levenshtein distance

From Wikipedia, the free encyclopedia Jump to navigation Jump to search

In information theory, linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965.[1]

Levenshtein distance may also be referred to as edit distance, although that term may also denote a larger family of distance metrics.[2]:32 It is closely related to pairwise string alignments.

Dear Abhilash

I think you can not compare between two vectors that have different length. So, I suggest to select some first items from both vectors to equalize the length of vectors then compare between them through take the differences between these two vectors.

Thank you for the reply @Hiba.

According to your suggested technique:

For eg:

** I have two vectors f1 and f2 : [f1]1x30 and [f2]1x20.

** Here, I would need to compare f1(1:20) with f2(1:20).

** Let the data in f1(1:15) be very similar/or equal to f2(1:15).

** But, from f1(15:30) , which is half the data, the data is following a different trend as compared to the whole trend in f2(1:20).

** Now, let us assume the similarity to be in the range [0,1] (1 means perfectly similar)

** According to the technique, I would compare f1(1:20) with f2(1:20) and since the majority of the data are similar, the similarity value will be close to 1. However, in reality the similarity value should be somewhere close to 0.5.

** And of course, this will result in the reduction of the accuracy of my clustering algorithm which uses the similarity matrix as input.

I think you can compare them by the amount of information they contain about what you're interested in. http://lc.kubagro.ru/

Try Cosine similarity between your vector pairs

http://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/

Alternative: Longest common subsequence (LCS)

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Do your feature vectors represent homogeneous data? For example, if a subset of your features represents temperature and remaining part represents weight; then it is a heterogeneous representation.

If your features are homogeneous, then you can employ-

1. DTW- as you mentioned.

2. Equalize the vector lengths through up/down sampling; and match

Кетан Котваль

That's why I suggested using the amount of information

Dynamic time warping?

Thank you for your responses.

The data is homogeneous.

To be specific, the data is angular. This means each element of the feature-vector represents the orientation of a "vector" from time ti to ti+1.

**If the feature vector lengths are similar then, using Cosine similarity measure is an good option. But, my data is angular and not vector data.

**LCS ( Longest common subsequence ) seems to be interesting , will look into it.

** Sampling the data is also possible. But what kind of sampling ? (In order to maintain the trend in the data)

** Again my question about DTW (Dynamic time warping) is, how well does it perform when the difference between the lengths of the feature vectors under comparison are large?? For eg: [1x30] and [1x10].

(I am getting bad results for similarity values after implementing it for comparing my feature vectors. NB: I have considered the problem with using angular data in my implementation )

** @ Prof. Lutsenko : What kind of information ?

Abhilash K Pai!

Check out my article on cognitive clustering:

Lutsenko E. V. AGGLOMERATIVE COGNITIVE CLUSTERING OF NOSOLOGICAL IMAGES IN VETERINARY MEDICINE / E. V. Lutsenko // Polythematic network electronic scientific journal of Kuban state agrarian University (scientific journal of Kubgau) [Electronic resource]. – Krasnodar: Kubsau, 2018. - №04 (138). P. 122 – 139. - IDA [article ID]: 1381804033. – Mode of access: http://ej.kubagro.ru/2018/04/pdf/33.pdf, 1,125 of the CPC.

The article deals with the similarity and difference of nosological images in veterinary medicine using a new method of agglomerative clustering implemented in Automated system-cognitive analysis (ASC-analysis) on a small numerical example. This method is called Agglomerative cognitive clustering. This method differs from the known traditional facts: a) parameters of a generalized image of the cluster are computed not as averages from the original objects (classes) or their center of gravity, and are defined using the same underlying cognitive operations of ASC-analysis, which is used for the formation of generalized images of the classes on the basis of examples of objects and which is really correct and provides a synthesis; b) as a criterion of similarity we do not use Euclidean distance or its variants, and the integral criterion of non-metric nature: "the total amount of information", the use of which is theoretically correct and gives good results in non-orthonormal spaces, which are usually found in practice; c) cluster analysis is not based on the original variables, matrices of frequency or a matrix of similarities (differences) dependent on the measurement units of the axes, and in the cognitive space in which all the axes (descriptive scales) use the same unit of measurement: the quantity of information, and therefore, the clustering results do not depend on the original units of measurement features. All this makes it possible to obtain clustering results that are understandable to specialists and can be interpreted in a meaningful way that is in line with experts' assessments, their experience and intuitive expectations, which is often a problem for classical clustering methods

Thanks. Will check it out.

If the data is angular, here are examples of my work with such data using information theory:

http://ej.kubagro.ru/2015/08/pdf/64.pdf

http://ej.kubagro.ru/2016/02/pdf/77.pdf

Abhilash K Pai you can compare two vector of different length by balancing them. There can be two techniques

In pattern recognition systems, this is a common thing: one object is described by a large number of features, and the other is less, and they are compared with generalized images in exactly the same way: the amount of information about belonging to the classes that is in these elements is summed up. The number of gradations in different schools may be different and they may not be alternative, text or numerical and in different units. They are still measured in units of information:

http://lc.kubagro.ru/

http://lc.kubagro.ru/aidos/index.htm

http://lc.kubagro.ru/aidos/_Aidos-X.htm

Well, if the features represent data within a given time interval; then is the total time-span of feature vectors same? If one feature vector (fv) is capturing data over a week's time and another fv represents a month, then DTW is unfair. It is better to cut the month fv to match week fv, and then proceed.

If both/all fv-s refer to the same time, but their sampling is different, then DTW or normalization are good options. If your fv lengths differ a lot, your can resample them. If you average out, essentially you are smoothing trends. If it doesn't hurt your application, then pure upsampling is easy and fast.

If the vectors are homogeneous, for example, images of different dimensions, then another approach is possible to compare them. It is necessary to compare a smaller vector with all fragments of a larger vector with similar lengths. In this case, a part of a larger vector may exactly coincide with a smaller vector. Modifications of this approach are possible.

@ Ketan, the interval between each reading is fixed (1 sec) and same for all feature vectors (total time span considered is 1 to 30 secs).

However, some feature vectors start at time,say "ti" and end at time "tn"(anywhere in the range 1-30 secs) and thus have different lengths.

@ Vladimir:

No, to put it short and sweet: i am looking for some technique which can compare the "overall-trend/pattern" between two feature vectors of different lengths.

then it is necessary to compare their meaning, i.e. the amount of information in them about what you are interested in

a simple suggest，you can compare them after a mapping(linear or nonlinea). Here you can refer to FCN’s Idea

If the feature vectors varying in length you can apply some linear or nonlinear transformation to obtain vectors equal in length. It can be done by narrowing or spanning the size of vectors. Simply speaking you can transform both vectors into the new space where they will have the same dimension/size.

I suggest using PCA, kernel PCA or similiar techniques to reduce size of vectors into common value. On the same way the size of vectors can be transformed into common bigger size using idea related to kernel (nonlinear transformation) trick like in SVM.

If the feature vectors represent information from different time slots (ti-n as per your notation) then it is better to compare the respective feature segments.

Following my previous example, say your data represents some feature computed every month. For some cases, you have 12-d vector for Jan-Dec, and sometimes you have 4-d vector for Jan-Apr. Then it may not be correct to compare 12-d feature against upsampled version of 4-d feature. You will be scaling trends of 1 month to trends to 3 months. A valid solution might be to consider only 4 values from 12-d vector that represent the same time intervals.

It depends on the nature of your problem. In some cases, scaling or warping may not create a problem.

try the DTW algorithme.

Search in net for the concept of "Levenshtein distance between vectors"

Levenshtein distance

From Wikipedia, the free encyclopedia Jump to navigation Jump to search

In information theory, linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965.[1]

Levenshtein distance may also be referred to as edit distance, although that term may also denote a larger family of distance metrics.[2]:32 It is closely related to pairwise string alignments.

I agree with @Vladimir Krasilenko. You should find a good distance function, whether it is Levenshtine distance or something else.

I agree with @Ketan Kotwal, you should make meaningful comparisons.

To deal with the length difference, I recommend using a sliding window approach (similar to what @Vladimir Krasilenko suggested). Slide the shorter vector along side of the longer one with step size of 1 sample (1 sec). At each step, compute the distance (e.g. Levenshtein) between the shorter vector and the its corresponding segment in the longer one, which are both of the same size. At the end, you can use max, min, average, or another meaningful rule to combine all of the computed distances into one number. This number is the edge between the two feature vectors that can be recorded in the final similarity matrix.

I proposed using the information distance (non-metric integral criterion). And the coordinates of the vectors are particular criteria

Hello

I suggest you:

1- the features separation in terms of type and meaning

2- after 1, use linear or nonlinear transformations to get vectors with equal length

Thanks everyone for the suggestions.

Combining the ideas mentioned by Ketan Kotwal , Vladimir Krasilenko and Tom Arjannikov will hopefully solve my problem.

Application of a linear/non-linear transform function, as mentioned by Marcin Piekarczyk , Maofeng Tang and Mohammad Mahdi Feraidooni , to my problem will require a definition of a robust transformation function which is able to keep the trend of the feature vector.

Also, the information-based comparison measure as suggested by @Евгений Луценко seems interesting and will be explored.

Abhilash K Pai !

In order to compare two vectors of different length it is necessary to obtain two vectors of the same length. This can be done in different ways, as we have seen above. I suggest another. Take a number of random vectors and multiply scalar first vector by each of them and second vector by each of them. As a result, we get two arrays of numbers of the same length, which can be interpreted as the coordinates of two vectors of the same length, which is not a problem to compare.

Look article: Lutsenko E. V. Theoretical bases of system-cognitive modeling of processes and machines of Agroengineering systems / E. V. Lutsenko // Polythematic network electronic scientific journal of the Kuban state agrarian University (scientific journal of Kubgau) [Electronic resource]. – Krasnodar: Kubsau, 2018. - №01 (135). C. 1 – 49. - IDA [article ID]: 1351801001. – Mode of access: http://ej.kubagro.ru/2018/01/pdf/01.pdf, 3,062 of the Premier League. In it I do something similar

resample or pad the vectors to have the same length...

best

Maybe you can use normalized Higher Order Crossings.

You use Statistical tests, if the data set contains more than one variable you can use Multivariate Analysis (Test for Equality of Mean Vector and Test for Equality of Covariance matrices etc.); if the data set comprises only on variable, you can use bivariate analysis (t-test, F-ratio test, etc.)

Unless otherwise, you can go for the techniques suggested by the above peer people.

https://www.researchgate.net/post/How_can_we_classify_variable_dimension_feature_vectors

https://www.researchgate.net/post/Similarity_between_two_vectors_with_different_lengths

https://www.researchgate.net/post/Unequal_data_feature_lengths

https://stackoverflow.com/questions/23966648/how-to-encode-different-size-of-feature-vectors-in-svm