CN102750315A - Rapid discovering method of conceptual relations based on sovereignty iterative search - Google Patents

Abstract

The invention discloses a method for quickly discovering concept relationships based on sovereign iterative search, which includes: using Boolean search to eliminate concept pairs that do not contain the same non-zero elements or only contain very few non-zero elements, and narrow down the candidate concept set in magnitude; Use the enumeration method to calculate the concept correlation in the vector space; obtain the most relevant concepts by sorting. The invention integrates the advantages of the method for discovering the conceptual relationship of the Boolean model and the method for discovering the enumerated relationship based on the vector space model, and provides a fast method with time efficiency close to the former and accuracy and recall close to the latter.

Description

A Fast Discovery Method of Conceptual Relations Based on Sovereign Iterative Search

technical field

The invention relates to a method for quickly discovering concept relationships, in particular to a method for quickly discovering concept relationships based on sovereign iterative search, and belongs to the technical field of semantic networks.

Background technique

In the natural language world, a concept is an abstract description of an objective entity and a collection of attributes and characteristics of an objective entity. Due to the interaction of objective entities, concepts are also inextricably linked, which we call concept relations. Concepts and conceptual relations together form the basis of the natural language world. If the natural language world is a semantic network, then concepts are the carriers of semantics, and concept relations are the links between semantic carriers. Through the study of conceptual relations, the content and nature of entity associations in the objective world can be reflected, and then serve for human work and life.

In the current information society, the Internet is undoubtedly the largest carrier of data. The hypertext information associated with hyperlinks is increasing day by day, forming an information network world, which has completely changed the way modern humans work and live. However, also because of the explosive growth of information, managing and using information is becoming more and more complex and difficult. In order to meet the needs of semantic reasoning and intelligent services, the next-generation information Internet network represented by the Semantic Web tries to build connections between any tiny data, and the conceptual relationship is the basis for building a semantic network. Therefore, concept relationship extraction technology is the basis of the second revolution of human information.

Search engine and text mining are the core technologies of the platform portal system, and the "semantic correlation calculation" of concepts and texts is the key basis of search engine and text mining. Under the pure statistical model, due to the lack of intellectual intelligence support, "similarity" can only be used to replace "semantic relevance" as the basis for solving a series of complex technical problems in search engines and text mining.

However, with the explosive growth of information volume, the increasingly complex information structure and the socialization trend of the Internet, people put forward increasingly strong demands for search intelligence and personalized services for search engines and text mining. At this time, semantic correlation calculation The problem of "similarity" is once again placed in front of search engines and text mining technology. The calculation of "similarity" can no longer meet this demand in terms of accuracy and physical sense. The calculation of "semantic relevance" seems to have become an era that must be solved in the era of intelligent search. basic question.

Currently, Boolean models and vector space models are widely and effectively used in text classification. Boolean search can quickly discover conceptual relationships, but the accuracy and recall rate cannot be guaranteed, and the number of feature elements used to construct Boolean queries is also difficult to determine. Too few query features will lead to low query efficiency and too many results. Too many features reduce the recall rate. The extended Boolean search can give weight to the feature elements matched by the query, which can improve the recall rate to a certain extent, but it cannot solve the problem of query logic construction. The vector space model also has some shortcomings, mainly as follows: the dimensionality of the vector space is often very high, resulting in a large amount of calculation and affecting the system speed. In addition, the determination of the feature weights in the vector is also a difficult part to consider.

Contents of the invention

Aiming at the deficiencies in the prior art, the technical problem to be solved by the present invention is to provide a method for quickly discovering concept relationships. This method can not only guarantee the query efficiency, but also ensure the accuracy and recall rate

For realizing above-mentioned purpose of the invention, the present invention adopts following technical scheme:

A rapid discovery method for concept relations based on sovereign iterative search, including:

Use Boolean search to eliminate concept pairs that do not contain the same non-zero elements or contain only very few non-zero elements;

Use the enumeration method to calculate the concept correlation in the vector space;

Sort to find the most relevant concepts.

Furthermore, the Boolean search includes:

The semantic feature vector of the concept is converted into a Boolean expression, and the feature vector forward index and feature inverted index are constructed. The semantic feature of the target concept is used to construct a logical query, and the related concept set of the target concept is searched in the logical expression set.

Further, the step of using the enumeration method to calculate the concept correlation degree under the vector space includes:

a. The searcher searches the eigenvector according to the forward index of the eigenvector;

b. Obtain the sovereign feature according to the searched feature vector;

c. The searcher is used for association search, selects candidate related concepts, and puts them into the candidate related concept set;

d. Candidate concept selection strategy to obtain candidate concepts;

e. After the candidate concept set saturation control strategy searches for the associated feature inverted zipper, select the candidate concept;

f. Determine whether the candidate concept set has reached saturation, if the candidate concept set has not reached saturation, return to b, and repeat b to f until the candidate concept set is saturated;

f. If the candidate concept set has reached saturation, the iterative search is stopped, and the correlation between the target concept and the candidate related concepts is accurately calculated.

Further, the candidate concept selection strategy includes:

a. The searcher uses the associated feature as the query key, executes the query in the feature inverted index, and obtains the candidate concept zipper;

b. Place the sliding window whose window is M at the head of the zipper, if there are no more than M elements, select all of them as candidate concepts;

