=Paper=
{{Paper
|id=Vol-2289/paper5
|storemode=property
|title=Computer-aided Diagnosis via Hierarchical Density Based Clustering
|pdfUrl=https://ceur-ws.org/Vol-2289/paper5.pdf
|volume=Vol-2289
|authors=Tom Obry,Louise Travé-Massuyès, Audine Subias 
|dblpUrl=https://dblp.org/rec/conf/safeprocess/ObryTS18
}}
==Computer-aided Diagnosis via Hierarchical Density Based Clustering==
<pdf width="1500px">https://ceur-ws.org/Vol-2289/paper5.pdf</pdf>
<pre>
          Computer-aided Diagnosis via Hierarchical Density Based Clustering

                      Tom Obry1,2 and Louise Travé-Massuyès 1 and Audine Subias 1
                    1
                      LAAS-CNRS, Université de Toulouse, CNRS, INSA, Toulouse, France
                             2
                               ACTIA, 5 Rue Jorge Semprun, 31432 Toulouse



                          Abstract                                data about all the influencial attributes. In particular, busi-
                                                                  ness concepts are highly sensitive to environmental parame-
      When applying non-supervised clustering, the                ters that fall outside the scope of the considered business do-
      concepts discovered by the clustering algorithm             main and that are not recorded, for instance stock exchange.
      hardly match business concepts. Hierarchical                In addition, the clusters corresponding to business concepts
      clustering then proves to be a useful tool to exhibit       may be quite "close" in the data space and the only way to
      sets of clusters according to a hierarchy. Data can         capture them would be to guess the right number of clusters
      be analyzed in layers and the user has a full spec-         to initialize correctly the clustering algorithm. This is obvi-
      trum of clusterings to which he can give meaning.           ously quite hard. Hierarchical clustering then proves to be
      This paper presents a new hierarchical density-             a useful tool because it exhibits sets of clusters according to
      based algorithm that advantageously works from              a hierarchy and it modulates the number of clusters. Data
      compacted data. The algorithm is applied to the             can then be analyzed in layers, with a different number of
      monitoring of a process benchmark, illustrating             clusters at each level, and the user has a full spectrum of
      its value in identifying different types of situa-          clusterings to which he can give meaning.
      tions, from normal to highly critical.                      Hierarchical clustering identifies the clusters present in a
                                                                  dataset according to a hierarchy [8][9][10]. There are two
                                                                  strategies to form clusters, the agglomerative ("bottom up")
1    Introduction                                                 strategy where each observation starts in its own cluster and
                                                                  pairs of clusters are merged as one moves up the hierar-
In data-based diagnosis applications, it is often the case that
                                                                  chy. The divise method ("top down") where all observations
huge amounts of data are available but the data is not la-
                                                                  start in one cluster and splits are performed recursively as
belled with the corresponding operating mode, normal or
                                                                  one moves down the hierarchy. The results of hierarchical
faulty. Clustering algorithms, known as non-supervised
                                                                  clustering are usually presented in a dendrogram. A den-
classification methods, can then be used to form clusters that
                                                                  drogram is a tree diagram frequently used to illustrate the
supposedly gather data corresponding to the same operating
                                                                  arrangement of the clusters. In order to decide which clus-
mode.
                                                                  ters should be combined or where a cluster should be split,
   Clustering is a Machine Learning technique used to group       a measure of dissimilarity between sets of observations is
data points according to some similarity criterion. Given         required. In most methods of hierarchical clustering, splits
a set of data points, a clustering algorithm is used to clas-     or merges of clusters are achieved by use of an appropriate
sify each data point into a specific group. Data points that      metric like euclidean, manhattan or maximum distance.
are in the same group have similar features, while data
points in different groups have highly dissimilar features.          Few algorithms propose a density-based hierarchical
Among well-known clustering algorithms, we can mention            clustering approach like α-unchaining single linkage [11]
K-Means [1], PAM [2], K-Modes [3], DBSCAN [4].                    or HDBSCAN [12]. In this paper, we present a new hi-
   Numerous validity indexes have been proposed to evalu-         erarchical clustering algorithm, named HDyclee, based on
