CN107391584B - Faceted Search Method and System Based on Formal Concept Lattice - Google Patents

Abstract

The invention relates to the technical field of computer search, and discloses a faceted search method and system based on a formal concept lattice, which pre-constructs a formal concept lattice for original information based on a formal concept analysis theory, and establishes an index on the basis of the formal concept lattice, thereby Build a faceted search system. The method of the invention includes: constructing a formal concept lattice, and in the construction process, the formal concept lattice uses the fake attribute fake_attribute to initialize the minimum concept Bottom; establishing an index of the leaf concept in the formal concept lattice; in the query process, the connotation of the concept corresponds to the query statement, The extension of the concept corresponds to the result set; after obtaining the facet value set of the user query, the leaf concept is used in the constructed formal concept lattice to match the minimum connotation of the attribute set from the bottom up to find the target concept corresponding to the facet value set, and Returns the extension corresponding to the target concept.

Description

Faceted Search Method and System Based on Formal Concept Lattice

technical field

The invention relates to the technical field of computer search, in particular to a faceted search method and system based on a formal concept lattice.

Background technique

Faceted Search is an information retrieval technology that provides context-related facet information according to the current search results on the basis of keyword search. Users can customize the category of interest from various perspectives, breaking away from the category tree established by the system designer. After the user specifies a certain facet value, the system dynamically obtains more refined information according to the result set corresponding to the facet value. The new refined result can divide the result set from multiple facets, helping the user to further Learn about the data they are interested in. Throughout the search process, users can flexibly switch facets to quickly get relevant content.

Formal Concept Analysis (Formal Concept Analysis) theory is a method of knowledge mining and analysis for structured data, which is widely used in knowledge discovery, software engineering and other fields. The core data structure of formal concept analysis is the formal concept lattice, and the concept lattice represents the hierarchical structure between concepts through Hasse Diagram.

The current popular faceted search technology is mainly based on the traditional relational database. It is an urgent problem to quickly retrieve these contents and provide the corresponding faceted information.

SUMMARY OF THE INVENTION

The purpose of the present invention is to disclose a faceted search method and system based on a formal concept lattice, which pre-constructs a formal concept lattice for original information based on the formal concept analysis theory, and establishes an index on the basis of the formal concept lattice, thereby establishing a faceted search system.

In order to achieve the above object, the present invention discloses a faceted search method based on formal concept lattice, including:

Construct a formal concept lattice, the formal concept lattice uses the fake attribute fake_attribute to initialize the minimum concept Bottom, and each time the concept lattice structure is updated, the attribute set of the input object Obj is added to the content of Bottom, and finally the fake_attribute is eliminated to obtain a complete and the correct formal concept lattice; at the same time, in the process of adding new objects to the formal concept lattice, after inputting the attribute set Y, first obtain the standard generator uniquely corresponding to Y, if the connotation of the existing concept in the concept lattice is equal to Y , then Y does not generate a new concept, and adds the new object to the extension of the concept associated with its equivalent intension, and adds the new object to the extension of all parent concepts of this concept; if there is no existing concept in the concept lattice The connotation is equal to Y, then a new concept is created, and all candidate direct parent concepts of the new concept are calculated according to the direct parent concepts of the standard generator and the real direct parent concepts are filtered out, and then the parent-child relationship between the concepts is updated, and the new concept is The object is added to the extension of all parent concepts of the new concept;

establishing an index of leaf concepts in the formal concept lattice, where the leaf concepts refer to the direct parent concept of the smallest concept in the formal concept lattice;

In the query process, the connotation of the concept corresponds to the query statement, and the extension of the concept corresponds to the result set; after obtaining the facet value set of the user query, the leaf concept is used in the constructed formal concept lattice to match the minimum connotation of the attribute set from bottom to top to find the target concept corresponding to the set of facets, and return the extension corresponding to the target concept.

Corresponding to the above method, the present invention also discloses a faceted search system based on formal concept lattice, including:

Subsystem 1 is used to construct a formal concept lattice. The formal concept lattice uses the fake attribute fake_attribute to initialize the minimum concept Bottom, and every time the concept lattice structure is updated, the attribute set of the input object Obj is added to the content of Bottom, and finally Then remove fake_attribute to obtain a complete and correct formal concept lattice; at the same time, in the process of adding new objects to the formal concept lattice, after inputting the attribute set Y, first obtain the only standard generator corresponding to Y, if the concept lattice already exists The intension of the concept is equal to Y, then Y does not generate a new concept, and adds the new object to the extension of the concept to which its equal intension is associated, and to the extension of all parent concepts of this concept; if the concept lattice If there is no existing concept whose connotation is equal to Y, create a new concept, and calculate all candidate direct parent concepts of the new concept according to the direct parent concepts of the standard generator and filter out the real direct parent concepts, and then update the parent-child between concepts relationship, while adding the new object to the extension of all parent concepts of the new concept;