c. If there are more elements than M, the supervisor monitors the supervisory conditions, that is, compares the head and tail weight reduction with the amplitude threshold;

d. If the decrease of the first and last weights is less than or equal to the amplitude threshold, move the sliding window one bit and return to c, and repeat c to d until the decrease of the first and last weights is greater than the amplitude threshold;

e. If the reduction of the head and tail weights is greater than the magnitude threshold, the elements behind the window are cut off, and the rest are selected as candidate concepts.

Further, the candidate concept set saturation control strategy includes:

a. Search for candidate concepts, if the candidate concept already exists in the set of candidate related concepts, calculate the "false correlation degree" for the associated feature incrementally, if the candidate concept is a newly added concept, use the associated feature to calculate the "pseudo-related degree";

b. Re-adjust the zipper order of candidate concepts;

c. The sliding window is placed at the head of the zipper, and the number of elements and the size of the window are judged. If the number of elements is not greater than the size of the window, re-execute the candidate concept selection strategy. If the number of elements is not less than the size of the window, check the "false correlation" of the first and last candidate concepts Amplitude reduction, compared with the amplitude threshold;

d. If the decrease of "false correlation degree" is less than the magnitude threshold, enter the step of sliding the window to the end of the zipper, if it has reached the end of the zipper, re-execute the candidate concept selection strategy, otherwise return to c, repeat c~d, until the "false correlation degree" The decrease is not less than the magnitude threshold;

e. If the decrease of the "false correlation degree" is not less than the magnitude threshold, the set of candidate related concepts is saturated, and the iterative search is stopped.

Further, the construction of the feature vector forward index includes:

Number all concepts, sort the semantic features of all concepts in descending order of weight, and normalize the feature vectors to unit vectors;

Construct the feature vector forward index with the key-value relationship of "concept number - feature vector".

Further, the construction of the feature inverted index includes:

Each unit feature vector is regarded as a document, and the vector feature is used as an inverted entry. The concept numbers in the index zipper are arranged in descending order according to the weight of the feature, and the feature inverted index is constructed.

The present invention combines the advantages of the concept relationship discovery method based on the Boolean model and the enumeration relationship discovery method based on the vector space model, maximizes the strengths and avoids the weaknesses, and provides a time efficiency close to the former, while the accuracy rate and recall rate are close to the latter the quick method.

Description of drawings

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

Figure 1 is a schematic diagram of unit normalization of feature vectors and index structure;

Figure 2 is a schematic diagram of feature inversion construction and index structure;

Fig. 3 is a schematic diagram of the operation flow of a single iterative search;

Figure 4 is a schematic diagram of the relationship discovery process based on sovereign iterative search;

Fig. 5 is a schematic diagram of the execution flow of a candidate concept selection strategy;

Fig. 6 is a schematic diagram of the execution flow of the candidate concept set saturation control strategy;

Figure 7 is a schematic diagram of the overall flow of the comparative experiment of recall rate and time efficiency;

Fig. 8 is a schematic diagram of a single search concept selection average value;

Figure 9 is a schematic diagram of the average recall rate under the regulation of saturation control strategy parameters;

Figure 10 is a schematic diagram of the average recall rate under the regulation of saturation control strategy parameters;

Figure 11 is a schematic diagram of the comparison of time efficiency and recall rate.

Detailed ways

Concept relationship discovery refers to the discovery of concept relationship pairs with close semantic relations, which is a key step in concept relationship extraction. Concept relationship discovery generally only searches for the Top-M concepts that are most closely related to concepts. In general, M is a natural number and the value is not large. In the range of two digits, if the value of M is too large, the meaning of related concepts will be lost.

For a target concept, searching Top-M (M<100) most relevant concepts from 3 million candidate concepts has an effective rate of only 1/10000. If the enumeration method is used to search for the most relevant concepts, 99.99% of computing resources will be used to calculate the degree of correlation with non-related concepts, which is extremely uneconomical. The average number of elements of the conceptual semantic feature vector is only about 300. Compared with the 3 million-dimensional conceptual semantic space, the feature vector has only 1/10000 non-zero elements, which can be described as extremely sparse. Therefore, most concept pairs do not contain the same non-zero elements, even if they contain the same non-zero elements, most concept pairs only contain a very small number of the same non-zero elements.

The present invention uses Boolean search to eliminate concept pairs that do not contain the same non-zero elements or only contain very few non-zero elements, narrows down the candidate concept set in magnitude, and then uses the enumeration method to calculate the concept correlation under the vector space in the concept set degree, and then sorted to obtain the Top-M most relevant concepts. Then the query efficiency can be guaranteed, and the accuracy and recall rate can also be guaranteed.

The Boolean model is to use Boolean expressions to represent the text. The Boolean model is widely used in traditional information retrieval. It retrieves text through logical comparison with the retrieval formula given by the user, which is a keyword-based matching. In the standard Boolean model, the text is shown in equation (1):

d _i =(w _i1 , w _i2 ,... _wik ... _win ), where k=1, 2,..., n (1)

Among them, n is the number of feature items, and w _ik is 0 or 1, indicating whether the kth feature item appears in text i. Boolean models are easy to implement, but in the field of text classification, their precision and recall are poor.