ate clusterings [5]. These are generally based on two funda-      density that advantageously works from compacted data in
mental concepts :                                                 the form hypercubes. This contribution is an extension of
                                                                  the clustering algorithm DyClee [13], [14], [15]. The pur-
    • compactness, the members of each cluster should be as       pose of this work is to generate a flat partition of clusters
      close to each other as possible. A common measure           with a hypercube’s density level higher or equal to a thresh-
      of compactness is the variance, which should be mini-       old and to be able to visualize all existant clusters in the
      mized.                                                      dataset with a dendogram by varying the density of the hy-
                                                                  percubes present in a group. The value of the algorithm in
    • separation, the clusters themselves should be widely        a diagnosis context is illustrated with the monitoring of a
      spaced.                                                     Continuous Stirred Tank Heater benchmark, for which it al-
   Nevertheless, one must admit that the concepts discov-         lows the user to identify different types of situations, from
ered by even the most scored clusterings hardly match busi-       normal to highly critical.
ness concepts [6] [7]. One of the reasons is that data bases         This paper is organized as follows. In section 2 the Dy-
are often incomplete in the sense that they do not include the    Clee algorithm is presented. In section 3 the concepts and
                                                                  gathers a group of data samples close in all dimensions and
                                                                  whose information is summarized in a characteristic fea-
                                                                  ture vector (CF). For a µ-cluster µCk , CF has the following
                                                                  form:


                                                                         CFk = (nk , LSk , SSk , tlk , tsk , Dk , Classk ) .    (1)
             Figure 1: Global description DyClee.
                                                                  where nk ∈ < is the number of objects in the µ-cluster k,
principles underlying Dyclee, like the definition of micro        LSk ∈ <d is the vector containing the linear sum of each
clusters µC, dynamic clusters and the KD-Tree structure,          feature over the nk objects, SSk ∈ <d is the square sum of
are explained. In the section 4, the hierarchical clustering      features over the nk objects, tlk ∈ < is the time when the
based-density algorithm is presented. Tests and results are       last object was assigned to that µ-cluster, tsk ∈ < is the time
detailed in section 5. The conclusion and perspective for         when the µ-cluster was created, Dk is the µ-cluster density
future work end this paper in section 6.1                         and Classk is the µ-cluster label if known. Using LSk , SSk
                                                                  and nk the variance of the group of objects assigned to the
2       Dyclee: a dynamic clustering algorithm                    µ-cluster k can be calculated.
                                                                     The µ-cluster is shaped as a d-dimensional box since the
DyClee is a dynamic clustering algorithm which is able to         L1-norm is used as distance measure. The distance between
deal with large amounts of data arriving at fast rates by         an object X = [x1 , ..., xd ]T and a µ-cluster µCk , named
adopting a two stages strategy similar to [16], [17], [18].       as dis(X, µCk ), is calculated as the sum of the distances
The first stage is a fast scale distance-based algorithm that     between the µCk vector center ck = [c1k , . . . , cdk ]T and the
collects, pre-processes and compresses data samples to form       object value for each feature as shown in equation (2):
so-called micro-clusters (µ-clusters). It operates at the rate
of the data stream and creates µ-clusters putting together                                                  d
data samples that are close, in the sense of a given distance,                                              X
                                                                          dis(X, µCk ) = L1 (X, ck ) =            xi − cik .    (2)
to each other. µ-clusters are stored in the form of summa-
                                                                                                            i=1
