A Diagnosability-Integrated Design Approach Based on Graph Theory

Abstract

In order to take into account the influence of both system structure and diagnosis algorithm in the diagnosability design of the system, a diagnosability-integrated design method based on graph theory was proposed in this paper. Firstly, based on the diagnosability evaluation results, the difficulty of fault diagnosis was qualitatively analyzed using the K-means method, and the diagnosis plot of measurement point was drawn based on the analysis results. Secondly, the Bron–Kerbosch algorithm was used to extract the maximal cliques from the diagnosis plot of measurement point and determine the set of maximal cliques that can diagnose faults in the system based on the hypergraph edge coverage theorem. Finally, a cascade classifier was set on the maximal clique set to classify and identify faults in the system, and the performance of the diagnosis scheme was evaluated using the posterior probabilities of the classifier outputs combined with the Shannon entropy. At the same time, the method incorporated a measurement point update mechanism, which can decide whether to add additional measurement point according to the evaluation results of Shannon entropy to ensure better diagnosis effect. The results of simulation experiments showed that the fault diagnosis scheme designed by the method of this paper improved the correct rate of diagnosis results by 3.25 percentage points compared with other diagnosis schemes due to the simultaneous consideration of the structure of the system and the diagnosis method, and the diagnosis results of this paper were relatively stable in repeated experiments, which proved the practicality and effectiveness of the method of this paper.

1. Introduction

With the development of science and technology, the systems involved in people’s production and life are developing in the direction of complexity, large-scale and modularization. This change in the system poses a challenge for the fast and accurate detection and isolation of faults in the system and, so, how to improve the fault diagnosis capability of the system, so as to improve the reliability and utilization of the system, has become a hot spot for researchers to study.

The concept of diagnosability has been introduced in order to improve the fault diagnosis capability of the system. Diagnosability is a property that indicates the extent to which system faults can be accurately and efficiently identified [1]. The diagnosability concept was originally established to uncover deeper information about fault diagnosis, such as how difficult or costly it is to detect and isolate a fault, from a system perspective. The current research concluded that the diagnosis capability of the system is suitable to be improved by designing fault diagnosis methods only when the fault of the system can be diagnosed. If the system fault itself is difficult to diagnose or even undiagnosable, it is meaningless to improve the performance of the diagnosis algorithm for this kind of fault [1]. Therefore, taking the difficulty of fault diagnosis into the scope of fault diagnosis, that is, considering the diagnosability of the system, can fundamentally improve the diagnosis capability of the system.

Research work on diagnosability can be divided into two aspects: diagnosability evaluation [2,3,4] and diagnosability design [5,6]. Diagnosability evaluation refers to the process of measuring the degree to which system faults can be identified deterministically and efficiently, mainly revealing how difficult the fault can be diagnosed. High diagnosability means that the system is more capable of fault diagnosis, while low diagnosability means that the system is less capable of fault diagnosis. Diagnosability design refers to a design technique that takes diagnosability as an optimization index in the design stage of system and diagnosis algorithm [1]. It can be seen that the diagnosability design is a key step in improving the system’s ability to diagnose faults. Depending on the object of diagnosability design, diagnosability design can be further categorized into the design of system structure and the design of diagnosis methods.

(1)

Design of the system structure. Researchers in this direction focus on optimizing the design of the system’s structure to improve the system’s ability to respond to faults and, thus, improve the system’s diagnosis capability, while satisfying the premise of system diagnosability. Since the location and number of sensors can affect the effectiveness of fault identification and isolation [7], the current research direction focuses on changing the structure of the system by optimizing the configuration of the sensors in order to improve the diagnosis capability of the system. The optimal configuration of sensors is essentially a multi-objective decision-making (MODM) problem in the multi-criteria decision-making (MCDM) problem [8]. Various objectives such as system cost [9], reliability, number of sensors, redundancy between sensor information [10], system diagnosability [5,11,12,13], and the degree of hazard of missed faults are considered in different sensor configuration schemes to select one of them that is suitable for the system by balancing the conflicts between multiple objectives and reducing information redundancy [14], making the system inherently more capable of acquiring fault information.

(2)

Design of the diagnosis method of the system. Ding [6] evaluated the false alarm rate, fault detection rate and fault detection time based on a stochastic algorithm, and based on this, proposed a design method for observer-based fault detection system, and [15] proposed an adaptive application strategy that combines system diagnosability analysis with actual fault diagnosis. For different degrees of diagnosability, different diagnosis methods are used to detect and isolate faults, so as to achieve a balance between time efficiency and diagnosis accuracy; [16,17] defined K-gap and used it to give performance indexes of fault detection and isolation for use in the analysis of fault diagnosis capability. Literature [18] proposes a strategy for verifying the diagnosability of discrete-time systems using conjunctive regular expressions, and illustrates the construction of diagnoser and the verification of diagnosability in a real-world case. The diagnosability design of the diagnosis method is mainly to take the diagnosability of the system into account, combined with the fault pattern recognition method [19,20], relying on the model or signal of the system, so that the fault of the system can be exposed as much as possible, in order to achieve the purpose of improving the diagnosability of the system.

From the above analysis, it can be seen that the diagnosability design method starts from the system structure design and diagnosis method design to improve the fault diagnosis capability of the system, in which the system structure design is mainly for the design of the system’s sensors, which mainly solves the problem of extracting information from the system; after all, only by extracting high-quality information from the system can reflect the change of the system fault and the system fault be quickly diagnosed. The diagnosis method design mainly solves the problem of how to utilize the information, by transforming the sensor information, extracting the features and other operations, the fault information can be exposed and the diagnosis of the fault can be realized.

Thus, both aspects can have an impact on the diagnosability of a system, but the two factors are currently considered separately when designing for diagnosability. The current process for diagnosability design is shown in Figure 1a. In this process, the design of system structure and diagnosis method are two successive steps, which do not affect each other. Diagnosis method and system structure are separated. However, it is clear from the above analysis that the design of the system structure determines what diagnosis algorithm is used, and the choice of diagnosis algorithm affects the design of the system structure. If both factors are taken into account in the diagnosability design, the degree of fit between the fault diagnosis method and the system structure can be greatly improved, and, thus, the diagnosis capability of the system can be enhanced.