If it is a sufficient condition for a close semantic relationship between concepts to contain one or several features, then the concept relationship discovery can be transformed into a search process under the Boolean model. Transform the semantic feature vector of the concept into a Boolean expression, and build an inverted index, use the semantic feature of the target concept to construct a logical query, and search in the set of logical expressions to get the related concept set of the target concept.

The Boolean model discretizes continuous values into 0 or 1, and only makes a choice between existence or non-existence. Although the one-size-fits-all approach is not very accurate, it has extremely high efficiency. However, in a high-dimensional semantic space, the semantic properties of a concept are jointly determined by all the semantic features in the feature vector, and their decision weights are quite different. Therefore, the search method based on the Boolean model cannot be directly used for the relationship discovery of massive concepts.

Compared with Boolean search, the accuracy can be improved by narrowing down the set of candidate concepts and then using the enumeration method to calculate the correlation in the vector space. But to ensure a good recall rate, it is necessary to include relevant concepts in the reduced candidate concept set as much as possible. However, in order to ensure efficiency, the candidate concept set cannot be too large. Therefore, how to use Boolean logic to narrow down the set of candidate concept relationships while minimizing the loss of related concepts is the core key issue of this method.

The vector space model was proposed by Gerard Salton and McGill in 1969. Because of its simple concept, it is widely used in Information Retrieval (IR). The use of this method in automatic text classification is mainly introduced from IR. The basic idea of the vector space model is: take each entry as one dimension of the feature space coordinate system, regard the text as a vector in the feature space, and use the angle between the two vectors to measure the similarity between the two texts Spend. In the vector space model, each text is represented as a point in the vector space spanned by a set of normalized orthogonal term vectors, that is, it is formalized as a vector in n-dimensional space, so we can abstract the text as Formula (2) shows:

V(d _i )=((t ₁ ,w _1j ),...(t _i ,w _ij ),...(t _n ,w _nj )), i=1,2, ...... n (2)

Among them, t _i is feature item i, w _ij is the weight of t _i in text d _j . For a training text set, we can get a vector space W as shown in Table 1 below:

d ₁ d _{2 m} t ₁ w ₁₁ w ₁₂ w _1m t ₂ t ₂₁ t ₂₂ t _2m t _n t _n1 t _n2 t _nm

Table 1 Text representation under vector space

W is usually a sparse matrix. Both the training text and the text to be classified can be expressed in the same way in the vector space model. The closer the vector of the text to be classified is to the vector of the training text, the greater the similarity between it and the text in the training space, and the more likely it belongs to the same category as the training text.

The vector space model is a widely used text representation model, which has the following advantages:

(1) The text content is formalized to a point in the multi-dimensional space, given in the form of a vector, and the text is defined in the real number field in the form of quantity, which improves the computability and operability of the natural language text;

(2) Calculate the weight value for the word, and reflect the degree of relevance between the word and the text by adjusting the weight value corresponding to the word, which overcomes the defects of the traditional Boolean model;

(3) By calculating the similarity between the texts, the texts with similar attributes are gathered together as much as possible to improve the matching efficiency.

Under the vector space model, the most relevant concept is calculated by the method of vector cosine angle, which is different from the Boolean model in essence. In the vector space model, the dimensions are discrete, but within any dimension, they are continuous. The vector space model uses this combination of discrete and continuous methods to realize the interaction between features, without absolutely relying on a certain feature, but without giving up any feature.

For each concept in the corpus, use the expressive semantics construction method to construct a semantic feature vector, use TF-ODF feature weighting, and adjust the weight based on Chinese pragmatics. After feature dimensionality reduction, the semantic feature vector representation of the concept can be obtained.

Assuming that the average length of the vector is n, after sorting the features, the cosine angle can be calculated in O(n) time, and the time complexity of quick sorting is O(nlogn), so the final time complexity is O(nlogn).

After constructing the concept semantic feature vector based on the interpretation relationship, the semantic features are given weights, and the concept correlation is calculated in pairs and then sorted to obtain the Top-M related concepts of any concept. Assuming that the total number of concepts in the Open Encyclopedia corpus is N, the time complexity of pairwise calculation is O(N ² ). Use the maximum heap search for any concept to save the current maximum M correlation values and corresponding concepts, then after calculating the correlation of all concept pairs, you can get the Top-M most relevant concepts of any concept, and the maximum heap is adjusted each time The time consumption is logM. It is also known that the average complexity of concept correlation calculation is O(nlogn), then it can be seen that the time complexity of Top-M related concept discovery using the method of pairwise calculation of concept correlation is O(N ² nlognlogM). Among them, n is the average number of features of the vector, and n is about 300 after dimensionality reduction, and N is the total number of concepts in the Open Encyclopedia corpus, which is about 3 million. Roughly calculated, a single computer with a computing capacity of 1 billion/s would take about 3 years to complete, which is obviously unacceptable.

In the vector space model, the weight corresponding to each dimension feature item is called feature weight, or weight for short. Sovereign feature refers to the dominant feature in the semantic feature vector. Statistics show that in 80% of the feature vectors, 80% of the sum of the weights is concentrated in the top 20% of the features. Iterative search is to continuously adjust and maintain the candidate concept set during the search process until certain conditions are met to terminate the iteration and determine the candidate concept set.

The rapid discovery method of concept relationship based on sovereign iterative search combines the Boolean model and the vector space model, learns from each other, uses the efficiency advantage of the Boolean model to perform rough calculations, limits the candidate related concepts to a small order of magnitude, and then uses the accuracy advantage of the vector space model Carry out detailed calculations, and finally get the most relevant concepts of Top-M.