rized representations including statistical and temporal in-
formation.                                                           The data is normalized according to the data context,
The second stage is a slower scale density-based algorithm        i.e. the feature range [mini , maxi ] of each feature i, i =
that groups the µ-clusters into actual clusters that can be in-   1, ..., d. If no context is available in advance, it may be es-
terpreted semantically as classes. It takes place once each       tablished online. The size of the hyperboxes S i along each
tslow seconds and analyses the distribution of µ-clusters.        dimension i is set as a fraction of the corresponding feature
The density of a µ-cluster is considered as low, medium           range. The hyperbox size per feature is hence found ac-
or high and is used to create the final clusters by a density     cording to (3), where φi is a user constant parameter in the
based approach, i.e. dense µ-clusters that are close enough       interval (0, 1), establishing the fraction:
(connected) are said to belong to the same cluster. Simi-
larly to [19], a cluster is defined as the group of connected
µ-clusters where every inside µ-cluster presents high den-                 S i = φi |maxi − mini |,        ∀i = 1, . . . , d.   (3)
sity and every outside µ-cluster exhibits either medium or
low density. The above dense µ-cluster structure allows the       Whenever an object X arrives, the algorithm searches for
algorithm to create clusters of non convex shapes even in         the closest µ-cluster. Once found, a maximal distance cri-
high dimensional spaces and it has proved outliers rejection      terion is evaluated to decide whether or not the object fits
capabilities in evolving environments [18]. In addition, µ-       inside the µ-cluster hyper-box. If the fitting is sufficient the
clusters of similar densities can form clusters of any shape      µ-cluster feature vector is updated using the object infor-
and any size.                                                     mation; if not, a new µ-cluster is created with the object
In DyClee, both stages work on-line, but operate at different     information using its time-stamp as cluster time of creation.
time scales. This multi-density feature allows the detection         The density of a µ-cluster µCk is calculated using the
of novelty behavior in its early stages when only a few ob-       current number of objects Qnk and the current hyper-volume
jects giving evidence of this evolution are present. Figure 1     of the bounding box Vk = di=1 S i , as shown in (4):
gives the global description of DyClee.
                                                                                                    nk
                                                                                             Dk =      .                        (4)
                                                                                                    Vk
3       Main principles of DyClee
All the principles explained in this section are from the core    Let µCkα and µCkβ be two µ-clusters, then µCkα and µCkβ
algorithm.                                                        are said to be directly connected if their hyper-boxes overlap
                                                                  in all but ϕ dimensions, where ϕ is an integer. The parame-
3.1      Notion of micro-clusters µC                              ter ϕ, fixed by the user, establishes the feature selectivity.
Considering a d-dimensional object X = [x1 , ..., xd ] marked        A µ-cluster µCk1 is said to be connected to µCkn if
with a timestamp tX and qualified by d features, a µ-cluster      there exists a chain of µ-clusters {µCk1 , µCk2 , · · · , µCkn }
                                                                  such that µCki is directly connected to µCki+1 for i =
    1
    This work is performed in the framework of a CIFRE Project    1, 2, · · · , n − 1. A set of connected µ-clusters is said to be
supported by ACTIA.                                               a group.
3.2    Dynamic clusters                                           are unordered pairs of elements of G. Finally, W is a set of
Dyclee is a dynamic clustering algorithm, which means that        weights on E with wij defined in the equation 6.
not only the parameters but the classifier structure changes
according to input data in an automatic way. It achieves                               wi,j = min(Di , Dj ).                (6)
several cluster operations like creation, elimination, drift,
merge, and split. For instance, a cluster is splitted into two
                                                                  where the density of a µ-cluster Di is defined in the equa-
or more clusters if, with the arrival of new data, high density
                                                                  tion 4.
regions can be distinguished inside the cluster. In that sce-
                                                                  An edge eij between µ-clusters µCi and µCj means those
nario, dense regions are separated by low density regions,
                                                                  are directly connected in the sense defined in the section
making the cluster no longer homogeneous. Even more, the
                                                                  3.1. If two µ-clusters are not directly connected, there is no
cluster center could be situated in a low density region, loos-
                                                                  edge between them which leads to a Graph that is not full.
ing its interpretability as prototype of the elements in the
                                                                  The Graph of µ-cluster’s connections is built according to
cluster. Splitting the cluster creates smaller homogeneous
                                                                  the algorithm 1. Neighbors are searched for each µ-cluster
clusters, completely representative of the belonging sam-
                                                                  with respect to the equation 5 (lines 3 to 6). The function
ples. An illustrative example of this phenomenon is shown
                                                                  Search_neighbors() is detailed in the algorithm 2. For each
in Figure 2.
                                                                  µCk , the distance L∞ defined in equation 5 is applied where
                                                                  r = φi , xik the value of µCk at the ith dimension and cij the
                                                                  center of the µCj at the dimension i. The variable Neigh-
                                                                  bors_of_k contains all the neighbors of µCk . An edge ekj
                                                                  is added to the Graph G for each neighbor µCj of the µ-
                                                                  cluster studied µCk and the weight wkj is calculated with
                                                                  the equation defined above (lines 7 to 11).

                                                                  Algorithm 1 Build the Graph of µ-cluster’s connections
                                                                  Require: KD-Tree
              Figure 2: Splitting of cluster A.                    1: G = Graph()
                                                                   2: Connection = ()
                                                                   3: for k = 1 to Number of µ-clusters do
