FLAME clustering

Description of the FLAME algorithm

The FLAME algorithm is mainly divided into three steps:

1. Extraction of the structure information from the dataset:
   1. Construct a neighborhood graph to connect each object to its K-Nearest Neighbors (KNN);
   2. Estimate a density for each object based on its proximities to its KNN;
   3. Objects are classified into 3 types:
      1. Cluster Supporting Object (CSO): object with density higher than all its neighbors;
      2. Cluster Outliers: object with density lower than all its neighbors, and lower than a predefined threshold;
      3. the rest.
2. Local/Neighborhood approximation of fuzzy memberships:
   1. Initialization of fuzzy membership:
      1. Each CSO is assigned with fixed and full membership to itself to represent one cluster;
      2. All outliers are assigned with fixed and full membership to the outlier group;
      3. The rest are assigned with equal memberships to all clusters and the outlier group;
   2. Then the fuzzy memberships of all type 3 objects are updated by a converging iterative procedure called Local/Neighborhood Approximation of Fuzzy Memberships, in which the fuzzy membership of each object is updated by a linear combination of the fuzzy memberships of its nearest neighbors.
3. Cluster construction from fuzzy memberships in two possible ways:
   1. One-to-one object-cluster assignment, to assign each object to the cluster in which it has the highest membership;
   2. One-to-multiple object-clusters assignment, to assign each object to the cluster in which it has a membership higher than a threshold.