CN106709011B - A kind of position concept level resolution calculation method based on space orientation cluster - Google Patents

Abstract

The invention discloses a kind of, and the position concept level based on space orientation cluster clears up calculation method, belongs to natural language position concept computing technique field；It is primarily based on position concept parsing matching result building positioning cluster, including the building of initial alignment cluster and global object node determine；It is then based on node member ancestralCBottom-up progressive disambiguate realizes that the calculating of positioning cluster is cleared up.Level resolution is carried out the present invention is based on the position concept of space orientation cluster to calculate, hierarchical step by step can be layered to position concept in conjunction with models such as spatial relationships and calculate resolution, and is finally met the positioning result that people recognize criterion and description habit.

Description

A Location Concept Hierarchy Digestion Computation Method Based on Spatial Location Clusters

technical field

The invention belongs to the technical field of natural language position concept calculation, in particular to a position concept level resolution calculation method based on spatial positioning clusters.

Background technique

The multi-source heterogeneous place name data has increased in large numbers. In order to share and integrate the location data of different sources and different structures, and retrieve the prepared query results according to the location name, it is necessary to analyze a large number of standard and non-standard data from the perspective of people's cognitive habits. Place name description text, summarize the structure and spatial relationship of the relatively complete place name description, and need to use the analysis method of location concept matching to process the location concept model instance according to the corresponding combined object-level rules to achieve efficient extraction of location concept objects.

The premise of the final location description is that it conforms to people's cognitive criteria. When people understand and express the location description, they will unconsciously use the environment, communicator-related knowledge, and semantic and spatial calculation methods. The process of understanding complex location descriptions is a process. The hierarchical heuristic process can be regarded as a process of comprehensive disambiguation and calculation using space and semantics. Therefore, after matching and parsing the semantic part of the location description and finding the corresponding spatial entity for each sub-part in the description, it is necessary to combine the spatial relationship and other models to perform hierarchical calculation and digestion of the location concept in layers and steps, and obtain the final result. Positioning results that conform to people's cognitive criteria and description habits.

SUMMARY OF THE INVENTION

In order to solve the above technical problems, the present invention proposes a location concept hierarchy disambiguation calculation method based on spatial positioning cluster, which organically integrates the spatial relationship calculation logic, concept mode and spatial search concept disambiguation, and makes full use of the hierarchical characteristics of concept trees, The concept search strategy and semantic information of the location model improve the accuracy and efficiency of localization.

The technical scheme adopted in the present invention is: a method for calculating location concept hierarchy based on spatial positioning cluster, which is characterized in that it includes the following steps:

Step 1: Analyzing the matching results based on the location concept to construct a positioning cluster, including initial positioning cluster construction and global target node determination;

First, an initial positioning cluster T ₀ with only spatial relationship positioning nodes and pattern positioning nodes is constructed by the matching results from the top-level matching object, and each node n has found the tuple where it is located as a vertex node. The target node of C; then select one of the local target nodes as the global target node of the positioning cluster; finally, the subtree of the initial positioning cluster T ₀ is connected by a virtual space relationship node, and the target node assigns the space The fields of the relational concept object finally form the positioning cluster T;

Step 2: Based on the bottom-up progressive disambiguation of the node tuple C, the calculation and elimination of the positioning cluster is realized. The specific implementation process is: input the positioning cluster T, the node n, the algorithm is a recursive call, and the initial input of the node n is the root node of the positioning cluster n _root ;

If n is not a spatial relationship node, if its parent node is empty, and it is a failure or mode positioning node, it returns a single node calculation, otherwise it returns empty, if its parent node is not empty, it must be a certain spatial relationship node The child node of , the calculation type is determined by the upper tuple, and empty is returned directly here;

If n is a spatial relationship node, recursively call its child nodes; if all return null, extract the reference child node set _TR from its child node set, if there is a pattern positioning node in the set _TR , directly return multiple child nodes Disambiguation, if not, it means that the reference child node set has been disambiguated; at this time, the reference node must be a combined node, if the target node of n is itself, it will return to the calculation of the location-based spatial relationship node, where the n node itself is the Input; if not, continue to distinguish if the node is a failure mode node, directly return to the single-node calculation, where its target node is the input; if the node is valid, return to the connectivity space relationship node disambiguation step, where n The node itself is the input; when the recursive call finally returns empty, the calculation disambiguation terminates, and the positioning cluster T is reduced to one node, that is, its global target node.

The present invention performs hierarchical digestion and calculation based on the location concept of the spatial positioning cluster, and can combine the spatial relationship and other models to perform hierarchical calculation and digestion of the location concept in layers and steps, and obtain a positioning result that finally conforms to people's cognitive criteria and description habits.

