CN108154189A - Grey relational cluster method based on LDTW distances - Google Patents

Abstract

The present invention relates to the field of mining, specifically a gray relational clustering method based on LDTW distance, comprising: processing the original data set to obtain a preprocessed sequence; constructing the maximum value of each dimension in the preprocessed sequence to form a reference sequence ; Calculate the LDTW distance between the preprocessed sequence and the reference sequence and its curved path length; calculate the gray correlation degree between the preprocessed sequence and the reference sequence based on the LDTW distance; determine the critical value interval according to the result of the gray correlation degree, Divide the critical value interval into a plurality of critical intervals, if the gray correlation degree of two sequences falls in the same critical interval, then cluster the two sequences into one class, the present invention reduces the similarity measure between the two sequences. Errors can help biologists study the function of proteins.

Description

Gray Relational Clustering Method Based on LDTW Distance

technical field

The invention belongs to the field of data mining, in particular to a gray relational clustering method for biometric data based on dynamic time warping distance (DTW under limited warping path length, LDTW) under limited warping length.

Background technique

With the massive increase in the scale of biological databases, more and more people use computer programs to automatically classify. Bioinformatics brings great hope to human beings, but also brings opportunities and challenges to data analysts. Tens of billions of data are pouring into public databases, and relying on experimental methods to analyze these data is time-consuming and expensive. Therefore, it is necessary to find effective and fast calculation methods to automatically analyze these data. The huge biological information database poses many challenging problems to data mining technology, and also provides broad opportunities. Clustering analysis technology is an important and commonly used technology in data mining. Applying clustering technology to analyze biological data can help us study the properties and functions of genes and proteins, and provide help for exploring the mysteries of biology.

Cluster analysis has become a very active research topic in the field of data mining research. It has been successfully applied to research in various fields of life sciences, such as effectively dividing different gene sequence sets, identifying functional genes, inferring species phylogenetic trees, and clustering protein physical and chemical properties. Predicting its function, etc., has become an important tool for functional gene research in the post-genome era. Due to its wide application, a large number of available cluster analysis software has appeared to facilitate its promotion and application.

Professor Deng Julong proposed gray system theory in 1982 (references: Liu Sifeng, Yang Yingjie, Wu Lifeng. Gray system theory and its application [M]. Science Press, 2014.) has become an emerging structural system, including grayscale, Basic systems such as interval gray numbers, gray equations, and gray matrices. Among them, the core of gray relational clustering lies in the calculation of the gray relational degree between sequences, so whether to choose the appropriate gray relational analysis method is very important for the clustering effect. As a very active branch of gray system theory, gray relational analysis transforms the discrete behavior observations of system factors into piecewise continuous polylines, and then constructs a model to measure the degree of correlation according to the geometric characteristics of polylines. Gray relational degree is a scale index to determine the relational relationship between factors, among which Deng's gray relational degree proposed by Deng Julong is widely used (Reference: Deng Julong. Gray System Theory Tutorial [M]. Huazhong University of Science and Technology Press, 1990.). In bioengineering, there are many uncertain factors in the collected data of each organism, which can be regarded as a gray system. The traditional gray relational degree model cannot effectively deal with uncertain phenomena such as missing data, bending and drifting, and usually uses methods such as deleting long sequence data, mean values, and GM (1,1) model predictions to complete them, resulting in uncertain information Further amplification, resulting in unnecessary loss of information. Therefore, a dynamic correlation analysis model for uncertain sequences is urgently needed. The LDWT distance is calculated by using the dynamic time warping (Dynamic Time Warping, DTW) distance through the total number of connections between the added sequences. This method does not need to complete the sequence data, and still uses the shortest path of the distance matrix between data sequences as the most basis in judging the degree of similarity. Therefore, the gray relational degree model based on LDTW is applied to biological clustering, which can effectively cluster biological sequences, mine their potential information from the station, and obtain new biological knowledge at the same time.

At present, the source of error in the traditional Deng's gray relational degree is mainly because it uses the difference of absolute value to represent the distance between two sequences. Existing scholars have improved the calculation method of the distance between two sequences , proposed to use dynamic time warping DTW to replace the difference in absolute value, but the DTW distance has long had pathological alignment problems, and most existing solutions basically impose strict constraints on curved paths, But it is likely to miss the correct alignment. See literature: Dai J, Hu F, Liu X. Research on gray incidence measurement method based on dynamic time warping distance [J]. Journal of Gray System, 2015, 27(1): 117-126. It can be seen that there are still defects in the existing methods, which lead to deviations when we mine the potential information.

Contents of the invention

Aiming at the problems of the prior art, the present invention provides a gray relational clustering method based on LDTW distance. The present invention is applied to data mining, clusters data, and quantitatively analyzes the differences between the attributes of clustered objects, and can group proteins with similar functions into one group, thereby providing biologists with the ability to study protein functions Offered help.

The gray relational clustering method based on LDTW distance of the present invention, as shown in Figure 1, comprises:

S1. Process the original data set to obtain a preprocessed sequence;

S2. The maximum value of each dimension in the preprocessed sequence constitutes a reference sequence;

S3. Calculate the LDTW distance between the preprocessed sequence and the reference sequence and its curved path length λ;