Based on the above ideas, an integrated design process was utilized in this paper when performing diagnosability design to improve system fault diagnosis, and the flow of this design method is shown in Figure 1b, in which the mutual influence between the diagnosis method and the system structure was considered, and the degree of fit between the two factors was improved by considering the specificity of each measurement point for fault diagnosis. Thus, the fault diagnosis performance of system is greatly improved [21]. Relying on this process, a diagnosability integration design method based on graph theory was proposed in this paper. In the current literature, it is rare to see an approach that enhances the diagnostic capability of a system by considering both system architecture design and diagnostic algorithms at the same time. The method was divided into three main steps: 1. Measurement point determination. The diagnosis plot of measurement point was drawn based on the diagnosability evaluation results, the maximal clique in the plot was extracted, and the maximal clique set was obtained according to the edge covering theorem, so that the set could cover the fault mode of the system. 2. Diagnosis method determination. The method of setting a cascade classifier on a maximal clique set was studied, and the posterior probability output problem of the classifier was studied. The output results of classifier and Shannon entropy were used to evaluate the fault identification results of the diagnosis method. 3. Measuring point updating mechanism. The measurement points can be replaced according to the evaluation results of the diagnosis method in order to obtain better diagnosis results.

The rest of this paper can be summarized as follows: Section 2 describes the framework of the algorithm proposed in this paper; Section 3 describes the specific details of the algorithm based on Section 2; Section 4 gives the flow block diagram of the whole algorithm; and Section 5 illustrates the practicality and effectiveness of the method in this paper by taking the filter amplifier circuit as an example.

2. Diagnosability-Integrated Design Method Framework

In the process of actual fault diagnosis, a complete fault diagnosis scheme needs to clarify two basic aspects: where to extract signals, i.e., the selection of measurement points; and how to process the extracted signals so that the faults can be diagnosed, i.e., the determination of the diagnosis method. Both the selection of measurement point and the diagnosis method can affect the effect of diagnosis. In order to take the influence of both into account and improve the fit of both factors, the flow chart of the diagnosability integrated design method proposed in this paper is shown in Figure 2.

As shown in Figure 2, the diagnosability-integrated design method based on graph theory proposed in this paper firstly needed to evaluate the diagnosability of the system, and through the diagnosability evaluation, we can obtain the diagnosis difficulty degree of different test points for different faults, and then, based on the results of the evaluation, the determination of the test points and then the diagnostic program. At this point, the diagnosis effects of the determined measurement points and diagnosis methods were compared with the existing fault diagnosis methods, and if the diagnosis effects of the obtained diagnosis methods were weaker, the measurement points were re-selected through the measurement point updating session until better diagnostic effects were obtained. In this flowchart, it is through the measurement point updating session that the two factors of test points and diagnosis methods can be adjusted to achieve a coordinated and balanced effect through the form of feedback, so as to maximize the final diagnosis capability.

3. Diagnosability Integrated Design Method Details

In this section, the details of the design framework proposed in Section 2 are developed in detail.

In order to facilitate the method description, the notation of this paper is explained.

Let the set of fault modes of the system be $\mathcal{F}=\left\{f_0,f_1,\cdots ,f_m\right\}$, where $m$ denotes the number of fault modes, $f_0$ denotes the normal state, The set of tests is $\mathcal{T}=\left\{t_1,t_2,\cdots ,t_n\right\}$, where $n$ denotes the number of test. The results of the diagnosability evaluation for this system are

$$FD={\left[F{D}_{ji}\right]}_{n\times m}$$

(1)

$$FI=\left[\begin{array}{cccc}F{I}_{1,(f_1,f_2)}& F{I}_{1,(f_1,f_3)}& \cdots & F{I}_{1,(f_{m-1},f_m)}\\ F{I}_{2,(f_1,f_2)}& F{I}_{2,(f_1,f_3)}& \cdots & F{I}_{2,(f_{m-1},f_m)}\\ ⋮& ⋮& \ddots & ⋮\\ F{I}_{n,(f_1,f_2)}& F{I}_{n,(f_1,f_3)}& \cdots & F{I}_{n,(f_{m-1},f_m)}\end{array}\right]$$

(2)

where $FD$ is the fault detectability evaluation matrix, $F{D}_{ji}$ indicates the detection difficulty when using test $t_j$ to detect the fault $f_i$, and a higher value means less difficulty (cost) to detect the fault. $FI$ is the fault isolability evaluation matrix, $F{I}_{j,(f_i,f_k)}$ indicates the isolation difficulty when using test $t_j$ to isolate the system fault pair $\left(f_i,f_k\right)$, and a larger value means that the difficulty (cost) of isolating the fault pair is smaller.

3.1. Measurement Point Determination

3.1.1. Diagnosis Plot of Measurement Point Determination

The column vectors of Equations (1) and (2) indicate the difficulty of the fault or fault pair to be detected or isolated by the tests in the system. The tests were grouped according to the contents of Equations (1) and (2) and using the K-means clustering algorithm. Use $test\left(f_i\right)$ to denote the set of tests that can detect faults $f_i$ at a smaller cost, and use $test\left(\left(f_i,f_j\right)\right)$ to denote the set of tests that can distinguish fault pair $\left(f_i,f_j\right)$ at a smaller cost.

According to the results of $test\left(f_i\right)$ and $test\left(\left(f_i,f_j\right)\right)$, the detection and isolation capability of the measurement point $t_i$ for different faults and fault pairs can be further revealed. In order to more graphically represent the diagnosis capability of measurement points for different faults, the diagnosis plot of measurement point was introduced in this paper.

The following algorithm was used to draw the diagnosis plot of measurement point ${\mathcal{G}}_{t_i}$.