Description of drawings

1 is a schematic diagram of a location concept location method based on a spatial location cluster according to an embodiment of the present invention;

FIG. 2 is a schematic diagram of the construction and digestion process of the positioning cluster according to the embodiment of the present invention;

3 is a schematic diagram of a localization cluster and a digestion process according to an embodiment of the present invention (a hotel near the intersection of Guangba Road and Bayi Road);

4 is a schematic diagram of the results of hierarchical digestion according to an embodiment of the present invention (a hotel near the intersection of Guangba Road and Bayi Road);

FIG. 5 is a schematic diagram of a localization cluster and a digestion process according to an embodiment of the present invention (between Gutian 2nd Road and 3rd Road, the clinic opposite the light rail station).

Detailed ways

In order to facilitate the understanding and implementation of the present invention by those of ordinary skill in the art, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the embodiments described herein are only used to illustrate and explain the present invention, but not to limit it. this invention.

The result formed by semantic matching in the present invention can be regarded as a matching cluster composed of multiple semantic matching trees, and the cluster is transformed into a cluster for the positioning process, wherein the nodes correspond to the objects of spatial relationship and complex position concept . This cluster is called a spatially localized cluster.

The spatial positioning cluster T can be regarded as a set of positioning trees T=(t ₁ , t ₂ , ..., t _n ), and the root node of each subtree t corresponds to a top-level virtual concept object formed in the matching process, which can be Formalized as t=(N, L, d). Among them, N is a set of nodes, corresponding to matching objects, spatial relationships, or location concept objects formed in the calculation process. These objects may be stored spatial entities corresponding to the real world, or spaces calculated from spatial relationships. object. L is an edge set, which represents the association relationship between nodes, which connects nodes from bottom to top in a hierarchical manner, and the two-level nodes of each level are regarded as several independent node groups C. Each tuple contains a top-level node and several sub-nodes, in fact, the basic unit of computing and digestion for the entire positioning cluster. The leaf node itself acts as a node tuple and has no child nodes. d is the target node, which represents the final calculation direction of the subtree t, and all calculations and disambiguation are carried out around the target node. The entire positioning cluster T also has its corresponding target node d _T , which corresponds to the positioning node of the subtree and is determined after final selection. For the entire positioning cluster T, there is only one target node d _T , and relatively speaking, other nodes are reference nodes. Let d _T be the global target node, and the target node of subtree t is a local target node. In fact, if any node is taken from T, the local subtree formed by it and the child nodes corresponds to a local target node and several reference nodes.

In the present invention, different nodes represent different types of location concepts, and the location nodes in the location cluster can be divided into mode location nodes, failure mode nodes, spatial relationship location nodes, location concept object location nodes and combined location nodes.

A pattern positioning node refers to a positioning node containing a set of patterns formed through a pattern query. In the process of forming a positioning cluster, a pattern positioning node mainly corresponds to a non-spatial relational location concept object in the input matching result. A graph query is formed by generating a set of schemas. The failure mode node is a failure node generated when the description is wrong in the process of forming the mode positioning node or the mode decomposition query in the mode graph fails to find any mode node, which does not affect the calculation and resolution of the positioning graph itself. , but will directly affect the final scoring process. The spatial relationship positioning node is a kink in the positioning cluster, which represents the constraint of a certain reference object on the target object. The spatial relationship positioning node is generated by the spatial relationship type position concept object in the input matching result in the process of positioning the cluster itinerary. The location concept object location node is a set of location concept objects, which is generated by the pattern location node or the spatial relation location node. The combined positioning node is an intermediate form of node type in the calculation and resolution process of the positioning cluster, which contains multiple reference nodes to disambiguate and select a combination of several groups of position concept objects.

