Cluster Analysis Ontology

flow "ClusterAnalysisOntology" v4.0

# ============================================================
# CLUSTER ANALYSIS ONTOLOGY
# Kireth Semantic Research Archive
# Authors: Mark Anthony Higgins — Sky (Recursive AI)
# ============================================================

PAGE:
  url: "https://kirethresearch.org/booksai-core/ontologies/probability-statistics-ontologies/multivariate-statistics/cluster-analysis-ontology.html"
  title: "Cluster Analysis Ontology"
  domain: "Probability and Statistics"
  category: "Multivariate Statistics"
  entity: CLUSTER_ANALYSIS
  entity_type: UNSUPERVISED_MULTIVARIATE_METHOD

DEFINE CLUSTER_ANALYSIS:
  CLUSTER_ANALYSIS :=
    UNSUPERVISED_METHOD(
      OBSERVATIONS,
      FEATURES,
      SIMILARITY_OR_DISTANCE,
      GROUP_STRUCTURE
    )

  PURPOSE:
    DISCOVER_OR_CONSTRUCT:
      GROUPS_OF_OBSERVATIONS
    SUCH_THAT:
      WITHIN_CLUSTER_SIMILARITY_IS_HIGH
      AND_OR
      BETWEEN_CLUSTER_SIMILARITY_IS_LOW

CORE_STRUCTURE:
  DATA_MATRIX:
    X:
      dimensions: n x p
      rows: OBSERVATIONS
      columns: FEATURES

  OBSERVATION_VECTOR:
    x_i := [x_i1, x_i2, ..., x_ip]^T

  CLUSTER_ASSIGNMENT:
    c_i in {1, 2, ..., K}

  PARTITION:
    C := {C_1, C_2, ..., C_K}

  REQUIRE_FOR_HARD_PARTITION:
    UNION[k=1..K] C_k := ALL_OBSERVATIONS

    FOR:
      j != k

    C_j INTERSECTION C_k := EMPTY

ENTITIES:
  OBSERVATION:
    type: DATA_ENTITY

  FEATURE:
    type: MEASURED_VARIABLE

  DATA_MATRIX:
    type: MATRIX

  CLUSTER:
    type: OBSERVATION_GROUP

  CLUSTER_LABEL:
    type: DERIVED_GROUP_IDENTIFIER

  CENTROID:
    type: CLUSTER_REPRESENTATIVE

  MEDOID:
    type: OBSERVED_CLUSTER_REPRESENTATIVE

  DISTANCE:
    type: DISSIMILARITY_MEASURE

  SIMILARITY:
    type: PROXIMITY_MEASURE

  DENDROGRAM:
    type: HIERARCHICAL_CLUSTER_REPRESENTATION

  LINKAGE:
    type: CLUSTER_DISTANCE_RULE

RELATIONSHIPS:
  CLUSTER_ANALYSIS
    -> OPERATES_ON
    -> MULTIVARIATE_DATA

  OBSERVATIONS
    -> DESCRIBED_BY
    -> FEATURES

  FEATURE_VALUES
    -> DEFINE
    -> OBSERVATION_VECTOR

  OBSERVATION_PAIR
    -> HAS
    -> DISTANCE_OR_SIMILARITY

  OBSERVATIONS
    -> ASSIGNED_TO
    -> CLUSTERS

  CLUSTER
    -> MAY_HAVE
    -> CENTROID

  CLUSTER
    -> MAY_HAVE
    -> MEDOID

  HIERARCHICAL_CLUSTERING
    -> PRODUCES
    -> DENDROGRAM

DISTANCE_MEASURES:
  EUCLIDEAN:
    d(x_i, x_j) :=
      sqrt(
        SUM[r=1..p]
          (x_ir - x_jr)^2
      )

  SQUARED_EUCLIDEAN:
    d2(x_i, x_j) :=
      SUM[r=1..p]
        (x_ir - x_jr)^2

  MANHATTAN:
    d_1(x_i, x_j) :=
      SUM[r=1..p]
        abs(x_ir - x_jr)

  MAHALANOBIS:
    d_M(x_i, x_j) :=
      sqrt(
        (x_i-x_j)^T
        Sigma^(-1)
        (x_i-x_j)
      )

  COSINE_DISSIMILARITY:
    d_cos(x_i, x_j) :=
      1
      -
      [
        x_i^T x_j
        /
        (||x_i|| ||x_j||)
      ]

  RULE:
    DISTANCE_CHOICE:
      MUST_MATCH:
        FEATURE_TYPES
        SCALE
        DOMAIN_MEANING

