Finding the Key Structure of Mechanical Parts with Formal Concept Analysis

Abstract

Aiming at the problem that the assembly body model is difficult to classify and retrieve (large information redundancy and poor data consistency), an assembly body retrieval method oriented to key structures was presented. In this paper, a decision formal context is transformed from the 3D structure model. The 3D assembly structure model of parts is defined by the adjacency graph of function surface and qualitative geometric constraint graph. The assembly structure is coded by the linear symbol representation of compounds in chemical database. An importance or cohesion as the weight to a decision-making objective on the context is defined by a rough set method. A weighted concept lattice is introduced on it. An important formal concept means a key structure, since the concept represents the relations between parts’ function surfaces. It can greatly improve the query efficiency.

1. Introduction and Problem Statement

Currently, engineering drawing retrieval is mainly text-based, which makes full use of spatial relationships and properties of components between these geometric elements. Berchtold and Kriegel [1] developed the S3 system, which is a text-based retrieval system and supports local similarity search. The S3 system mainly relies on matching the contour of the graphics, while the spatial relationships are ignored. Therefore, this search method is not suitable for complex graphics. Muller and Rigoll [2] put forward a new stochastic model retrieval method, using a pseudo 2D hidden Markov model (P2DHMM). This method only supports a simple graphic search, but it is not suitable for complex graphics. Park and Um [3] proposed a complex 2D mechanical parts drawing method based on the shape of the key features. It is difficult to handle a large number of engineering drawings because of the minimum geometric components and non-efficient matching algorithm.

The similarity computing is a key issue in the engineering drawings retrieval. It is closely related to feature extraction [4]. Wang and Jiang [5] studied a retrieval method based on graph matching. The method extracted features of the structures and the shapes. Then, the pattern matching problem was transformed into a graph and sub-graph isomorphism problem. Sub-graph isomorphism has been proven to be an NP-complete problem. The time complexity of the algorithm is relatively high, and the performance of the existing solution is unstable.

Zehtaban and Roller [6] developed a shape-based symbol code Opitz and a comprehensive similarity comparison toolbox by two different techniques for data retrieval. Opitz code structure is selected as the grouping technique to classify and regulate geometric information of the CAD model. One of the main challenges in this work is to accurately extract the GT code according to the request. Another challenge is the quality of the code generated by Opitz.

Xu and Dong [7] proposed a parts retrieval method based on similar structures. The parts geometry drawings are marked as functional surfaces. If they have a common edge, a common point or points on the edge, the functions surfaces are topologically connected. A 2D parts structure model is produced by the functional relations. They defined the “and” operation restricting common vertexes and common edges to construct a 3D parts structural model. The codes of parts structure drawings are generated by linear symbols draw representation of the chemical compound database. Through expressing the request using Boolean model of parts drawing sub-structure, matching the sub-structure code and branch structure codes, it is used to retrieve parts drawings. By comparing the overall structure codes of parts drawings with one of the 3D part model, the parts drawings model retrieval is accomplished. In this way, it is required that the user is familiar with the structures of the abstract codes. It is time-consuming and inefficient when dealing with complex and large quantities of engineering drawings.

The concept lattice theory (Formal Concept Analysis FCA) was first proposed by Wille in 1982 as a mathematical theory. Its core is the formal concepts based on the binary relations between objects and attributes in the formal context [8]. The object set, the attribute set, and binary relations between them are the three elements in the formal context. If the attribute set contains the condition attributes and decision attributes, this formal context is a decision formal context [9]. Concept lattice is becoming a powerful tool to study various decision-making problems since the decision formal context was presented by Zhang in 2005 [10]. Subsequently, various extended decision formal contexts are constantly proposed, such as: fuzzy decision formal context, the real value decision formal context, incomplete decision formal context, etc. [11,12,13,14,15]. The main purpose to propose the decision formal context is for decision analysis for relational data. Along this idea, Shao [16] and Qu et al. [15] studied the rules extraction problem of decision formal context using concept lattice. Wu et al. [11] proposed granulation rule mining methods of the decision formal context by means of granulation calculation. Recently, Li et al. [17] discussed theoretical framework construction problems to extract rules from the decision formal context, and a corresponding method is developed by using the discernibility matrix and Boolean function. The knowledge hidden in a decision formal context can compactly be unravelled in the form of implication rules.

It should be pointed out that, in the recent research on the concept lattice, it is usually assumed that all the intents are equally important, and all the nodes would be generated from the formal context. The consequence is that a large number of nodes would be generated, and hence more storage space occupation and longer building time consumption. (With the sharp increasing of the data to deal with, the amount of concept lattice node constructed from original formal context is enormous, accordingly, requiring the larger storage space and time. At the same time, users are not interested in all the intents composed of all the attribute sets. Furthermore, it takes more time to extract useful knowledge from them). Consequently, the user would take more time to extract knowledge in which he is interested from the overall concept lattice. Therefore, it becomes advantageous to introduce some weights into the intent to capture its importance. Since the value of the weight assigned to the intent quantifies its importance, the user does not need to investigate all the nodes but only those nodes he is interested in. As a result, the knowledge extraction can be accelerated, the storage space can be saved, and the time to get results can be shortened. This is the underlying idea that motivates researchers to propose a weighted concept lattice [10]. This construct inherits a structure of general concept lattices while facilitates extraction of interesting knowledge. In many situations, it is apparent that the attributes are quite different from each other when it comes to their relevance and usefulness in knowledge acquisition. For example, we note that people are more interested in recent transaction data than the past ones. In [18], Zhang et al. introduced a virtual node into the frequent weighted concept lattice (FWCL) to ensure that FWCL is retained to be complete, which is to preserve the existence of each nodes’ infima and suprema in the FWCL. Some theories were provided for further applications of the weighted concept lattice [19,20].

