JP5652332B2 - Data structure comparison program and data structure comparison device - Google Patents

Description

  The present invention relates to a data structure comparison program and a data structure comparison apparatus.

  As a conventional method of comparing data structures, for example, a tree structure that frequently appears using a pattern extraction technique is extracted from a plurality of data having a tree structure as a sample data structure, and the similarity of the extracted sample data structures is calculated. Some are calculated (for example, see Non-Patent Documents 1 and 2).

  Non-Patent Document 1 compares the arrangement of leaf nodes of each tree structure when comparing between tree structures composed of an internal node that branches from a root node as a vertex and a leaf node at the bottom. Disclosed is a method for calculating a minimum number of procedures (hereinafter referred to as “edit distance”) such as insertion, deletion, and replacement of data required for transforming from one leaf node sequence to another leaf node sequence. . Using this edit distance, tree structures having an edit distance smaller than a predetermined value are set as similar tree structures.

  Non-Patent Document 2 includes not only the leaf nodes of a tree structure but also the insertion and deletion of data required for transformation from one tree structure to the other, including root nodes and internal nodes between tree structures. , A method of calculating the minimum number of procedures such as replacement (hereinafter referred to as “Tree Edit distance”) is disclosed. This tree edit distance calculation method increases the amount of calculation compared to the method of Non-Patent Document 1 described above, but calculates a more reliable value as the similarity between tree structures in order to consider other than leaf nodes.

Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN0-521-58519-8. Philip, Bille.A survey on tree edit distance and related problems.Journal Theoretical Computer Science, Volume 337 Issue 1-3, 9 June 2005.Elsevier Science Publishers Ltd. Essex, UK

  An object of the present invention is to provide a data structure comparison program and a data structure comparison apparatus that reduce the amount of calculation compared to a case where this configuration is not adopted.

  In order to achieve the above object, one aspect of the present invention provides the following data structure comparison program and data structure comparison apparatus.

[1]
A plurality of comparison objects including, as a structural element, an object, a first type of data associated as belonging to the object, and a second type of data associated as belonging to the first type of data Acquisition means for acquiring a data structure that appears at a predetermined frequency from the data as a sample data structure;
The second type of data in which the first type of data is common among the sample data structures when comparing the second type of data of the plurality of sample data structures acquired by the acquisition unit First similarity calculation means for calculating a first similarity between
Second similarity calculation for calculating a second similarity between the data structures of the samples based on the first similarity calculated by the first similarity calculation unit for each of the second type of data Means,
A data structure comparison program that functions as an extraction unit that extracts the data structure of the sample showing the similarity equal to or greater than a predetermined value as the second similarity.

[2] Date and time data acquisition means for acquiring date and time data in units of time from the plurality of comparison target data acquired from the sample data structure when the acquisition means acquires the sample data structure;
The first similarity calculating unit compares the second type of data of a plurality of sample data structures with the second type of data having the first type of data common between the sample data structures. The date and time data acquired by the date and time data acquisition means is added to the type of data by a predetermined method, and the first similarity between the sample data structures to which the date and time data is added is calculated. 1] The data structure comparison program according to [1].

[3] The data structure comparison program according to [1] or [2], wherein the first similarity calculation unit calculates the similarity by weighting according to the content of the second type of data.

[4] A plurality of objects including a target, a first type of data associated as belonging to the target, and a second type of data associated as belonging to the first type of data as structural elements. Acquisition means for acquiring a data structure of a sample having a data structure that appears at a predetermined frequency from the comparison target data;
The second type of data in which the first type of data is common among the sample data structures when comparing the second type of data of the plurality of sample data structures acquired by the acquisition unit First similarity calculation means for calculating a first similarity between
Second similarity calculation for calculating a second similarity between the data structures of the samples based on the first similarity calculated by the first similarity calculation unit for each of the second type of data Means,
A data structure comparison apparatus comprising: extraction means for extracting the data structure of the sample showing the similarity equal to or greater than a predetermined value as the second similarity.

  According to the invention which concerns on Claim 1 or 4, the amount of calculations can be reduced compared with the case where this structure is not employ | adopted.

  According to the invention which concerns on Claim 2, the 1st similarity including date data can be calculated.

  According to the invention which concerns on Claim 3, weighting can be performed according to the content of 2nd type data.