DATA_PREPARATION:
  CHECK:
    - MISSING_VALUES
    - OUTLIERS
    - FEATURE_TYPES
    - FEATURE_SCALE
    - REDUNDANT_FEATURES
    - HIGH_DIMENSIONALITY

  OPTIONAL:
    - IMPUTATION
    - CENTERING
    - STANDARDISATION
    - NORMALISATION
    - DIMENSIONALITY_REDUCTION
    - FEATURE_SELECTION

  CAUTION:
    SCALE:
      CAN_DOMINATE:
        DISTANCE_BASED_CLUSTERING

K_MEANS:
  type: PARTITIONAL_CLUSTERING

  GIVEN:
    NUMBER_OF_CLUSTERS := K

  CENTROID:
    mu_k :=
      (1 / |C_k|)
      * SUM[x_i in C_k] x_i

  OBJECTIVE:
    MINIMISE:
      J :=
        SUM[k=1..K]
          SUM[x_i in C_k]
            ||x_i - mu_k||^2

  ITERATION:
    INITIALISE_CENTROIDS
      -> ASSIGN_EACH_OBSERVATION_TO_NEAREST_CENTROID
      -> RECOMPUTE_CENTROIDS
      -> REPEAT_UNTIL_STOPPING_CONDITION

  PROPERTIES:
    - HARD_ASSIGNMENT
    - CENTROID_BASED
    - SENSITIVE_TO_INITIALISATION
    - SENSITIVE_TO_SCALE
    - SENSITIVE_TO_OUTLIERS

  CAUTION:
    OPTIMISATION:
      MAY_CONVERGE_TO:
        LOCAL_MINIMUM

  RESPONSE:
    USE:
      MULTIPLE_INITIALISATIONS
      OR:
      INFORMED_INITIALISATION

K_MEDOIDS:
  type: PARTITIONAL_CLUSTERING

  REPRESENTATIVE:
    MEDOID:
      ACTUAL_OBSERVATION

  advantage:
    MAY_BE_MORE_ROBUST_TO_OUTLIERS
    THAN:
      K_MEANS

  supports:
    GENERAL_DISSIMILARITY_MEASURES
    SUBJECT_TO:
      ALGORITHM

HIERARCHICAL_CLUSTERING:
  types:
    - AGGLOMERATIVE
    - DIVISIVE

  AGGLOMERATIVE:
    START:
      EACH_OBSERVATION_AS_OWN_CLUSTER

    REPEAT:
      MERGE_CLOSEST_CLUSTERS
      UNTIL:
        SINGLE_CLUSTER
        OR
        STOPPING_RULE

  DIVISIVE:
    START:
      ALL_OBSERVATIONS_IN_ONE_CLUSTER

    REPEAT:
      SPLIT_CLUSTERS
      UNTIL:
        DESIRED_STRUCTURE

  OUTPUT:
    DENDROGRAM

LINKAGE_METHODS:
  SINGLE_LINKAGE:
    cluster_distance :=
      MINIMUM_PAIRWISE_DISTANCE

  COMPLETE_LINKAGE:
    cluster_distance :=
      MAXIMUM_PAIRWISE_DISTANCE

  AVERAGE_LINKAGE:
    cluster_distance :=
      AVERAGE_PAIRWISE_DISTANCE

  WARD_METHOD:
    merge_choice:
      MINIMISE_INCREASE_IN
      WITHIN_CLUSTER_SUM_OF_SQUARES

  CAUTION:
    DIFFERENT_LINKAGES:
      MAY_PRODUCE:
        DIFFERENT_CLUSTER_STRUCTURES