3.3    Finding groups of µ-clusters: the KD-Tree                   4:   N = []
       structure                                                   5:   N = Search_neighbors(k)
                                                                   6:   Connection[k] = N
To find groups of connected µ-clusters, a KD-Tree [20] is          7:   for j = 1 to Nbre of neighbors of k do
used. A KD-Tree is a binary tree, each of whose nodes rep-         8:      Weight = min(Dk , Dj )
resents an axis-aligned hyperrectangle. Each node specifies        9:      G.add_edges(k, j, Weight)
an axis and splits the set of points based on whether their       10:   end for
coordinate along that axis is greater than or less than a par-    11: end for
ticular value. The tree is queried to return only neighbors
who are at a maximum distance from a point. A µCj is
the neighbor of the µCk if the condition in equation (5) is
respected :                                                       Algorithm 2 Research of a µ-cluster’s neighbors
                                                                  Require: KD-Tree, µ-cluster µCk
                           d
                 L∞ = max |xik − cij |       r.            (5)     1: for j = 1 to Number of µ-clusters do
                                         ∧




                          i=1                                      2:   Neighbors_of_k = []
                                                                             d
where d is the number of dimension, cji the center of the          3:    if max |xik − cij |       r then
                                                                                               ∧




                                                                            i=1
µCj at the dimension i and r the maximal distance from the         4:      Neighbors_of_k.add(j)
µCk . In this context, r is set to φi .                            5:   end if
                                                                   6: end for
4     A new hierarchical clustering                                7: return Neighbors_of_k
      density-based algorithm
In this section, a new hierarchical clustering density-based        Let us consider five µ-clusters µC1 , µC2 , µC3 , µC4 and
algorithm is presented. Inputs are the connections between        µC5 with their densities D1 = 14, D2 = 12, D3 = 3, D4 = 9,
µ-clusters from the KD-Tree and the output is a flat partition    D5 = 13. Figure 3 shows those five µ-clusters.
of clusters where all µ-clusters that are in clusters have a
minimum density level guaranteed.

4.1    Representation of the µ-clusters connections
The representation of the connections between all µ-clusters
can be visualized by a weighted Graph. A weighted Graph
G = (N , E, W) is a triplet where N is a set of nodes. A
node ni corresponds to the µ-cluster µCi . E is the set of
edges with eij the edge between the node ni and nj , which                    Figure 3: Example of five µ-clusters.
   The search of neighbors begins with the densest µ-cluster.    but on µ-clusters that contains the objects to decrease the
In this example, the research starts with the µC1 as shown       complexity of calculation. At the root of the tree, there is
in Figure 4. All µ-clusters that satisfy the equation 5 are      one cluster composed by all µ-clusters. Each cut in the tree
neighbors of µC1 .                                               corresponds to a density threshold, i.e each cluster formed
                                                                 below this cut level is composed by µ-clusters that have a
                                                                 density higher to the density threshold. At the bottom of the
                                                                 tree, there is one cluster for each µ-cluster. So root’s density
                                                                 level is 0 and the last cut on the tree is max(w ∈ W).
                                                                 Like [12], a variable ε is user parameter evolving in the
                                                                 interval ε ∈ [0, max(w ∈ W)]. For each iteration of ε, all
                                                                 the weights w ∈ W are checked. if wij ε, the edge eij




                                                                                                             ∧
                                                                 is removed. The vertical axis of the dendogram is 1/D to
                                                                 keep an ascending direction.
        Figure 4: Search of neighbors for the µC1 .

   Once neighbors of µC1 are found, the neighbors of the