S4. Calculating the gray relational degree between the preprocessed sequence based on the LDTW distance and the reference sequence;

S5. Determine the critical value ε according to the results of the gray relational degree, and divide the gray relational degree interval into a plurality of critical intervals according to the critical value ε. If the gray relational degrees of the two sequences fall in the same critical interval, the two Sequences are clustered into one class.

Preferably, in step S1, the original data set is processed to obtain a preprocessed sequence, which is transformed into dimensionless data of approximately similar quantity.

The processing of the original data set to obtain the preprocessed sequence includes: using the original sequence to preprocess the original sequence so that the original sequence is converted into dimensionless data, and the dimensionless data is preprocessed sequence; the preprocessed sequence specifically includes:

Original sequence: X′ _i =(x′ _i (1),x′ _i (2),...,x′ _i (n));

Preprocessed sequence: Xi ₌ ( _xi (1), _i (2),..., _i (n));

Among them, X' _i represents the i-th original sequence, x' _i (j) represents the data value of the j-th dimension of the i-th original sequence; _Xi represents the i-th preprocessed sequence, and x _i (j) represents The value of the j-th dimension of the i-th preprocessed sequence;

in, x′ _max (j) represents the maximum value of all sequences in the jth dimension of the original sequence, x′ _min (j) represents the minimum value of all sequences in the jth dimension of the original sequence, i∈{1,2,... ,I}; j∈{1,2,...,n}; I is the number of sequences, n is the number of dimensions.

The maximum value of each dimension in the preprocessed sequence to form a reference sequence includes:

in, Indicates the value of the jth dimension of the reference sequence; x _max (j) indicates the maximum value of the jth dimension in the preprocessed sequence; j∈{1,2,...,n}, n is the number of dimensions.

Preferably, calculating the LDTW distance and path length λ between the preprocessed sequence and the reference sequence includes:

The preprocessed sequence is X _i =( _xi (1), _xi (2),..., _xi (n)); the reference sequence is X ₀ ={x ₀ (1),x ₀ (2 ),...,x ₀ (n)};

Further, when it is necessary to calculate the LDTW distance, path length and gray correlation degree, the preprocessed sequence X _i =( _xi (1), _xi (2),..., _xi (n)) needs Remove the dimensions of the missing data to obtain a new preprocessed sequence X _i =(xi ₍ 1), _i (2),..., _i (m));

Preferably, the dimension of the missing data of the preprocessed sequence is removed to obtain a new preprocessed sequence: X _i =( _xi (1), _xi (2),..., _xi (m) ); Calculate the LDTW distance between the new preprocessed sequence and the reference sequence; then the distance matrix between the preprocessed sequence _Xi and the reference sequence X ₀ is:

Among them, dis( _xi (m), x ₀ (n))=| _xi (m)-x ₀ (n)|, dis( _xi (m), x ₀ (n)) is the nth dimension The distance between the component value x _i (m) in the i-th sequence and the n-th dimension component x ₀ (n) of the reference sequence;

The LDTW distance between the new preprocessed sequence X _i and the reference sequence X ₀ includes:

D(X _i (m), X ₀ (n), s) represents the LDTW distance between X ₀ and X _i , min represents the minimum value, D( _xi (m), x ₀ (n-1), s- 1) indicates the distance from x ₀ (n-1) to x _i (m); D( _xi (m-1), x ₀ (n), s-1) indicates the distance from x ₀ (n) to x _i (m) -1) distance; D(x _i (m-1), x ₀ (n-1), s-1) represents the distance from x ₀ (n-1) to x _i (m-1); i∈{ 1,2,...,I}, s represents the step size, I is the number of sequences; m and n are the number of dimensions, m≤n.

Further, the path length λ includes: when calculating the LDTW distance between the preprocessed sequence and the reference sequence, the LDTW distance imposes constraints on the length of the curved path; considering the current length of the curved path as an additional factor; the matrix traveled The cells of are path lengths.

Further, LDTW works by limiting the length of the curved path. Therefore, taking the length of the curved path as an additional factor, in order to describe the length of the curved path more intuitively, it is represented by the number of steps, the number of steps = path length – 1, and the number of steps is represented by "s".

Preferably, step S4 calculates the gray correlation degree between the preprocessed sequence based on the LDTW distance and the reference sequence including:

A given sequence X ₀ ={x ₀ (1),x ₀ (2),...,x ₀ (m)} and X _i =(x _i (1),x _i (2),..., x _i (n)), preferably, the dimension of the missing data of the preprocessed sequence _Xi is removed to obtain a new preprocessed sequence: Xi ₌ ( _xi (1), x _i (2), ..., _xi (m)); for example, the preprocessed sequence _Xi = ( _xi (1),xi ₍ 2),..., _xi (n)) in the x _i (2 ₎ is no _data , then _change the data of x _i (3) into new x _i (2); ,..., _xi (m)); m≤n; Calculate the gray correlation degree between the new preprocessed sequence and the reference sequence; specifically include:

Then the gray correlation degree between two sequences is defined as follows:

in, Denotes the two-level minimum difference between the value of an element of sequence X ₀ and the value of an element in sequence X _i , Indicates the two-level maximum difference between the value of the element of the sequence X ₀ and the value of the element in the sequence _Xi , ξ is the resolution coefficient, and ξ∈[0,1], LDTW(X ₀ ,X _i ) represents X ₀ and X The dynamic time warping distance of _i under finite length, λ is the path length corresponding to LDTW(X ₀ ,X _i ), i∈{1,2,...,I}, I is the number of sequences; t ₀ Indicates the t _0th dimension, t _i indicates the t _i th dimension; 1<t ₀ ≤n, 1<t _i ≤m, m and n are the number of dimensions, m≤n.

In order to verify the correctness of the gray relational degree based on LDTW, it can be proved from whether the gray relational axiom is satisfied; among them, the gray relational axiom includes:

(1) Normative:

Write Δ(X ₀ ,X _i )=LDTW(X ₀ ,X _i )/λ, because Therefore:

0<γ(X ₀ ,X _i )≤1;

(2) Integrity:

Since the gray relational degree of dynamic time warping is only a measure of the degree of correlation between the sequence X ₀ and _Xi without considering other factors, there is no overall problem here;

(3) Pair symmetry:

According to the LDTW distance property, γ(X ₀ ,X _i )=γ(X _i ,X ₀ );

(4) Proximity:

LDTW(X ₀ ,X _i ) reflects the distance between sequence X ₀ and X _i , the smaller the distance, the larger γ(X ₀ ,X _i ), and thus the closer sequence X ₀ is to X _i .

It has been proved that the gray relational clustering method based on the LDTW distance adopted in the present invention simultaneously satisfies the four theorems required by the gray relational theorem.

Preferably, according to the results of the gray relational degree, an appropriate critical value ε is determined, and the critical value ε is divided into a plurality of critical intervals, namely [0, ε], [ε, 2ε], ..., [1 -ε,1], if the gray relational degrees of the two sequences fall in the same critical interval, calculate the gray relational values of the two sequences, and if the gray relational degrees of the two sequences fall in the same critical interval, the two Sequences are clustered into one category; specifically include: in the preprocessed sequence _Xi, assume that any two sequences are expressed as:

_Xp = { _xp (1), _xp (2),..., _xp (n)};

X _q ＝{x _q (1),x _q (2),...,x _q (n)}

Among them, X _p represents the p-th sequence, X _q represents the q-th sequence; x _p (n) represents the n-th data of the p-th sequence; x _q (n) represents the n-th data of the q-th sequence; p∈{1,2,...,I}, q∈{1,2,...,I}; use the critical value ε to divide [0,1] into multiple critical intervals, namely [0,ε ], [ε, 2ε], ..., [1-ε, 1]; when the values of the gray relational degrees of the two sequences X _p and X _q are in the same interval, then the two sequences X _p and X _q clustered into one class.

The present invention solves the problem that due to the traditional Deng’s gray relational degree, long sequences need to be deleted when data is missing, and the missing data needs to be supplemented by methods such as GM (1, 1) model prediction, thereby causing the original data to be destroyed , resulting in an error in the measurement of the final gray relational degree. A new calculation method of gray relational degree is proposed, which reduces the error of the similarity measure between two sequences and provides help for biologists to study the function of proteins.

Description of drawings

Fig. 1 is the schematic flow chart of the preferred embodiment of the gray relational clustering method based on LDTW distance of the present invention;

Figure 2 is an example of singular points generated by DTW;

Fig. 3 is the comparison (no missing data) of the present invention and the purity of traditional gray correlation degree;

Fig. 4 is the comparison (no missing data) of the present invention and the entropy of traditional gray correlation degree;

Fig. 5 is the comparison (no missing data) of the purity of the present invention and existing gray relational degree DTW gray relational degree;

Fig. 6 is the comparison (no missing data) of the present invention and the entropy of existing gray relational degree DTW gray relational degree;

Fig. 7 is the comparison (missing data) of the purity of the present invention and traditional gray correlation degree;

Fig. 8 is the comparison (missing data) of the present invention and the entropy of traditional gray correlation degree;

Fig. 9 is the comparison (missing data) of the purity of the present invention and existing gray relational degree DTW gray relational degree;

Fig. 10 is the comparison (missing data) of the present invention and the entropy of existing gray relational degree DTW gray relational degree;

Detailed ways

The gray relational clustering method based on LDTW distance of the present invention will be further elaborated below in combination with specific embodiments and specific experimental data sets. A kind of gray correlation clustering method based on LDTW distance of the present invention, as shown in Figure 1, comprises the following steps:

S1. Process the original data set to obtain a preprocessed sequence;

S2. The maximum value of each dimension in the preprocessed sequence constitutes a reference sequence;

S3. Calculate the LDTW distance between the preprocessed sequence and the reference sequence and its curved path length λ;

S4. Calculating the gray relational degree between the preprocessed sequence based on the LDTW distance and the reference sequence;

S5. Determine the critical value ε according to the results of the gray relational degree, and divide the gray relational degree interval into a plurality of critical intervals according to the critical value ε. If the gray relational degrees of the two sequences fall in the same critical interval, the two Sequences are clustered into one class.

As an implementable manner, the acquisition of the preprocessed data of the data set may be implemented in the following manner:

Let the initial value image of each sequence be:

X _p '＝{x _p (1)/x _p (1),x _p (2)/x _p (1),...,x _p (n)/x _p (1)}(0≤p≤I, x _p (1)≠0)

Among them, I is the number of sequences, and n is the number of dimensions. The entire X _p 'sequence represents the value of the initial image of the p-th sequence in the 1,2,...,n dimension, q∈{1,2,...,n}, x _p (q) represents the p-th sequence The qth initial value image of the sequence.

Initial point zeroing image: Generally, after obtaining the initial value image, the difference between the values corresponding to the comparison sequence and the reference sequence is calculated sequentially, but the prerequisite is that the units of the two sequences are consistent.

X _p ' ⁰ ＝{|x _p ' ⁰ (1)-x ₀ ' ⁰ (1)|,|x _p ' ⁰ (2)-x ₀ ' ⁰ (2)|,…,|x _p ' ⁰ ( n)-x ₀ ' ⁰ (n)|}(1≤p≤I)

Among them, I is the number of sequences, and n is the number of dimensions; the entire sequence represents the value of the initial point zeroization image of the p-th sequence on dimensions 1, 2,..., n, q∈{1,2, ..,n}, x _p ' ⁰ (q) represents the qth initial zeroing image of the pth sequence; where, the initial value image and the initial zeroing image of the sequence are both preprocessing the data set.

Example 1

As shown in _{Table 1} , it is _a specific example of calculating the gray relational degree based on LDTW distance. The output value of the tertiary industry X ₃ data;

The initial values of the sequence of gross production value X ₀ , primary industry X ₁ , secondary industry X ₂ , and tertiary industry output value X ₃ correspond to:

X' ₀ = (1,1.0966,1.2379,1.4576,1.6691)

X' ₁ = (1,0.0452,1.1032,1.3548,1.4903)

_X'2 = (1,1.0444,1.2606,1.4929,1.7576);

X' ₃ = (1,1.1256,1.2915,1.4574,1.6368);

The initial point zeroing images of the sequence of gross production value X ₀ and primary industry X ₁ , secondary industry X ₂ , and tertiary industry output value X ₃ correspond to:

Table 1 China's 2001-2005 GDP and output value of various industries (unit: 100 billion yuan)

sequence 2001 2002 2003 2004 2005 X ₀ 109.7 120.3 135.8 159.9 183.1 _x1 15.5 16.2 17.1 twenty one 23.1 _x2 49.5 53.9 62.4 73.9 87 _x3 44.6 50.2 56.3 65 73

As an achievable way, the LDTW distance matrix between the sequences is obtained by using the distance matrix of the zeroing image of the starting point between the sequences, and the following method is used to realize:

Table 2 Inter-sequence distance matrix under the same length

Let DM(X ₀ ,X _i ) be the distance matrix of sequences X ₀ and X _i , where LDTW(X ₀ ,X _i ) is the distance between sequences X ₀ and X _i , where λ denotes the length of the curved path. The path length includes: when calculating the LDTW distance between the preprocessed sequence and the reference sequence, the LDTW distance imposes constraints on the length of the curved path; the current length of the curved path is considered as an additional factor; The cell is the length of the path, the step size = the length of the path – 1, and "s" represents the step size.

As an achievable way, the gray correlation degree model based on LDTW distance can be realized in the following ways according to the distance matrix between sequences:

γ(X ₀ ,X _i ) is the gray correlation value of sequence X ₀ and sequence X _i , where the value of i is 1, 2, 3. From the definition of the gray relational degree model based on the LDTW distance, it can be known that the gray relational degree value of the gray relational degree model based on the LDTW distance depends on the distance between the two sequences X ₀ and X _i , so the error of the existing gray relational degree calculation method is analyzed Reasonable calculation of the distance between two sequences will play an important role in the similarity effect between the sequences of the gray relational degree model based on LDTW distance.

Wherein, LDTW(X ₀ ,X _i ) is the distance between the sequence X ₀ and X _i .

As shown in Table 3, comparing the method of the present invention with other several traditional methods, it can be seen that Deng's correlation degree, relative correlation degree, DTW distance gray correlation degree and LDTW distance gray correlation degree all have a positive effect on the relationship between sequences. The degree of correlation has been relatively consistent, which is consistent with the conclusion of qualitative analysis (the tertiary industry has the highest degree of correlation, the second is the secondary industry, and the primary industry is the lowest). There is a clear error in absolute correlation. Therefore, when the sequence lengths are consistent, the LDTW-GIM correlation performance is reliable and the calculation results are valid.

Table 3 compares the results of different gray relational degrees under the same sequence length

Example 2

As shown in Table 4, in order to consider the performance of the gray relational degree model based on LDTW distance when the sequence data is missing (that is, the sequence length is inconsistent), the data in Table 1 are partially lost. The initial value of the sequence is like:

X' ₀ = (1,1.0966,1.2379,1.4576,1.6691)

X' ₁ = (1,1.0452,1.1032,1.3548,1.4903)

X' ₂ =(1,1.2606,1.4929,1.7576)

X' ₃ ＝(1,1.1256,1.4574,1.6368)

The initial zeroing image is:

Table 4 China's 2001-2005 GDP and output value of various industries (some missing, unit: 100 billion yuan)