There is a lot of research on concept lattice in graph data mining [21,22], especially using stable emerging molecular patterns and mining convex polygon patterns [23,24]. Exponential explosion makes it difficult to consider the whole concept lattice arising from data; one needs to select the most useful and interesting concepts. In [25], interestingness measures of concepts are considered and compared with respect to various aspects, such as efficiency of computation and applicability to noisy data and performing ranking correlation. A cohesion function is based on the pairwise similarity of objects from an extent.

In Ref. [7], the geometric graph of part engineering drawing is labeled as functional surface. The functional surface which is attached topologically is determined according to the fact that, whether they are in the common edge, or whether they have concurrent or point in the edge, and further the position relationship between functional surfaces is decided. The model retrieval is realized via 3D structure code matching of part engineering drawing and part 3D model.

The present work aims to give a comprehensive study on the application of weighted concept lattice in finding the key structure of mechanical parts. In Section 2, the 3D structural model of the parts and its coding were derived. This derivation naturally leads to a new set of the functional surfaces. In Section 3, a direct mapping method from parts drawing structure model to FCA was considered. Identifying important formal concepts was made in this section. In Section 4, an algorithm to find the key structure was proposed, and some examples were applied to demonstrate the new method. In Section 5, some conclusions were given.

2. Structure Model of Parts

The structural models of part drawings shown in [7] are based on functional surfaces. Basic types of functional surface are planar, cylindrical, conical surface, spherical, and holes. Capital letters $P,C,H$, and S represent the planar, cylindrical surfaces, holes and slots, respectively. Lowercase $w,k,h$, and r denote the threaded connection, flat key connection, semi-rotary surface, and ring structures.

Figure 1, Figure 2 and Figure 3 show a few parts and its function surface views.

The positional relation between the function surfaces can be represented by vector position relations, including orientation and field relations (see [7]).Topological relations between functional surfaces are represented by concave-convex connection edges: concave side with “0” mark, and the convex with “1”. If the two connected surfaces are revolution ones, the topology can be divided into inner and outer surfaces and use the “!” mark. It can be judged whether the functional surfaces of the part drawings are topologically connected according to three criteria: they have a common edge, a common point, or points in the side. Its basic uses include orientation and domain. The orientation is defined by vectors of geometric space: parallel (||), coaxial (⊙), vertical (⊥), and skew (∠). The domain refers to the relations between the areas that functional surfaces occupy.

Table 1. Binary field relations between the functional surfaces.

			Coaxial	Parallel			Vertical
Meaning	separate	meet	overlapping	common	amidst	middle	intersect	biased
mark	s	m	o	c	d	i	i	b
icon

shows the domain relations [7]. The length of the area occupied by the surface of the plane function is 0; therefore, face encounter, overlap, and concurrent are merged into encounters between plane and revolution surfaces. The binary relations between two vertical planes are not defined and marked with the “!” mark. Sign “!♯” represents two functional surfaces being topologically connected, and the symbol “♯” indicates that the topology is not connected. The symbol “?” indicates that the positional relations between the surface features cannot be determined by a single view. The field relations are shown as Table 1.

The part drawings structural model can be labeled based on the functional surfaces, according to the geometric conditions of their topology connection and a method of determining their positional relations. For example, Figure 4 and Figure 5 are the structural models of Figure 1 and Figure 2.

3. Theory and Method

3.1. Structure Model of Part Drawings Mapping to Concept Lattice

As described above, the main component of the part drawings 3D structural model is the functional surface and their positions. If they are considered as the objects and the attributes, we can build the formal context of the part drawings structure, and then build the concept lattice.

Because the position is for the functional surface of the part, we use “Source” to represent the functional surface of the part, and “Target” to represent the position. Let Source, Relation, and Target be three components of $PG$ (Parts Graph) with g.source, g.relation and g.target, respectively, the I constitutes (Object, Attribute) sets of the formal context. A formal context consists of a set of objects (g.source), a set of attributes (g.relation and g.target), and a binary relation I that indicates the attributes possessed by each object. There is $g\in G⟹$ (g.target, g.source∼ g.relation) $\in I$. Mapping it makes $PG$’s relations target become a transfer of another relation’s source concept $CG$ (Concept Graph). This transfer generates implicit map reasoning.

The algorithm works in the following sequence: First, MovingTarget and FixedTarget for each triples are initialized. Second, it calls FormBinaries through all triples iteration. Third, a corresponding formal concept pair (Object, Attribute) is formed. Each time, MovingTarget matches one target concept of the triples. Binary conversion is formed by a recursive call FormBinaries, setting MovingTarget for the current source concept, leaving FixedTarget unchanged.

Using the Algorithm 1, we can get the formal context of part model as shown in