Wherein, the subsystem 1 is also used to establish an index of a leaf concept in the formal concept lattice, and the leaf concept refers to the direct parent concept of the smallest concept in the formal concept lattice;

Subsystem 2 is used in the query process, the connotation of the concept corresponds to the query statement, and the extension of the concept corresponds to the result set; after obtaining the face value set of the user query, the leaf concept is used to match bottom-up in the constructed formal concept lattice. Contains the minimum intension of the attribute set to find the target concept corresponding to the set of facets, and returns the extension corresponding to that target concept.

The present invention has the following beneficial effects:

On the one hand, in the process of constructing the formal concept lattice, the minimum concept is dynamically updated, and the complete formal background is avoided to be loaded in advance, which improves the flexibility of the algorithm.

On the other hand, each time an object is added, an update operation will be performed based on the standard generator on the basis of the original concept lattice to obtain a new concept lattice, which is simple, fast and reliable. The hash value calculation is used as an index, and all concepts are stored in the hash table, so that in the process of determining the standard generator, the standard generator is searched bottom-up in combination with the hash value of the calculated attribute set Y to effectively improve the standard generation. The query speed of the server is avoided, and redundant computation is avoided.

On the other hand, the present invention also parses the query conditions into attribute sets, and uses the leaf concept to match the minimum connotation including the attribute set from bottom to top, so that impossible routes can be quickly eliminated and the target concept can be found.

In addition, the faceted search technology of the present invention based on the formal concept lattice can realize the pre-calculation of the context relationship and facet information of the result set before the user searches, or to quickly calculate the facet information corresponding to the result at the same time of retrieval, which shortens the system time. The response time improves the user experience and reduces the user browsing cost.

The present invention will be described in further detail below with reference to the accompanying drawings.

Description of drawings

The accompanying drawings constituting a part of the present application are used to provide further understanding of the present invention, and the exemplary embodiments of the present invention and their descriptions are used to explain the present invention and do not constitute an improper limitation of the present invention. In the attached image:

1 is an example diagram of a formal concept lattice disclosed in an embodiment of the present invention;

2 is a flowchart of a faceted search method based on a formal concept lattice disclosed in an embodiment of the present invention;

FIG. 3 is a schematic diagram of a construction process of a formal concept lattice disclosed in an embodiment of the present invention.

Detailed ways

For the convenience of those skilled in the art to fully understand the present invention, the relevant terms, theorems and inferences of the present invention are described in detail as follows:

为一个形式背景(简称背景)。(u，m)∈I(或写作uIm)表示对象u具有属性m。背景可以用一个矩形的表来表示，它的每一行是一个对象，每一列是一个属性。若u行m列的交叉处是×，则表示对象u具有属性m。如表1给出示例。Definition 1.1: Let U be a set of objects, M be a set of attributes, and I be the relationship between two sets U and M, then it is called a triple

For a form background (referred to as background). (u, m) ∈ I (or written as uIm) means that object u has attribute m. The background can be represented by a rectangular table, where each row is an object and each column is an attribute. If the intersection of u row and m column is ×, it means that object u has attribute m. Examples are given in Table 1.

Table 1 Example Background

是一个背景，若

令Definition 1.2: Let

is a background, if

make

and

或

表示背景

上的所有概念的集合。If A and B satisfy f(A)=B, g(B)=A, then the binary group (A, B) is called a concept (Concept). A is the extension (Extent) of the concept (A, B), and B is the connotation (Intent) of the concept (A, B). use

or

show background

Collection of all concepts on .

A是一个外延当且仅当A＝g(f(A))；对于任意

B是一个内涵当且仅当B＝f(g(B))。Corollary 1.1: For any

A is an extension if and only if A=g(f(A)); for any

B is an intension if and only if B=f(g(B)).

存在二元组(A，f(A))，明显有f(A)＝f(A)，又因为g(f(A))＝A，所以二元组(A，f(A))是一个概念(定义2.2)，则A是一个外延。Proof: (1) Sufficient: For any

There is a dyad (A, f(A)), obviously f(A)=f(A), and because g(f(A))=A, the dyad (A, f(A)) is a concept (definition 2.2), then A is an extension.

(2) Necessity: Since A is an extension, the binary group (A, f(A)) is a concept, then A=g(f(A)).

The extension part is proved here, and the same can be proved for the intension.

Theorem 2.1: Let (U, M, I) be a background, A, A ₁ , A ₂ ∈ U, B, B ₁ , B ₂ ∈ M, then we have:

one,

(1)

(2)

(3) f(A)=f(g(f(A)))