FIG. 1 is a diagram showing an example of the configuration of a data structure comparison apparatus according to an embodiment of the present invention. FIG. 2 is a schematic diagram illustrating an example of a configuration of a DPC data pattern. FIG. 3 is a schematic diagram illustrating an example of a configuration of calculation coefficient information. FIG. 4 is a schematic diagram illustrating an example of the configuration of the weighting coefficient information. FIGS. 5A and 5B show a configuration example of DPC data support that is a pattern acquisition source of the pattern acquisition unit 100. FIGS. 6A and 6B are schematic diagrams illustrating an example of a pattern configuration of DPC data to which additional date / time data is added. FIG. 7 is a diagram for explaining a partial pattern used for calculating the first similarity. FIG. 8 is a diagram for explaining generation of a list used for calculating the first similarity. FIG. 9 is a diagram for explaining a first similarity calculation method. FIG. 10 is a diagram for explaining a second similarity calculation method. 11A to 11C are schematic diagrams for explaining an example of the data structure extraction operation.

(Configuration of data structure comparison device)
FIG. 1 is a diagram showing an example of the configuration of a data structure comparison apparatus according to an embodiment of the present invention.

  The data structure comparison apparatus 1 includes a CPU and the like, and controls each unit and executes various programs, and a storage unit configured by a storage medium such as an HDD (Hard Disk Drive) or a flash memory and stores information. 11, for example, used for analyzing patient clinical information and electronic data of medical practice.

  The control unit 10 executes a data structure comparison program 110, which will be described later, to thereby obtain a pattern acquisition unit 100, a date / time data addition unit 101, a first similarity calculation unit 102, a second similarity calculation unit 103, and a data structure extraction. It functions as the means 104 or the like.

  The pattern acquisition unit 100 uses a patient name as a root node as a target from a plurality of comparison target data (hereinafter referred to as “support”) included in DPC data 111 described later from the storage unit 11 as electronic data to be analyzed. Get multiple sample tree structures. Here, the sample tree structure (hereinafter referred to as “pattern”) is extracted as a common tree structure that appears in a plurality of data having a tree structure at a predetermined frequency by using a pattern extraction technique. That means.

  Note that the pattern acquisition unit 100 acquires, as a pattern, a common E file and F file described later among a plurality of supports by using a well-known pattern extraction technique. As a well-known pattern extraction technique, for example, Prefix Span, BIDE, CloSpan or the like of sequential pattern mining or sub-tree mining can be used.

  The date / time data adding unit 101 extracts date / time data in units of time from a plurality of supports that are the basis of the pattern acquired by the pattern acquiring unit 100 and adds them to the pattern. The time may be any of date, hour, minute, second, etc.

  The first similarity calculation unit 102 lists F files that are common to E files, which will be described later, among the F files that are leaf nodes among the patterns to be compared, and further lists the date and time data in the patterns. In addition, the edit distance is calculated for each E file as the similarity of the list (hereinafter referred to as “first similarity”).

  Based on the first similarity for each E file calculated by the first similarity calculation unit 102, the second similarity calculation unit 103 calculates a similarity between patterns to be compared (hereinafter, “second similarity”). The edit distance is calculated.

  The data structure extraction unit 104 extracts a set of a plurality of patterns whose second similarity calculated by the second similarity calculation unit 103 is equal to or less than a predetermined value as one classification.

  The storage unit 11 stores a data structure comparison program 110, DPC data 111, calculation coefficient information 112, weighting coefficient information 113, and the like that cause the control unit 10 to operate as the above-described units.

  The DPC data 111 is an electronic data set of patient clinical information and medical practice in a nationally unified format that can be analyzed. Patient clinical information includes, for example, patient basic information, disease name, technique, various score / stage classifications, etc., and medical practice information includes medical practice, pharmaceuticals, medical materials, implementation date, frequency / quantity, clinical department, ward And insurance type.

  The DPC data 111 includes data called format 1, E file, and F file as basic data. Form 1 includes patient clinical information, names of wounds, surgical procedures, adjuvant treatment, and the like. The E file is information such as the implementation date, number of times, clinical department, ward, order doctor, and the like. The F file is a detailed content of the E file, and is information such as an action, a medicine, a material, and a quantity.

  In the present embodiment, a tree structure including a patient as a root node, date / time data belonging to the patient and an E file as an internal node, and an F file belonging to the E file as a leaf node is supported. A support data structure that appears at a frequency higher than the specified frequency is acquired as a pattern, a similarity is calculated between the acquired patterns, and a set of a plurality of patterns is extracted based on the calculated similarity.

  FIG. 2 is a schematic diagram illustrating an example of a configuration of a DPC data pattern.

  The patterns 2a and 2b acquired from the DPC data 111 include date / time data 22 belonging to a patient, an E file 21 belonging to the date / time data 22, and an F file belonging to the E file 21, and constitute a tree structure.

  FIG. 3 is a schematic diagram illustrating an example of a configuration of calculation coefficient information.

  The calculation coefficient information 112 defines a coefficient to be multiplied by the F file or the date / time data when the first similarity calculation unit 102 calculates the edit distance, with the F file, the period, and the day unit as matrix items. Since the F file and the period, and the F file and the day unit are not objects to be compared, the coefficient is “∞”.

  FIG. 4 is a schematic diagram illustrating an example of the configuration of the weighting coefficient information.

  The weighting coefficient information 113 includes an F file content field and a weighting coefficient field. When the first similarity calculation unit 102 calculates the edit distance, the weighting coefficient information 113 is multiplied by the F file or date / time data according to the content of the F file. Define the coefficients.