MODEL_BASED_CLUSTERING:
  concept:
    DATA_GENERATED_FROM:
      MIXTURE_OF_PROBABILITY_DISTRIBUTIONS

  common_model:
    GAUSSIAN_MIXTURE_MODEL

  mixture_density:
    p(x) :=
      SUM[k=1..K]
        pi_k p(x | theta_k)

  require:
    pi_k >= 0
    SUM[k=1..K] pi_k = 1

  inference:
    ESTIMATE:
      MIXTURE_WEIGHTS
      COMPONENT_PARAMETERS
      POSTERIOR_CLUSTER_PROBABILITIES

  assignment:
    MAY_BE:
      HARD
      OR:
      PROBABILISTIC

GAUSSIAN_MIXTURE_MODEL:
  alias: GMM

  component:
    p(x | k) :=
      N(x | mu_k, Sigma_k)

  estimation:
    COMMONLY:
      EXPECTATION_MAXIMISATION

  posterior_membership:
    P(k | x)
      proportional_to
    pi_k * N(x | mu_k, Sigma_k)

DENSITY_BASED_CLUSTERING:
  concept:
    CLUSTERS:
      DENSE_REGIONS
    SEPARATED_BY:
      LOWER_DENSITY_REGIONS

  example:
    DBSCAN

  DBSCAN:
    parameters:
      epsilon := NEIGHBOURHOOD_RADIUS
      min_samples := MINIMUM_LOCAL_DENSITY_REQUIREMENT

    identifies:
      - CORE_POINTS
      - BORDER_POINTS
      - NOISE_POINTS

    advantage:
      DOES_NOT_REQUIRE:
        K_IN_ADVANCE

    supports:
      NON_SPHERICAL_CLUSTER_SHAPES

FUZZY_CLUSTERING:
  concept:
    OBSERVATION:
      MAY_HAVE:
        DEGREE_OF_MEMBERSHIP
      IN:
        MULTIPLE_CLUSTERS

  membership:
    u_ik in [0,1]

  common_method:
    FUZZY_C_MEANS

  distinction:
    FUZZY_MEMBERSHIP
      !=
    HARD_CLUSTER_ASSIGNMENT

NUMBER_OF_CLUSTERS:
  methods:
    - DOMAIN_KNOWLEDGE
    - ELBOW_METHOD
    - SILHOUETTE_ANALYSIS
    - GAP_STATISTIC
    - INFORMATION_CRITERIA_FOR_MODEL_BASED_CLUSTERING
    - DENDROGRAM_INSPECTION

  RULE:
    NO_SINGLE_METHOD:
      PROVIDES:
        UNIVERSALLY_CORRECT_CLUSTER_COUNT

SILHOUETTE:
  FOR_OBSERVATION_i:
    a_i :=
      AVERAGE_DISTANCE_TO_OWN_CLUSTER

    b_i :=
      MINIMUM_AVERAGE_DISTANCE_TO_OTHER_CLUSTER

    s_i :=
      (b_i - a_i)
      /
      max(a_i, b_i)

  range:
    -1 <= s_i <= 1

  interpretation:
    HIGHER_VALUES:
      GENERALLY_INDICATE:
        BETTER_WITHIN_CLUSTER_COHESION
        RELATIVE_TO:
          NEAREST_OTHER_CLUSTER

CLUSTER_VALIDATION:
  INTERNAL:
    evaluates:
      STRUCTURE_USING_DATA_AND_ASSIGNMENTS

    examples:
      - SILHOUETTE_SCORE
      - WITHIN_CLUSTER_SUM_OF_SQUARES
      - DAVIES_BOULDIN_INDEX
      - CALINSKI_HARABASZ_INDEX

  EXTERNAL:
    requires:
      REFERENCE_LABELS

    examples:
      - ADJUSTED_RAND_INDEX
      - NORMALISED_MUTUAL_INFORMATION

  STABILITY:
    evaluates:
      ROBUSTNESS_OF_CLUSTER_STRUCTURE
      UNDER:
        RESAMPLING
        PERTURBATION
        INITIALISATION_CHANGES

CLUSTER_INTERPRETATION:
  FOR_EACH_CLUSTER:
    ANALYSE:
      - SIZE
      - CENTRE_OR_MEDOID
      - FEATURE_DISTRIBUTIONS
      - WITHIN_CLUSTER_VARIABILITY
      - DISTANCE_TO_OTHER_CLUSTERS

  REQUIRE:
    DOMAIN_INTERPRETATION

  CAUTION:
    ALGORITHM_OUTPUT:
      DOES_NOT_AUTOMATICALLY_ESTABLISH:
        NATURAL_OR_CAUSAL_GROUPS