other µ-clusters are searched. The result is shown in table
1:



                  µ-clusters    Neighbors
                    µC1           µC2
                    µC2         µC1 , µC3
                    µC3         µC2 , µC4
                                                                 Figure 6: Example 1: Graph of connections between µ-
                    µC4         µC3 , µC5
                                                                 clusters after removed all weight’s edges wij < 3.
                    µC5           µC4

          Table 1: Neighbors for each µ-clusters                    Figure 6 represents the case when ε = 3. We can
                                                                 observe two clusters composed by µ-clusters that have their
                                                                 densities strictly higher to three and one µ-cluster alone.
  The weights are calculated for every edge following the        This method allows to detect a split of clusters case and to
equation 6 :                                                     isolate the least denses µ-clusters as early as possible.
                                                                Once all values in the interval of ε studied and all edges
     w12 = min(D1 , D2 ) = min(14, 12) = 12,                    removed, the dendogram can be generated (see Figure 7).
    
      w23 = min(D2 , D3 ) = min(12, 3) = 3,
    
                                                      (7)
    
     w 34 = min(D3 , D4 ) = min(3, 9) = 3
    
      w45 = min(D4 , D5 ) = min(9, 13) = 9.

The Figure 5 shows the weighted Graph which represents
the connections between all µ-clusters in the dataset.




                                                                           Figure 7: Dendogram of the example 1.

                                                                    At the density threshold D = 3, two clusters composed
                                                                 by µC1 , µC2 and µC4 , µC5 are found and the µ-cluster
                                                                 µC3 is alone. One cluster composed by µC1 and µC2 is
Figure 5: Example 1: Graph of connections between µ-             found and µC4 , µC5 . Then for D=9, one cluster composed
clusters.                                                        by µC3 . Finally, above density D = 12, all µ-clusters are
                                                                 alone.

4.2   Representation of the hierarchy of clusters                4.3   Extracting a flat partition of clusters
The objective of the algorithm proposed in this paper is to      The dendogram generated, a partition of clusters corre-
represent and visualize all the possible clusters at different   sponding to a specific density level can be extracted from the
levels of density in a dataset. In contrast to most known        Graph of µ-cluster’s connections with a density threshold
hierarchical clustering algorithm, links that relies level       according to the algorithm 2. To find clusters, the edges that
ln and ln + 1 in our new algorithm’s dendogram are not           have a weight strictly lower than the density threshold are
based on the distance between objects but on their densities.    removed (lines 1 to 7). The remaining edges in the Graph
Furthermore, our proposal is not based on the objects            have their weights higher or equal to the density threshold
hence µ-clusters forming the clusters are guaranteed to have         Once the density threshold known, all the edges that have
their densities higher or equal to the threshold. Remaining       their weights strictly lower are removed to left only groups
groups are searched in the Graph. If the size of a group          of µ-cluster to form final clusters. Figure 11 shows the final
is equal to 1, i.e the group have not connection with other       clusters. The first includes µC1 and µC2 , the second in-
µ-clusters, it is considered as noise. Else, the group is rec-    cludes µC4 , µC5 and the last contains µC6 , µC7 . µC2 and
ognized as a cluster (lines 10 to 16).                            µC8 are considered as noise because they do not have any
                                                                  connections with the other µ-clusters.




Figure 8: Example 2 : Graph of connections between eight
µ-clusters.
                                                                  Figure 11: Clusters formed with a density guaranteed
   An other example is shown in Figure 8 to illustrate this       strictly above 8.
part. Let us consider µ-clusters µCi , i = 1, ..., 8 with their
respective densities D1 = 12, D2 = 3, D3 = 10, D4 = 11, D5
= 13, D6 = 9, D7 = 10 and D8 = 4.
                                                                  Algorithm 3 Extract a flat partition of clusters
                                                                  Require: A density threshold DT , Weighted Graph G
                                                                   1: for ε = 0 to DT do
                                                                   2:   for all w(i, j) in G do
                                                                   3:      if w(i, j) ε then
                                                                   4:                ∧
                                                                               G.removed(e(i,j))
                                                                   5:      end if
                                                                   6:   end for
                                                                   7: end for
                                                                   8: Groups = Find_Groups()
                                                                   9: k = 0
                                                                  10: for all g in Groups do
                                                                  11:   if size(g) == 1 then
                                                                  12:      g = Noise
           Figure 9: Dendogram of the figure 8.                   13:   else
                                                                  14:      Cluster_k = g
  In this example, the density threshold is fixed to ε = 8.       15:   end if