The calculation and resolution of the positioning cluster in the present invention corresponds to the calculation of the spatial relationship and the disambiguation of the mode nodes, which can be approximately formalized as an optimization problem. Each leaf node in the positioning cluster represents a set of candidate set of position concept objects, and Spatial relationships represent constraints imposed on a set of child nodes and can be expressed as where: n _root locates the cluster root node, F(L _n ) is the objective function, where is the combination of all position concept objects that meet the spatial constraints corresponding to the tuple where the node n is located, and the positioning of the positioning cluster T can be transformed into a combination that maximizes the objective function through this function. L _n contains both the target position concept object , which also contains a reference location concept object. The constraint condition in L _n is represented by V(L _n , n), which represents whether a certain combination satisfies the constraint condition of the spatial relationship corresponding to this tuple. If n _root is a positional spatial relationship node, it is necessary to The corresponding object of the target node in , solves the confidence field object according to the spatial calculation as the positioning result; if n _root is a connection-type spatial relationship node, select The target node in the corresponds to the object as the positioning result. F(L _n ) is represented as a score function with values between 0 and 1. It is accumulated by the scores of the underlying positioning nodes, and the H(n) function is used to adjust the scores according to the proportion of failed nodes. G(L _n ) is represented as a function of the node where the current tuple is located, which is represented as a weighted function, where D(L _n ) represents the normalized distance between the geometric convex hull of the reference location concept object set and the target object, Represents node ni and one of the candidate objects The semantic similarity between them is called self-semantic similarity, while S ₁ (L(n)) considers the semantic similarity between a set of candidate position concept objects, which is called intra-group semantic similarity. A special case is that at leaf nodes, G(L _n ) is directly represented by semantic self-similarity. Among them, r, p, q are the weights of the three, respectively. The following is the specific representation of the objective function F(L _n ):

Aiming at the spatial relationship calculation function of position description and positioning, the present invention design includes two basic spatial relationship calculation functions (confidence field calculation and selection filtering), which are specifically realized by each spatial relationship position concept. The confidence field calculation combines the spatial relationship and the semantic properties of the reference position concept object to calculate and return a confidence field. The present invention assumes that a homogeneous confidence field is returned, represented by a two-dimensional geometric object. The selection filter is used to filter the input set of location concept objects, and returns the filtered set of objects.

The present invention realizes the basic calculation model of the location concept by considering the spatial relationships of side relationship, interrelationship, building structure relationship, distance and orientation relationship, distance topological relationship, internal relationship, cross relationship, and order measurement relationship.

In the confidence field calculation of the present invention, the realization of the basic calculation model of the position concept of the side relationship includes the following steps: (1) calculating the convex hull T of the reference object set as the boundary of the reference object set; (2) calculating the buffer of T, buffering the The threshold is h; (3) return the buffer. The basic calculation model of the position concept of the relationship is to directly return the convex hull T of the reference object set. Building structural relationships and internal relationships directly return the reference object to its own implementation. The realization of the basic calculation model of the position concept of the distance-azimuth relationship includes the following steps: (1) Perform a spatial search from the road network to find the edge e closest to the reference object, where e is in the form of a polyline; (2) Project the center point of the reference object to e to find The line segment e' where the point is located; (3) Perform affine transformation to solve the reference object l symmetry and the geometric object l^' of the line segment e'; (4) Select the threshold h according to the semantics of the orientation word: including the front, opposite, Oblique face, etc.; (5) Calculate and return the buffer of l', the threshold is h. The realization of the basic calculation model of the position concept of the distance topology relationship includes the following steps: (1) If there is a linear geometric object in the reference object, find a point with a specified distance along the geometric object and return; (2) If the reference object is a nested azimuth space relationship, then combined with the reference object of the orientation, look for the point offset by the specified distance in the direction corresponding to its direction vocabulary (such as "east", "south", "west", "north") and return. The realization of the basic calculation model of the location concept of the intersection relationship includes the following steps: (1) Calculate the intersection point l corresponding to the reference object set; (2) If l is not empty, calculate and return the buffer of l, the threshold is h, otherwise return null.

In the selection filtering calculation function of the present invention, the basic calculation models of the position concept of the side relationship, the relationship between the buildings, the relationship between the building structure, the relationship between the distance and the orientation, the topological relationship between the distance, the internal relationship and the cross relationship are all filtering the input objects according to the confidence field T. collection. The basic calculation model of the position concept of the sequential measurement relationship is to select the kth object closest to the confidence field in the input set (k is a member variable of the measurement relationship object).

The location concept hierarchy resolution calculation method based on the spatial positioning cluster proposed by the present invention combines spatial relationship computation logic, pattern query and search, disambiguation, and similarity measurement to perform hierarchical computation and resolution on the location concept in layers and steps, and obtain final positioning result.

Please refer to FIG. 1 and FIG. 2 , a method for calculating location concept hierarchy based on spatial positioning cluster provided by the present invention includes the following steps:

Step 1, analyze the matching result based on the location concept to construct a location cluster. First, an initial positioning cluster T ₀ with only spatial relationship positioning nodes and pattern positioning nodes is constructed by the matching results from the top-level matching object, and each node n has found the tuple where it is located as a vertex node. C's target node. Then, one of the local target nodes is selected as the global target node of the positioning cluster. Finally, the subtrees of the initial positioning cluster T ₀ are connected by a virtual spatial relationship node, and the target node assigns the fields of the spatial relationship concept object to finally form the positioning cluster T.