Based on Algorithm 1 and Definition 1, it can be inferred that

Algorithm 1 the diagnosis plot of measurement point $\mathcal{G}$ determination

Input: $test\left(f_i\right)$, $i=1,2,\cdots ,m$    $test\left(\left(f_i,f_j\right)\right)$, $i,j=1,2,\cdots ,m$, $i\ne j$ Output: ${\mathcal{G}}_{t_i}=\left(V_{t_i},E_{t_i}\right)$ 01. initialize: $V_{t_i}\leftarrow \left\{f_0\right\}$, $E_{t_i}\leftarrow \varnothing$ 02. for $k=1$ to $m$ do 03.  if $t_i\in test\left(f_k\right)$ 04.    $V_{t_i}\leftarrow V_{t_i}\cup f_k$ 05.    $E_{t_i}\leftarrow E_{t_i}\cup \left\{f_0,f_k\right\}$ 06.    end if 07.    for $f_j\in V_{t_i}-f_k$ do 08.      if $t_i\in test\left(f_k,f_j\right)$ do 09.       $E_{t_i}\leftarrow E_{t_i}\cup \left\{f_k,f_j\right\}$ 10.      end if 11.    end for 12. end for 13. Return ${\mathcal{G}}_{t_i}=\left(V_{t_i},E_{t_i}\right)$

Definition 1. 

Diagnosis plot of measurement point. The diagnosis plot of measurement point ${\mathcal{G}}_{t_i}$ is used to qualitatively represent the diagnosis capability of the signal from measurement point $t_i$ for different faults, denoted as ${\mathcal{G}}_{t_i}=\left(V_{t_i},E_{t_i}\right)$, where $V_{t_i}$ denotes the set of vertices of the graph $V_{t_i}\subseteq \mathcal{F}$, indicating that the faults corresponding to the vertices can be detected by test $t_i$. The set of edges of the graph is denoted as $E_{t_i}=\left\{\left\{f_i,f_j\right\}|f_i,f_j\in V_{t_i}\right\}$, $\left\{f_i,f_j\right\}$ indicates that the fault pair $\left(f_i,f_j\right)$ can be isolated by test $t_i$.

Corollary 1. 

The diagnosis plot of measurement point ${\mathcal{G}}_{t_i}=\left(V_{t_i},E_{t_i}\right)$ for any measurement point $t_i$

(1)

$f_0\in V_{t_i}$,

(2)

$\forall f_i\in V_{t_i}, \exists \left\{f_i,f_0\right\}\in E_{t_i}$

3.1.2. Maximal Clique Extraction

According to Corollary 1, for a system with three states ($f_0,f_1,f_2$), all forms of the diagnosis plot of measurement point on this system are shown in Figure 3.

Among the four cases shown in Figure 3, (a) indicates that the measurement point is insensitive to both faults and cannot detect the occurrence of faults; (b) indicates that the measurement point can only detect one of the faults but not the other; (c) indicates that the measurement point can detect both faults but cannot distinguish between them; (d) indicates that the measurement point can detect and isolate both faults. In the diagnosability design of this test point, the information reflected by the test point in case (a) was too little, so it was not considered in this paper. The remaining three cases were discussed in this paper, and the distribution of samples in the feature space corresponding to these three cases is shown in Figure 4.

As can be seen in Figure 4, the different forms of diagnosis plot of measurement points corresponded to different situations that distinguish three system states. For the third case, the three states of the system were completely distinguishable, while for both the first and second cases, the presence of the fault $f_2$ caused some fault states to be indistinguishable, with the difference that for the second case, the fault state $f_1$ and $f_2$ were mixed and it was difficult to distinguish between the two fault states. In other words, the fault can be detected, but the fault cannot be isolated and identified, while for the first case, the fault state $f_2$ and $f_0$ were mixed. The reason for this situation may be that the fault $f_2$ was difficult to detect, or it may be that due to the existence of the system structure, the relevant information was not transmitted to the measurement point when the fault occurred, making the signal of the measurement point in the fault state not different from that in the normal state, causing the fault $f_2$ to be undetectable.

According to the above analysis, when the diagnosis plot of measurement point presented the third case, as shown in Figure 4, the states of the system were best discriminated at this time, and the states in the space did not appear to be mixed. However, in practice, it is not always possible to achieve this; therefore, the diagnosis plot of measurement point ${\mathcal{G}}_{t_i}=\left(V_{t_i},E_{t_i}\right)$ should contain as many states as possible, and these states should satisfy the structure shown in Figure 3d as much as possible, i.e., the diagnosis plot of measurement point should be as close as possible to the structure of the maximal clique.

In order to extract the maximal clique from the diagnosis plot of measurement point ${\mathcal{G}}_{t_i}=\left(V_{t_i},E_{t_i}\right)$, we can refer to the Bron–Kerbosch algorithm in the literature, the details of which are not described in this paper due to the length of the paper.

It should be noted that for each diagnosis plot of measurement point, the maximal cliques contained in it may not be unique (e.g., in (c) of Figure 3, both $\left\{f_0,f_1\right\}$ and $\left\{f_0,f_2\right\}$ are maximal cliques), and the p-th maximal clique of the diagnosis plot of measurement point ${\mathcal{G}}_{t_i}$ is noted as ${\mathcal{C}}_{t_i}^p$.

3.1.3. Maximal Clique Set Selection Algorithm Based on Hypergraph

Through the above analysis, it can be seen that the structure of the maximal clique found in the diagnosis plot of measurement point represents the system states that can be most easily distinguished using the information of the measurement point; so, maximal clique structure is the basis of designing fault diagnosis classifier. However, it was obvious that the maximal clique of measurement points did not necessarily contain all the states of the system, and so, a single maximal clique cannot correctly identify the state of the system. Therefore, multiple maximal cliques are needed to jointly identify the fault state of the system. Therefore, it is the main problem addressed in this section to select a suitable set of maximal cliques from among many maximal cliques to facilitate the detection and isolation of system faults.