(Operation of data structure comparison device)
Hereinafter, the operation example of the data structure comparison apparatus will be described by dividing into (1) basic operation, (2) similarity calculation operation, and (3) data structure extraction operation, with reference to each drawing.

(1) Basic Operation First, the pattern acquisition unit 100 acquires a plurality of patterns to be extracted from the DPC data 111 of the storage unit 11. Hereinafter, in order to simplify the description, a case where the two patterns 2a and 2b shown in FIG. 2 are acquired will be described.

  First, the pattern 2b will be described as an example to show the pattern acquisition method.

  FIGS. 5A and 5B show a configuration example of support of the DPC data 111 that is a pattern acquisition source of the pattern acquisition unit 100.

The pattern acquisition unit 100 acquires a pattern 2b from a plurality of supports 200b ₁ , 200b ₂ ... Shown in FIG.

In the conventional technique using the edit distance of the F file, since information other than the F file is not used, the date and time data 22 may be different in each of the supports 200b ₁ , 200b ₂ ... As shown in FIG. The pattern B is acquired as “day unit” at a place where the contents of the date and time data 22 are different.

However, in the present embodiment, the date / time data 22 is also taken into consideration, and the date / time data adding unit 101 includes a plurality of supports 200b ₁ , 200b ₂ ... (FIG. 5A )) To extract the date / time data 22 in units of time, and add the additional date / time data 210b ₁ , 210b ₂ ... As shown in FIG. .

  6A and 6B are schematic diagrams illustrating an example of a configuration of a pattern to which additional date / time data is added.

Next, the date / time data adding unit 101 adds the added date / time to the pattern 2b as shown in FIG. 6A based on the added date / time data 210b ₁ , 210b ₂ ... Added to the plurality of supports 200b ₁ , 200b ₂ . Data 22a is added.

Next, the date / time data adding means 101 searches the date / time data of a plurality of supports 200b ₁ , 200b ₂ ... Within the date / time range of the added date / time data 22b, and the date / time data 22a shown in FIG. As shown in (b), for example, the target date / time data is replaced with the additional date / time data 22b which is the minimum value. As described above, in this embodiment, the similarity is calculated by adding date and time data that has not been used in the conventional calculation of similarity as an element. The additional date / time data 22a is not limited to a minimum value, and may be set to a value that includes all date / time data in a predetermined unit.