Table 2. The formal context of 3D structure model in Figure 6.

	$1\perp \mathit{i}$	$1\perp !$	$\mathit{l}\Vert \mathit{m}$	$1\odot \mathit{s}$	$1\odot \mathit{m}$	$♯\Vert \mathit{s}$	$♯\mathit{\perp }!$	$♯\mathit{\angle }\mathit{i}$
$C_{h1}$	1	0	0	1	0	0	0	0
$C_{h2}$	1	0	0	1	0	0	0	0
$H_3$	0	0	1	0	0	0	0	0
$H_4$	0	0	1	0	0	0	0	0
$H_5$	0	0	1	0	0	0	0	0
$H_6$	0	0	1	0	0	0	0	0
$H_7$	0	0	1	0	0	0	0	0
$P_1$	1	1	1	0	0	1	0	0
$P_2$	0	1	0	1	1	0	0	0

.

Algorithm 1: A mapping algorithm.

begin

foreach $g\in G$ do

FormBinaries(g.target, g.source);

end

FormBinaries(FixedTarget, MovingTarget)

begin

foreach $g\in G$ do

if g.target = MovingTarget then

Attribute⟵g.source∼g.relation;

Object⟵FixedTarget;

$I⟵\cup \{$(Object, Attribute)};

FormBinaries(FixedTarget, g.source);

end

According to the functional group, for example, group by functional surface of cylinder, hole, plane, and slot, $D_1=\{C_{h1},C_{h2}\},D_2=\{H_3,H_4,H_5,H_6,H_7\},D_3=\{P_1,P_2,P_3,P_4,P_5,P_6\},D_4=\{H_{w1},H_{w2},H_{w8},H_{w9}\}$, we can get a decision formal context as described below.

3.2. Weighted Concept Lattice Based on Decision Formal Context

Due to space limitations, we assume that readers are familiar with the basic concepts of formal concept analysis [8].

A formal context can be depicted visually in a tabular form with crosses (or 1) representing the pairs $(g,m)\in I$. For example, consider the cross table in

Table 3. A tabular form, or cross table, with $U=\{1,2,3,4,5\}$ and $A=\{a,b,c,d,e\}$. The relation I is indicated by the set of crosses in the table.

$(\mathit{g},\mathit{m})$	a	b	c	d	e
1	×		×
2	×
3		×	×	×
4	×	×
5		×	×	×	×

.

The cross table in Table 3 depicts a formal context in which object 1 has attributes a and c, object 2 has attribute a, etc.

Let $(U,A,I)$ be a formal context. A set pair $(X,B)$ of $(U,A,I)$, $X\subseteq U,B\subseteq A$ is a formal concept if and only $X^{\uparrow }=B$ and $B^{\downarrow }=X$, where $X^{\uparrow }=\{a\in B|x\in X:(x,a)\in I\},B^{\downarrow }=\{x\in X|a\in B:(x,a)\in I\}$ are common attributes set of all the objects in X and common objects set of all attributes in B, respectively. The set of all formal concepts in $(U,A,I)$ is expressed as $\mathcal{B}(U,A,I)$. Partial order ⪯ of super-concept and sub-concept in $\mathcal{B}(U,A,I)$ constitutes the concept lattice of $(U,A,I)$.

Figure 7 is the formal concept lattice of the formal context shown in Table 2.

The formal context is the basis of formal concept analysis. Its main objective is to form concepts and concept lattice: The concept is unity of the extension and intension. In essence, the concept lattice describes the link between objects and attributes, indicating generalization relations between concepts, The corresponding Hasse diagram is achieved for data visualization. The traditional concept lattice is based on a simple binary context. In practical application, the data are large and complex. Thus, we must extend it. Belohlávek et al. studied the concept lattice in fuzzy and uncertain data [26,27]. The critical part of concept lattice (called core concepts or important concepts) is an important part of the parts structure. As a user is usually interested in some certain attribute characteristics, according to his/her preference and requirement, the researchers establish a new concept lattice structure with the weight $w(0\le w\le 1)$ to identify importance of intentions: weighted concept lattice [10].

Example 1.

Table 4. A formal context.

	E	F	G	K	L
1	×		×
2		×	×	×
3	×	×
4	×	×	×	×
5	×
6	×
7		×			×

is a formal context. Its object set U, attribute set A, and I describe the value set of attribute in A that U has.

Table 5. Weight table of single attribute intent.

A	W
E	0.1
F	0.2
G	0.7
K	0.9
L	1

is the weight table of a single attribute intent.

($\left\{1\right\},\{F,L\}$,0.6) and ($\left\{2\right\},\{F,G,K\}$,0.6) are the weighted formal concept formed by the above formal context and single attribute intent weight table. All such formal concepts constitute the weighted concept lattice.

Let $K_w=(U,A,I,W)$ be a formal context and a set of attributes is denoted by $A=\{a_1,a_2,\cdots ,a_n\}$. $W=\{w_1,w_2,\cdots ,w_n\}$ are the weights of attributes, where $w_i\in W(0\le w_i\le 1)$ denotes the importance of the attribute $a_i$. $(X,B,w)$ is known as a weighted formal concept on $(U,A,I,W$) if $(X,B)$ is a formal concept and $w=W\left(B\right),w$ is the weight of the attribute set $B,0\le w_i\le 1$. A and B are the extent, the intent of weighted formal concepts, respectively. Its super-concept and sub-concept are the same as the general concept lattice.