1.

Problem Description

The problem in this section can be described formally as follows:

For the aforementioned system, suppose the set of maximal cliques of the system is $\mathcal{C}=\left\{{\mathcal{C}}_{t_i}^p\right\}$, $i=1,2,\cdots ,n$. Now, it is necessary to choose the optimal set of maximal cliques $C^{\star }$ for the maximal cliques in $\mathcal{C}$ such that ${\displaystyle \underset{{\mathcal{C}}_{t_i}^p\in {\mathcal{C}}^{\star }}{\cup }{\mathcal{C}}_{t_i}^p}=\mathcal{F}$, while ensuring that $\min \left|C^{\star }\right|$.

2.

Problem solving

In this section, the above problem is solved based on the concept of hypergraph (Definitions 2 and 3).

Definition 2 (Hypergraph). 

Given the undirected hypergraph $\mathcal{H}=\left(\mathcal{V},\epsilon \right)$, the hypergraph vertex set is defined as $\mathcal{V}=\left\{v_1,v_2,\cdots ,v_m\right\}$, which contains $m$ hypergraph vertices. The set of hypergraph edges is defined as a set $\epsilon =\left\{{\epsilon }_1,{\epsilon }_2,\cdots ,{\epsilon }_n\right\}$ containing $n$ hypergraph edges, where for any hypergraph edge $v$ in the set of hypergraph edges $\epsilon$, $\epsilon =\left\{{\epsilon }_1^{\prime },{\epsilon }_2^{\prime },\cdots ,{\epsilon }_p^{\prime }\right\}$, it means that the hypergraph edge has $p$ hypergraph vertices.

Definition 3 (Edge Coverage). 

Given the hypergraph $\mathcal{H}=\left(\mathcal{V},\epsilon \right)$, $C\subseteq \epsilon$. $C$ is said to be an edge covering of $\mathcal{H}$ if each vertex is associated with at least one edge in $C$.

The problem in this section can be converted to solving the edge covering problem in hypergraph: where the state of the system is equivalent to the vertex in hypergraph, and the maximal clique is the edge in hypergraph. For the edge-covering problem of hypergraph, the most classical method is to use a greedy algorithm to solve this problem, and the steps of this method are shown as follows (Algorithm 2).

Algorithm 2 the set of maximal cliques $C^{\star }$ determination

Input: $\mathcal{C}=\left\{{\mathcal{C}}_{t_i}^p\right\}$, $i=1,2,\cdots ,n$    $\mathcal{F}=\left\{f_0,f_1,\cdots ,f_m\right\}$ Output: $C^{\star }$ 01. initialize: $X\leftarrow \mathcal{F}$, $C^{\star }\leftarrow \varnothing$ 02. while $X=\varnothing$ do 03.    selecet ${\mathcal{C}}_{t_i}^p$, so that it can cover most fault in $X$ 04.    $C^{\star }=C^{\star }\cup \left\{{\mathcal{C}}_{t_i}^p\right\}$ 05.    $X=X\backslash F$ 06. end while 07. Return $C^{\star }$

3.2. Diagnosis Method Determination

3.2.1. Design of Maximal Clique Classifier

The set of maximal cliques determined through Section 3.1.3 is denoted as

$$C^{\star }=\left\{{\mathcal{C}}_1,{\mathcal{C}}_2,\cdots ,{\mathcal{C}}_{ni}\right\}$$

(3)

where ${\mathcal{C}}_j$ represents the j-th maximal clique in the set.

According to the previous section, the system faults contained in the maximal clique ${\mathcal{C}}_j$ are easily distinguishable under the measurement signal of the measurement point, and so, a classifier can be set for any maximal clique ${\mathcal{C}}_j$ in the set $C^{\star }$, and the classifier can identify the system fault states by the signal of the current measurement point.

In classification problems, the difficulty of the classification problem is closely related to the kind of classification. In general, the more kinds of classification, the more detailed features are required and the more resources are consumed.

In order to reduce the difficulty of classification, researchers try to use a cascade approach to solve the classification problem in the current classification problem [22], that is, the problems are first roughly classified by using features, and then the characteristics are finely classified for each rough classification, so as to achieve the purpose of correctly classifying the target samples. Studies have shown that the cascade classification approach has good classification results [23]. In this section, cascade classifiers of each maximal clique in maximal clique set $C^{\star }$ were designed to reduce classification categories as far as possible, so as to select fewer features in feature extraction and identify the state of the system.

Based on the structure shown in Equation (3), construct the matrix

$$\begin{array}{l}W={\left[w_{kj}\right]}_{(m+1)\times ni}\\ k=0,1,2,\cdots ,m\\ j=1,2,\cdots ,ni\end{array}$$

(4)

where $w_{kj}=0,1$, if $w_{kj}=1$ denotes the j-th maximal clique ${\mathcal{C}}_j$ in the maximal cluster clique set $C^{\star }$ can recognize the fault state $f_k$, and vice versa, $w_{kj}=0$.

In this paper, the method of setting up classifiers for each maximal clique can be followed as follows.

The following is a concrete example to illustrate the calculation process of Algorithm 3.

Algorithm 3 Design of cascade classifier on the maximal cliques set