Step 2: Based on the node tuple C, the bottom-up progressive disambiguation is performed to realize the calculation and elimination of the positioning cluster. According to the number of C nodes and the type of nodes, there are different calculation situations. First input the positioning cluster T, node n, the algorithm is a recursive call, the initial input of node n is the positioning cluster root node n _root ; if n is not a spatial relationship node, if its parent node is empty, and it is a failure or mode positioning node , return single node calculation, otherwise return empty, if its parent node is not empty, it must be a child node of a spatial relationship node, the calculation type is determined by the upper tuple, and empty is returned directly here; if n is a space Relationship node, recursively called on its children. If both return empty, the reference child node set _TR is extracted from its child node set. If there is a pattern positioning node in the set _TR , the multi-child node disambiguation is directly returned. If not, it means that the reference child node set has been disambiguated. Finish. At this time, the reference node must be a combined node. If the target node of n is itself, it will return to the positional spatial relationship node calculation (with the n node itself as the input); if not, continue to distinguish if the node is a failure mode node, Then return the single-node calculation directly (with the target node as input); if the node is valid, return to the disambiguation step of the connectivity space relationship node (with n node itself as the input); but the recursive call finally returns to empty when the calculation of disambiguation terminates , at this time, the positioning cluster T is reduced to one node, that is, its global target node.

The initial positioning cluster construction in step 1 includes the following sub-steps:

1) To construct an initial positioning cluster, it is first necessary to input a matching result, which represents a set of matching objects L=(l ₁ , l ₂ ,...l _n );

2) traverse the set L, corresponding to each matching object l _i , generate the corresponding positioning node and its child nodes according to 3), which is represented as a positioning tree t _i ;

3) According to the type of _li , the situation is processed. Follow steps i and ii below. During the construction process, each node assigns a local target node to its tuple C as the top-level node to prepare for the generation of the global target node in the second stage. There are mainly the following steps:

i. Complex location concepts for non-spatial relationships: make a pattern query to form _np nodes and designate their local target nodes as themselves. If the l _i type is POI, since the embedded place name of the POI is actually a spatial limitation of the POI, during the generation process of the POI pattern positioning node, the POI place name set G will be extracted, and the pattern node set will be generated separately. It is connected to the same parent node in parallel with the node of the POI itself.

ii. Spatial relational object: traverse its sub-part conceptual object collection to recursively call down the sub-node collection, and itself forms an n _r node as the parent node. The local target node is determined according to the spatial relationship concept annotation corresponding to k. If the sub-concept marked as the target field is empty, the local target node is assigned as the n _r node itself.

4) Finally, merge the subtrees to form the initial positioning cluster T ₀ =(t ₀ , t ₁ , . . . t _n );

In the embodiment, the object to be compared with the global target node determined in step 1 must be a pattern positioning node. If a local target node itself is a location-based spatial relationship node, a most significant pattern needs to be selected from its child nodes. The positioning node represents the process in which it participates in the sorting. In the present invention, the salience of a pattern node is formalized as a tuple (v, c, l, n) composed of four elements; where v represents the node validity, c represents the node object category, l represents the number of valid characters of the node object, n represents the number of node objects. These four elements are the basis for people to judge the target. The importance of each element is different, which can be expressed as a kind of weight information, or the factors can be sorted in a logical way. factor to make a judgment, and when equal, skip to the next factor. Based on the summary and observation of the location description, the latter method is adopted in the implementation, and its form and algorithm are relatively concise. The judgment sequence is: v>c>l>n, let the set of pattern nodes to be judged be n ₀ , the basic process is as follows:

1) First judge the validity of the object, the significance of valid nodes is greater than that of invalid nodes. Take the determined set of valid nodes as n ₁ . If |n ₁ |=1, complete the judgment process and return to the unique node, otherwise go to 2);

₂ ) Select the priority category according to the category of n1. In the process of sorting the categories, the complex location concept types are divided into the following three levels: POI, address > simple place names excluding administrative area names > administrative area names; in other words, the above set sequence lists POI and address as the most prominent location concepts Types, and administrative district names are the least significant type of location concept, and administrative district names are further divided into five levels according to the administrative district level: village>town, street>county>city>province. The above-mentioned division of levels forms a priority sequence Q of location concepts, which contains all complex location concept types except spatial relationships, and each element q in the sequence is a set of location concept categories. Traverse the priority sequence, and return the corresponding pattern positioning node n ₂ in one of the sets from the n ₁ set. If |n ₂ |>0, enter 3, otherwise skip to the next element in the priority sequence;

