CN104820775A - Discovery method of core drug of traditional Chinese medicine prescription - Google Patents

Abstract

A method for discovering the core drugs of traditional Chinese medicine prescriptions, which consists of two parts: an improved clustering algorithm and a weighted TF-IDF algorithm. The clustering algorithm includes three parts: preprocessing of prescription data, selection of clustering distance functions, and clustering mining algorithm. The prediction theory of prescription data processes the prescription data into a model suitable for the clustering algorithm; the selection of clustering distance is used to select a reasonable clustering distance function; the distance mining algorithm is used to cluster similar prescriptions into a cluster; the weighted TF- The IDF algorithm is used to calculate the weight of the drug. The invented weight calculation formula combines three parts: the clustering result, the order importance of the drug, and the TF-IDF algorithm; the algorithm has high accuracy.

Description

A method for discovering core drugs of traditional Chinese medicine prescriptions

Technical field:

The invention mainly relates to the discovery of core medicines of traditional Chinese medicine prescriptions, and is used for excavating the core medicines in prescriptions for treating certain diseases.

Background technique:

Drugs are the basic components of prescriptions. As we all know, "the emperor, ministers, assistants and envoys" is the basic principle of formulating prescriptions in traditional Chinese medicine. According to the functions they play in the prescription, the medicines in the prescription are divided into monarch medicine, minister medicine, adjuvant medicine and envoy medicine, which are referred to as "junchen, adjuvant and envoy". Various medicines play different roles in prescriptions. Finding the core drug that plays a major role in the treatment of a certain disease in a traditional Chinese medicine prescription can reveal the medication rules in the compatibility of traditional Chinese medicine prescriptions. It is of great significance for young Chinese medicine practitioners to learn the experience of famous and old Chinese medicine practitioners, master the essence of Chinese medicine theory, and further study Chinese medicine theory. important role.

The existing prescription database has nearly 100,000 first prescriptions, involving more than 10,000 medicines. Prescriptions for a specific disease often involve hundreds of prescriptions and drugs. The traditional manual method to extract the core drugs of these prescriptions can no longer meet the modern needs, and computer-assisted methods are urgently needed.

At present, there are mainly frequency-based methods and PageRank-based methods for mining the core drugs of traditional Chinese medicine prescriptions. The frequency-based method is easily affected by the frequency of drug occurrence, and the mining results are not accurate enough. The method based on PageRank also has the characteristics that the ranking is not reasonable enough, and the algorithm is relatively difficult to understand, which cannot meet the needs well.

Invention content:

The technical problem to be solved in the present invention is to provide a method for the core drug of traditional Chinese medicine prescriptions, especially the method for extracting the core drugs of traditional Chinese medicine prescriptions based on improved K-Means clustering and weighted TF-IDF, which is mainly aimed at the current existing methods that are easily affected by drugs. A common, accurate, effective, and reasonable mining method for core drugs of traditional Chinese medicine prescriptions is proposed due to problems such as frequency impact, inaccurate mining results, and complex algorithms.

The technical scheme adopted by the present invention to solve the above problems is: a method for discovering the core drug of a traditional Chinese medicine prescription, that is, a method for extracting the core drug of a traditional Chinese medicine prescription based on improved K-Means clustering and weighted TF-IDF. The algorithm and the weighted TF-IDF algorithm are composed of two parts. The clustering algorithm includes three parts: the preprocessing of the prescription data, the selection of the clustering distance function and the clustering mining algorithm. model; the selection of clustering distance is used to select a reasonable clustering distance function; the distance mining algorithm is used to cluster similar prescriptions into a cluster;

The weighted TF-IDF algorithm is used to calculate the weight of drugs, and the invented weight calculation formula combines clustering results, drug order importance, and TF-IDF algorithm in three parts;