Input: $C^{\star }=\left\{{\mathcal{C}}_1,{\mathcal{C}}_2,\cdots ,{\mathcal{C}}_{ni}\right\}$    $\mathcal{F}=\left\{f_0,f_1,\cdots ,f_m\right\}$ Output: classifier design results 1. $W_i$ is determined by ${\mathcal{C}}_i$ according to Formula (4) 2. while $\mathcal{F}\ne \varnothing$ do 3. $W_i$ adds up the rows to get the vector $w={\left[w_{0\cdot },w_{1\cdot },\cdots ,w_{m\cdot }\right]}^T$ 4. if $w_{0\cdot }=w_{1\cdot }=\cdots =w_{m\cdot }$ then 5.       Set the classifier on ${\mathcal{C}}_j^i\in C^{\star }$, the number of categories is $w_{0\cdot }$ 6.       $\mathcal{F}\leftarrow \varnothing$ 7.      else 8.        $n=\min \left\{w_{0\cdot },w_{1\cdot },\cdots ,w_{m\cdot }\right\}$ 9.        $i=\arg \min \left\{w_{j\cdot }\right\}$ 10.        if $n=1$ and $\left|i\right|=1$then 11.         $\exists {\mathcal{C}}_j^i\in C^{\star }$, s.t $w_{ji}=1$ 12.         the binary classifier is set on ${\mathcal{C}}^i{}_j$, the positive class is $f_i$, the negative class is all the remaining faults 13.         $\mathcal{F}\leftarrow \mathcal{F}-\left\{f_i\right\}$ 14.         $C^{\star }\leftarrow C^{\star }-\left\{{\mathcal{C}}_j^i\right\}$ 15.        end if 16.        if $n=1$ and $\left|i\right|>1$ then 17.         Select ${\mathcal{C}}^i{}_j$ so that it can cover the most faults in $f_i$, 18.         $\mathcal{F}=\mathcal{F}-\left\{f_i\right\}$ 19.         ${\mathcal{C}}_i={\mathcal{C}}_i-\left\{{\mathcal{C}}^i{}_j\right\}$ 20.        end if 21.        if $n>1$ then 22.         the binary classifier is set on ${\mathcal{C}}^i{}_j$, the positive class is $f_i$, the negative class is all the remaining faults 23.         $\mathcal{F}\leftarrow \mathcal{F}-\left\{f_i\right\}$ 24.         $C^{\star }\leftarrow C^{\star }-\left\{{\mathcal{C}}_j^i\right\}$ 25.        end if 26.      end if 27. end while

Suppose the fault mode of a system is $\mathcal{F}=\left\{f_0,f_1,f_2,f_3,f_4\right\}$, the set of maximal clique is $C^{\star }=\left\{{\mathcal{C}}_{t_1},{\mathcal{C}}_{t_2},{\mathcal{C}}_{t_3}\right\}$, and the matrix is determined according to Equation (4) as

$$W=\begin{array}{cc}& \begin{array}{ccc}{\mathcal{C}}_{t_1}& {\mathcal{C}}_{t_2}& {\mathcal{C}}_{t_3}\end{array}\\ \begin{array}{l}{f}_0\hfill \\ f_1\hfill \\ f_2\hfill \\ f_3\hfill \\ f_4\hfill \end{array}& \left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\\ 0& 1& 1\\ 0& 0& 1\end{array}\right]\end{array}$$

(5)

According to the approach of Algorithm 3, at this time, $W$ is accumulated according to the rows to obtain $w={\left[3,3,3,2,1\right]}^T$. Then, choose maximal clique ${\mathcal{C}}_{t_3}$ and set the binary classifier, where the positive class label is $f_4$ and the negative class label is $\left\{f_0,f_1,f_2,f_3\right\}$, and update $W$ as

$$W=\begin{array}{cc}& \begin{array}{cc}{\mathcal{C}}_{t_1}& {\mathcal{C}}_{t_2}\end{array}\\ \begin{array}{c}{f}_0\\ f_1\\ f_2\\ f_3\end{array}& \left[\begin{array}{cc}1& 1\\ 1& 1\\ 1& 1\\ 0& 1\end{array}\right]\end{array}$$

(6)

according to the approach of Algorithm 3, we can obtain $w={\left[2,2,2,1\right]}^T$, and then choose a maximal clique ${\mathcal{C}}_{t_2}$ and set the binary classifier, where the positive class label is $f_3$ and the negative class label is $\left\{f_0,f_1,f_2\right\}$, and update $W$ as

$$W=\begin{array}{cc}& {\mathcal{C}}_{t_1}\\ \begin{array}{l}{f}_0\hfill \\ f_1\hfill \\ f_2\hfill \end{array}& \left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\end{array}$$

(7)

$w={\left[1,1,1\right]}^T$ is obtained, then the maximal clique ${\mathcal{C}}_{t_2}$ is chosen and a triple classifier is set up, in which three system states $f_0$, $f_1$ and $f_2$ are distinguished, respectively.

3.2.2. Feature Cacullation and Feature Selection

Section 3.2.1 sets the cascade classifier on maximal clique, but the features of the signal need to be extracted and selected before the classification, assuming that the set of features of the signal is $\mathcal{J}=\left\{J_1,J_2,\dots ,J_d\right\}$, where $d$ denotes the number of features. The signal features here can use a variety of signal features such as time domain signal characteristics, frequency domain signal characteristics, and time-frequency domain signal characteristics.

In the feature selection session, the signal features that are beneficial for fault diagnosis are selected based on the Relief_F algorithm. The specific algorithm for feature selection is shown in Algorithm 4.

Algorithm 4 Signal feature screening algorithm based on Relief_F

Input: feature set $\mathcal{J}=\left\{J_1,J_2,\cdots ,J_d\right\}$    samples $\left\{x_p,y_p\right\}$, $p=1,\cdots ,T$, $y_p\in \mathcal{F}$ Output: $C^{\star }$ 01. initialize: $W\leftarrow \varnothing$ 02. for $i=1$ to $T$ do 03.   select sample $x_i$ 04.   for $j=1$ to $d$ do 05.     find $k$ neighbors of the same class for $x_i\left(nearhits\right)$ 06.     for every class $c\ne class\left(x_i\right)$ 07.       find $k$ neighbors of different classes of $x_i\left(nearmisses\right)$ 08.     end for 09.   $W(j)=W(j)-\frac{{\displaystyle \sum _{n=1}^{k}diff(x_i,near{h}_n)}}{T\times k}+\frac{{\displaystyle \sum _{c\notin class\left(x_i\right)}\frac{p(c)}{1-p\left(class\left(x_i\right)\right)}{\displaystyle \sum _{n=1}^{k}diff(x_i,near{m}_n\left(c\right))}}}{T\times k}$ 10.   end for 11. end for 12. $sum\leftarrow 0$ 13. ${\mathcal{J}}^{\star }\leftarrow \varnothing$ 14. while $snm<0.5$ do 15.     $i=\arg \max \left(W\right)$ 16.     $sum\leftarrow sum+\max \left(W\right)$ 17.     $\mathcal{J}\leftarrow \mathcal{J}\cup \left\{J_i\right\}$ 18.     $W\leftarrow W-W\left(i\right)$ 19. end while 20. Return ${\mathcal{J}}^{\star }$