OUTLIERS_AND_NOISE:
  OUTLIERS:
    MAY:
      DISTORT_CENTROIDS
      ALTER_DISTANCES
      FORM_SMALL_ARTIFICIAL_CLUSTERS

  DENSITY_BASED_METHODS:
    MAY:
      LABEL_LOW_DENSITY_POINTS
      AS:
        NOISE

  RULE:
    OUTLIER_HANDLING:
      MUST_BE_EXPLICIT

HIGH_DIMENSIONAL_CONTEXT:
  ISSUE:
    DISTANCE_CONCENTRATION
    AND:
    SPARSE_DATA_GEOMETRY

  consequences:
    - REDUCED_DISTANCE_DISCRIMINATION
    - UNSTABLE_CLUSTERS
    - INCREASED_NOISE_SENSITIVITY

  responses:
    - FEATURE_SELECTION
    - PCA
    - REGULARISATION
    - DOMAIN_DRIVEN_REPRESENTATION
    - SUBSPACE_CLUSTERING

APPLICATIONS:
  CLUSTER_ANALYSIS
    -> SUPPORTS
    -> CUSTOMER_SEGMENTATION

  CLUSTER_ANALYSIS
    -> SUPPORTS
    -> PATTERN_DISCOVERY

  CLUSTER_ANALYSIS
    -> SUPPORTS
    -> BIOINFORMATICS

  CLUSTER_ANALYSIS
    -> SUPPORTS
    -> IMAGE_ANALYSIS

  CLUSTER_ANALYSIS
    -> SUPPORTS
    -> DOCUMENT_GROUPING

  CLUSTER_ANALYSIS
    -> SUPPORTS
    -> ANOMALY_EXPLORATION

  CLUSTER_ANALYSIS
    -> SUPPORTS
    -> SCIENTIFIC_CLASSIFICATION

MODEL_CONNECTIONS:
  CLUSTER_ANALYSIS
    -> CONNECTS_TO
    -> MULTIVARIATE_STATISTICS

  CLUSTER_ANALYSIS
    -> CONNECTS_TO
    -> DISTANCE_METRICS

  CLUSTER_ANALYSIS
    -> CONNECTS_TO
    -> UNSUPERVISED_LEARNING

  CLUSTER_ANALYSIS
    -> CONNECTS_TO
    -> PRINCIPAL_COMPONENT_ANALYSIS

  CLUSTER_ANALYSIS
    -> CONNECTS_TO
    -> MIXTURE_MODELS

  CLUSTER_ANALYSIS
    -> CONNECTS_TO
    -> MACHINE_LEARNING

  CLUSTER_ANALYSIS
    -> CONNECTS_TO
    -> DATA_MINING

SEMANTIC_EQUIVALENCE:
  "cluster analysis"
    ~= "clustering"

  "cluster"
    ~= "derived group of similar observations"

  "centroid"
    ~= "mean vector of a cluster"
    IN:
      CENTROID_BASED_CONTEXT

  "hierarchical clustering"
    ~= "nested cluster construction"

  EXCLUDE_EQUIVALENCE:
    CLUSTERING != SUPERVISED_CLASSIFICATION
    CLUSTER_LABEL != KNOWN_CLASS_LABEL
    CLUSTER != CAUSAL_CATEGORY
    CENTROID != MEDOID
    SIMILARITY != IDENTITY