3) Sort n ₂ according to the number of valid words of the virtual concept object corresponding to the pattern node. The corresponding assumption is that in the case of the same category, the object with a longer description is more significant, and the set of nodes with the number of valid words ranked first is n ₃ . If |n ₃ |=1, the judgment process is completed, and the Unique node, otherwise go to 4);

4) The selection is made according to the number of objects corresponding to the pattern nodes. The assumption is that the objects corresponding to pattern nodes with fewer objects are more specific and more likely to be target nodes. Let the set of nodes with the first number of valid words be n ₄ , and return its first element as the final destination node. In a rare case, there are still multiple nodes in n ₄ , which generally corresponds to that the location description itself does not have a clear direction, and the present invention selects any node as its target node.

In step 2, the specific implementation of the bottom-up progressive disambiguation based on the node tuple C to realize the calculation and elimination of the positioning cluster includes the following sub-steps:

1) First input the positioning cluster T, node n, the algorithm is a recursive call, and the initial input of node n is the positioning cluster root node n _root ;

2) If n is not a space relationship node, if its parent node is empty, and it is a failure or mode positioning node, return single node calculation, otherwise return empty, if its parent node is not empty, it must be a space For the child nodes of the relationship node, the calculation type is determined by the upper-level tuple, and null is returned directly here;

3) If n is a spatial relationship node, recursively call to its child nodes. If both return empty, the reference child node set _TR is extracted from its child node set. If there is a pattern positioning node in the set _TR , the multi-child node disambiguation is directly returned. If not, it means that the reference child node set has been disambiguated. Finish. At this time, the reference node must be a combined node. If the target node of n is itself, it will return to the positional spatial relationship node calculation (with the n node itself as the input); if not, continue to distinguish if the node is a failure mode node, Then return the single-node calculation directly (with the target node as input); if the node is valid, return to the disambiguation step of the connectivity space relationship node (with n node itself as the input); but the recursive call finally returns to empty when the calculation of disambiguation terminates , at this time, the positioning cluster T is reduced to one node, that is, its global target node.

During specific implementation, different calculation situations are classified according to the number of C nodes and the type of nodes.

The single-node calculation algorithm in step 2 (that is, when the node tuple |C|=1) mainly includes the following sub-steps:

Step 2.1, the input is a mode positioning node, select the top k position concept objects of the mode positioning node, and convert them into entity position concept object nodes;

In step 2.2, the input is the failure mode positioning node, which is converted into the failure object node.

In specific implementation, the multi-sub-node disambiguation algorithm in step 2 (|C|>1, but the reference node is still a pattern or concept positioning node, run multi-sub-node disambiguation to convert it into a combined positioning node;) mainly includes: The following substeps:

Step 2.1, input the reference node set N;

Step 2.2, separate the n _v node set N _v from the set N, and the n _p and n _l node sets N _pl ;

Step 2.3, calculate the proportion of failed nodes

Step 2.4, obtaining the first k*|N _pl | permutations and combinations of each node in N _pl to form a set C _P ;

Step 2.5, sort C _P according to spatial proximity to form a permutation combination C′ with score information;

Step 2.6, traverse C', and integrate h into the combined score as a multiplication weight;

In step 2.7, the combined positioning node n _c is generated by C′, and the node set N is replaced in the graph to complete the elimination of the positioning cluster in this step.

In specific implementation, in step 2, when the node ancestor |C|>1 and is a location-based spatial relationship node, the specific implementation of the disambiguation process includes: there is only one input node n, and this node can only be a location concept object node or combination Locate the node; after calculating the spatial relationship, a confidence field concept object is obtained to locate the node n_lc, and the node n is replaced in the localization cluster; there is no disambiguation operation of the object in the whole step.

During specific implementation, the disambiguation algorithm of the connected spatial relationship node in step 2 (|C|>1 and is a connected spatial relationship node, at this time the reference node has been converted into a combined positioning node) mainly includes the following sub-steps:

Step 2.1, input the spatial relation node n _r , locate the cluster T;

Step 2.2, extract the reference node n _ref and the local target node n _p of the n _r node, wherein the n _ref node can only be a combination node or a position concept object node;

Step 2.3, if n _p is the failure mode node, generate the failure object node n _lv to replace the n _r node and return;

Step 2.4, according to the spatial relationship calculation model of n _r nodes, obtain a confidence field position concept set P with the object list of n _ref ;