3.2.3. Posterior Probability Output of Classifier

According to the approach shown in Section 3.2.1, a classifier can be determined for each maximal clique. In the design of classifiers, constructing a classifier to generate posterior probabilities is a better approach in the discrimination case. Combining multiple types of posterior probabilities is useful in the final decision, even if the discrimination result is chosen based on the maximum posterior probability, which is the most Bayesian decision for the equal loss case. The output of the posterior probabilities allows not only to determine the classification of the classifier but also to measure the classification performance of the classifier by the posterior probabilities.

In this paper, we took the support vector machine (SVM) as an example to illustrate the output method of its posterior probability.

Assume that the training sample data set is $\left\{x_i,y_i\right\}$. For a sample $x$ in it, the output of the support vector machine takes the form

$$f\left(x\right)=\mathrm{sign}\left(f\left(x\right)\right)=\mathrm{sign}\left(h\left(x\right)+b\right)$$

(8)

where $\mathrm{sign}\left(\cdot \right)$ denotes the symbolic function acting as a decision function.

$$h\left(x\right)={\displaystyle \sum _i{y}_i{\alpha }_{i}k\left(x_i,x\right)}$$

$h\left(x\right)+b$ is a quantity proportional to the distance of the interface, and it is also believed that the closer the point is to the interface, the less likely it is to be correctly classified; the farther it is from the interface, the more likely it is to be correctly classified.

For a binary classification problem, based on the Bayesian formula, we can get

$$P\left(y=1|f\left(x\right)\right)=\frac{P\left(f\left(x\right)|y=1\right)P\left(y=1\right)}{{\displaystyle \sum _{i=\pm 1}P\left(f\left(x\right)|y=i\right)P\left(y=i\right)}}$$

(9)

By fitting the Equation (9), we can get

$$P\left(y=1|f\left(x\right)\right)=\frac{1}{1+\exp \left(Af\left(x\right)+B\right)}$$

(10)

where $A$ and $B$ are the parameters to be estimated.

Equation (10) was got from dataset $\left\{f\left(x_i\right),y_i\right\}$ using maximum likelihood estimation.

Construct the maximum likelihood function according to Equation (10)

$$L={\displaystyle \prod _{y_i=1}P\left(y=1|f\left(x_i\right)\right)}\times {\displaystyle \prod _{y_i=-1}P\left(y=-1|f\left(x_i\right)\right)}$$

(11)

Turning Equation (11) into a log-likelihood function

$$\begin{array}{l}\log L\\ =\log \left({\displaystyle \prod _{y_i=1}P\left(y=1|f\left(x_i\right)\right)}+{\displaystyle \prod _{y_i=-1}P\left(y=-1|f\left(x_i\right)\right)}\right)\\ =\log \left({\displaystyle \prod _{y_i=1}P\left(y=1|f\left(x_i\right)\right)}\right)+\log \left({\displaystyle \prod _{y_i=-1}P\left(y=-1|f\left(x_i\right)\right)}\right)\\ ={\displaystyle \sum _{y_i=1}\left(\log \left(P\left(y=1|f\left(x_i\right)\right)\right)\right)}+{\displaystyle \sum _{y_i=-1}\left(\log \left(P\left(y=-1|f\left(x_i\right)\right)\right)\right)}\end{array}$$

(12)

So

$$\begin{array}{l}{A}^{\ast },B^{\ast }\\ =\underset{\left(A,B\right)}{\arg \max }\log L\\ =\underset{\left(A,B\right)}{\arg \max }\left[\begin{array}{c}{\displaystyle \sum _{y_i=1}\left(\log \left(P\left(y=1|f\left(x_i\right)\right)\right)\right)}+\\ {\displaystyle \sum _{y_i=-1}\left(\log \left(P\left(y=-1|f\left(x_i\right)\right)\right)\right)}\end{array}\right]\end{array}$$

3.3. Performance Evaluation Method of Diagnosis Scheme Based on Information Entropy

A diagnosis scheme for the system can be designed according to the methods shown in Section 3.1 and Section 3.2. In order to study the pros and cons among the schemes, this section examines the evaluation of the diagnosis scheme.

It is assumed that the signal set of each measurement point obtained by a certain operation of the system is $s=\left\{s_1,s_2,\cdots \right\}$, the diagnosis results for this sample can be expressed in terms of the posterior probability vector of the output of the diagnosis scheme according to the previous section

$$\begin{array}{l}L\left(s\right)=\left\{P\left(f_0|s\right),P\left(f_1|s\right),\cdots ,P\left(f_m|s\right)\right\}\\ {\displaystyle \sum _{m}P\left(y_m|s\right)}=1\end{array}$$

(13)