As shown in Figure 1, first, we number all concepts and store them instead of concept words to save space, and then sort the semantic features of all concepts in descending order of weight, and normalize the feature vectors into unit vectors. The modulus of the unit vector is 1, which is convenient for calculating the cosine of the included angle of the vector, and also convenient for horizontally comparing the weights of the same feature in different vectors. In addition, the index is constructed with the key-value relationship of "concept number-feature vector", which is convenient to randomly and quickly obtain the feature vector corresponding to any concept number. In order to distinguish it from the feature inverted index constructed later, we call the index constructed here the feature vector forward index.

Then, each unit feature vector is regarded as a document, and the vector feature is used as an inverted entry to construct an inverted index. The concept numbers in the index zipper are arranged in descending order according to the feature weight. As shown in Figure 2, this structure can conveniently and quickly randomly access the set of concepts associated with any semantic feature horizontally, and the concepts are sorted by weight, which is conducive to accessing related concepts in order from strong to weak.

The forward index of the feature vector and the inverted index of the feature are the structural basis and efficiency guarantee of the subsequent search iteration. After the index is constructed, the concept relationship can be discovered according to the search iteration method. For the convenience of method description, we refer to the concept of the related concept to be calculated as the target concept.

The search iteration method includes two parts: "searcher" and "candidate related concept set". The candidate related concept set is composed of candidate related concepts, and is initially an empty set. The searcher uses the high-weight features of the target concept as the associated features to perform an associated search, selects candidate related concepts, and puts them into the candidate related concept set. Candidate concepts have the same associated features as the target concept, and these dynamically changing associated features are used to calculate the correlation between the candidate concept and the target concept, which we call "pseudo-correlation". The reason why it is called "pseudo-correlation" is that it is only calculated from the partial matching features between the target concept and the candidate concept. However, since the correlation feature is the main weight feature of the target concept, and the candidate concept is obtained from the head of the correlation feature list, the "false correlation" is the main part of the "true correlation". When the correlation feature is close to the target concept When all the features of , the "false correlation" is equal to the "true correlation". Because the eigenvectors have been normalized by the unit, the modulus is 1, so the calculation of the "false correlation degree" does not need to consider the modulus of the vector, and then the incremental calculation can be realized, and the calculation efficiency can be improved. The iterative search process framework is shown in Figure 3, where the first two sovereign feature searches are combined for display. Fig. 4 is a schematic diagram of the relationship discovery process based on sovereign iterative search.

There are two key strategic steps in the iterative search process. One is how many candidate concepts are selected after searching for the associated feature inverted zipper, which we call "candidate concept selection strategy"; the second is when the set of candidate related concepts is saturated and the associated search is stopped. , which we refer to as the "candidate concept set saturation control strategy". The sliding window with a supervisor can use the over-regulation supervisor to ensure that the pruned elements will not appear in the target result set with a high probability to a certain extent. We also introduce a sliding window with a supervisor into the two strategy steps here. Like feature dimensionality reduction, the parameters of the supervisor are also obtained through experiments.

A sliding window with a supervisor requires setting the window size winLen and the magnitude threshold δ. Since we want to obtain Top-M related concepts, the sliding window size of the candidate concept selection strategy is set as winLen ₁ =M, and the amplitude threshold δ ₁ is obtained through experiments. The sliding window size of the candidate concept set saturation control strategy is set to winLen ₂ , and the amplitude threshold is set to δ ₂ .

As shown in Figure 5, the execution steps of the candidate concept selection strategy are as follows:

Step 401 , the searcher uses the associated feature as a query key to perform a query in the feature inverted index to obtain a candidate concept zipper, and enters step 402 .

Step 402, place the sliding window whose window is M at the head of the zipper, if there are no more than M elements, select all of them as candidate concepts, and if there are more elements than M, go to step 404.

In step 404, the supervisor monitors the supervisory conditions, that is, compares the head-to-tail weight reduction with the amplitude threshold _δ1 and proceeds to step 405.

In step 405, if the decrease of the first and last weights is less than or equal to the amplitude threshold, go to step 407; if the decrease of the first and last weights is greater than the amplitude threshold, go to step 406.

In step 406, the elements behind the window are cut off, and the rest are selected as candidate concepts.

Step 407, move the sliding window by one bit, and return to step 404.

As shown in Figure 6, the execution steps of the candidate concept set saturation control strategy are as follows:

Step 501, search for candidate concepts, if the candidate concept already exists in the set of candidate related concepts, go to step 502; if the candidate concept is a newly added concept, go to step 503.

Step 502, calculate the "false correlation degree" for the correlation feature increment, and go to step 504.

Step 503 , search for candidate concepts, calculate "pseudo-correlation" using associated features, and proceed to step 504 .

Step 504, according to the "pseudo-correlation", readjust the order of candidate concept zippers, and go to step 505.

Step 505, place the sliding window at the head of the zipper and proceed to step 506.

Step 506, judge the number of elements and the size of winLen ₂ , if the number of elements is not greater than winLen ₂ , re-execute the candidate concept selection strategy and enter sub-process 4; if the number of elements is not less than winLen ₂ , enter step 507.