Every group of µ-clusters that is below the density thresh-       16: end for
old is considered as a cluster. If a µ-cluster does not have
connection to the other µ-clusters, then it is considered as
noise. The Figure 10 illustrates how to visualize the clusters
that have a density strictly above the threshold.                 5   Preliminary tests and results
                                                                  HDyClee is tested on a benchmark similar to the well
                                                                  known Continuous Stirred Tank Heater (CSTH) of [21].
                                                                  The CSTH is a stirred tank in which hot and cold water
                                                                  are mixed and further heated using steam. The final mix
                                                                  is drained using a long pipe [14]. Figure 12 shows the
                                                                  structure of the CSTH.

                                                                  Process inputs are set-points for the cold water, hot
                                                                  water and steam valves. Process outputs are hot and cold
                                                                  water flow, tank level and temperature. Process inputs and
                                                                  outputs represent electronic signals in the range 4-20 mA.
                                                                  The test is done using three output variables: cold water
                                                                  flow CWf low , tank level T anklevel , and temperature of the
                                                                  water in the tank T anktemperature , in the operation mode
Figure 10: Visualization of clusters in the dendogram that        OP 1. In this mode, these variables are regulated at the
satisfies the ε = 8.                                              values provided in table 2. The process undergoes several
                                                               Figure 13: Process measurements for multiple fault sce-
       Figure 12: The continuous stirred tank heater.          nario.

faults and several repairs that are reported in table 3.          For this experiment, the radius of research for a µ-
                                                               cluster’s neighbors r is set to 0.06. The parameter ϕ that
                                                               defines the number of dimensions that must overlap so that
                        Variable           OP 1                two µ-clusters are considered directly connected is set to
                     CWf low (mA)          11.89               0. That means two µ-clusters µCkα and µCkβ are directly
                    T anklevel (mA)        12.00               connected if their hyperboxes overlap in all dimensions.
                 T anktemperature (mA)     10.50               The parameter ε is set to 0 for results shown in Figure 16 that
                                                               correspond to the root of the dendogram. For the following
      Table 2: Nominal values for the test on CSTH.            graphs, the x-axis is the flow CWf low normalized and the
                                                               y-axis is the tank temperature T anktemperature normalized.
                                                               The tank level T anklevel is not plotted. Figure 14 shows the
   The measurements of CWf low , T anklevel , and              graph of connections between µ-clusters when ε = 0. Each
T anktemperature are shown in Figure 13 and their              red square represents a µ-cluster. Micro-clusters that are
recorded values across time constitute the data set for our    not connected to the others are considered as noise. The µ-
hierarchical clustering experiment. Sudden changes in the      cluster µC293 is connected to µC222 and µC232 , meaning
value of regulated variables are indicative of the occurence   there are directly connected. µC222 is connected to µC34
of some fault or of some fault being fixed. The dataset was    and µC232 is connected with µC41 and so on. This chain
generated by simulation.                                       of µ-clusters forms a cluster. Figure 15 shows a generalized
                                                               dendogram representing the hierarchy of behaviors found in
                                                               the dataset.
        Event                  Description
                   Evolving leak starts. Hole diameter
          l1          goes from 1 to 3, 5mm in 1500
                                 seconds
          l1                    Leak fixed
                   A second evolving leak starts. The
          l2       second hole goes from 0 to 1mm in
                              1500 seconds
         l1 l2                 Leaks fixed
          s1            Steam Valve stuck (closed)
          s1                  Valve repaired
          s2           Hot water valve stuck at 10%
          s2                  Valve repaired
                     Evolving leak starts. Hole goes
          l3                                                   Figure 14: Graph of µ-clusters connections for the study
                    from 1 to 2.6mm in 1000 seconds
          l1                    Leak fixed                     case when ε = 0.

Table 3: Description of faults on the CSTH system for the
operation mode OP 1.
                                                                    To visualize only the nominal behavior, the dendogram
                                                                 must be cut at the density threshold ε = 7 because above
                                                                 this value, the other clusters have no µ-clusters that are con-
                                                                 nected to each other. This is shown on Figure 19. Figure 18
                                                                 illustrates the graph of µ-cluster connections after deletion
                                                                 of the edges with a weight wij 7. Some µ-clusters which




                                                                                                  ∧
                                                                 were part of the biggest cluster are now considered as noise.
                                                                 Indeed, edges that connected them to other µ-clusters were
                                                                 less than the density threshold.