(2) Similarity Calculation Operation FIG. 7 is a diagram for explaining a partial pattern used for calculating the first similarity.

Next, as shown in FIG. 7, the first similarity calculation means 102, the partial pattern _2a 1 _{to 2A region} 4 based on the predetermined data classified patterns 2a and 2b on the E file _21, 2b 1 ~2b ₄ Divide into

Next, the first similarity calculation unit 102 calculates that the partial patterns 2a ₁ and 2b ₁ that coincide with the division “60”, 2a ₂ and 2b ₂ that coincide with the division “50”, and the division “54”. The first similarity between the matching 2a ₃ and 2b ₃ and the matching 2a ₄ and 2b ₄ with the section “70” is calculated. Hereinafter, the calculation method will be described.

  FIG. 8 is a diagram for explaining generation of a list used for calculating the first similarity.

For example, the first similarity calculation unit 102 generates lists 3a ₁ and 3b ₁ including the date and time data 22 and the F file 20 as character strings from the partial patterns 2a ₁ and 2b ₁ that match in the category “60”, respectively. . At this time, the first similarity calculation unit 102 adds the date / time data 22 to which the F file 20 belongs to the list in the order of the front of the F file 20. The order in which the date / time data 22 is added is not limited to this, and may be added after the F file 20.

  FIG. 9 is a diagram for explaining a first similarity calculation method.

Next, the first similarity calculation unit 102 calculates the edit distances of the lists 3a ₁ and 3b ₁ . Specifically, as shown in FIG. 9, the similarity for each item included in the lists 3a ₁ and 3b ₁ is digitized into a matrix, and moved so as to take the minimum value from the upper left element to the lower right element. .

  Here, moving to the lower right for the same element in the matrix is not editing for the list, moving to the lower for different elements is to move to the right for different elements when deleting elements in the list. Corresponds to the case of inserting list elements.

  The minimum value obtained as a result of the above operation is the editing distance. In the example shown by the broken line in FIG. 9, the element “next day” and the element “two days later” are exchanged, the element “TP” is inserted, the element “GPT” is deleted, the element “ALP” is inserted, and the element “ALb” is inserted. You are performing an insert operation.

  In addition, the calculation coefficient information 112 is used as a coefficient for the above operation, thereby excluding operations other than the editing operation between date data and the editing operation between F files, and the restriction on the exchange of F files is increased. The F file exchange coefficient may be 1.

  Moreover, you may use the weighting coefficient information 113 with respect to the said operation. That is, the operation of exchanging the element “next day” and the element “two days later” is multiplied by 0.7 as a coefficient because the F file content field corresponds to “one day difference” in FIG. Similarly, the operation for inserting the element “TP” is multiplied by 1 as a coefficient, the operation for deleting the element “GPT” is multiplied by 1 as a coefficient, and the operation for inserting the element “ALP” is 0.5. The edit distance may be calculated by multiplying the operation for inserting the element “ALb” by 2 as a coefficient.

The above edit distance is calculated for all partial patterns 2a ₁ and 2b ₁ , 2a ₂ and 2b ₂ , 2a ₃ and 2b ₃ , 2a ₄ and 2b ₄ , and the first similarity between the patterns 2a and 2b is obtained. obtain.

  FIG. 10 is a diagram for explaining a second similarity calculation method.

  In the matrix in which all the F files that are the targets of the patterns 2a and 2b are items and classified for each E file, the first similarity of each partial pattern obtained is shown in FIG. Arranged diagonally.

  Next, the second similarity calculation unit 103 calculates the second similarity in the matrix shown in FIG. Specifically, as described with reference to FIG. 9, the first similarity may be simply added from the upper left to the lower right. Thus, since the first similarity between the E files 21 “50” and “54”, “60” and “70”, etc. is not calculated, the editing distance between F files with different E files is not calculated. Compared to the conventional method that calculates the edit distance between F files, the amount of calculation is reduced.