The preprocessing of the prescription data uses a vector space model. Each prescription is abstracted into a vector, and the medicine in the prescription is expressed as a certain dimension of the vector. If the prescription contains a certain drug, its corresponding dimension is 1, otherwise it is 0;

The selection of the described clustering distance function adopts the cosine distance function, and its distance is: It can reasonably measure the similarity of two prescriptions; here αi and βi are the prescription vectors respectively;

Described cluster mining algorithm, what it adopts is the improved K-Means algorithm based on node partial distribution; Algorithm pre-sets a threshold α, when assigning nodes to central points, for the distance to all central points all exceeds The node of α is temporarily not assigned to any cluster represented by the central node; so there may be some unassigned nodes at the end of a round of assignment. In the next round of allocation, some seed nodes are randomly selected from these nodes as the center point; in this way, through continuous iteration, each node in the final data set will be assigned to the appropriate classification;

The importance of the drug sequence refers to the importance of a certain drug in the composition of the prescription; it is defined as: Here h _i is the i- _{th drug in the prescription, and I(hi) is the order importance of drug h i ;} the total importance of drug h in all prescriptions is defined as:

The TF-IDF algorithm refers to the word frequency-inverse document frequency algorithm in informatics; the weight of a word is defined as: Here n _{i, j} is the word frequency, which means the number of occurrences of word t _i in file d _j . |D| indicates the total number of documents in the corpus, and |{j:t _i ∈ d _j }| indicates the number of documents containing word t _i ;

Calculate the weight W(h,x) of drug h according to the following formula, which is used to calculate the weight index of drug h in treating a certain disease x, defined as: $w(h,x)=\left({\mathrm{\Σ}}_{c_i\∈\mathrm{set}\left(x\right)}I(h\∈c_i)\right)\×\log \left(\frac{\left|\right|\mathrm{all}\_\mathrm{set}\left|\right|}{{\mathrm{\Σ}}_{c_j\∈\mathrm{all}\_\mathrm{set}}\mathrm{count}(h\∈c_j)}\right),$ The first half of the formula is the word frequency of the prescription of the drug in the treatment of a certain disease, and the second half is Represents the logarithm of the quotient of the clustering number of the entire prescription database divided by the weight of the drug h appearing in the entire prescription database, which is the "inverse document frequency" of the drug; it is the inverse document frequency in the prescription database;

The count(h∈c _j ) in the formula is defined as $\mathrm{count}(h\∈c_i)=\frac{{\mathrm{\Σ}}_{f\∈c_i}\mathrm{bool}(h\∈f)}{\left|\right|c_i\left|\right|},I(h\∈c_i)$ defined as In the two sub-formulas, h represents the specific drug, c _i represents the cluster i of the prescription, f represents a certain first prescription, ||c _i || represents the number of prescriptions contained in the prescription cluster c _i , bool(h∈f ) indicates whether the drug h appears in the prescription f, which is 1 if it appears, and 0 if it does not appear; count( _h∈ci ) indicates the number of times that the drug h appears in the prescription cluster c _i divided by the number of prescriptions in the prescription cluster, the value The domain is [0,1]; If (h) is the order importance of drug h in prescription _f , the definition Here i means that the drug h is the ith drug of the prescription f; I( _h∈ci ) means that the total order importance of the drug h in the prescription cluster c _i is divided by the number of clustered prescriptions; set(x) means the treatment disease All formulas of x, all_set means the entire formula database; Indicates the weight of drug h appearing in the clustering of prescriptions for treating disease x, which is the "weighted word frequency" of the drug.

Beneficial effects of the present invention: mainly aiming at the problems that the current existing methods are easily affected by the frequency of drug occurrence, the mining results are not accurate enough, and the algorithm is complicated, etc., a general, accurate, effective, and reasonable method for mining core drugs of traditional Chinese medicine prescriptions is proposed. The invention mainly relates to core medicine mining of traditional Chinese medicine prescriptions. The purpose of clustering is to reduce the impact of similar prescriptions on the core drug mining results. Compared with the existing technology, its notable points are:

(1) simple to realize: the realization process involved in the present invention is very simple, and the structure is clear and clear, and is suitable for treating various

The discovery of the core drug of a prescription for different diseases.

(2) Not affected by the frequency of prescriptions and medicines: the present invention uses clustering prescriptions for processing, and only calculates once for similar prescriptions that appear multiple times. Based on the TF-IDF algorithm to reduce the impact of the frequency of wild drugs.

(3) High accuracy: the present invention considers the clustering of similar prescriptions, the order importance of medicines, and the TF-IDF algorithm simultaneously, and comprehensively designs the weight formula of medicines. Through comparative analysis of experimental results, the accuracy rate is high.

Description of drawings:

Fig. 1 is the overall flowchart of the method of the present invention;

Fig. 2 is the pseudocode figure of clustering algorithm of the present invention;

Fig. 3 is a pseudocode diagram of the core drug algorithm of the present invention.

Detailed ways:

The invention mainly relates to the discovery of core medicines of traditional Chinese medicine prescriptions, and is used for excavating the core medicines in prescriptions for treating certain diseases. This paper proposes a general, accurate, effective and reasonable mining method for the core drugs of traditional Chinese medicine prescriptions mainly for the problems that the existing methods are easily affected by the frequency of drug occurrence, the mining results are not accurate enough, and the algorithm is complex.

The algorithm process mainly includes three steps: 1) Preprocessing of prescription data; 2) Cluster processing stage of prescription data; 3) Extraction of core drugs. The real experimental test results show that the algorithm has high accuracy and can extract core drugs that are effective for a certain disease.

The implementation process of the entire system is described in detail below in conjunction with the accompanying drawings:

Referring to Fig. 1, the overall framework of the present invention is:

1. Preprocessing of traditional Chinese medicine prescription data:

① In order to meet the requirements of clustering, firstly, preprocess the data of the antidote. Traditional Chinese medicine prescriptions are text data, so the present invention adopts VSM (vector space model) model. Each prescription is abstracted into a vector, and the medicine in the prescription is expressed as a certain dimension of the vector. If the prescription contains a certain drug, its corresponding dimension is 1, otherwise it is 0. Therefore, the prescription collection is abstracted as a 0,1 matrix with drug as the attribute column and each prescription as a row. Corresponds to step 1 in Figure 1.

2. Clustering of traditional Chinese medicine prescriptions:

②Clustering must first choose the measure of prescription distance. What the present invention selects is cosine distance, and it is defined as: Here αi, βi are prescription vectors respectively. Corresponding to step 2 in Figure 1.

③Invoke the "K-Means algorithm based on node partial distribution" to cluster the entire prescription database and the prescriptions for treating a certain disease X respectively. The purpose of clustering is to reduce the influence of similar prescriptions on the calculation of drug weights. The clustering algorithm of the present invention is an improvement to the original K-Means algorithm, and has the following characteristics: 1) can reduce the impact of noise data on the clustering result; 2) can reduce the impact of the initial seed point on the clustering result; 3) pass The fusion strategy and the strategy of reselecting seed nodes from unselected nodes have changed the fact that the number of clusters is fixed in the traditional k-means approach, making the final number of clusters the same as the number of initial center points It has nothing to do with the selection of , so that the results can converge to the real results as much as possible. Corresponding to step 3 in Figure 1

3. Call the "core drug mining algorithm":

For each medicine in the prescription for treating a certain disease X, call the formula defined in the present invention to calculate its importance, and extract the medicine whose importance value is greater than the average value avg_w of all medicines as the core medicine. Corresponding to step 4 and step 5 in Figure 1.

Referring to Fig. 2, the "K-Means algorithm based on node partial distribution" of the present invention is a clustering core algorithm. Since traditional Chinese medicine prescriptions contain a large number of addition and subtraction prescriptions, frequently occurring similar prescriptions will affect the experimental results. Therefore, the purpose of clustering is to find a set of similar prescriptions to reduce the impact of frequent prescriptions and improve the accuracy of core drug extraction. Its detailed process is:

Step 11 is the beginning of the algorithm.

Step 12 is to input the parameters p, a, and data set data_set of the algorithm. Here p can choose 1 or 2, which means that p% points are randomly selected as the center point first. a represents the maximum distance from a node to the cluster center, so its selection strategy can be obtained by calculating the distance of internal points in the same cluster in the sample data through sample sampling. data_set is the prescription data matrix after data preprocessing.

Step 13 randomly selects p% cluster center points from the data set and stores them in k_centers.

Step 14 judges whether the clustering meets the convergence condition, and if so, executes step 32 . Otherwise, go to 16. The condition for clustering convergence here is: the clustering center point does not change anymore, or the clustering results of the previous two iterations do not change.

Step 15 makes variable i=0;

Step 16 judges whether i is smaller than data_set.size(), if true, execute step 17, otherwise jump to step 29.

Step 17 makes variable xi=data_set[i], i.e. the i-th point vector;

Step 18 makes variable j=0;

Step 19 judges whether j is smaller than centers.size(), if true, execute step 20, otherwise jump to step 25;

Step 20 makes variable centerj=k_enters[j], i.e. the jth center point vector;

Step 21 calculates the distance d between point xi and centerj, and the distance function defined in the present invention is a cosine function, $\mathrm{dis}\mathrm{the\; tan}\mathrm{ce}(\mathrm{\α},\mathrm{\β})=1-\frac{\underset{i}{\mathrm{\Σ}}{\mathrm{\α}}_i\×{\mathrm{\β}}_i}{\sqrt{\underset{i}{\mathrm{\Σ}}{\mathrm{\α}}_i^2\×\underset{i}{\mathrm{\Σ}}{\mathrm{\β}}_i^2}};$

Step 22 judges whether j is 0, or j is not 0 and the size of d is smaller than shortest_d, if true, then execute step 23, otherwise execute step 24;

Step 23 assign d to shortest_d, and centerj to shortest_c, that is, record the shortest distance and the corresponding center point.

Step 24 increases the variable j by 1, i.e. j++;

Step 25 judges whether shortest_d is smaller than the set threshold a, if so, assigns the node to the cluster formed by the center point closest to itself, that is, executes step 26, otherwise does not assign the point temporarily, executes step 27;

Step 26: Add the vector xi to the cluster to which the center point of shortest_c belongs;

Step 27 temporarily does not allocate this point, that is, add the vector xi to the unallocated_nodes set;

Step 28 increases the variable i by 1, i.e. i++;

Step 29 recalculates the central points formed by each cluster. If the two clusters meet specific fusion conditions, the two clusters are merged into one cluster according to a certain fusion strategy. The purpose of this is to reduce the random The influence of the selected initial center point on the clustering results, and at the same time prevent the number of clusters from increasing, which leads to the problem of too fine division of the clustering results.

The fusion strategy that the present invention takes is divided into four steps:

1) Calculate the average distance from the center points of the two clusters to the remaining points in the respective sets;

2) Calculate the distance between the center points of the current two clusters. If the distance between the center points of the two clusters is less than twice the average distance from the center points of the respective clusters to the rest of the clusters, the current two Clustering is used as a fusion candidate set, skip to the third step, otherwise the two clusters are not fused;

3) Put all points in one cluster whose distance to another cluster center point is less than the distance between the two cluster center points themselves into the set to be fused, and put the rest of the points into the set of unassigned points.

4) Calculate the center point formed by all the points in the set to be fused, and replace the center point in the original two sets with this center point and add it to the center point set as a new center point.

Step 30 randomly selects p% cluster center points from the data set and stores them in k_centers.

Step 31 adds the center points fused in step 29 to k_centers.