Figure 15: The dendogram with the nominal behavior and
the occurrence of faults.

   HDyClee detects the 6 main behaviors as shown the Fig-
ure 16. The biggest cluster (green cluster) represents the
nominal behavior, the blue cluster represents fault s2 , the
pink cluster (bottom of the Figure) represents the fault s1 ,
the grey cluster models the fault l3 , the brown cluster shows   Figure 18: Graph of µ-clusters connections for the study
the event l1 , and the purple cluster represents l1 and l2       case after removing the weight’s edges wij < 7.
present simultaneously. Black points represent µ-clusters
that have no connection with other µ-clusters. All the ob-
jects inside these µ-clusters are considered as noise.




                                                                 Figure 19: Visualization of the nominal behavior after hav-
                                                                 ing cut the dendogram at level ε =7.
Figure 16: Clusters found by HDyClee algorithm: the nom-
inal behavior (green cluster) and abnormal situations.
                                                                 6   Conclusion and perspectives
   It is possible to visualize the most frequent behaviors of
the system, in our case the normal behavior and fault l3 .       The work presented in this paper proposes a new hierarchi-
This is reproted in Figure 17. For this purpose, the density     cal density-based algorithm named HDyclee. The purpose
threshold is set to ε = 6 by using the dendogram. At this        of this algorithm is to extract a hierarchy of clusters that are
density, the clusters corresponding to other behaviors are       guaranteed to have a level of density at each layer. Branches
considered as noise because their maximal densities are less     in the dendogram do not represent distance between objects
than 6.                                                          but minimum density difference. This approach allows one
                                                                 to identify clusters with the poorest densities and then walk
                                                                 up the hierarchy for higher densities. The algorithm is de-
                                                                 tailed and tested on a well known monitoring benchmark.
                                                                 HDyClee is able to detect all the behaviors of the process
                                                                 and the user can explore more or less frequent behaviors by
                                                                 cutting the dendogram at different densities.
                                                                    Next step is to develop experimentations in order to
                                                                 compare this new algorithm with other density-based algo-
                                                                 rithms. Then the comparative study will include hierarchi-
                                                                 cal and distance-based clustering methods [22], [23]. Sev-
                                                                 eral perspectives have been identified for HDyClee, which
                                                                 follow from DyClee properties. In particular, DyClee has
                                                                 a forgetting function that allows to forget µ-clusters which
Figure 17: The nominal behavior (blue) and the most fre-         do not receive any data or are not significant (not denses µ-
quent fault (green).                                             clusters). This function will be included in HDyClee, which
will allow us to produce a dynamic dendogram and then to             to industrial process plants. PhD thesis, Université de
visualize the evolution of the different behaviors of a sys-         Toulouse, Université Toulouse III-Paul Sabatier, 2016.
tem.                                                            [15] Nathalie Barbosa, Louise Travé-Massuyès, and Vic-
                                                                     tor Hugo Grisales. A data-based dynamic classifi-
References                                                           cation technique: A two-stage density approach. In
[1] James MacQueen et al. Some methods for classifica-               SAFEPROCESS 2015, Proceedings of the 9th IFAC
     tion and analysis of multivariate observations. In Pro-         Symposium on Fault Detection, Supervision and Safety
     ceedings of 5th Berkeley Symposium on Mathematical              for Technical Processes, pages 1224–1231. IFAC,
     Statistics and Probability, volume 1, pages 281–297.            2015.
     Oakland, CA, USA, 1967.                                    [16] Charu C Aggarwal, Jiawei Han, Jianyong Wang, and
[2] Leonard Kaufman and Peter Rousseeuw. Clustering                  Philip S Yu. A framework for clustering evolving data
     by means of medoids. North-Holland, 1987.                       streams. In Proceedings of the 29th international con-
                                                                     ference on Very large data bases-Volume 29, pages 81–