suppose the posterior probability of the diagnosis scheme for the current state of the system is $P\left(f_1|s\right)=0.9$ and $P\left(f_0|s\right)=0.1$, then it can be considered that the current state of the system is $f_1$; while when its diagnosis posterior probability is $P\left(f_1|s\right)=0.51$ and $P\left(f_0|s\right)=0.49$, although it can also be considered that the system is in the fault state $f_1$, However, in this case, it is reasonable to assume that the reliability of the diagnosis scheme for the current system state identification results is low. Therefore, from the posterior probability results shown in Equation (13), its distribution indicates confidence of the diagnosis scheme to the diagnosis result, when $L\left(s\right)$ are more concentrated, it means that the diagnosis scheme has more confidence for the diagnosis results, and the diagnosis scheme has better diagnosis performance at this time, while when $L\left(s\right)$ are more dispersed, it means that the diagnosis method has lower confidence for the diagnosis results. Therefore, by calculating the entropy of Equation (13) to quantify the confidence $ES\left(s\right)$ of the classifier on the sample, the smaller the entropy, the lower the uncertainty in the classification, and the higher the confidence of the classifier output, i.e., the confidence and entropy are inversely proportional. In the selection of entropy, the more commonly used Shannon entropy is chosen as a measure of the diagnosis effect of a single sample in this paper. If the diagnosis of the current sample is correct, the Shannon entropy of Equation (13) is the loss of the diagnostic scheme to the sample diagnosis, and if the diagnosis of the current sample is wrong, the maximum Shannon entropy in this classification case is used as the loss of the diagnostic scheme to the sample diagnosis, that is