Given a value $\theta \in V$, we can obtain a part of the formal concept $\mathcal{B}(U,A,I)$, ${\mathcal{B}}_{\theta }(U,A,I)=\{(X,B)\in \mathcal{B}(U,A,I,W)|w\ge \theta \}.{\mathcal{B}}_{\theta }(U,A,I)$ can be seen as a set of important formal concepts.

Definition 1.

[28] Let $(U,A,I)$ be a formal context, $B\subseteq A$.$f_B\left(x\right)=\{a\in B|x{I}_{B}a\}$ is called an attribute set x in B for $x\in U.g\left(a\right)=\{x\in U|xIa\}$ is called an object set of attribute a for $a\in B$.

Definition 2.

[9] A decision formal context is defined as a quintuple $(U,A,I,D,J)$, where $(U,A,I)$ and $(U,D,J)$ are two formal contexts in which their attribute sets are disjoint. A and D are called condition and decision attribute sets, respectively.

Definition 3.

In a decision formal context $(U,A,I,D,J),B\subseteq A$, if $R_B=\{(x,y)\in U\times U|f_a\left(x\right)=f_a\left(y\right),\forall a\in B\}$ and $R_D=\{(x,y)\in U\times U|f_d\left(x\right)=f_d\left(y\right),\forall d\in D\}(R_B$ and $R_D$ are called the indiscernibility relation determined by the condition and decision attribute, respectively), then ${\left[x\right]}_B=\{y\in U|(x,y)\in R_B\}=\{y\in U|f_a\left(x\right)=f_a\left(y\right),\forall a\in B\}$ is denoted as the equivalence class of object x on B. ${\left[x\right]}_D=\{y\in U|(x,y)\in R_D\}=\{y\in U|f_d\left(x\right)=f_d\left(y\right),\forall d\in D\}$ is the equivalence class of object x on D.

Definition 4.

Let X be a subset of U, $B\subseteq A$.

(1)The lower approximation of X with respect to B is the set of all objects, which can be for certain classified as X with respect to B and it is denoted by ${\underline{R}}_{\underline{B}}\left(X\right)$. That is, ${\underline{R}}_{\underline{B}}\left(X\right)=\{x\in U|{\left[x\right]}_B\subseteq X\}$.

(2)The upper approximation of X with respect to B is the set of all objects, which can be possibly classified as X with respect to B and it is denoted by ${\overline{R}}_B\left(X\right)$. That is, ${\overline{R}}_B\left(X\right)=\{x\in U|{\left[x\right]}_B\cap X\ne \varnothing \}$.

Definition 5.

Let $(U,A,I,D,J)$ be a decision formal context. If $R_A\subseteq R_D$, then we say $(U,A,I,D,J)$ is consistent.

Definition 6.

In $(U,A,I,D,J)$, the lower approximation on the condition attribute B of the decision attribute $Dj$ is ${\underline{R}}_{\underline{B}}\left(D_j\right)=\{x\in U|{\left[x\right]}_B\subseteq D_j\}$. The positive domain of B at the decision-making objective is defined as $PO{S}_B\left(\delta \right)={\cup }_{j\le r}{\underline{R}}_{\underline{B}}\left(D_j\right).j=\{1,2,\cdots ,r\}$ indicates that there are r decision-making objectives.

Theorem 1.

Let $(U,A,I,D,J)$ be consistent, $R_B\subseteq R_D\iff PO{S}_B\left(\delta \right)=PO{S}_A\left(\delta \right)$.

Proof. 

If $R_B\subseteq R_D$, then, for any $D_j$, we have ${\underline{R}}_{\underline{B}}\left(D_j\right)=D_j(j\le r)$. Since $(U,A,I,D,J)$ is consistent, it follows that $R_A\subseteq R_D$. Then, there exists ${\underline{R}}_{\underline{A}}\left(D_j\right)=D_j(j\le r)$ such that $PO{S}_B\left(\delta \right)=PO{S}_A\left(\delta \right)$.

If $PO{S}_B\left(\delta \right)=PO{S}_A\left(\delta \right)$, then, for ${\underline{R}}_{\underline{B}}\left(D_j\right)\subseteq {\underline{R}}_{\underline{A}}\left(D_j\right)(j\le r)$ and ${\underline{R}}_{\underline{A}}\left(D_j\right)=D_j,D_i\cap D_j=\varnothing (i\ne j)$, it is clear that ${\underline{R}}_{\underline{B}}\left(D_j\right)={\underline{R}}_{\underline{A}}\left(D_j\right)$. We have ${\underline{R}}_{\underline{B}}\left(D_j\right)=D_j(i\le j)$. Consequently, $R_B\subseteq R_D$. □

Theorem 2.

If $(U,A,I,D,J)$ be consistent, then a is a core(No-remove attributes)$\iff PO{S}_A\left(\delta \right)\ne PO{S}_{A-\{a\}}\left(\delta \right)$.

Proof. 

It follows immediately from Theorem 1. □

Definition 7.

For a decision formal context $F=(U,A,I,D,J)$, let $(X,B)$ be a formal concept of F. The importance of the decision-making objective δ with $(X,B$) is defined as follows:

$${\eta }_{(X,B)}\left(\delta \right)=\frac{\left|POSB\right(\delta \left)\right|}{\left|D_j\right|}=\frac{{\cup }_{(i\le j)}\left|{\underline{R}}_B\left(D_j\right)\right|}{\left|D_j\right|}$$

(1)

It is obvious that $0\le {\eta }_{(X,B)}\left(\delta \right)\le 1$.

Example 2.

A formal context of part as

Table 6. A formal context of the part.

	$!\perp \mathit{b}$	$1\perp \mathit{b}$	$0\odot \mathit{m}$	$♯\odot \mathit{s}$	$1\Vert \mathit{m}$
$C_1$	1	1	1	0	0
$C_2$	0	1	1	0	0
$C_3$	1	0	0	0	0
H	0	0	0	0	1
$P_1$	0	0	1	1	0
$P_2$	0	0	1	1	0
$P_3$	0	1	0	0	1
$P_4$	0	1	0	0	0

, and $D_1=\{C_1,C_2,C_3\},D_2=\left\{H\right\},D_3=\{P_1,P_2,P_3,P_4\}$. Its formal concept lattice is shown as Figure 8.

Computing the importance of concepts: ${\eta }_{(\{C_1,C_3\},\{!\perp b\})}\left(\delta \right)=2/3,{\eta }_{(\{C_1,C_2,P_1,P_2\},\{0\odot m\})}\left(\delta \right)=0,{\eta }_{(\{C_1,C_2,P_3,P_4\},\{1\perp b\})}\left(\delta \right)=0,{\eta }_{(\{P_1,P_2\},\{♯\odot s,0\odot m\})}\left(\delta \right)=2/4,{\eta }_{(\left\{C_1\right\},\{!\perp b,1\perp b,0\odot m\})}\left(\delta \right)=1/3,{\eta }_{(\{C_1,C_2\},\{1\perp b,0\odot m\})}\left(\delta \right)=2/3$.

In the decision formal context, cohesion of the equivalence classes determined by the condition attributes and decision attributes indicates that the condition attributes impact decision-making, namely the importance of attributes. Next, we will compare attributes of the concept to study the cohesion of the concept to objects (functional surfaces).

The similarity of attributes $b_1$ and $b_2$ can naturally be assessed by the similarity of their corresponding extents, i.e., similarity of ${\left\{b1\right\}}^{\downarrow }$ and ${\left\{b2\right\}}^{\downarrow }$. That is, the similarity measure between attributes $b_1$ and $b_2$ is given by

$$sim(b_1,b_2)=sim({\left\{b_1\right\}}^{\downarrow },{\left\{b_2\right\}}^{\downarrow })$$

(2)

In our experiments, we use the following functions for $sim$ on the decision formal context $(U,A,I,D,J)$:

$sim(B_1,B_2)=\frac{|{\underline{(B_1^{\downarrow }\cap B_2^{\downarrow })}}_D|}{|B_1^{\downarrow }\cup B_2^{\downarrow }|}$, where ${\underline{(B_1^{\downarrow }\cap B_2^{\downarrow })}}_D$ is the lower approximation of in the decision attribute D. In particular,

(1) If $B_1=B_2$ and $\left|B_1\right|=\left|B_2\right|=1$, then $sim(B_1,B_2)=\frac{|{\underline{\left(b_1^{\downarrow }\right)}}_D|}{|b_1^{\downarrow }|},b\in B_1,B_2$;

(2) If $R_D=U$, then $sim(B_1,B_2)=\frac{\left|\right(B_1^{\downarrow }\cap B_2^{\downarrow }\left)\right|}{|B_1^{\downarrow }\cup B_2^{\downarrow }|}$. It produces a computing formula for the general formal context.

Note that $sim$ is the number of objects that belong to both $B_1,B_2$ and $D^{\prime }s$ classes divided by the number of all attributes that belong to $B_1$ or $B_2$.

Definition 8.

Cohesion $coh(X,B)$ for a formal concept $(X,B)\in B(U,A,I)$ on the decision formal context $(U,A,I,D,J)$ is defined as the following:

$$coh(X,B)=\left\{\begin{array}{cc}{\displaystyle \frac{{\sum }_{(b_i,b_j)\subseteq B,b_i\ne b_j}sim(b_i,b_j)}{\left|B\right|\left(\right|B|-1)/2}}\hfill & \left|B\right|\ne 1\hfill \\ {\displaystyle \frac{\left|X\right|}{\left|U\right|}}\hfill & \left|B\right|=1,X\subseteq D_i\hfill \\ 0\hfill & \left|B\right|=1,X⊈D_i\hfill \end{array}\right.$$

(3)

Theorem 3.

The $coh(X,B)$ satisfies:

(1) $0\le sim(b_i,b_j)\le 1$;

(2) For a formal concept $(X,B)$, if ${\underline{({\left\{b_k\right\}}^{\downarrow }\cap {\left\{b_l\right\}}^{\downarrow })}}_D\ne \varnothing$ and ${\underline{({\left\{b_k\right\}}^{\downarrow }\cap {\left\{b_l\right\}}^{\downarrow })}}_D=D_i,k,l\in \{1,2,\cdots ,|B\left|\right\}$, then $Max\left(sim({\left\{b_i\right\}}^{\downarrow },{\left\{b_j\right\}}^{\downarrow })\right)=sim({\left\{b_k\right\}}^{\downarrow },{\left\{b_l\right\}}^{\downarrow }),i,j=1,2,\cdots ,\left|B\right|$.

(3) For a formal concept $(X,B)$, if $X\ne \varnothing$, $X\subseteq D_i$ and $k,l\in \{1,2,\cdots ,|B\left|\right\},(\underline{{\left\{b_k\right\}}^{\downarrow }}\cap \underline{{\left\{b_l\right\}}^{\downarrow }})\subseteq A$, then $coh(X,B)\ne 0$.

Proof. 

(1) Obviously, ${\underline{(B_i^{\downarrow }\cap B_j^{\downarrow })}}_D\subseteq B_i^{\downarrow }\cap B_j^{\downarrow }\subseteq B_i^{\downarrow }\cup B_j^{\downarrow }$; therefore, the conclusion holds.

(2) In fact, for $b_i,b_j\in B,i,j=1,2,\cdots ,\left|B\right|,sim({\left\{b_i\right\}}^{\downarrow },{\left\{b_j\right\}}^{\downarrow })=|{\underline{({\left\{b_i\right\}}^{\downarrow }\cap {\left\{b_j\right\}}^{\downarrow })}}_D|/|{({\left\{b_i\right\}}^{\downarrow }\cup {\left\{b_j\right\}}^{\downarrow })}_D|$, there exist only two cases ${\underline{({\left\{b_i\right\}}^{\downarrow }\cap {\left\{b_j\right\}}^{\downarrow })}}_D\subset D_i,{\underline{({\left\{b_i\right\}}^{\downarrow }\cap {\left\{b_j\right\}}^{\downarrow })}}_D=D_i$, hence, $Max\left(sim({\left\{b_i\right\}}^{\downarrow },{\left\{b_j\right\}}^{\downarrow })\right)=sim({\left\{b_k\right\}}^{\downarrow },{\left\{b_l\right\}}^{\downarrow }),i,j=1,2,\cdots ,\left|B\right|$.

(3) Since $(\underline{{\left\{b_k\right\}}^{\downarrow }}\cap \underline{{\left\{b_l\right\}}^{\downarrow }})\subseteq X,k,l\in \{1,2,\cdots ,|B\left|\right\},X\subseteq D_i$, it follows from Definition 8 that $\underline{{\left\{b_k\right\}}^{\downarrow }}\cap \underline{{\left\{b_l\right\}}^{\downarrow }})\subseteq D_i,{\underline{({\left\{b_k\right\}}^{\downarrow }\cap {\left\{b_l\right\}}^{\downarrow })}}_D\ne \varnothing ,sim({\left\{b_k\right\}}^{\downarrow },{\left\{b_l\right\}}^{\downarrow })\ne 0$. Thus, $coh(X,B)\ne 0$. □

Example 3.

Table 7. A decision formal context.

	a	b	c	d	e	f	g	h	k
$x_1$	1	0	1	1	1	0	1	0	1
$x_2$	1	0	1	0	0	0	1	0	1
$x_3$	0	1	0	0	1	1	0	1	0
$x_4$	0	1	0	0	1	1	0	1	0
$x_5$	1	0	0	0	0	0	0	0	1
$x_6$	1	1	0	0	1	1	0	1	1

is a decision formal context, where $U=\{x_1,x_2,x_3,x_4,x_5,x_6\}$ is the object set, $A=\{a,b,c,d,e,f\}$ is the condition attribute set. $D=\{g,h,k\}$ is the decision attribute set.

$D_1=\{x_1,x_2\}$, $D_2=\{x_3,x_4\}$, $D_3=\left\{x_5\right\}$, $D_4=\left\{x_6\right\}$. $coh(\{x_1,x_2,x_5,x_6\},\left\{a\right\})=0$, $coh(\{x_1,x_3,x_4,x_6\},\left\{e\right\})=0$, $coh(\{x_1,x_2\},\{a,c\})=1/2$, $coh(\{x_1,x_6\},\{a,e\})=0$, $coh(\{x_3,x_4,x_6\},\{b,e,f\})=0$, $coh(\left\{x_1\right\},\{a,c,e,d\})=17/60$, $coh(\left\{x_6\right\},\{a,b,e,f\})=1/18$.

A simple approach to measure the cohesion $coh(X,B)$ for a formal concept $(X,B)\in \mathcal{B}(U,A,I)$ is the following if $R_D=U$:

$$coh(X,B)=\left\{\begin{array}{cc}{\displaystyle \frac{{\sum }_{(x_i,x_j)\subseteq X,x_i\ne x_j}sim(x_i,x_j)}{\left|X\right|\left(\right|X|-1)/2}}\hfill & \left|X\right|\ne 1\hfill \\ {\displaystyle \frac{|X^{\uparrow }|}{\left|A\right|}}\hfill & \left|X\right|=1\hfill \end{array}\right.$$

(4)

Definition 9.

Let $(U,A,I,D,J)$ be a decision formal context. $(X,B,w)$ is a triple on $(U,A,I,D,J)$. If $(X,B)$ is a formal concept, $w={\eta }_{(X,B)}\left(\delta \right)$ or $w=coh(X,B)$ is the weight of attribute set B and $0\le w\le 1$. $(X,B,w)$ is called the weighted concept of $(U,A,I,D,J)$. The set $\mathcal{B}(U,A,I,D,J)$ consisting of all of these concepts is the weighted concept lattice of $(U,A,I,D,J)$.

Its formal concept lattice is as Figure 9. Here, the black is an important concept.

4. An Algorithm Getting the Part Key Structure and Examples.

For a formal context transformed from the part drawings structure model, the formal concept is a set pair of the positional relations (the attributes) and function surfaces (the objects). The decision attribute can be seen as the division in which experts think the function surfaces have the same properties (In other words, these functional surfaces play the same role in the part assembly structure). Thus, if given the importance or cohesion value of the concept, to determine important concepts, we can get the part key structure.

In order to verify the validity of the proposed method, five part drawings structure models [7] were calculated individually. Transformed concept lattice and the concept’s extension, intent, and weights are listed below, where concept lattice nodes are denoted by $(X,B),w=1/2$. The weight value marked in red in the table is the key structure (critical concept). If the weight values are all less than $\alpha$, the key structure is the concept node in which w is the closest to $\alpha$ (As shown in

Table 8. The $Coh$ value of a double bond set.

X	B	$\mathit{coh}(\mathit{X},\mathit{B}){\mathit{w}}_{\mathit{i}}$
$P_1,P_2,P_3,C_1,C_4,C_{k2}$	$0\odot m$	47/90
$C_{k2},C_{k3}$	$♯\odot 0$	1/4
$H,C_{k3}$	$!\perp i$	1/2
$P_2,P_3$	$0\odot m,♯\odot s$	1
$P_1,C_{k2}$	$1\odot m,0\odot m$	2/3
$C_{k2}$	$♯\odot 0,1\odot m,0\odot m$	3/5
$C_{k3}$	$♯\odot 0,!\perp i$	2/5

,

Table 9. The $Coh$ value of a sets of cylinder.

X	B	$\mathit{coh}(\mathit{X},\mathit{B}){\mathit{w}}_{\mathit{i}}$
$P_2,C_2$	$0\odot m$	1/2
$P_1,H_1$	$1\odot m$	1/3
$P_3,C_{w3}$	$0\odot s$	1/2
$P_1,C_1$	$1\odot s$	1/4
$C_1,C_2,H_1,H_2$	$!\perp i$	13/36
$C_1,P_3$	$♯\odot s$	1/4
$C_2$	$0\odot m,!\perp i$	1/3
$H_1$	$1\odot m,!\perp i$	1/3
$P_1$	$1\odot s,1\odot m$	1/3
$C_1$	$♯\odot s,!\perp i,1\odot s$	1/2
$P_3$	$♯\odot s,0\odot s$	1/3

,

Table 10. The $Coh$ value of a fork.

X	B	$\mathit{coh}(\mathit{X},\mathit{B}){\mathit{w}}_{\mathit{i}}$
$C_2,P_3,P_4$	$1\parallel m$	2/3
$C_1,P_1,P_2$	$1\odot s$	5/9
$C_1,C_2$	$♯\parallel c$	1/4
$H,C_1$	$!\perp i$	1/3
$C_1$	$!\perp i,1\odot s,♯\parallel c$	3/4
$C_2$	$1\parallel m,♯\parallel c$	1/2

,

Table 11. The $Coh$ value of a tray.

X	B	$\mathit{coh}(\mathit{X},\mathit{B}){\mathit{w}}_{\mathit{i}}$
$P_1,P_3,H_3,H_1$	$1\parallel m$	5/9
$H_3,H_2$	$1\odot s$	2/3
$H_3,H_2,P_1,C_1$	$♯\perp b$	1/2
$P_1,P_2$	$1\perp !$	1/3
$P_1,H_3$	$1\parallel m,♯\parallel b$	2/3
$P_1$	$1\parallel m,♯\perp b,1\perp !$	3/4
$H_3$	$1\odot s,♯\perp b,1\parallel m$	3/4
$H_2,H_3$	$1\odot s,♯\perp b$	2/3

and

Table 12. The $Coh$ value of a gear unit housing.

X	B	$\mathit{coh}(\mathit{X},\mathit{B}){\mathit{w}}_{\mathit{i}}$
$H_3,H_4,H_5,H_6,P_1,P_4,P_5,H_7,H_{w8}$	$1\parallel m$	1361/2160
$C_{h1},C_{h2},P_2,P_3$	$1\odot s$	1/2
$C_{h1},C_{h2},P_1$	$1\perp i$	1/2
$P_1,P_2,P_3$	$1\perp i$	4/9
$P_2,P_3,P_6,H_{w9}$	$1\odot m$	7/18
$P_1,P_4$	$♯\parallel s,1\parallel m$	2/5
$P_4,P_6$	$♯\perp !$	1/4
$H_{w8},H_{w9}$	$♯\angle i$	1/3
$C_{h1},C_{h2}$	$1\odot s,1\perp i$	1
$P_1$	$1\perp i,1\perp !,♯\parallel s,1\parallel m$	1/2
$P_2,P_3$	$1\odot s,1\perp !,1\odot m$	1
$P_6$	$♯\perp !,1\odot m$	1/4
$P_4$	$♯\perp i,♯\parallel s,1\parallel m$	3/8
$H_{w9}$	$1\odot m,♯\angle i$	1/4
$H_{w8}$	$1\parallel m,♯\angle i$	1/4

and Figure 10, Figure 11, Figure 12, Figure 13 and Figure 14).

5. Experiments

In order to verify the effectiveness of the method proposed in this paper, the author calculated and compared 7 of the 11 part engineering drawing structural models in Ref. [7]. Here, we set the node of any concept lattice as $(X,B)$. If $\alpha =0$, w is taken as the maximum value, and the important concepts, and key structures of the three-dimensional part structure model as shown in

Table 13. Important concepts and key structures of the 3D parts structural model.

Model Name	Important Concept	Key Structure
$Trimmingscrew$	$(\{C_1,H\},\{!\perp i\})$	[Cow]$♯\odot sCo-0\odot sP♯\odot sP-0\odot s$[Cow]$♯\odot sCo-!\perp iH$
$Rodshaft$	$Uncertain$
$Pendulumshaft$	$(\{C_1,C_2,P_2\},\{1\perp b\})$	$P(-1\perp bCo-1\odot mP-0\odot sCo)(-1\perp bCo-1\odot dSro)-1\odot sCi$
$Waveguideswitchrotor$	$(\{C_2,C_3,P_2,P_3\},\{0\odot m\}$	$P\left[1\right](-1\odot mCo(-1\odot mP(-0\odot mCo-1\odot mP-0\odot mCo-1\perp bP)(-1\parallel mH)-!\parallel cCi\left[1\right]-1\parallel m)(-1\parallel mCo)-1\parallel m\left[Hw\right]$
$Doublekeysleeve$	$(\left\{C{k}_3\right\},\{♯\odot 0,!\perp i\}),(\{C{k}_3,H\},\{!\perp i\}),(\{P_2,P_3\},\{♯\odot s\}),(\{C{k}_2,C{k}_3\},\{♯\odot 0\}),(\{P_1,C{k}_2\},\{l\odot m\})$	$\left[Cok\right](-1\odot mP-0\odot mCo)(-0\odot mP♯\odot sP-0\odot mCo)♯\odot o\left[Cik\right]-!\perp i[H::l_2]$
$Pullfork$	$(\left\{C_2\right\},\{1\parallel m\}),(\{C_1,P_1,P_2\},\{1\odot s\}$	$Ci(-1\odot sP)(-1\odot sP)(-!\perp iH)♯\parallel cCi(-1\parallel mP)-1\parallel mP$
$Bracket$	$(\{H_2,H_3\},\{1\odot s\}),(\left\{P_1\right\},\{1\perp !\})$	$P(-1\perp !P)(-1\parallel mH)♯\perp bCi\left[1\right]♯\perp bH(-1\parallel mP)-\odot s\left[Hw\right]\left[1\right]♯\perp b$

can be obtained.

The code of “key structure” in the table is the part drawing structure code from Ref. [7], and the part with red is the key structure calculated by the Algorithm 2 in this paper. From Table 13, it can be seen that, for most parts, the method in this paper can not only determine the important position relation (important intent), but also determine the functional surface (concept object) that constitutes this relationship, and then determine the key structure of parts. Of course, for completely symmetrical parts without “characteristics”, this method also shows limitations (such as pull rod shaft). The reason is that, in these problems, the weight of position relation (concept intent) is exactly the same; that is to say, the information provided by the part drawing itself is not enough to distinguish it. Therefore, as long as the designer provides further information, this problem will be solved.

Algorithm 2: cAn algorithm of the part key structure with concept lattice searching.

Input $(U,A,I,D,J)$ and $\alpha$

begin

foreach $(X,B)\in \mathcal{B}(U,A,I)$ do

Computing w by (1)or (4),compare w and $\alpha$

if $w<\alpha$ then next $(X,B)$;

else

$(X,B)$ is a key structure;

end

Two parts models were selected and searched in Visual C + +, ACIS, HOOPS and the part library (a total of 9010) of the self-developed mechanical parts retrieval system. The CPU of the computer is Intel 3.30 GHz, and the memory is 4.0 GB.

Table 14. The parts and time consuming that are similar to the model in the model base(I).

Model	Time (s)	001	002	003	004	005	006	007
	This method 18.137
	Ref. [7] method 26.334

and

Table 15. The parts and time consuming that are similar to the model in the model base(II).

Model	Time (s)	008	009	010	011	012	013	014
	This method 31.072
	Ref. [7] method 38.256

are the results of the two methods.

6. Conclusions

This paper has developed a novel scheme for 3D mechanical structure model retrieval. A 3D model is converted into a formal context with the object as the functional surface, and the attribute indicating the positional relations between the functional surfaces. Each concept node contains a topological graph corresponding to the structure that it represents. Integrating the topology and feature structure signatures in FCA not only solves the feature interaction problem, but also accelerates the search process. Due to the significant reduction of the structure number, the graph comparison required in the similarity assessment can be finished in a polynomial time.

This work can be further improved. For example, the structure should consider engineering attributes such as tolerance, fit, and other design descriptions, so that it can capture the user’s intent more accurately. In addition, AI techniques (e.g., fuzzy set, nonlinear neural network) can be applied to determine the weighting factors in our approach more systematically. It ensures that the search scheme properly reflects the user’s intent. Our current research is focused on this.

7. Patents

Qiang Wu: The method and system of key structure modeling of equipment parts based on Weighted Concept Lattice. ZL201610884995.1.