sequence 2001 2002 2003 2004 2005 X ₀ 109.7 120.3 135.8 159.9 183.1 _x1 15.5 16.2 17.1 twenty one 23.1 _x2 49.5 -- 62.4 73.9 87 _x3 44.6 50.2 -- 65 73

As an achievable way, the distance matrix of the initial point zeroing image between the described utilization sequences is used to obtain the LDTW distance matrix between the sequences, which is realized in the following manner:

Table 5 Distance matrix of LDTW

Let DM(X ₀ ,X _i ) be the distance matrix of sequences X ₀ and X _i , where LDTW(X ₀ ,X _i ) is the distance between sequences X ₀ and X _i , where λ denotes the length of the curved path.

As an achievable way, the gray correlation degree model based on LDTW distance can be implemented in the following ways according to the distance matrix between sequences:

γ(X ₀ ,X ₁ )=0.8407; γ(X ₀ ,X ₂ )=0.8863; γ(X ₀ ,X ₃ )=0.9058

It can be seen from Table 6 that when the sequence lengths are inconsistent, artificial completion has a relatively large impact on the final analysis conclusion. Deng's correlation degree, absolute correlation degree, and relative correlation degree all have misjudgments, while the gray correlation degree of LDTW distance is consistent with the conclusion of qualitative analysis, indicating that the correlation degree has strong adaptability.

Table 6. Comparison of the correlation degree results of sequences of different correlation degrees with different lengths

Traditional calculation method of gray relational degree (references: Liu Sifeng, Yang Yingjie, Wu Lifeng. Gray system theory and its application [M]. Science Press, 2014.):

in, Indicates the minimum difference between two levels, Indicates the maximum difference between two levels; directly using the difference in absolute value to represent the distance between two sequences does not reflect the real distance between the two sequences, i represents the i-th dimension, k represents the k-th dimension, 1≤i≤m, 1≤k ≤n.

Existing calculation methods of gray relational degree (references: Dai J, Hu F, Liu X. Research on greyincidence measurement method based on dynamic time warping distance [J]. Journal of Gray System, 2015, 27(1): 117- 126.):

DTW(X ₀ ,X _i ) represents the DTW distance between sequence X ₀ and sequence X _i ; ξ is the resolution coefficient, and λ represents the path length;

Gray relational calculation method of the present invention:

in, Denotes the two-level minimum difference between the value of an element of sequence X ₀ and the value of an element in sequence X _i , Indicates the two-level maximum difference between the value of the element of the sequence X ₀ and the value of the element in the sequence _Xi , ξ is the resolution coefficient, and ξ∈[0,1], LDTW(X ₀ ,X _i ) represents X ₀ and X The dynamic time warping distance of _i under finite length, λ is the path length corresponding to LDTW(X ₀ ,X _i ), i∈{1,2,...,I}, I is the number of sequences, t ₀ Indicates the t _0th dimension, t _i indicates the t _i th dimension; 1<t ₀ ≤n, 1<t _i ≤m, n is the number of dimensions, and m is the number of sequences.

The present invention improves the formula (2) to obtain the formula (3). As a method to measure the similarity between two time series, DTW obtains the minimum distance by bending the time axis to match the sequences with inconsistent lengths. In addition, different time series may only have a displacement on the time axis, that is to say, in the case of restoring the displacement, the two time series are consistent. In these complicated cases, the distance (or similarity) between two time series cannot be effectively obtained using the traditional Euclidean distance. However, DTW has the disadvantage of causing pathological alignment. Figure 2 shows a typical pathological alignment produced by DTW, where we can observe several singular points (red triangle positions). A singularity is a data point within one time series that is linked to a large portion of another time series. Clearly, such an alignment is not "correct" and this alignment greatly affects the accuracy of the similarity measure. LDTW works by limiting the total number of links between two time series. Because the entire optimization process is done by letting DTW decide how many links to assign to each data point and where to place those links, rather than setting rigid limits, such as window constraints, the number of links is not enough to form a singularity. Therefore, it allows more flexibility and avoids the risk of misalignment, and provides a more accurate judgment of the similarity between sequences, which is convenient for further cluster analysis.

As an achievable way, the gray correlation degree model based on LDTW distance can be implemented in the following ways according to the LDTW distance between sequences and the length λ of the curved path:

A given sequence X _i =( _xi (1), _xi (2),..., _xi (n)) and X ₀ ={x ₀ (1),x ₀ (2),..., x ₀ (n)}, then the distance matrix between _Xi and X ₀ is:

Among them, dis( _xi (m), x ₀ (n))=| _xi (m)-x ₀ (n)|, dis( _xi (m), x ₀ (n)) is the nth dimension The distance between the component value x _i (m) in the i-th sequence and the n-th dimension component x ₀ (n) of the reference sequence;

The LDTW distance between the new preprocessed sequence X _i and the reference sequence X ₀ includes:

D(X _i (m), X ₀ (n), s) represents the LDTW distance between X ₀ and X _i , min represents the minimum value, D( _xi (m), x ₀ (n-1), s- 1) indicates the distance from x ₀ (n-1) to x _i (m); D( _xi (m-1), x ₀ (n), s-1) indicates the distance from x ₀ (n) to x _i (m) -1) distance; D(x _i (m-1), x ₀ (n-1), s-1) represents the distance from x ₀ (n-1) to x _i (m-1); i∈{ 1,2,...,I}, s represents the step size, I is the number of sequences; m and n are the number of dimensions, m≤n.

LDTW works by limiting the length of the curved path. Therefore, taking the curved path length as an additional factor, for a more intuitive description, the number of steps = path length – 1, and "s" is used to represent the number of steps.

in, Denotes the two-level minimum difference between the value of an element of sequence X ₀ and the value of an element in sequence X _i , Indicates the two-level maximum difference between the value of the element of the sequence X ₀ and the value of the element in the sequence _Xi , ξ is the resolution coefficient, and ξ∈[0,1], LDTW(X ₀ ,X _i ) represents X ₀ and X The dynamic time warping distance of _i under finite length, λ is the path length corresponding to LDTW(X ₀ ,X _i ), i∈{1,2,...,I}, I is the number of sequences; t ₀ Indicates the t _0th dimension, t _i indicates the t _i th dimension; 1<t ₀ ≤n, 1<t _i ≤m, m and n are the number of dimensions, m≤n.

Example 3

The gray relational degree model based on LDTW distance in the present invention can realize the clustering of certain biological related data sequences in bioinformatics, and better analyze the similarity of some biological sequences, such as finding the commonality between similar proteins. It is of great significance to deduce the biological functions of these proteins. Proteins with similar structures have similar functions, so we cluster proteins with similar functions into one group to help biologists study protein functions.

The biological clustering method of the gray correlation degree model of LDTW distance of the present invention includes clustering of yeast protein positioning sites and clustering of abalone age. Yeast attributes include mcg: McGeoch's signal sequence identification method; gvh: von Heijne's signal sequence identification method; alm: score of ALOM transmembrane region prediction program; mit: discriminant analysis score for amino acid content; erl: presence of "HDEL" sub string (considered as a signal retained in the ER lumen); pox: peroxisome targeting signal at the C-terminus; vac: discriminant analysis score for amino acid content; nuc: discriminant analysis score for nuclear localization signal . Clustering of the ages of abalones depends on cutting the shells from the cones, staining them, and counting the number of rings by microscopy, which is a tedious and time-consuming task. Abalone properties include gender, length, diameter, height, weight, stripped weight, visceral weight, shell weight, rings/integer;

According to the meaning of biological attributes, it is clustered according to some existing attribute information sequences of the data, including:

In order to check the effect of the present invention, the present invention is compared with the prior art in experiments below.

The comparative techniques involved in the comparative experiments include:

The gray relational degree based on LDTW distance is a biological clustering scheme based on the gray relational degree of LDTW distance in the present invention.

Deng's gray relational degree, absolute gray relational degree and relative gray relational degree are biological clustering schemes based on the traditional gray relational degree, by directly calculating the distance between points between corresponding sequences.

The gray relational degree based on DTW distance is based on the existing biological clustering scheme that improves the traditional gray relational degree, and the direct calculation of the distance between sequences is replaced by dynamic time warping distance.

Comparing and referring to the evaluation indicators of previous clustering effects, this paper selects the comparison of two indicators commonly used in the prior art, including entropy and purity: specifically including:

Entropy: For a cluster i, first calculate P _ij . P _ij refers to the probability that a member in cluster i belongs to class (class) j, Among them, m _i is the number of all members in cluster i, and m _ij is the number of members in cluster i belonging to cluster j. The entropy of each cluster can be expressed as where L is the number of classes. The entropy of the whole cluster division is Where K is the number of clusters, and m is the number of members involved in the entire cluster division.

Purity: Using the definition of P _ij in the above entropy, we define the purity of cluster i as P _i =max(P _ij ), and the purity of the entire cluster division is Where K is the number of clusters, and m is the number of members involved in the entire cluster division. Entropy represents the degree of information between classes, and purity represents the degree of aggregation. The lower the entropy and the higher the purity, the better the clustering effect

This experiment is based on the yeast data set in UCI, and the yeast attributes include mcg: signal sequence recognition method of McGeoch; gvh: signal sequence recognition method of von Heijne; alm: score of ALOM transmembrane region prediction program; mit: amino acid content Discriminant analysis score; erl: presence of "HDEL" substring (considered to be a signal retained in the lumen of the endoplasmic reticulum); pox: peroxisome targeting signal at the C-terminus; vac: discriminant analysis of amino acid content score; nuc: discriminant analysis score for nuclear localization signals. It is clustered, and finally the clustering effect is judged according to the location of the protein, as shown in Table 7.

Table 7 The attribute sequence of yeast

Example 4

In order to further verify the clustering effect of the present invention, the present invention also uses the abalone data set in UCI to cluster the age of the abalone, the age of the abalone depends on the number of rings cut from the cone, stained, and counted through the microscope- This is a boring and time-consuming task. The properties of abalone include gender, length, diameter, height, weight, stripped weight, visceral weight, shell weight, ring/integer, as shown in Table 8,

Table 8 Attribute sequence of abalone