Step 32 clustering algorithm ends;

Referring to Fig. 3, the detailed algorithm flow of "extraction of core drug" of the present invention is:

Step 40 is the beginning of the algorithm;

Step 41 extracts all medicines from all prescriptions for treating disease X, and stores them in the set h_set. Step 42 sets variable i=0, total_w=0.

Step 43 judges whether i is smaller than h_set.size(), that is, the quantity of prescription medicine. If so, execute

Go to step 44, otherwise go to step 49;

Step 44 makes the variable h=h_set[i], i.e. the i-th drug;

Step 45 calculates the weight h_w of medicine h according to the formula, and the formula defined in the present invention is:

$h\_w=\left({\mathrm{\Σ}}_{c_i\∈\mathrm{set}\left(x\right)}I(h\∈c_i)\right)\×\log \left(\frac{\left|\right|\mathrm{all}\_\mathrm{set}\left|\right|}{{\mathrm{\Σ}}_{c_j\∈\mathrm{all}\_\mathrm{set}}\mathrm{count}(h\∈c_j)}\right),$ The count(h∈c _j ) in the formula is defined as $\mathrm{count}(h\∈c_i)=\frac{{\mathrm{\Σ}}_{f\∈c_i}\mathrm{bool}(h\∈f)}{\left|\right|c_i\left|\right|},I(h\∈c_i)$ defined as $I(h\∈c_i)=\frac{{\mathrm{\Σ}}_{f\∈c_i}\mathrm{bool}(h\∈f)\×I_f\left(h\right)}{\left|\right|c_i\left|\right|}.$ In these two sub-formulas, h represents the specific drug, c _i represents the cluster _{i of the prescription, f represents a certain first prescription, ||ci || represents the number of prescriptions contained in the prescription cluster c i ,} bool(h∈ f) Indicates whether drug h appears in prescription f, 1 if it appears, and 0 if it does not. count(h ∈ c _i ) means the number of drug h appearing in the prescription cluster c _i divided by the number of prescriptions in the prescription cluster, and the value range is [0,1]. If _f (h) is the order importance of drug h in prescription f, defined Here i means that drug h is the ith drug of prescription f. I(h ∈ c _i ) represents the total order importance of drug h in prescription cluster c _i divided by the number of clustered prescriptions. set(x) represents all prescriptions for treating disease x, and all_set represents the entire database of prescriptions. Indicates the weight of drug h appearing in the clustering of prescriptions for treating disease x, which is the "weighted word frequency" of the drug. Indicates the logarithm of the quotient of the clustering number of the entire prescription database divided by the weight of drug h appearing in the entire prescription database, which is the "inverse document frequency" of the drug.

Step 46 stores the drug h and its weight h_w in the mapping set w_map in the form of key-value pairs;

Step 47 accumulates the calculated importance value h_w into the total importance total_w.

Step 48 increases the variable i by 1, i.e. i++;

Step 49 divides the total importance by the number of drugs to calculate the average importance avg_w;

Step 50 makes i=0 again;

Step 51 judges whether i is less than h_set.size(), if so, executes step 52, otherwise executes step 56;

Step 52 makes h=h_set[i], i.e. the ith medicine;

Step 53 checks whether the importance h_w of h is greater than avg_w, if so, then execute step 54, otherwise directly execute step 55;

Step 54 adds drug h to the set core_herbs;

Step 55 increases the variable i by 1, i.e. i++;

Step 56 obtains the core drug set core_herbs;

In step 57, the algorithm ends.

Claims (1)