In step 507, the supervisor checks the reduction of the first and last candidate concept "pseudo-correlation" and compares it with the amplitude threshold δ ₂ to enter step 508.

In step 508, if the decrease in "false correlation degree" is not less than δ ₂ , go to step 509; if the decrease in "false correlation degree" is smaller than δ ₂ , go to step 510.

Step 509 , when the set of candidate related concepts is saturated, the iterative search is stopped, and the flow of the control strategy for the set of candidate concepts is saturated.

Step 510, slide the window to the tail of the zipper and go to step 511.

Step 511, if the end of the zipper has been reached, re-execute the candidate concept selection strategy and enter sub-process 4; otherwise, return to step 507.

After the candidate concept set reaches saturation, the iterative search stops, and at this time, the candidate related concept set is determined, and the set size is much smaller than the entire concept set of Open Encyclopedia. Further accurately calculate the correlation between the target concept and the candidate related concepts, and after sorting, the Top-M most related concepts can be obtained. The overall data flow of the conceptual relationship discovery method based on sovereign iterative search is shown in Figure 6, and the specific steps are as follows:

In step 601, the target concept search starts, and the process goes to step 603.

Step 602, number all the concepts, and construct the forward index of the feature vector.

In step 603, the searcher searches for the feature vector according to the forward index of the feature vector, and proceeds to step 604.

Step 603, obtain the sovereign feature according to the searched feature vector, and go to step 606.

Step 605, constructing a feature inverted index with vector features as inverted entries.

Step 606, the searcher uses the high-weight features of the target concept as associated features to perform an associated search, selects candidate related concepts, and puts them into the candidate related concept set.

Step 4, the candidate concept selection strategy sub-process obtains candidate concepts, and proceeds to step 5.

Step 5, after the sub-flow of the candidate concept set saturation control strategy searches for the associated feature inverted zipper, select a candidate concept and enter step 607.

Step 607, judge whether the candidate concept set has reached saturation, if the candidate concept set has reached saturation, stop the iterative search, go to step 608; if the candidate concept set is not saturated, return to step 603.

Step 608, accurately calculate the degree of correlation between the target concept and the candidate related concepts, and after sorting, the Top-M most related concepts can be obtained, and go to step 609.

In step 609, the flow of the method for discovering concept relationships based on sovereign iterative search ends.

Feature vector forward index, vector feature inverted index, searcher, candidate related concept set, candidate concept selection strategy and candidate concept set saturation control strategy constitute a relation discovery system based on sovereign iterative search.

On this basis, the algorithm based on sovereign iterative search is further verified, and the optimal sliding window parameters of candidate concept selection strategy and candidate concept set saturation control strategy are obtained, and compared with "relationship discovery under Boolean model" and "vector space model The next exhaustive relationship discovery" is compared in efficiency and recall rate.

Efficiency is the key problem to be solved in concept relationship discovery, and it is also the purpose of the sovereign iterative search method. Therefore, time efficiency is an important indicator of this experiment. The time required to calculate the Top-M related concepts of a concept is recorded as Time _rel M, and we use the average time As a measure of the time efficiency of a concept relation discovery method.

The average time spent on concept relationship discovery can certainly reflect the time efficiency of the method, but since the iterative search method is divided into multiple steps, in order to more clearly analyze the distribution of time efficiency among the steps to find out the efficiency bottleneck, we add the number of iterative searches and saturation candidate related concept set size as two auxiliary time efficiency metrics. Each iterative search needs to query the forward index of the feature vector, and the size of the saturated candidate related concept set directly affects the calculation amount of the subsequent accurate correlation. Therefore, these two indicators can well reflect the efficiency change of the iterative search.

We use the Top-M related concepts calculated by the exhaustive concept correlation under the vector space model as the recall standard, calculate the recall rate of relationship discovery, and record the Top-M related concepts set obtained by the exhaustive concept correlation calculation as Φ _std , Denote the set of related concepts to be evaluated as Φ _est , and use Card(Φ) to represent the number of elements contained in the countable set. The formula for calculating the recall rate is as follows:

$\mathrm{<span\; class="notranslate">\; recall</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&Phi;</span>}}_{\mathrm{<span\; class="notranslate">\; est</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; \&Phi;</span>}}_{\mathrm{<span\; class="notranslate">\; std</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; card</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&Phi;</span>}}_{\mathrm{<span\; class="notranslate">\; std</span>}}<span\; class="notranslate">\; \&cap;</span>{\mathrm{<span\; class="notranslate">\; \&Phi;</span>}}_{\mathrm{<span\; class="notranslate">\; est</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; card</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&Phi;</span>}}_{\mathrm{<span\; class="notranslate">\; std</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; \%</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

Although the recall rate cannot reflect the difference in the absence of related concepts in different positions, the quality evaluation of related concepts pays more attention to the quality of the difference. Therefore, the recall rate can directly reflect the result quality price paid by the search-based fast relationship discovery method for computational efficiency.

The above relationship discovery method based on sovereign iterative search has three parameters to be determined experimentally, candidate concept selection strategy amplitude threshold δ ₁ , candidate concept set saturation control strategy sliding window size winLen ₂ and amplitude threshold δ ₂ . where δ ₁ ∈ (0, 1), winLen ₂ ∈ [M, +∞), δ ₂ ∈ (0, 1). These three variables interact with the candidate concept selection strategy sliding window size winLen ₁ =M, and the relationship is complicated. Simultaneously experimenting with three variables will increase the experimental grouping and make the experimental results complicated and difficult to analyze.

The magnitude threshold δ ₁ of the candidate concept selection strategy will affect the number of concepts selected in a single search, and then affect the number of iterative searches when the sliding window size winLen ₂ and the magnitude threshold δ ₂ of the candidate concept set saturation control strategy are determined. If the magnitude threshold δ ₁ is too large, the number of concepts selected in a single search will be too large, which may lead to a decrease in the number of iterative searches and reduce the recall rate; if the magnitude threshold is too small, the number of concepts selected in a single search will be too small, which may lead to The increase in the number of search iterations reduces the time efficiency. Since the sliding window of the candidate concept selection strategy has been determined, the number of concepts selected by a single search is preferably between [M, 2M] through trial and error experience. Therefore, the number of concepts selected by a single search can be used as the result feedback to narrow down The range for the amplitude threshold.

After determining the parameters of the candidate concept selection strategy, the two parameters of the candidate related concept set saturation control strategy can be jointly tested. First determine the size of the sliding window according to the trend of the recall rate, and then analyze the recall rate and time efficiency of the experiment with multiple sets of amplitude threshold combinations to determine the optimal parameter combination.

After the parameters are determined, the relationship discovery method based on sovereign iterative search reaches the known optimal state, and then compares the recall rate and time efficiency with the search method under the Boolean model and the enumeration method under the vector space model to verify the effectiveness of the method. effectiveness.

As shown in Figure 7, the comparison experiment of the relationship discovery method of sovereign iterative search with the search method under the Boolean model and the enumeration method under the vector space model is roughly divided into three stages in terms of recall rate and time efficiency. The determination of the threshold, the determination of the saturation control parameters of the candidate related concept set, and the comparison of the efficiency and recall rate of the relationship discovery methods.

(1) Candidate concept selection strategy amplitude threshold experiment

Design 2*9 groups of experiments, the values of M are 10 and 20, and the values of _δ1 are 5%, 10%, 15%, 20%, 25%, 30%, 35%, 40%, 45%. Each group of experiments calculates the average number of concepts selected by a single search of all target concepts in the target concept set, and selects the top M features of each concept for association search. The results are shown in Table 2 below:

Table 2 The average number of concepts selected in a single search

As shown in Figure 8, the M value of 2 times the average value of the number of concepts selected in a single search appears between 25% and 30% of the amplitude threshold. Since the parameters affect each other, the small-scale fluctuation of a single parameter can be found in other The parameters are adjusted to the optimum. Through the analysis of the results of this experiment, we choose 25% which is closer to 2 times M as the magnitude threshold of the candidate concept selection strategy to continue the follow-up experiment.

(2) Candidate related concept set saturation control strategy parameter experiment

The saturation control strategy parameter is an important experimental content of the present invention, because this strategy has a decisive impact on the recall rate and time efficiency of relation discovery. In actual operation, the experiment was completed after several iterations. The experiment found that when the relationship number M is found to be in different ranges, the strategy parameters are very different. For the convenience of description, the experiment is now divided into two parts. The first part is for the experimental description and analysis of the situation of M≥10, and the second part is for the experiment and analysis of the situation of 0<M<10.

First, the first part of the experiment is explained. Design 4*10*7 groups of experimental parameters, in which the M value is 4 groups, the sliding window is 5 groups, and the amplitude threshold is 7 groups. The experimental settings for the amplitude threshold are 20%, 30%, 40%, 50%, 60%, 70% and 80%. The size of the sliding window takes M as the initial value, first doubles until it approaches or becomes M2, and then increases linearly by the same amount. The combination of the M value and the sliding window is shown in Table 3 below:

WinLen10 10 20 40 60 80 100 150 200 250 300

WinLen20 20 40 80 160 240 320 400 500 600 700 WinLen30 30 60 120 240 480 900 1000 1100 1200 1300 WinLen50 50 100 200 400 800 1600 2500 2600 2700 2800

Table 3 M value and sliding window experimental value

Each set of experimental parameters can generate a specific saturation control strategy, use each set of parameters to conduct an iterative search method for relationship discovery experiments, obtain related concepts of the target concept set, and record the saturation value of the candidate concept set. At the same time, the enumeration method is used to calculate the set of standard related concepts, and then the recall rate of relationship discovery is calculated according to the recall rate formula.

We calculate the average value of the concept number of the recorded saturated related concept set. Under 4 different M values, the amplitude threshold is used as the horizontal axis variable, and the concept value is used as the vertical axis to make the concept number of the saturated set under different sliding windows. Threshold curve. Since the number of concepts will increase beyond a linear rate as the sliding window increases, we use an exponentially changing vertical axis to facilitate observation of the curves under different sliding windows.

Figure 9 shows the average number of saturated related set concepts, as shown in the four small pictures contained in Figure 9 below, from left to right, and from top to bottom are the saturated set concepts when M is 10, 20, 30, and 50 The graphs are denoted as Saturation Set 10, Saturation Set 20, Saturation Set 30 and Saturation Set 50. From these four figures, it can be found that when the sliding window is small, the concept number of the saturated set is more sensitive to the magnitude threshold, which increases with the increase of the magnitude threshold, but with the increase of the sliding window, the sensitivity will be greatly weakened, even When a certain window size is reached, the number of concepts in the saturated set basically remains unchanged, except that there will be a small increase when the magnitude threshold is large, but the relative proportion of the increase can basically be ignored.

The phenomenon that the smaller sliding window saturation set exceeds the larger sliding window appears in the four figures. This phenomenon can be explained as follows: when the sliding window is small, the amplitude change monitor can only monitor a relatively small range, and when the range is smaller than The local discrimination ability of concept correlation will lead to continuous iterative search, and the number of concepts in the final candidate related concept set may exceed the level of the larger sliding window under the same amplitude threshold. Therefore, the sliding window should be increased appropriately as the value of M increases, so as to avoid the situation where the iterative search continues.

Next, calculate the average value of the relational recall rate of the target concept set, and make a line chart of the average recall rate under different combinations of sliding windows and floating thresholds under 4 different M values. The abscissa is the size of the sliding window, the ordinate is the recall rate, and each magnitude threshold corresponds to a colored curve. The following four figures are from left to right and from top to bottom the recall rate curves when M values are 10, 20, 30, and 50, which are recorded as recall rate 10, recall rate 20, recall rate 30, and recall rate 50.

It is easy to see from the four graphs included in Fig. 10 that as the sliding window increases, the changing trends of the recall rate at each amplitude threshold are similar. When the amplitude threshold is constant, the recall rate will increase with the increase of the sliding window, but the growth rate will be from fast to slow until it rises to the (0.95, 1) interval and then tends to be flat. When the size of the sliding window is constant, the recall rate increases with the increase of the magnitude threshold, but it cannot reach a satisfactory value when the sliding window is small.

Summarizing and analyzing the results of the recall experiment can draw the following conclusions:

1) When the sliding window remains unchanged, the recall rate can be improved by increasing the amplitude threshold, but the adjustment ability of the amplitude threshold is limited. If the sliding window is too small, a satisfactory recall rate cannot be obtained only by adjusting the amplitude threshold.

2) When the magnitude threshold remains unchanged, the recall rate can be increased by increasing the sliding window, but the sliding window value does not need to be increased blindly. When the window increases to a certain extent, the recall rate reaches a certain level and there will be no obvious difference. promote