Through VS2012 and database sql sever2012, the comparison between the present invention and the prior art is obtained, and the comparison between the clustering results of the two data sets (without missing data) and the purity of the traditional gray relational degree is shown in Figure 3, wherein, there is no missing data Indicates that in the preprocessed sequence X _i ={ _xi (1), _xi (2),..., _xi (n)}, the value of each dimension has data, that is, x _i ( j ₎ all correspond _to a data value, _{correspondingly} , the missing data represents one _or There are no data values in multiple dimensions; no missing data and missing data in the figure below are explained above, and will not be repeated below.

The entropy comparison with the traditional gray relational degree is shown in Figure 4, and the comparison with the purity of the DTW gray relational degree is shown in Figure 5. The comparison with the purity of DTW gray relational degree is shown in Figure 6. In Figure 3 and Figure 4, the abscissa GID indicates several gray correlation degrees for comparison, the ordinate indicates the value of purity and entropy, Yeast indicates yeast, and Abalone indicates abalone. The same is true for Yeast and Abalone in the figure below, so I will not repeat them; Figure 5 And in Figure 6, the abscissa represents the value of purity and entropy, and the ordinate represents the data set. Among them, the average purity increased by 14.81%, and the average entropy decreased by 42.73%. The purity of the gray relational degree based on the LDTW distance in the two data sets is the highest, and the entropy is also the lowest, indicating that the clustering effect is better. LDTW itself is an improvement on DTW, of course, the distance calculation between sequences is consistent. In order to verify the performance of the gray relational degree based on LDTW distance, the loss rate of 0.1 was carried out on the two data sets, and the clustering results in the case of missing data information were carried out. The clustering results of the two data sets (missing data) were compared with the traditional The comparison of the purity of the gray relational degree is shown in Figure 7, the entropy comparison with the traditional gray relational degree is shown in Figure 8, and the comparison with the purity of the DTW gray relational degree is shown in Figure 9. The comparison with the purity of DTW gray relational degree is shown in Figure 10. In Figure 7 and Figure 8, the abscissa represents several gray correlation degrees for comparison, the ordinate represents the value of purity and entropy, the abscissa in Figure 9 and Figure 10 represents the value of purity and entropy, and the ordinate represents the data set. Among them, the average purity increased by 19.14%, and the average entropy decreased by 62.19%. When the data is incomplete, the purity of the absolute gray relational degree, relative gray relational degree and Deng's gray relational degree decreases rapidly, and the entropy also increases significantly, which has a significant impact on the final clustering effect. LDTW gray relational degree will not complement the missing data, avoid the addition of interference information, and can effectively solve the situation of inconsistent sequence lengths, so that the final clustering effect is basically not affected. The purity of the gray relational degree based on the LDTW distance is still the highest, and the entropy is also the lowest, indicating that the clustering effect is better.

In data mining, the gray correlation method based on LDTW distance provided by the present invention can calculate the similarity of biological sequences more accurately and provide more accurate clustering results, which can help us study the properties and functions of genes and proteins, and provide a basis for exploring biological Mystery helps.

The above examples have further described the purpose, technical solutions and advantages of the present invention in detail. It should be understood that the above examples are only preferred implementations of the present invention and are not intended to limit the present invention. Any modification, equivalent replacement, improvement, etc. made to the present invention within the spirit and principles of the present invention shall be included within the protection scope of the present invention.

Claims (8)

1. A grey relational clustering method based on LDTW distance, characterized in that the method comprises:

s1, processing the original data set to obtain a preprocessed sequence;

s2, forming a reference sequence by the maximum value of each dimensionality in the preprocessed sequence;

s3, calculating the LDTW distance between the preprocessed sequence and the reference sequence and the length lambda of the bending path of the LDTW distance;

s4, calculating the grey correlation degree between the preprocessed sequence based on the LDTW distance and the reference sequence;

and S5, determining a critical value epsilon according to the result of the grey correlation degree, dividing the grey correlation degree interval into a plurality of critical intervals according to the critical value epsilon, and if the grey correlation degrees of the two sequences fall into the same critical interval, clustering the two sequences into one class.

2. The LDTW distance-based gray-associated clustering method of claim 1, wherein the processing the raw data set to obtain a pre-processed sequence comprises: preprocessing the original sequence by utilizing the original sequence to convert the original sequence into dimensionless data, wherein the dimensionless data is a preprocessed sequence; the method specifically comprises the following steps:

original sequence: x'_i＝(x′_i(1),x′_i(2),...,x′_i(n))；

The sequence after pretreatment: x_i＝{x_i(1),x_i(2),...,x_i(n)}；

Wherein, X'_iDenotes the ith original sequence, x'_i(j) A data value representing a jth dimension of an ith original sequence; x_iDenotes the ith pre-processed sequence, x_i(j) A value representing a j dimension of an ith preprocessed sequence;

wherein,x′_max(j) represents the maximum value of the j dimension in the original sequence, x'_min(j) Representing the minimum value of the j dimension in the original sequence, I belongs to {1, 2.., I }; j belongs to {1, 2., n }, wherein I is the number of sequences and n is the number of dimensions.

3. The LDTW distance-based gray associative clustering method according to claim 1, wherein the constructing the maximum value of each dimension in the preprocessed sequence as the reference sequence comprises:

wherein,which is indicative of a reference sequence, a value representing the jth dimension of the reference sequence; x is the number of_max(j) Representing the maximum value of the j dimension in the preprocessed sequence; j is in the form of {1, 2.,. n }, and n is the number of dimensions.

4. The LDTW distance-based gray association clustering method of claim 1, wherein the calculating the LDTW distance of the preprocessed sequence from the reference sequence comprises:

removing dimensionality of missing data of the preprocessed sequence to obtain a new preprocessed sequence: x_i＝(x_i(1),x_i(2),...,x_i(m)); calculating the LDTW distance between the new preprocessed sequence and the reference sequence; the method specifically comprises the following steps:

the reference sequence is: x₀＝{x₀(1),x₀(2),...,x₀(n)}；

Novel preprocessed sequence X_iWith reference sequence X₀The distance matrix of (a) includes:

wherein, dis (x)_i(m),x₀(n))＝|x_i(m)-x₀(n)|，dis(x_i(m),x₀(n)) is x_i(m) and x₀(n) the distance between; x is the number of_i(m) a value representing the m-dimension of the ith preprocessed sequence; x is the number of₀(n) represents a value of the nth dimension of the reference sequence;