1. A method for discovering core drugs of traditional Chinese medicine prescriptions, characterized in that it consists of two parts, an improved clustering algorithm and a weighted TF-IDF algorithm, and the clustering algorithm includes preprocessing of prescription data, selection of clustering distance functions and clustering There are three parts of the mining algorithm, in which the prediction theory of the prescription data processes the prescription data into a model suitable for the clustering algorithm; the selection of the clustering distance is used to select a reasonable clustering distance function; the distance mining algorithm is used to cluster similar prescriptions into a cluster; The weighted TF-IDF algorithm is used to calculate the weight of drugs, and the invented weight calculation formula combines clustering results, drug order importance, and TF-IDF algorithm in three parts; The preprocessing of the prescription data uses a vector space model. Each prescription is abstracted into a vector, and the medicine in the prescription is expressed as a certain dimension of the vector. If the prescription contains a certain drug, its corresponding dimension is 1, otherwise it is 0; The selection of the described clustering distance function adopts the cosine distance function, and its distance is: It can reasonably measure the similarity of two prescriptions; here αi and βi are the prescription vectors respectively; Described cluster mining algorithm, what it adopts is the improved K-Means algorithm based on node partial distribution; Algorithm pre-sets a threshold α, when assigning nodes to central points, for the distance to all central points all exceeds The node of α is temporarily not assigned to any cluster represented by the central node; so there may be some unassigned nodes at the end of a round of assignment. In the next round of allocation, some seed nodes are randomly selected from these nodes as the center point; in this way, through continuous iteration, each node in the final data set will be assigned to the appropriate classification; The importance of the drug sequence refers to the importance of a certain drug in the composition of the prescription; it is defined as: Here h _i is the i- _{th drug in the prescription, and I(hi) is the order importance of drug h i ;} the total importance of drug h in all prescriptions is defined as: $I\left(h\right)=\underset{i=1}{\overset{m}{\mathrm{\Σ}}}{I}_i\left(h\right);$ The TF-IDF algorithm refers to the word frequency-inverse document frequency algorithm in informatics; the weight of a word is defined as: Here n _{i, j} is the word frequency, which means the number of occurrences of word t _i in file d _j . |D| indicates the total number of documents in the corpus, and |{j:t _i ∈ d _j }| indicates the number of documents containing word t _i ; Calculate the weight W(h,x) of drug h according to the following formula, which is used to calculate the weight index of drug h in treating a certain disease x, defined as: $W(h,x)=\left({\mathrm{\Σ}}_{c_i\∈\mathrm{set}\left(x\right)}I(h\∈c_i)\right)\×\log \left(\frac{\left|\right|\mathrm{all}\_\mathrm{set}\left|\right|}{{\mathrm{\Σ}}_{c_j\∈\mathrm{all}\_\mathrm{set}}\mathrm{count}(h\∈c_j)}\right),$ first half of the formula $\left({\mathrm{\Σ}}_{c_i\∈\mathrm{set}\left(x\right)}I(h\∈c_{\text{i}})\right)$ The word frequency of the prescription for the treatment of a certain disease, the second half Represents the logarithm of the quotient of the clustering number of the entire prescription database divided by the weight of drug h appearing in the entire prescription database, which is the "inverse document frequency" of the drug in the total prescription database; The count(h∈c _j ) in the formula is defined as I( _h∈ci ) is defined as In the two sub-formulas, h represents the specific drug, c _i represents the cluster i of the prescription, f represents a certain first prescription, ||c _i || represents the number of prescriptions contained in the prescription cluster c _i , bool(h∈f ) indicates whether the drug h appears in the prescription f, which is 1 if it appears, and 0 if it does not appear; count( _h∈ci ) indicates the number of times that the drug h appears in the prescription cluster c _i divided by the number of prescriptions in the prescription cluster, the value The domain is [0,1]; If (h) is the order importance of drug h in prescription _f , the definition Here i means that the drug h is the ith drug of the prescription f; I( _h∈ci ) means that the total order importance of the drug h in the prescription cluster c _i is divided by the number of clustered prescriptions; set(x) means the treatment disease All formulas of x, all_set means the entire formula database; Indicates the weight of drug h appearing in the clustering of prescriptions for treating disease x, which is the "weighted word frequency" of the drug.