$$ES\left(s\right)=\left\{\begin{array}{l}-{\displaystyle \sum _{m}P\left(y_m|s\right)\log P\left(y_m|s\right),s\mathrm{is}\mathrm{correctly}\mathrm{diagnosed}}\hfill \\ -\log \frac{1}{m+1},s\mathrm{is}\mathrm{misdagnosed}\hfill \end{array}\right.$$

(14)

3.4. Measurement Point Update Mechanism

The diagnosis result of the current fault diagnosis scheme can be evaluated by Equation (14), and when the evaluation result is not good, it means that the current set of maximal cliques $C^{\star }$, i.e., the selected measurement points, does not fully reflect the fault information of the system, and additional information needs to be obtained by adding new measurement points and using this new information to diagnose the system.

For the existing set $C^{\star }$ of maximal cliques, it is necessary to find new maximal cliques from the set $C-C^{\star }$ to supplement the fault information of the system, and the following principles should be followed when selecting new maximal cliques:

(1)

The new maximal clique should cover as many faults as possible in order to provide more information for the fault diagnosis of the system;

(2)

When there are multiple maximal cliques in $C-C^{\star }$ that can cover the same number of faults, the most economical one is selected based on the principle of economy.

4. Algorithm Flow Design and Implementation

The schematic diagram of the diagnosability-integrated design approach based on graph theory proposed in this paper is shown in Figure 5.

5. Instance Verification

5.1. Experiment Preparation

In this paper, a filter amplifier circuit was used to verify the proposed method. The circuit diagram of the experimental circuit is shown in Figure 6, and 20 dB of noise was added to the measured signal in it. The simulated faults of the experimental circuit are shown in

Table 1. Circuit fault setting.

	Component	Fault
$f_0$	\	\
$f_1$	$C_1$	$10 \mathrm{nf}$
$f_2$	$R_8$	$50 \mathrm{k}\Omega$
$f_3$	$R_{18}$	short circuit
$f_4$	$R_{18}$	$20 \mathrm{k}\Omega$

. The circuit diagram was run 50 times in different states, where 30 sets of data for each state were used for classifier training, 10 sets were used for diagnosis method evaluation, and 10 sets were used for final testing. The set of all classifier training data is denoted as $D_1$, the set of all diagnosis method evaluation data is denoted as $D_2$, and the set of test data is denoted as $D_{test}$. The signal features selected in this paper is shown in

Table 2. Signal feature.

NO.	Feature	NO.	Feature
1	maximum value	8	skewness
2	maximum value	9	waveform factor
3	mean value	10	impulse Factor
4	root-mean-square value	11	margin factor
5	peak-to-peak value	12	gravity frequency
6	peak factor	13	mean square frequency
7	kurtosis	14	root-mean-square frequency

.

5.2. Experimental Results

Based on the results of the diagnosability evaluation of the system shown in Figure 6, the diagnosis plot of measurement point is drawn in conjunction with Algorithm 1, as shown in Figure 7.

Using the Bron–Kerbosch algorithm to analyze the diagnosis plot of measurement point and extract maximal cliques, a total of four maximal cliques can be extracted from the diagnosis plot of measurement point shown in Figure 7, which is recorded as $\mathcal{C}=\left\{{\mathcal{C}}_{t_2},{\mathcal{C}}_{t_3},{\mathcal{C}}_{t_5},{\mathcal{C}}_{t_6}\right\}$. We can obtain $C^{\star }=\left\{{\mathcal{C}}_{t_6}\right\}$ from $\mathcal{C}=\left\{{\mathcal{C}}_{t_2},{\mathcal{C}}_{t_3},{\mathcal{C}}_{t_5},{\mathcal{C}}_{t_6}\right\}$ using Algorithm 2, and according to Algorithm 3, the design result of cascade classifier based on the maximal clique can be obtained: using the data of measurement point 6, the five states of the system were identified. Algorithm 4 was used to calculate the contribution of each feature to the diagnosis, which is shown in Figure 8. Finally, feature 12 and 13 were selected to distinguish the system state, and then, a complete fault diagnosis scheme can be obtained.

Data set $D_2$ was used to evaluate the diagnosis results of this scheme, and the average Shannon entropy of samples is 0.4815.

The measurement point information was updated to $C^{\star }=\left\{{\mathcal{C}}_{t_5},{\mathcal{C}}_{t_6}\right\}$. Repeating the above steps, the average Shannon entropy of the evaluation using the sample in this condition was 0.5369. This result was not as good as the last diagnosis, indicating that the diagnosis method obtained using $C^{\star }=\left\{{\mathcal{C}}_{t_6}\right\}$ is better.

Therefore, the diagnosis scheme obtained by the graph-theory-based diagnosability-integrated design method in this paper was as follows: the signal of measuring point 6 was collected, and the two features of gravity frequency and mean square frequency can be used to identify the fault of the system.

Using this diagnosis scheme, the state of $D_{test}$ was identified, and the results are shown in Figure 9.

5.3. Diagnosis Results of Other Methods in the Literature

The method in this paper was compared with four common fault recognition methods in the literature, namely, K-nearest neighbor (KNN) classifiers [24], random forests (RF) [25], discriminative classifiers, and support vector machines (SVM) [26], to illustrate the degree of superiority of the different methods by comparing the error rate of recognizing systematic fault patterns under the different methods.

Firstly, the data of measurement points 5 and 6 were extracted according to the signal features in Table 2, and the feature vectors of multiple measurement points were then pieced together to form a new vector or matrix for diagnosis [27], and the schematic diagram of the piecing method is shown in Figure 10.

In this paper, the feature vectors were recombined by means of horizontal splicing of the data from multiple measurement points. In performing the diagnosis, the data set $D_1$ (a total of 5 × 30 groups of samples) was used for training, and the data sets $D_2$ and $D_{test}$ (a total of 5 × 20 groups of samples) were used for testing. The fault diagnosis results are shown in

Table 3. Other diagnosis methods results.

NO.	Method	f0	f1	f2	f3	f4	Total
1	KNN	0	2	0	0	3	5 (5%)
2	RF	0	0	0	0	6	6 (6%)
3	discriminative classifier	0	0	0	0	1	1 (1%)
4	SVM	0	0	0	0	1	1 (1%)

, and the table shows the number of samples that were incorrectly diagnosed.

The four methods in the literature and the method in this paper were subjected to 50 simulation experiments, and the number of samples that were misdiagnosed in each experiment was recorded, and the statistical indexes such as the mean and quartile of the experimental results of each method were counted and plotted as a box-and-line diagram, as shown in Figure 11.

5.4. Experimental Analysis

Table 3 and Figure 9 show the diagnosis of different fault modes in one experiment. From the results, the fault diagnosis scheme designed by this paper’s method can identify the faults of the system well, and the methods in the literature can only identify some of the fault modes, while there were difficulties in identifying other faults. For example, the KNN and random forest methods had poorer results in the identification of fault mode 4 compared to other fault modes. In terms of diagnosis correctness, the correctness of this paper’s method was improved by 3.25 percentage points compared to the average correctness of the four methods in the literature.

Figure 11 shows the statistical results of the diagnosis of different fault modes in 50 repeated experiments. From the statistical results, the median number of incorrectly diagnosed samples of this paper’s method was 0, and the maximum value was 2, which indicates that at least in half of the experiments, this paper’s method was able to correctly diagnose all the samples, and the number of incorrectly diagnosed samples of the worst diagnosis result was 2. This diagnosis result was already better than that of the KNN and the random forest (the minimum value of the number of incorrectly diagnosed samples of the two methods was 5 and 2, respectively), while for the use of discriminative classifier and SVM, both methods performed stably in 50 repetitions, and their number of incorrectly diagnosed samples was 1.

In the comparison method, the design of the fault diagnosis method can only be based on the measurement points that have been selected, which does not guarantee that the information provided by the selected measurement points is best adapted to the current fault diagnosis method. Since the information provided by two groups of measurement points, measurement point 5 and measurement point 6, was used in the experiments to diagnose the faults of the system, in order to handle multiple groups of measurement points, the method adopted in the literature was to splice the signal features of multiple measurement points horizontally to form new feature vectors to be used, which seems to be a fast and easy way, but the implied premise of doing so is that the distinguishing ability of each signal for the faults is the same, and the same features on different signals for the faults, which makes the implied premise obviously over-idealized. In the actual classifier, the classification is based on the relative position of the sample features in the feature space, in this case, when the features used are not sensitive to faults, the addition of these features will make the originally clear relative position become blurred, and, thus, the phenomenon of misclassification occurs. This leads to the situation in the experiment: although the information of two measurement points was used in the comparison experiment, which provided more diagnosis information, the diagnosis effect was not satisfactory. Therefore, it is not the case that the more measurement point information is used, the better the diagnosis effect is, but only by combining the information of the measurement points with the specific fault diagnosis method can the best fault diagnosis effect be produced.

In the method of this paper, the inclusion of the measurement point updating link makes the diagnosability design work to form a feedback, and the existence of the feedback makes the selection of the measurement point and the fault pattern recognition method no longer a back-and-forth step, and the two can be balanced to realize the optimal fit. In this paper, people can not only choose the fault diagnosis method based on the selected test points but also the existence of feedback allows people to “reflect” on whether the current measurement data are appropriate for the fault diagnosis method, and improve the data through the measurement-point-updating mechanism. Thus, in a cycle, the selected test points and the diagnosis methods are adapted to each other, thus obtaining better diagnosis results and improving the system’s diagnostic capability.

6. Conclusions

To address the problem of diagnosability design, in order to take into account both system structural factors and diagnostic schemes, and to improve the degree of fit between diagnostic methods and system structure, a diagnosability-integrated design method based on graph theory was proposed in this paper, which can generate specific fault diagnosis methods for specific systems, and can be applied to the diagnosis of faults on electronic, mechanical, and other systems. The method draws a diagnosis plot of measurement point through the diagnosability evaluation results, extracts the maximal cliques from the diagnosis plot of measurement point, and sets cascading classifiers on the based on maximal cliques to achieve the design of diagnosis methods, and calculates the Shannon entropy based on the posterior probability of the classifier output as the diagnosis capability measure of each diagnosis scheme. The diagnosis scheme with low diagnosis capability is reconfigured through the measurement point update mechanism to achieve the purpose of diagnostic scheme optimization. The results of simulation experiments showed that compared with the existing methods in the literature, the method in this paper improved the average diagnosis correct rate by 3.25 percentage points, while in many simulation experiments, the error rate of most of the methods in this paper was 0, which indicates that the method in this paper had a high degree of accuracy and stability.

The ultimate aim of the method purpose of this paper was to design the diagnostic scheme of the system to improve the fault diagnosis capability of the system through the diagnosability design, and the operation of the method was based on the rich operation data of the system. In the future, how to improve the fault diagnosis capability of the system through the diagnosability design can be considered, especially in the case of the system signal data being difficult to obtain or the data being contaminated.