novel pretreatmentLast sequence X_iWith reference sequence X₀The LDTW distance includes:

D(X_i(m),X₀(n), s) represents X₀And X_iLDTW distance of (D), min represents taking the minimum value, D (x)_i(m),x₀(n-1), s-1) represents x₀(n-1) to x_i(m) a distance; d (x)_i(m-1),x₀(n), s-1) represents x₀(n) to x_i(m-1) distance; d (x)_i(m-1),x₀(n-1), s-1) represents x₀(n-1) to x_i(m-1) distance; i belongs to {1, 2.,. I }, s represents the step length, and I is the number of sequences; m and n are dimension numbers, and m is less than or equal to n.

5. The LDTW distance-based gray associative clustering method of claim 1, wherein calculating the curved path length λ of the preprocessed sequence and the reference sequence comprises:

will in calculating the LDTW distance of the preprocessed sequence and the reference sequence, the LDTW distance imposes a constraint on the curved path length; considering the current length of the curved path as an additional factor; the cells of the matrix that are traversed are the path lengths λ.

6. The LDTW distance-based gray associative clustering method of claim 5, wherein the path length λ further comprises:

λ＝s+1

s denotes the step size, i.e. the path length is equal to the step size plus one.

7. The LDTW distance-based gray association clustering method according to claim 1, wherein the calculating the gray association degree between the LDTW distance-based preprocessed sequence and the reference sequence comprises:

dimensionality removal of missing data of the preprocessed sequenceTo get a new pre-processed sequence: x_i＝(x_i(1),x_i(2),...,x_i(m)); calculating the grey correlation degree of the new preprocessed sequence and the reference sequence; the method specifically comprises the following steps:

the reference sequence includes: x₀＝{x₀(1),x₀(2),...,x₀(n)}；

The new pre-processed sequence includes: x_i＝(x_i(1),x_i(2),...,x_i(m))；

The grey correlation between the reference sequence and the new pre-processed sequence is defined as follows:

wherein,represents sequence X₀Value and sequence of elements of (1) X_iThe two-level minimum difference of the values of the elements in (b),represents sequence X₀Value and sequence of elements of (1) X_ithe maximum difference of two levels of the values of the elements in (1), ξ is a resolution coefficient, and ξ belongs to [0,1 ]]，LDTW(X₀,X_i) Represents X₀And X_iIs the dynamic time warping distance of limited length, λ is LDTW (X)₀,X_i) The corresponding path length I belongs to {1, 2.., I }, wherein I is the number of sequences; t is t₀Denotes the t-th₀Dimension of, t_iDenotes the t-th_iA dimension; 1<t₀≤n，1<t_iM is less than or equal to m, m and n are dimension numbers, and m is less than or equal to n.

8. The LDTW distance-based gray correlation clustering method as claimed in claim 1, wherein the threshold value ε is determined according to the gray correlation result, the threshold value ε is divided into a plurality of threshold intervals, and if two sequences of gray are presentIf the correlation degree falls within the same critical interval, the two sequences are grouped into one type including: calculating grey correlation values of the two sequences, and if the grey correlation values of the two sequences fall in the same critical interval, clustering the two sequences into one class; the method specifically comprises the following steps: pretreated sequence X_iLet us assume that any two sequences are represented as:

X_p＝{x_p(1),x_p(2),...,x_p(n)}；

X_q＝{x_q(1),x_q(2),...,x_q(n)}；

wherein, X_pDenotes the p-th sequence, X_qRepresents the q sequence; x is the number of_p(n) nth data representing a pth sequence; x is the number of_q(n) nth data representing a qth sequence; p belongs to {1, 2., I }, and q belongs to {1, 2., I }; using a threshold value of ε to be [0,1 ]]Divided into a plurality of critical intervals, i.e. [0, [ epsilon ]]，[ε,2ε]，...，[1-ε,1](ii) a When two sequences X_pAnd X_qWhen the gray correlation values of (1) are in the same interval, the two sequences X are combined_pAnd X_qThe polymers are grouped into one group.