3) When the sliding window reaches a certain size, the amplitude threshold has no obvious effect in the experiment. There may be a drop in recall as the magnitude threshold approaches zero as far as possible, but this situation is not practical.

4) The recall rate does not change significantly after exceeding 95%. When the size of the sliding window reaches a certain value, the recall rate can reach 95%, but the relationship with the amplitude threshold is not obvious.

Increasing the floating threshold does not guarantee that the recall rate will increase. Increasing the size of the sliding window on a base of 3 million will have a great impact on computational efficiency, not to mention that the recall rate in exchange cannot guarantee an increase in the correlation coefficient. Therefore, we choose a smaller sliding window under the condition of 95% recall.

The dark lines in the figure mark the boundaries of the fast-growing region and the stable region of the recall rate under each value of M. Experiments have proved that different amplitude thresholds have little influence on the boundaries. Because a certain sliding window size is very important for the candidate correlation concept saturation control strategy, we hope to analyze the relationship between the M value and the boundary by fitting. The relationship between the record M value and the boundary window is shown in Table 4 below:

M value 10 20 30 50 Boundary sliding window 96 385 1017 2530

Table 4 Correspondence between M value and boundary sliding window

We chose a common fitting method - polynomial fitting to process the relationship data between the M value and the boundary sliding window, and simplified the fitting results to obtain the following formula:

WinLen ₂ = M ² (4)

Although there are only four pairs of reference data, the formula is basically consistent with relational data, and for the engineering requirements of this method, the meaning of the determined relationship itself is greater than the significance of the accuracy of the relationship. For this sliding window value, the need for relation discovery can be met.

In order to compare the time efficiency and recall rate of three relation discovery methods, namely search relation discovery under the Boolean model, enumeration relation discovery under the vector space model, and relation discovery based on sovereign iterative search, we designed 3*10 groups of experiments, each group of experiments Calculate the Top-M most relevant concepts for all concepts in the target concept set, record and calculate the average recall rate and time, and make a graph.

As shown in Figure 11, the one on the left is a comparison chart of the efficiency of the three relationship discovery methods, the horizontal axis is the M value of 5 to 50, and the vertical axis is the execution time of relationship discovery, because the efficiency of the three methods is quite different , beyond the linear range, so the vertical axis uses a logarithmic scale with base 10, ranging from 0.0001 seconds to 10000 seconds.

The one on the right is a comparison chart of the recall rate of the three relational methods. The horizontal axis is also the M value of 5 to 50, and the vertical axis is the recall rate percentage.

It can be seen from the efficiency curve that the time-efficiency relationship of the three methods is: the Boolean search is higher than the sovereign iterative search, and the latter is higher than the vector pair enumeration method. Among them, the efficiency difference between the Boolean search method and the sovereign iterative search method is in the same order of magnitude, while the efficiency of the vector pair enumeration method is 5-6 orders of magnitude lower, that is, the average time is hundreds of thousands of times higher. As the value of M increases, the average time spent by the three methods increases. Since the coordinates of the vertical axis are in logarithmic scale, the comparison line of y=x is given in the figure. From the comparison of the slopes of the three efficiency curves with the comparison line, it can be seen that the enumeration method basically grows linearly with the increase of M value, while the growth rate of the two methods of Boolean search and sovereign feature iterative search is higher than linear, and when the value of M is small Especially obvious.