Step 2.5, initialize the object set L with score information;

Step 2.6, traverse the set P, and evaluate the retrieval strategy jointly with n _p and the geometric object g _p . In the case of pattern retrieval, pattern search is performed; in the case of spatial retrieval, the spatial nearest neighbor search is performed in conjunction with the searchable fields, and the neighbor parameter m is taken as the upper limit of the number of objects K, and the searchable fields are the basis for joint entry in the process of spatial storage. Concept field, this paper mainly considers fields such as special name and common name in POI. After searching, a set of objects is formed and added to L;

Step 2.7, weighting the set L, and multiplying the score of the concept of confidence field position in the corresponding set P for each object, and then taking K objects to construct a set L';

Step 2.8, construct the location concept object node n _l from the set L′ and replace the node n _r in the location cluster;

The present invention is further described below by specific embodiments;

Example 1: Hotels near the intersection of Guangba Road and Bayi Road;

The above description has a two-layer spatial relationship, and the original input text form of the first matching tree is: (AdjacentRelation((IntersectRelation((TraCityRoadName((TraCityRoad wide), (FeaWord eight road)), (Conjunction and), (TraCityRoadName( (TraCityRoad 8), (FeaWord 1st Road)), (IntersectionWord intersection)), (near AdjacentWord), (POI ((CommonName Hotel))), please refer to Figure 3, for the positioning cluster constructed for it and the digestion flow chart. Its The target node is a POI type mode positioning node, which has undergone three steps: multi-child node disambiguation, location-based spatial relationship node calculation, and connectivity spatial relationship node disambiguation. See Figure 4, which is a schematic diagram of the hierarchical resolution result. The ten result sets are shown in Table 1 below, and their effective word count scores are all the same. Since the word "de" in the original description was skipped in the process of matching the "nearby" spatial relationship, the number of words is 14.

Table 1. Hierarchical digestion calculation and positioning set table: hotels near the intersection of Guangba Road and Bayi Road

ID name Cascading Weighted Similarity Cascading significant characters 1 Fengyi Hotel 0.82031 14.0 2 Prince Grill Hotel 0.53949 14.0 3 7Days Inn Wuhan Guangbutun Branch 0.48875 14.0 4 Seven Days Hotel 0.45576 14.0 5 Xinghuyuan Hotel 0.38647 14.0 6 Junyue Hotel 0.32572 14.0 7 Sanli Hotel 0.32438 14.0 8 Home Inn Guangbutun 0.30921 14.0 9 Junyi Dynasty Hotel 0.30397 14.0 10 Environmental protection hotel 0.29892 14.0

Example 2: The clinic opposite the light rail station between Gutian 2nd Road and 3rd Road;

It consists of two phrases with two layers of spatial relationship description. The position description of this sentence corresponds to an exact query, so the correct result needs to be given in the first returned item. The textual form of the first matching tree of its original input is:

(DistanceDirectionRelation((BetweenRelation((TraCityRoadName((TraCityRoad Gutian), (FeaWord 2nd Road)), (Conjunction and), (TraCityRoadName((FeaWord 3rd Road))), (BetweenWord), (POI((CommonName Light Rail Station)) )), (opposite FaceToDirectionWord), (POI ((CommonName Clinic))).

Please refer to Figure 5 for the positioning cluster and resolution flow chart constructed for it. The target node is a POI-type mode positioning node, which has gone through three steps of multi-child node disambiguation and two connection-type spatial relationship node disambiguation. Among them, the "three roads" and "light rail stations" in the reference nodes in this example all need to be disambiguated. See Table 2 for the calculation and positioning of hierarchical digestion;

Table 2. Hierarchical digestion calculation and positioning set table: Between Gutian 2nd and 3rd Road, the clinic opposite the light rail station

It should be understood that the parts not described in detail in this specification belong to the prior art.

It should be understood that the above description of the preferred embodiments is relatively detailed, and therefore should not be considered as a limitation on the scope of the patent protection of the present invention. In the case of the protection scope, substitutions or deformations can also be made, which all fall within the protection scope of the present invention, and the claimed protection scope of the present invention shall be subject to the appended claims.

Claims (9)

1. a kind of position concept level resolution calculation method based on spatial positioning cluster, is characterized in that, comprises the following steps: Step 1: Analyzing the matching results based on the location concept to construct a positioning cluster, including initial positioning cluster construction and global target node determination; First, an initial positioning cluster T ₀ with only spatial relationship positioning nodes and pattern positioning nodes is constructed by the matching results from the top-level matching object, and each node n has found the tuple where it is located as a vertex node. The target node of C; then select one of the local target nodes as the global target node of the positioning cluster; finally, the subtree of the initial positioning cluster T ₀ is connected by a virtual space relationship node, and the target node assigns the space The fields of the relational concept object finally form the positioning cluster T; Step 2: Based on the bottom-up progressive disambiguation of the node tuple C, the calculation and elimination of the positioning cluster is realized. The specific implementation process is: input the positioning cluster T, the node n, the algorithm is a recursive call, and the initial input of the node n is the root node of the positioning cluster n _root ; If n is not a spatial relationship node, if its parent node is empty, and it is a failure or mode positioning node, it returns a single node calculation, otherwise it returns empty, if its parent node is not empty, it must be a spatial relationship node The child node of , the calculation type is determined by the upper tuple, and empty is returned directly here; If n is a spatial relationship node, recursively call its child nodes; if all return null, extract the reference child node set _TR from its child node set, if there is a pattern positioning node in the set _TR , directly return multiple child nodes Disambiguation, if not, it means that the reference child node set has been disambiguated; at this time, the reference node must be a combined node, if the target node of n is itself, it will return to the calculation of the location-based spatial relationship node, where the n node itself is the Input; if not, continue to distinguish if the node is a failure mode node, directly return to the single-node calculation, where its target node is the input; if the node is valid, return to the connectivity space relationship node disambiguation step, where n The node itself is the input; when the recursive call finally returns empty, the calculation disambiguation terminates, and the positioning cluster T is reduced to one node, that is, its global target node. 2. the position concept hierarchy resolution calculation method based on spatial positioning cluster according to claim 1, is characterized in that, described in step 1, initial positioning cluster is constructed, and its concrete realization comprises the following sub-steps: Step A1: input the matching result, which represents a set of matching objects L=(l ₁ , l ₂ , . . . l _n ); Step A2: traverse the set L, corresponding to each matching object l _i , generate the corresponding positioning node and its child nodes according to step A3, which is represented as a positioning tree t _i ; Step A3: perform case-by-case processing according to the _li type; in the construction process, each node will designate a local target node for its tuple C as the top-level node to prepare for the generation of the second-stage global target node; Step A4: Form an initial positioning cluster T ₀ =(t ₀ , t ₁ , . . . t _n ). 3. the position concept hierarchy resolution calculation method based on spatial positioning cluster according to claim 2, is characterized in that, described in step A3, carry out case-by-case processing according to l _i type, and its concrete realization process is: For non-spatial relational objects: perform a pattern query to form n _p nodes, and specify its local target node as itself; if the l _i type is POI, since the embedded place name of POI is actually a spatial limitation of POI, therefore, During the generation process of POI's mode positioning node, the POI's place name set G will be extracted, and the separately generated mode node set will be connected to the same parent node side by side with the POI's own node; For spatial relational objects: traverse its subpart conceptual object set to recursively call the child node set, and itself forms an n _r node as the parent node; the local target node restricts the spatial relation concept corresponding to the parameter k according to the returned object The labeling decision, if the _subconcept labelled as the target field is empty, assign its local target node as the nr node itself. 4. the location concept hierarchy resolution calculation method based on spatial positioning cluster according to claim 1, is characterized in that, described in step 1, the global target node is determined, and its concrete realization comprises the following substeps: Step B1: Input the initial positioning cluster T ₀ =(t ₀ , t ₁ , . . . t _n ); Step B2: Traverse the T ₀ subtree, and backtrack to obtain the local target node of each subtree The backtracking process is to first recursively go up to the root node of the subtree, and then recursively go down to find the target node; if the node If the node is located for the spatial relationship type, the recursive form finds its most significant child node replacement form a set of target nodes Step B3: Set D to extract significant node n; Step B4: Backtracking out the target node from the subtree where n is located as the global target node d. 5. The position concept level resolution calculation method based on spatial positioning cluster according to claim 4, is characterized in that, described in step B2, if the node If the node is located for the spatial relationship type, the recursive form finds its most significant child node replacement form a set of target nodes The specific implementation process: first formalize the saliency of the pattern node as a tuple (v, c, l, n) composed of four elements, where v represents the node validity, c represents the node object category, and l represents the node object The number of valid words, n represents the number of node objects; then let the set of mode nodes to be judged be n ₀ , the basic process is as follows: Step C1: First judge the validity of the object, the significance of valid nodes is greater than that of invalid nodes; take the set of judged valid nodes as n ₁ ; if |n ₁ |=1, complete the judgment process and return to the unique node, otherwise enter step C2; Step C2: Select n ₁ according to the category of priority category; in the process of category sorting, the location concept type is divided into the following three levels: (1) POI and address, (2) place names other than administrative district names, ( 3) Administrative district place names, among which POI and address are the most prominent location concept types, while administrative district place names are the least significant location concept types; administrative district place names are further divided into five levels according to the administrative district level: (1) village, (2) town , street, (3) county, (4) city, (5) province, where village is the most prominent location concept type, and province is the least significant location concept type; Sequence Q, which contains all location concept types except spatial relations, each element q in the sequence is a set of location concept categories; traverse the priority sequence, and return the corresponding one in one of the sets from the n ₁ set Mode positioning node n ₂ ; if |n ₂ |>0, then go to step C3, otherwise skip to the next element in the priority sequence; Step C3: Sort n ₂ according to the number of valid words of the virtual concept object corresponding to the mode node; the corresponding assumption is that in the case of the same category, the object with a longer description is more significant, and the number of valid words ranks first. The node set is n ₃ ; if |n ₃ |=1, the judgment process is completed, and the unique node is returned, otherwise, go to step C4; Step C4: Select according to the number of objects corresponding to the pattern nodes; the assumption is that the objects corresponding to pattern nodes with fewer objects are more specific and more likely to be target nodes; let the set of nodes with the number of valid words ranked first be n ₄ , return its first element as the final target node; if there are still multiple nodes in n ₄ , select any node as its target node. 6. The method for calculating location concept hierarchy based on spatial positioning cluster according to claim 1, characterized in that, in step 2, when the node primitive |C|=1, the concrete realization of the disambiguation process comprises the following substeps: Step D1: the input is a mode positioning node, select the first k position concept objects of the mode positioning node, and convert them into entity position concept object nodes; Step D2: The input is the failure mode positioning node, which is converted into the failure object node. 7. The method for calculating location concept hierarchy based on spatial positioning cluster according to claim 1, characterized in that, in step 2, when the node ancestor |C|>1, but the reference node is still a pattern or concept positioning node, run The multi-child node disambiguation converts it into a combined positioning node; the specific implementation of the multi-child node disambiguation process includes the following sub-steps: Step E1: Input the reference node set N; Step E2: separate the n _v node set N _v , and the n _p and n _l node sets N _pl from the set N; Step E3: Calculate the proportion of failed nodes Step E4: obtain the first k*|N _pl | permutations and combinations of each node in N _pl to form a set C _P ; Step E5: Sort C _P according to spatial proximity to form a permutation combination C′ with score information; Step E6: Traverse C', and integrate h into the combined score as a multiplication weight; Step E7: Generate a combined positioning node n _c with C′, and replace the node set N in the graph to complete the elimination of the positioning cluster in this step. 8. The method for calculating location concept hierarchy based on spatial positioning cluster according to claim 1, characterized in that, in step 2, when the node ancestor |C|>1 and is a location-based spatial relationship node, the specific disambiguation process is The implementation includes: there is only one input node n, and the node can only be a position concept object node or a combined positioning node; after calculating the spatial relationship, a confidence field concept object positioning node n_lc is obtained, and node n is replaced in the positioning cluster; There is no disambiguation of objects throughout the step. 9. The method for calculating location concept hierarchy based on spatial positioning cluster according to claim 1, characterized in that, in step 2, when the node ancestor |C|>1 and it is a connection type spatial relationship node, the specific disambiguation process is Implementation includes the following sub-steps: Step F1: Input the spatial relationship node n _r to locate the cluster T; Step F2: Extract the reference node n _ref and the local target node n _p of the n _r node, wherein the n _ref node can only be a combination node or a position concept object node; Step F3: If n _p is the failure mode node, generate the failure object node n _lv to replace the n _r node and return; Step F4: According to the spatial relationship calculation model of n _r nodes, obtain a confidence field position concept set P with the object list of n _ref ; Step F5: Initialize the object set L with score information; Step F6: Traverse the set P, and evaluate the retrieval strategy jointly with n _p and the geometric object g _p ; if it is a pattern retrieval, perform a pattern search; if it is a spatial retrieval, perform a spatial nearest neighbor search in conjunction with the searchable fields, and take the neighbor parameter m as The upper limit of the number of objects is K, and the searchable fields are the basic concept fields that are jointly entered in the space storage process; after searching, an object set is formed and added to L; Step F7: Weighting the set L, multiplying the score of the belief field position concept in the corresponding set P for each object, and then taking K objects to construct a set L'; Step F8: Construct the location concept object node n _l from the set L' and replace the node n _r in the location cluster.