(3) Data Structure Extraction Operation FIGS. 11A to 11C are schematic diagrams for explaining an example of the data structure extraction operation.

  When the second similarity calculation unit 103 calculates the second similarity between the patterns, a matrix indicating the relationship of the second similarity between the patterns is generated as shown in FIG. Is done.

  The data structure extraction unit 104 determines that the similarity of the data structure of each pattern is high in order from the smallest second similarity value in the matrix shown in FIG. As shown, a plurality of patterns having high data structure similarity are extracted as one classification.

  Here, for example, if the second threshold value is less than 3, the classification threshold is divided into the patterns 2a to 2h and the patterns 2i and 2j as shown in FIG. Then, as shown in FIG. 11C, the data structure extraction unit 104 extracts the classification of the patterns 2a to 2h as the cluster 1, and the classification of the patterns 2i and 2j as the cluster 2.

[Other embodiments]
The present invention is not limited to the above embodiment, and various modifications can be made without departing from the spirit of the present invention.

  In addition, the data structure comparison program 110 used in the above embodiment may be read from a storage medium such as a CD-ROM into a storage unit in the apparatus, or from a server apparatus or the like connected to a network such as the Internet. You may download to the memory | storage part. In addition, a part or all of the DPC pattern acquisition unit 100, the date / time data addition unit 101, the first similarity calculation unit 102, the second similarity calculation unit 103, and the data structure extraction unit 104 used in the above embodiment. May be realized by hardware such as ASIC.

1 Data structure comparison device 2a-2h Pattern 2a ₁ -2a ₄ Partial pattern 3a ₁ , 3b ₁ List 10 Control unit 11 Storage unit 20 F file 21 E file 22 Date / time data 22a, 22b Additional date / time data 100 Pattern acquisition means 101 Date / time data Additional means 102 First similarity calculation means 103 Second similarity calculation means 104 Data structure extraction means 110 Data structure comparison program 111 DPC data 112 Calculation coefficient information 113 Weighting coefficient information 200b ₁ , 200b ₂ Support 210b ₁ , 210b ₂ Additional date and time data

Claims (4)

Computer
A plurality of comparison objects including, as a structural element, an object, a first type of data associated as belonging to the object, and a second type of data associated as belonging to the first type of data Acquisition means for acquiring a data structure that appears at a predetermined frequency from the data as a sample data structure;
The second type of data in which the first type of data is common among the sample data structures when comparing the second type of data of the plurality of sample data structures acquired by the acquisition unit First similarity calculation means for calculating a first similarity between
Second similarity calculation for calculating a second similarity between the data structures of the samples based on the first similarity calculated by the first similarity calculation unit for each of the second type of data Means,
A data structure comparison program that functions as an extraction unit that extracts the data structure of the sample showing the similarity equal to or greater than a predetermined value as the second similarity. Date and time data acquisition means for acquiring date and time data in units of time from the plurality of comparison target data acquired from the sample data structure when the acquisition means acquires the data structure of the sample;
The first similarity calculating unit compares the second type of data of a plurality of sample data structures with the second type of data having the first type of data common between the sample data structures. The date and time data acquired by the date and time data acquisition means is added to a type of data by a predetermined method, and a first similarity between sample data structures to which the date and time data is added is calculated. 1. The data structure comparison program according to 1.   The data structure comparison program according to claim 1, wherein the first similarity calculation unit calculates the similarity by weighting according to the content of the second type of data. A plurality of comparison objects including, as a structural element, an object, a first type of data associated as belonging to the object, and a second type of data associated as belonging to the first type of data Acquisition means for acquiring a data structure of a sample having a data structure that appears at a predetermined frequency from the data of
The second type of data in which the first type of data is common among the sample data structures when comparing the second type of data of the plurality of sample data structures acquired by the acquisition unit First similarity calculation means for calculating a first similarity between
Second similarity calculation for calculating a second similarity between the data structures of the samples based on the first similarity calculated by the first similarity calculation unit for each of the second type of data Means,
A data structure comparison apparatus comprising: extraction means for extracting the data structure of the sample showing the similarity equal to or greater than a predetermined value as the second similarity.

Images