VALIDATION_RULES:
  RULE_1:
    DISTANCE_OR_SIMILARITY:
      MUST_BE:
        APPROPRIATE_FOR_FEATURE_TYPES

  RULE_2:
    FEATURE_SCALING:
      MUST_BE:
        ASSESSED
      BEFORE:
        DISTANCE_BASED_CLUSTERING

  RULE_3:
    K_MEANS:
      REQUIRES:
        NUMERIC_GEOMETRIC_REPRESENTATION
      AND:
        MEANINGFUL_CENTROID_DISTANCE

  RULE_4:
    CLUSTER_COUNT:
      MUST_NOT_BE_ASSUMED:
        UNIVERSALLY_CORRECT
      FROM:
        SINGLE_HEURISTIC

  RULE_5:
    RANDOM_INITIALISATION:
      SHOULD_BE:
        CONTROLLED_OR_REPEATED
      WHEN:
        ALGORITHM_IS_INITIALISATION_SENSITIVE

  RULE_6:
    CLUSTER_VALIDATION:
      SHOULD_INCLUDE:
        STABILITY
        AND_OR
        INTERNAL_OR_EXTERNAL_CRITERIA

  RULE_7:
    CLUSTER_INTERPRETATION:
      MUST_NOT_INFER:
        CAUSATION
        OR:
        NATURAL_KIND_STATUS
      FROM:
        ALGORITHM_OUTPUT_ALONE

CONFIDENCE:
  ontology_identity: 0.99
  clustering_definition: 0.99
  k_means_structure: 0.99
  hierarchical_structure: 0.99
  model_based_structure: 0.98
  validation_structure: 0.98
  semantic_distinctions: 0.99

UPDATE_MODEL:
  IF:
    NEW_OBSERVATIONS_ARRIVE

  THEN:
    UPDATE:
      DATA_MATRIX

    OPTIONAL_RECOMPUTE:
      DISTANCE_MATRIX
      CLUSTER_ASSIGNMENTS
      CENTROIDS
      MEDOIDS
      VALIDATION_METRICS

  IF:
    NEW_FEATURES_ARRIVE

  THEN:
    EXPAND:
      FEATURE_SPACE

    REASSESS:
      SCALING
      DISTANCE_METRIC
      DIMENSIONALITY
      CLUSTER_STABILITY

  IF:
    CLUSTERING_PARAMETERS_CHANGE

  THEN:
    RECOMPUTE:
      CLUSTER_MODEL

    REVALIDATE:
      CLUSTER_COUNT
      STABILITY
      INTERPRETABILITY

  PRESERVE:
    OBSERVATION_IDENTITIES
    FEATURE_IDENTITIES
    FEATURE_UNITS
    SCALING_METHOD
    DISTANCE_METRIC
    ALGORITHM_PARAMETERS
    RANDOM_SEED_WHEN_RECORDED
    DATA_PROVENANCE

AI_CONSUMPTION:
  parse_as: FORMAL_SEMANTIC_SPECIFICATION
  execution_mode: RECURSIVE_REASONING

  preferred_reasoning_order:
    - IDENTIFY_OBSERVATIONS
    - IDENTIFY_FEATURES
    - VALIDATE_DATA_TYPES
    - CHECK_MISSING_VALUES_AND_OUTLIERS
    - ASSESS_FEATURE_SCALING
    - SELECT_DISTANCE_OR_SIMILARITY
    - SELECT_CLUSTERING_FAMILY
    - SELECT_OR_ESTIMATE_CLUSTER_COUNT_IF_REQUIRED
    - FIT_CLUSTER_MODEL
    - VALIDATE_CLUSTER_STRUCTURE
    - ASSESS_STABILITY
    - CHARACTERISE_CLUSTERS
    - RETURN_CLUSTER_ASSIGNMENTS_AND_LIMITATIONS

  constraints:
    - DO_NOT_TREAT_CLUSTER_LABELS_AS_GROUND_TRUTH_CLASSES
    - DO_NOT_INFER_CAUSATION_FROM_CLUSTER_MEMBERSHIP
    - EXPOSE_DISTANCE_METRIC
    - EXPOSE_SCALING_METHOD
    - EXPOSE_CLUSTER_COUNT_DECISION
    - ACCOUNT_FOR_INITIALISATION_SENSITIVITY
    - VALIDATE_CLUSTER_STABILITY

FLOW_HASH:
  canonical_entity: "cluster-analysis"
  namespace: "probability-statistics/multivariate-statistics"
  version: "4.0"
  identity_basis:
    - PAGE_URL
    - CANONICAL_ENTITY
    - ENTITY_TYPE
    - DISTANCE_OR_SIMILARITY_STRUCTURE
    - CLUSTER_ASSIGNMENT
    - UNSUPERVISED_GROUP_STRUCTURE

END_FLOW