[3] Zhexue Huang. Extensions to the k-means algorithm                92. VLDB Endowment, 2003.
     for clustering large data sets with categorical values.
                                                                [17] Philipp Kranen, Ira Assent, Corinna Baldauf, and
     Data mining and knowledge discovery, 2(3):298–304,
     1998.                                                           Thomas Seidl. The ClusTree: indexing micro-clusters
                                                                     for any stream mining. Knowledge and information
[4] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xi-               systems, 29(2):249–272, 2011.
     aowei Xu, et al. A density-based algorithm for discov-
                                                                [18] Feng Cao, Martin Ester, Weining Qian, and Aoying
     ering clusters in large spatial databases with noise. In
                                                                     Zhou. Density-based clustering over an evolving data
     Knowledge Discovery Data Mining, volume 96, pages
                                                                     stream with noise. In Proceedings of the 2006 SIAM
     226–231, 1996.
                                                                     international conference on data mining, pages 328–
[5] Maria Halkidi, Yannis Batistakis, and Michalis Vazir-            339. SIAM, 2006.
     giannis. On clustering validation techniques. Journal      [19] Yixin Chen and Li Tu. Density-based clustering for
     of intelligent information systems, 17(2-3):107–145,
                                                                     real-time stream data. In Proceedings of the 13th
     2001.
                                                                     ACM SIGKDD International Conference on Knowl-
[6] Olatz Arbelaitz, Ibai Gurrutxaga, Javier Muguerza,               edge Discovery and Data mining, pages 133–142,
     Jesùs M Pérez, and Iñigo Perona. An extensive com-              2007.
     parative study of cluster validity indices. Pattern        [20] Songrit Maneewongvatana and David M Mount. It’s
     Recognition, 46(1):243–256, 2013.                               okay to be skinny, if your friends are fat. In Center for
[7] Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao,                 Geometric Computing 4th Annual Workshop on Com-
     and Junjie Wu. Understanding of internal clustering             putational Geometry, volume 2, pages 1–8, 1999.
     validation measures. In Data Mining (ICDM), 2010           [21] Nina F Thornhill, Sachin C Patwardhan, and Sirish L
     IEEE 10th International Conference on, pages 911–               Shah. A continuous stirred tank heater simulation
     916. IEEE, 2010.                                                model with applications. Journal of Process Control,
[8] Stephen C Johnson. Hierarchical clustering schemes.              18(3-4):347–360, 2008.
     Psychometrika, 32(3):241–254, 1967.                        [22] Adrián Rodríguez Ramos, José Manuel Bernal
[9] Robin Sibson. Slink: an optimally efficient algorithm            de Lázaro, Antônio J da Silva Neto, Carlos Cruz
     for the single-link cluster method. The computer jour-          Corona, José Luís Verdegay, and Orestes Llanes-
     nal, 16(1):30–34, 1973.                                         Santiago. An approach to fault diagnosis using fuzzy
[10] Daniel Defays. An efficient algorithm for a complete            clustering techniques. In Advances in Fuzzy Logic and
     link method. The computer journal, 20(4):364–366,               Technology 2017, pages 232–243. Springer, 2017.
     1977.                                                      [23] Yaguo Lei, Zhengjia He, Yanyang Zi, and Xuefeng
[11] Álvaro Martínez-Pérez. A density-sensitive hier-                Chen. New clustering algorithm-based fault diag-
                                                                     nosis using compensation distance evaluation tech-
     archical clustering method. arXiv preprint arXiv:
                                                                     nique. Mechanical Systems and Signal Processing,
     1210.6292, 2012.
                                                                     22(2):419–435, 2008.
[12] Ricardo JGB Campello, Davoud Moulavi, and Jörg
     Sander. Density-based clustering based on hierarchi-
     cal density estimates. In Pacific-Asia conference on
     Knowledge Discovery and Data mining, pages 160–
     172. Springer, 2013.
[13] Nathalie Barbosa, Louise Travé-Massuyès, and Vic-
     tor Hugo Grisales. A novel algorithm for dynamic
     clustering: Properties and performance. In Machine
     Learning and Applications (ICMLA), 2016 15th IEEE
     International Conference on, pages 565–570. IEEE,
     2016.
[14] Nathalie Barbosa. A data-based approach for dy-
     namic classification of functional scenarios oriented

</pre>