It can be seen from the recall rate curve that the recall rate relationship of the three methods is: the vector pair enumeration method is higher than the sovereign iterative search, and the latter is higher than the Boolean search method. Since vector-to-enumeration is the benchmark of recall, it has a recall of 100%. Although the Boolean search method has high efficiency, the recall rate is unsatisfactory, the overall average level is lower than 50%, and it cannot even reach 30% when M is large. In contrast, Sovereign Iterative Search achieves an average recall exceeding 95% and is insensitive to the M value.

Comprehensive evaluation of sovereign iterative search, although the efficiency is slightly lower than that of Boolean search, but it is in the same order of magnitude, and the recall rate is much higher than Boolean search, close to 100%.

The method for quickly discovering conceptual relations based on sovereign iterative search provided by the present invention has been described in detail above. For those skilled in the art, any obvious changes made to it without departing from the essence of the present invention will constitute an infringement of the patent right of the present invention and will bear corresponding legal responsibilities.

Claims (6)

1. the quick discover method of the conceptual relation based on iterative search with sovereign right is characterized in that comprising the steps:

Use boolean search to eliminate not comprise identical nonzero element or only to comprise the notion of few nonzero element right; Wherein said boolean search comprises: the semantic feature vector of notion is converted into Boolean expression; And construction feature vector forward index and characteristic inverted index; Use the semantic feature constitutive logic inquiry of target concept, search obtains the related notion collection of target concept in the logical expression set;

Further use the conceptual dependency degree under the enumerative technique compute vector space, try to achieve related notion through ordering.

2. the quick discover method of conceptual relation as claimed in claim 1 is characterized in that:

Conceptual dependency degree step under the said use enumerative technique compute vector space comprises:

A. searcher is according to proper vector forward indexed search proper vector;

B. obtain characteristic with sovereign right according to the proper vector that searches;

C. searcher carries out association search, selects candidate's related notion, and puts into candidate's related notion collection;

D. use candidate's notion to choose strategy and obtain candidate's notion;

E. the saturated control strategy of candidate's concept set searches after linked character arranges slide fastener, chooses candidate's notion;

F. judge whether candidate's concept set reaches capacity,, repeat b～f, reach capacity up to candidate's concept set if candidate's concept set does not reach capacity and then returns b;

F. iterative search stops if candidate's concept set has reached capacity, and the accurate Calculation target concept is with the degree of correlation of candidate's related notion.

3. the quick discover method of conceptual relation as claimed in claim 2 is characterized in that:

Said candidate's notion is chosen strategy and is comprised:

3a. searcher uses linked character to be query key, in the characteristic inverted index, carries out inquiry, obtains candidate's notion slide fastener;

3b. with window is that the moving window of M places the slide fastener stem, if the no more than M of element then all elects candidate's notion as, said M is a natural number;

If 3c. element more than M, monitor monitoring surveillance requirements is about to head and the tail weight amount of decrease and amplitude threshold and compares;

3d. if head and the tail weight amount of decrease is less than or equal to amplitude threshold, moving window moves one and return 3c, repeats 3c～3d, up to head and the tail weight amount of decrease greater than amplitude threshold;

3e. if head and the tail weight amount of decrease is then cut the element behind the window greater than amplitude threshold, residue is promptly elected candidate's notion as.

4. the quick discover method of conceptual relation as claimed in claim 2 is characterized in that:

The saturated control strategy of said candidate's concept set comprises:

4a. the search for candidate notion is concentrated if candidate's notion has been present in candidate's related notion, to linked character incremental computations " spurious correlation degree ", calculates " spurious correlation degree " if candidate's notion is used linked character for newly-increased notion;

4b. readjust candidate's notion slide fastener order;

4c. moving window places the slide fastener stem, judges the size of number of elements and window, if number of elements is not more than window size; Again carry out candidate's notion and choose strategy; If number of elements is not less than window size, then inspection head and the tail candidate's notion " spurious correlation degree " amount of decrease compares with amplitude threshold;

4d. if " spurious correlation degree " amount of decrease less than amplitude threshold, gets into step to slide fastener afterbody moving window, if arrived the slide fastener afterbody; Again carry out candidate's notion and choose strategy; Otherwise return 4c, repeat 4c～4d, be not less than amplitude threshold up to " spurious correlation degree " amount of decrease;

4e. if " spurious correlation degree " amount of decrease is not less than amplitude threshold, candidate's related notion collection reaches capacity, and stops iterative search.

5. the quick discover method of conceptual relation as claimed in claim 1 is characterized in that:

Said construction feature vector forward index comprises:

All notions are numbered, the semantic feature of all notions according to the weight descending, and is normalized to vector of unit length with proper vector;

Key assignments with " notion numbering-proper vector " concerns structural attitude vector forward index.

6. the quick discover method of conceptual relation as claimed in claim 1 is characterized in that:

Said construction feature inverted index comprises:

Regard each unit character vector as a document, be characterized as with vector and arrange entry, the notion numbering in the index slide fastener is according to the descending sort of feature weight size, structural attitude inverted index.

Images