(4)f(A ₁ )∩f(A ₂ )=f(A ₁ ∪A ₂ )

(5)

(6) g(f(A))=g(f(g(f(A))))

(7)

two,

(1`)

(2`)

(3`)g(B)=g(f(g(B)))

(4`)g(B ₁ )∩g(B ₂ )=g(B ₁ UB ₂ )

(5`)

(6`)f(g(B))=f(g(f(g(B))))

Theorem 2.2: For any subset A of U, f(A) must be an intension, because the form (g(f(A)), f(A)) must be a concept; also for any subset B of M, g(B) must be an extension, because (g(B), f(g(B)) must be a concept.

Corollary 2.2: The intersection of connotation is still connotation, and the intersection of extension is still extension.

f(A₁∪A₂)一定是内涵，同理有A₁∩A₂＝g(B₁)∩g(B₂)＝g(B₁∪B₂)，易证g(B₁∪B₂)一定是外延。证毕。Proof: For any two concepts (A ₁ , B ₁ ), (A ₂ , B ₂ ), according to Theorems 2.1(4) and 2.1(4`), B ₁ ∩B ₂ =f(A ₁ )∩f( A ₂ )=f(A ₁ ∪A ₂ ), according to Theorem 2.2 for

f(A ₁ ∪A ₂ ) must be the connotation. Similarly, A ₁ ∩A ₂ =g(B ₁ )∩g(B ₂ )=g(B ₁ ∪B ₂ ), and it is easy to prove that g(B ₁ ∪B ₂ ) must be epitaxy. Certificate completed.

上的两个概念。而且

(由定理2.1(1)，易知等价于

)，则我们称(A₁，B₁)是(A₂，B₂)的子概念，(A₂，B₂)是(A₁，B₁)的父概念，并记作(A₁，B₁)≤(A₂，B₂)。如果

且不存在概念(A₃，B₃)使得

则称(A₁，B₁)是(A₂，B₂)的直接子概念，(A₂，B₂)是(A₁，B₁)的直接父概念，记作(A₁，B₁)＜(A₂，B₂)。由此得到一个半序集

其中

表示(U，M，I)的所有概念。Definition 2.3: If (A ₁ , B ₁ ), (A ₂ , B ₂ ) is a background

on the two concepts. and

(From Theorem 2.1(1), it is easy to know that it is equivalent to

), then we call (A ₁ , B ₁ ) the child concept of (A ₂ , B ₂ ), and (A ₂ , B ₂ ) the parent concept of (A ₁ , B ₁ ), and denoted (A ₁ , B 1 ), B ₁ )≤(A ₂ , B ₂ ). if

and there is no concept (A ₃ , B ₃ ) such that

Then (A ₁ , B ₁ ) is said to be the direct child concept of (A ₂ , B ₂ ), and (A ₂ , B ₂ ) is the direct parent concept of (A ₁ , B ₁ ), denoted as (A ₁ , B _{1 )} )<(A ₂ , B ₂ ). This results in a semi-ordered set

in

Represents all concepts of (U, M, I).

被称为形式概念格。其中令

则称图(V，E)为形式概念格的哈斯图。根据形式背景示例表1可以画出其对应形式概念格如图1。The semi-ordered set obtained in the above definition 2.3

is called the formal concept lattice. which order

Then the graph (V, E) is called a Haas diagram of the formal concept lattice. According to the form background example Table 1, the corresponding form concept grid can be drawn as shown in Figure 1.

Definition 2.4: Concepts whose direct subconcepts in the formal concept lattice are the smallest concepts in the formal concept lattice are called leaf concepts. Leaf concepts have and only minimal concepts as subconcepts. For example, in Figure 1, the concept (1, abef) and the concept (4, abcdf) are leaf concepts.

Definition 2.5: In the formal concept lattice, the support number of an attribute m is equal to the extension set cardinality of the largest concept that contains the attribute; the support number of a concept is equal to its extension set cardinality. As shown in Figure 1, the support number of attribute f is 4, and the support number of concept (1, abef) is 1.

形式概念格，在形式背景

中加入一个新对象o后得到新的形式背景

所对应的形式概念格为L，其中用f`(o)表示o所拥有的属性。令(A，B)为L`中任意一个概念，则Definition 3.1: Let L be the corresponding formal context

Form concept grid, on form background

After adding a new object o to get a new form background

The corresponding formal concept lattice is L, where f`(o) is used to denote the attributes possessed by o. Let (A, B) be any concept in L`, then

(1) (A, B) is a new concept if and only if B is not an intension of any concept in L.

(2) (A, B) is a Modified concept if and only if

(3) (A, B) is called the old concept if it already exists in L.

(4) For any new concept (X, Y), if B∩f`(o)=Y≠B, then the concept (A,B) is called a generator of (X,Y). A minimal concept is a generator of any other concept.

(5) In general, a new concept (X, Y) will have multiple generators (at least one generator), of which the standard generator is the parent concept of all other generators, that is, the upper limit of all generators boundary.

Corollary 3.1: There is one and only one standard generator for any new concept (X, Y). prove:

(1) If (X, Y) has only one generator, it is a standard generator.

(2) If (X, Y) has multiple standard generators, this is against the definition and need not be discussed.

那么

根据推论2.2，B₁∩B₂一定是一个内涵，那么一定存在概念(g(B₁∩B₂)，B₁∩B₂)也是(X，Y)的一个生成器，因为

这与(A₁，B₁)，(A₂，B₂)是极大概念相矛盾。故该假设不成立。(3) If there is no generator, there is disproven. Assuming that there are two maximal concepts (A ₁ , B ₁ ), (A ₂ , B ₂ ) in these generators, we have

So

According to Corollary 2.2, B ₁ ∩ B ₂ must be an intension, then there must be a concept (g(B ₁ ∩ B ₂ ), B ₁ ∩ B ₂ ) is also a generator of (X, Y), because

This contradicts the concept that (A ₁ , B ₁ ), (A ₂ , B ₂ ) are maximal. Therefore, this assumption does not hold.

To sum up, (X, Y) has one and only one standard generator.

The standard generator is a very important concept. In the process of constructing the concept lattice, the standard generator of the new concept (X, Y) needs to be found first. In fact standard generators are direct subconcepts of new concepts in the current generative concept lattice. So where did the new concept come from? We know that adding a new object o to a known formal concept lattice L can get a new formal concept lattice L`, indicating that o is the factor that causes L to update. Here are the conclusions:

Corollary 3.2: According to the definition 3.1, adding a new object o to the concept lattice L, we have:

(1) The attribute set f`(o) corresponding to the object o must be a connotation in the new conceptual lattice L`. If f`(o) is not the intension of any concept in L, then (g`(f`(o)), f`(o)) is a new concept; otherwise, there is no new concept in L`.

(2) If a new concept (A, B) is produced, the non-empty intersection of all intensions in L and B may also produce new intensions (Corollary 2.2), thereby producing more new concepts.

(3) The direct child concept of a new concept is its standard generator.

(4) The direct parent concept of the new concept may be the direct parent concept of the standard generator, or the concept corresponding to the intersection of the connotation of the new concept and the direct parent concept of the standard generator.

(5) The addition of object o will definitely lead to the generation of improved concepts. Specifically, all parent concepts of (g`(f`(o)), f`(o)) need to add object o to its extension.

其中

表示所有的概念。新增的分面丰富了属性的语义，同时对于形式概念格原有的结构没有影响。分面搜索与形式概念分析在逻辑概念上有良好的契合度，形式概念分析可以对分面搜索的所有操作，包括语义相关的操作提供支持。To sum up, the formal context is represented by a triple (U, M, I), where U represents a set of objects, M represents a set of attributes, and I represents the relationship between objects and attributes. There are also concepts of objects and attributes in faceted search, and attributes are divided by faceting, which is the common point of faceted search and formal concept analysis. If F represents the set of facets, and FV represents all facet values corresponding to the facets, the attribute set M can be represented by a two-tuple (F, FV). This results in a new expression (U, (F, FV), I) or quadruple (U, F, M, I) of the formal context. According to the formal background (U, F, M, I), the corresponding formal concept lattice can be obtained

in

represent all concepts. The new facets enrich the semantics of attributes without affecting the original structure of the formal concept lattice. Faceted search and formal concept analysis have a good fit in logical concepts, and formal concept analysis can provide support for all operations of faceted search, including semantically related operations.

Based on the above definitions, theorems and inferences, the embodiments of the present invention are described in detail below with reference to the accompanying drawings, but the present invention can be implemented in many different ways as defined and covered by the claims.

Example 1

This embodiment discloses a faceted search method based on formal concept lattice, as shown in FIG. 2 , including:

Step S1, construct a formal concept lattice, which uses the fake attribute fake_attribute to initialize the minimum concept Bottom, and each time the concept lattice structure is updated, the attribute set of the input object Obj is added to the connotation of Bottom, and finally the fake_attribute is eliminated. Obtain a complete and correct formal concept lattice; at the same time, in the process of adding new objects to the formal concept lattice, after inputting the attribute set Y, first obtain the standard generator uniquely corresponding to Y, if the concept lattice has the connotation of the concept and If Y is equal, then Y does not generate a new concept, and the new object is added to the extension of the concept associated with its equal intension, and the new object is added to the extension of all parent concepts of this concept; if the concept lattice does not exist already The connotation of the concept is equal to Y, then create a new concept, and calculate all the candidate direct parent concepts of the new concept according to the direct parent concepts of the standard generator and filter out the real direct parent concepts, then update the parent-child relationship between the concepts, and at the same time, This new object is added to the extension of all parent concepts of the new concept.

In this step, the formal concept lattice can adopt a static construction mode, a dynamic construction mode or a hybrid construction mode based on construction time prediction; wherein, the hybrid construction mode is based on the face value set prediction concept construction time, if less than a preset If the time threshold is greater than the preset time threshold, the dynamic mode is used to construct the formal concept grid. If the time threshold is greater than the preset time threshold, the formal concept grid is constructed using the static mode.

In contrast to the above steps, the existing minimal concept needs to know the set M composed of all attributes in the formal background (U, M, I), and the entire background must be preloaded, resulting in idle background data wasting limited memory resources, Too much data can even cause algorithms to fail to function properly.

此时还未计算新概念的直接父概念。图3(c)表示根据标准生成器的直接父概念(1，abef)计算出概念(3，cdf)的一个候选直接父概念为新概念(123，f)，而(123，f)的直接子概念为其标准生成器(12，bf)。图3(d)表示根据

的直接父概念(2，bcf)计算出(3，cdf)的另一个候选直接父概念为新概念(23，cf)。这里要说明的是(23，cf)的标准生成器(2，bcf)还有其他直接父概念(12，bf)，所以还需要根据(12，cf)为新概念(23，cf)计算其直接父概念，恰好是已存在的(123，f)，故这个步骤没有新概念生成。最后在(3，cdf)的候选直接父概念中选出真正的直接父概念(23，cf)，更新概念之间父子关系，概念格构造完成。In order to express the construction process conveniently, this embodiment uses [object number, object attribute set] to represent the object entity, two-tuple (extension, connotation) represents the concept, and the abbreviated form represents the set, such as abc={a, b, c}, 123 ={1, 2, 3}. As shown in Figure 3, it shows the process of adding object [3, cdf] to the concept lattice that has added object [1, abef] and object [2, bcf], omitting the process of extension update. The solid circles in the figure represent the pre-constructed minimal concepts (forgery attributes are omitted), the dashed circles represent the newly constructed concepts, and the solid circles represent the old concepts in the concept grid. Figure 3(a) shows the concept lattice structure without adding the object [3, cdf]. Figure 3(b) shows that the object [3, cdf] is added to generate a new concept (3, cdf), and the corresponding standard generator is the minimal concept after updating the connotation

The immediate parent concept of the new concept has not been calculated at this time. Figure 3(c) shows that a candidate direct parent concept of concept (3, cdf) is calculated according to the direct parent concept (1, abef) of the standard generator as the new concept (123, f), and the direct parent concept of (123, f) is The subconcept is its standard generator (12, bf). Figure 3(d) shows that according to

The direct parent concept of (2, bcf) computes another candidate direct parent concept of (3, cdf) as the new concept (23, cf). What is to be explained here is that the standard generator (2, bcf) of (23, cf) has other direct parent concepts (12, bf), so it is also necessary to calculate its new concept (23, cf) according to (12, cf) The immediate parent concept happens to be the existing (123, f), so no new concept is generated in this step. Finally, the real direct parent concept (23, cf) is selected from the candidate direct parent concepts of (3, cdf), the parent-child relationship between concepts is updated, and the concept lattice construction is completed.

Optionally, this embodiment uses the improved AddIntent algorithm to implement the pseudocode of the above object addition as shown in Table 2 below:

Table 2:

As shown in Table 2, the function AddIntent has three parameters: attribute set Y, a generator corresponding to Y, canonical_generator, and formal concept lattice L. After inputting the attribute set Y, the first line to the fourth line of the algorithm first obtains the standard generator corresponding to Y. If the connotation of the existing concept in the concept lattice L is equal to Y, then Y will not generate a new concept, and directly return the found concept , the algorithm ends; otherwise, lines 5 to 14 of the algorithm further calculate all candidate direct parent concepts of the new concept according to the direct parent concepts of the standard generator; lines 15 to 16 generate a new concept; lines 17 to 30 Lines exclude unsatisfactory concepts in candidate direct parent concepts, then delete possible old associations, and set the association of new concepts with direct parent concepts; lines 31 to 32 update the parent-child relationship between the new concept and the standard generator And return the new concept, the algorithm ends. Among them, the called function GetCanonicalGenerator is used to obtain the corresponding standard generator of Y.

Preferably, in this step S1, all concepts are stored in the hash table by calculating the hash value of the connotation of the concept as an index; in the process of determining the standard generator, combined with the calculated hash value of the attribute set Y The standard generator is searched from the bottom up by the value of the value; thereby, the query speed of the standard generator can be effectively improved, and redundant calculation is avoided. As a deteriorating implementation: the attribute set Y can also be compared with the connotation of the concept one by one in a bottom-up manner, until all parent concepts of a concept are found that are not generators of the concept corresponding to the attribute Y, then the concept is Standard generator.

In step S2, an index of a leaf concept is established in the formal concept lattice, and a leaf concept refers to the direct parent concept of the smallest concept in the formal concept lattice.

Step S3: In the query process, the connotation of the concept corresponds to the query statement, and the extension of the concept corresponds to the result set; after obtaining the facet value set of the user query, the leaf concept is used in the constructed formal concept lattice to match the inclusive attribute set from bottom to top. to find the target concept corresponding to the set of facets, and return the extension corresponding to the target concept.

In this step, faceted search conducts inductive retrieval of things in a faceted manner, which is often used in vertical search engines in professional fields. The operation specification of faceted search is not specified, and a typical faceted search operation is divided into two parts, keyword search and interactive refinement search. Keyword search is a traditional information retrieval technology. On this basis, faceted search technology allows users to conduct interactive exploration, further refine and decompose existing keyword search results, and improve the accuracy of search results. , which eliminates most irrelevant result sets, so that a good user experience can be obtained.

The faceted search has the following steps:

(1) After a certain keyword search, a result set about the keyword is obtained, and the facet information of the result set is calculated and displayed at the same time.

(2) The user selects the face value of interest according to the displayed result set and facet to further refine the result.

(3) Re-search the relevant result set.

In this way, the query can be looped interactively until the user obtains a satisfactory result or the result set is empty.

Further, this embodiment also includes:

After the target concept is found, the facet value support number corresponding to the target concept is calculated according to the context of the formal concept lattice, where the facet value support number refers to the number of objects corresponding to the facet value. For example: NBA players can have the following facets: name, age, height, weight, player type and team, each facet contains many attributes, such as facets - "player type" includes center, power forward, Small forward, etc., assuming that there are 150 center players in the NBA, it can be represented by ('player type', 'center', 150).

Further, this embodiment also includes:

Record the user's query records, and return the largest common parent concept and the smallest common child concept of multiple historical query results as query recommendation; or perform query recommendation based on concept similarity. Among them: There are two steps to obtain the maximum common parent concept:

(1), find the intersection of the connotations of the corresponding concepts of all historical queries;

(2) Use the result of (1) to query, and the matched concept is the largest common parent concept.

Similarly, the methods to obtain the largest common subconcept include:

(1), seek the union of the connotations of the corresponding concepts of all historical queries;

(2) Use the result of (1) to query, and the matched concept is the least common sub-concept.

Optionally, in this embodiment, the definition of conceptual similarity is as follows.

中任意两个概念A，B，使用extent表示外延，则Jaccard系数为：Definition 4.1: For the formal concept lattice

In any two concepts A, B, use extent to represent extension, then the Jaccard coefficient is:

The current concept is set as C, the Jaccard similarity is k, the generalization operation is to search for the largest parent concept with a similarity of not less than k, and the refinement operation is to search for the smallest sub-concept of the current concept with a similarity of not less than k. For the generalization operation, the algorithm starts from C to access its parent concepts in a breadth-first traversal manner, until all the parent concepts of a parent concept have a similarity with C less than k, the concept is the generalization target concept; for the refinement operation , the algorithm starts from C and accesses its sub-concepts in a breadth-first traversal manner, until all sub-concepts of a sub-concept have a similarity with C less than k, which is the refinement target concept.

To sum up, the faceted search method based on the formal concept lattice disclosed in this embodiment has the following beneficial effects:

On the one hand, in the process of constructing the formal concept lattice, the minimum concept is dynamically updated, and the complete formal background is avoided to be loaded in advance, which improves the flexibility of the algorithm.

On the other hand, each time an object is added, an update operation will be performed based on the standard generator on the basis of the original concept lattice to obtain a new concept lattice, which is simple, fast and reliable. The hash value calculation is used as an index, and all concepts are stored in the hash table, so that in the process of determining the standard generator, the standard generator is searched bottom-up in combination with the hash value of the calculated attribute set Y to effectively improve the standard generation. The query speed of the server is avoided, and redundant computation is avoided.

On the other hand, the present invention also parses the query conditions into attribute sets, and uses the leaf concept to match the minimum connotation including the attribute set from bottom to top, so that impossible routes can be quickly eliminated and the target concept can be found.

In addition, the faceted search technology of the present invention based on the formal concept lattice can realize the pre-calculation of the context relationship and facet information of the result set before the user searches, or to quickly calculate the facet information corresponding to the result at the same time of retrieval, which shortens the system time. The response time improves the user experience and reduces the user browsing cost.

Example 2

Corresponding to the above method embodiments, the present embodiment discloses a faceted search system based on a formal concept lattice, which at least includes the following subsystems 1 and 2, and preferably, further includes the following subsystems 3 and 2. / or subsystem four.

Subsystem 1 is used to construct a formal concept lattice. The formal concept lattice uses the fake attribute fake_attribute to initialize the minimum concept Bottom, and every time the concept lattice structure is updated, the attribute set of the input object Obj is added to the content of Bottom, and finally Then remove fake_attribute to obtain a complete and correct formal concept lattice; at the same time, in the process of adding new objects to the formal concept lattice, after inputting the attribute set Y, first obtain the only standard generator corresponding to Y, if the concept lattice already exists The intension of the concept is equal to Y, then Y does not generate a new concept, and adds the new object to the extension of the concept to which its equal intension is associated, and to the extension of all parent concepts of this concept; if the concept lattice If there is no existing concept whose connotation is equal to Y, create a new concept, and calculate all candidate direct parent concepts of the new concept according to the direct parent concepts of the standard generator and filter out the real direct parent concepts, and then update the parent-child between concepts relationship, adding the new object to the extension of all parent concepts of the new concept.

Wherein, the above-mentioned subsystem 1 is also used for establishing an index of a leaf concept in the formal concept lattice, and the leaf concept refers to the direct parent concept of the smallest concept in the formal concept lattice. Further, the first subsystem of this embodiment is also used to: store all concepts in the hash table by performing hash value calculation on the connotation of the concept as an index; in the process of determining the standard generator, combine the calculated The hash value of attribute set Y is searched bottom-up for the criterion generator.

Subsystem 2 is used in the query process, the connotation of the concept corresponds to the query statement, and the extension of the concept corresponds to the result set; after obtaining the face value set of the user query, the leaf concept is used to match bottom-up in the constructed formal concept lattice. Contains the minimum intension of the attribute set to find the target concept corresponding to the set of facets, and returns the extension corresponding to that target concept.

The third subsystem is used to calculate the facet value support number corresponding to the target concept according to the context of the formal concept lattice after finding the target concept, where the facet value support number refers to the number of objects corresponding to the facet value.

The fourth subsystem is used to record the user's query records, and return the largest common parent concept and the smallest common sub-concept of multiple historical query results as query recommendation; or perform query recommendation according to concept similarity.

In this system, the formal concept lattice adopts a static construction mode, a dynamic construction mode or a hybrid construction mode based on construction time prediction; the hybrid construction mode predicts the concept construction time according to the facet value set, if it is less than a preset time threshold, The dynamic mode is used to construct the formal concept lattice, and if it is greater than the preset time threshold, the static mode is used to construct the formal concept lattice.

Similarly, the faceted search system based on the formal concept lattice disclosed in this embodiment has the following beneficial effects:

On the one hand, in the process of constructing the formal concept lattice, the minimum concept is dynamically updated, and the complete formal background is avoided to be loaded in advance, which improves the flexibility of the algorithm.

On the other hand, each time an object is added, an update operation will be performed based on the standard generator on the basis of the original concept lattice to obtain a new concept lattice, which is simple, fast and reliable. The hash value calculation is used as an index, and all concepts are stored in the hash table, so that in the process of determining the standard generator, the standard generator is searched bottom-up in combination with the hash value of the calculated attribute set Y to effectively improve the standard generation. The query speed of the server is avoided, and redundant computation is avoided.

On the other hand, the present invention also parses the query conditions into attribute sets, and uses the leaf concept to match the minimum connotation including the attribute set from bottom to top, so that impossible routes can be quickly eliminated and the target concept can be found.

In addition, the faceted search technology of the present invention based on the formal concept lattice can realize the pre-calculation of the context relationship and facet information of the result set before the user searches, or to quickly calculate the facet information corresponding to the result at the same time of retrieval, which shortens the system time. The response time improves the user experience and reduces the user browsing cost.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (10)

1. A facet searching method based on formal concept lattices is characterized by comprising the following steps:

constructing a formal concept lattice, initializing a minimum concept lattice by using fake attributes fake _ attribute, adding an attribute set of an input object Obj into the connotation of the lattice when updating the concept lattice structure each time, and finally removing the fake _ attribute to obtain a complete and correct formal concept lattice; meanwhile, in the process of adding a new object in the form concept lattice, after an attribute set Y is input, a standard generator uniquely corresponding to the Y is obtained firstly, if the connotation of the existing concept of the concept lattice is equal to the Y, the Y does not generate a new concept, the new object is added into the extension of the concept related to the equal connotation of the new object, and the new object is added into the extension of all father concepts of the existing concept; if the concept lattice does not have the connotation of the existing concept equal to Y, a new concept is created, all candidate direct father concepts of the new concept are calculated according to the direct father concept of the standard generator, the real direct father concept is screened out, then the father-son relationship among the concepts is updated, and the new object is added into the extension of all the father concepts of the new concept;

building an index of leaf concepts in the formal concept lattice, the leaf concepts referring to immediate parents of a smallest concept in the formal concept lattice;

in the query process, the connotation of the concept corresponds to a query statement, and the extension of the concept corresponds to a result set; after a facet value set queried by a user is obtained, matching the minimum connotation containing an attribute set from bottom to top by utilizing leaf concepts in a constructed form concept lattice to find a target concept corresponding to the facet value set, and returning the extension corresponding to the target concept.

2. The method for faceted search based on formal concept lattice according to claim 1, further comprising:

all concepts are stored in a hash table by performing hash value calculation on the connotations of the concepts as indexes; in determining the criteria generator, the criteria generator is searched bottom-up in conjunction with the computed hash values of the set of attributes Y.

3. The facet searching method based on the formal concept lattice according to claim 1 or 2, wherein the formal concept lattice adopts a static construction mode, a dynamic construction mode or a hybrid construction mode based on construction time prediction; and the hybrid construction mode predicts the time consumed by the concept construction according to the facet value set, if the time consumed by the concept construction is less than a preset time threshold, the concept lattice is constructed in a dynamic mode, and if the time consumed by the concept construction is greater than the preset time threshold, the concept lattice is constructed in a static mode.

4. The method of claim 3, further comprising:

after the target concept is found, calculating the facet value support number corresponding to the target concept according to the context of the formal concept lattice, wherein the facet value support number is the number of objects corresponding to the facet value.

5. The method of claim 4, further comprising:

recording the query records of the user, and returning the maximum public father concept and the minimum public son concept of a plurality of historical query results as query recommendations; or performing query recommendation according to the concept similarity.

6. A faceted search system based on a formal concept lattice, comprising:

the system comprises a subsystem unification, a formal concept lattice, a minimum concept lattice and a concept lattice, wherein the formal concept lattice initializes the minimum concept lattice by using fake attributes fake _ attribute, adds an attribute set of an input object Obj into the connotation of the minimum concept lattice each time when a concept lattice structure is updated, and finally eliminates the fake _ attribute to obtain a complete and correct formal concept lattice; meanwhile, in the process of adding a new object in the form concept lattice, after an attribute set Y is input, a standard generator uniquely corresponding to the Y is obtained firstly, if the connotation of the existing concept of the concept lattice is equal to the Y, the Y does not generate a new concept, the new object is added into the extension of the concept related to the equal connotation of the new object, and the new object is added into the extension of all father concepts of the existing concept; if the concept lattice does not have the connotation of the existing concept equal to Y, a new concept is created, all candidate direct father concepts of the new concept are calculated according to the direct father concept of the standard generator, the real direct father concept is screened out, then the father-son relationship among the concepts is updated, and the new object is added into the extension of all the father concepts of the new concept;

wherein the subsystem is further configured to index leaf concepts in the formal concept lattice, the leaf concepts referring to direct parents of a smallest concept in the formal concept lattice;

the subsystem II is used for enabling the connotation of the concept to correspond to the query statement and the extension of the concept to correspond to the result set in the query process; after a facet value set queried by a user is obtained, matching the minimum connotation containing an attribute set from bottom to top by utilizing leaf concepts in a constructed form concept lattice to find a target concept corresponding to the facet value set, and returning the extension corresponding to the target concept.

7. The formal concept lattice based faceted search system according to claim 6, wherein said subsystem is further configured to: all concepts are stored in a hash table by performing hash value calculation on the connotations of the concepts as indexes; in determining the criteria generator, the criteria generator is searched bottom-up in conjunction with the computed hash values of the set of attributes Y.

8. The faceted search system according to claim 6 or 7 wherein said formal concept lattice employs a static construction mode, a dynamic construction mode, or a hybrid construction mode based on construction time prediction; and the hybrid construction mode predicts the time consumed by the concept construction according to the facet value set, if the time consumed by the concept construction is less than a preset time threshold, the concept lattice is constructed in a dynamic mode, and if the time consumed by the concept construction is greater than the preset time threshold, the concept lattice is constructed in a static mode.

9. The formal concept lattice-based faceted search system according to claim 8, further comprising:

and the subsystem III is used for calculating the facet value support number corresponding to the target concept according to the context of the formal concept lattice after the target concept is found, wherein the facet value support number is the number of objects corresponding to the facet value.

10. The formal concept lattice based faceted search system according to claim 9, further comprising:

the subsystem IV is used for recording the query records of the user and returning the maximum public father concept and the minimum public son concept of a plurality of historical query results as query recommendations; or performing query recommendation according to the concept similarity.

Images