43 minute read

1. Introduction: Letting Data Decide the Clusters

Imagine you’re organizing a collection of photos. You want to group photos of similar events or scenes together. You could try to guess how many groups there are and then manually sort photos into those groups. But wouldn’t it be better if the photos themselves could tell you how many groups naturally exist and which photos belong together based on their similarity?

Quality Threshold (QT) Clustering is a clustering algorithm that tries to do exactly that – automatically determine the number of clusters and group data points into clusters based on a “quality threshold.” Unlike algorithms like K-Means or K-Modes, where you have to pre-specify the number of clusters (k), QT Clustering figures out the number of clusters on its own, based on the data structure.

Real-world examples where QT Clustering can be useful:

  • Biological Data Analysis (Gene Expression Clustering): In biology, scientists often analyze gene expression data to find groups of genes that are co-expressed (expressed in similar patterns across different conditions). QT Clustering can be used to cluster genes based on their expression profiles. The algorithm can automatically identify clusters of co-regulated genes, without the need to guess the number of gene clusters beforehand. These clusters can then provide insights into biological pathways and gene functions.

  • Document Clustering (Finding Thematic Groups Automatically): When you have a collection of documents and you want to group them by topic, QT Clustering can automatically determine the number of thematic groups present in the document collection. You don’t need to predefine how many topics you expect; QT clustering will form clusters based on document similarity and a quality threshold. This is useful for exploratory text analysis to discover natural groupings of documents.

  • Anomaly Detection (Identifying Outlier Clusters): QT Clustering can sometimes be used for anomaly detection. Outliers might end up forming very small, isolated clusters, or might not be assigned to any cluster at all (depending on the threshold setting). By examining the sizes and characteristics of QT clusters, you might identify data points that don’t fit well into any major cluster and could be potential anomalies.

  • Image Segmentation (Grouping Similar Image Regions): In image processing, QT Clustering (or similar density-based clustering techniques) can be used to segment images by grouping pixels with similar color or texture features. QT Clustering can help automatically identify regions of interest in an image without needing to pre-define the number of regions.

In simple terms, QT Clustering is like a smart sorting machine that automatically decides how many groups to create and which items belong to each group, based on how “close” or “similar” the items are to each other, and a pre-set “quality threshold” for cluster diameter. It’s all about letting the data structure itself guide the clustering process and determine the number of clusters.

2. The Mathematics of Quality Threshold: Diameter-Based Clustering

Let’s explore the mathematical ideas behind Quality Threshold (QT) Clustering in a simplified way. The algorithm is based on the concept of cluster diameter and iteratively builds clusters.

Key Concepts in QT Clustering:

  • Distance Threshold (Radius or Diameter): QT Clustering requires you to define a distance threshold, often called radius or diameter. This threshold, denoted as (T), is a crucial parameter. It determines the maximum allowed “diameter” (or radius, depending on definition) for any cluster.

  • Cluster Diameter: The diameter of a cluster is the maximum distance between any two points within that cluster. Different definitions of “diameter” exist; a common one is the maximum pairwise distance within a cluster. Let (C) be a cluster, and (d(x, y)) be a distance function between data points (x) and (y). The diameter of cluster (C), denoted as (D(C)), can be defined as:

    \[D(C) = \max_{x, y \in C} d(x, y)\]
    • Example: If you have three points in a cluster with pairwise distances: d(point1, point2)=2, d(point1, point3)=3, d(point2, point3)=4. The diameter of this cluster (using max pairwise distance) is 4.

  • Clustering Criterion (Quality Threshold): QT Clustering aims to create clusters such that the diameter of each cluster is less than or equal to the specified distance threshold (T). (D(C) \le T) for all clusters (C). This threshold ensures that all points within a cluster are “close enough” to each other, according to your definition of “closeness” through the distance metric and threshold (T).

QT Clustering Algorithm Steps (Simplified):

  1. Choose a Distance Threshold (Radius) (T): You need to set the distance threshold (T) (hyperparameter). This is a critical decision and often requires domain knowledge or experimentation. A smaller (T) will lead to more, tighter (smaller diameter) clusters. A larger (T) will result in fewer, looser (larger diameter) clusters.

  2. Initialize Clusters (No clusters at start): Start with no clusters.

  3. Iterate through Unclustered Data Points: Process data points one by one in some order (e.g., in the order they appear in your dataset). For each unclustered data point (x):

    a. Find Nearest Existing Cluster: Find the existing cluster (if any) whose centroid (or representative point, e.g., the first point added to the cluster in some variations) is closest to (x). “Closest” is measured using your chosen distance metric (d(x, \text{centroid})).

    b. Check Diameter Threshold: If a nearest cluster is found, calculate the diameter of the cluster if you were to add data point (x) to it.

    c. Cluster Assignment or New Cluster Creation: * If adding (x) to the nearest cluster keeps the cluster diameter below or equal to (T): Assign data point (x) to that cluster. * If adding (x) would make the cluster diameter exceed (T): Do not add (x) to any existing cluster. Start a new cluster with (x) as the first point in this new cluster.

  4. Repeat Step 3: Continue iterating through all unclustered data points and attempt to assign them to existing clusters or create new clusters as described in step 3c, until all data points are clustered.

Example: QT Clustering Illustrated (Simplified in 1D)

Let’s imagine we have data points on a number line (1D data) and we use Euclidean distance as the distance metric. Let’s set a distance threshold (T = 3).

Data points (sorted for simplicity of illustration): 1, 2, 3, 7, 8, 9, 15, 16, 20

  1. No clusters initially.

  2. Process point 1: No clusters exist, so start a new cluster C1 = {1}. Mode of C1 = 1.

  3. Process point 2: Nearest cluster is C1 (centroid=1). Distance d(2, 1) = 1. Diameter of C1 if we add 2: max(d(1,1), d(1,2), d(2,2)) = d(1,2) = 1, which is ≤ (T=3). So, add 2 to C1. C1 = {1, 2}. Mode (let’s say, first point added) still 1.

  4. Process point 3: Nearest cluster is C1 (centroid=1). Distance d(3, 1) = 2. Diameter of C1 if we add 3: max(pairwise distances in {1, 2, 3}) = d(1, 3) = 2, which is ≤ (T=3). Add 3 to C1. C1 = {1, 2, 3}. Mode still 1.

  5. Process point 7: Nearest cluster is C1 (centroid=1). Distance d(7, 1) = 6. Diameter of C1 if we add 7: max(pairwise distances in {1, 2, 3, 7}) = d(1, 7) = 6, which is > (T=3). Do not add 7 to C1. Start a new cluster C2 = {7}. Mode of C2 = 7.

  6. Process point 8: Nearest cluster is C2 (centroid=7). Distance d(8, 7) = 1. Diameter of C2 if we add 8: max(d(7,7), d(7,8), d(8,8)) = d(7, 8) = 1, which is ≤ (T=3). Add 8 to C2. C2 = {7, 8}. Mode still 7.

  7. Process point 9: Nearest cluster is C2 (centroid=7). Distance d(9, 7) = 2. Diameter of C2 if we add 9: max(pairwise distances in {7, 8, 9}) = d(7, 9) = 2, which is ≤ (T=3). Add 9 to C2. C2 = {7, 8, 9}. Mode still 7.

  8. Process point 15: Nearest cluster is C2 (centroid=7). Distance d(15, 7) = 8. Diameter of C2 if we add 15: max(pairwise distances in {7, 8, 9, 15}) = d(7, 15) = 8, which is > (T=3). Do not add 15 to C2. Nearest cluster is C1 (centroid=1). Distance d(15, 1) = 14. Diameter of C1 if we add 15: max(pairwise distances in {1, 2, 3, 15}) = d(1, 15) = 14, which is > (T=3). No suitable existing cluster. Start a new cluster C3 = {15}. Mode of C3 = 15.

  9. Process point 16: Nearest cluster is C3 (centroid=15). Distance d(16, 15) = 1. Diameter of C3 if we add 16: max(d(15, 15), d(15, 16), d(16, 16)) = d(15, 16) = 1, which is ≤ (T=3). Add 16 to C3. C3 = {15, 16}. Mode still 15.

  10. Process point 20: Nearest cluster is C3 (centroid=15). Distance d(20, 15) = 5. Diameter of C3 if we add 20: max(pairwise distances in {15, 16, 20}) = d(15, 20) = 5, which is > (T=3). Do not add 20 to C3. Nearest cluster is C2 (centroid=7). Distance d(20, 7) = 13. Diameter of C2 if we add 20: max(pairwise distances in {7, 8, 9, 20}) = d(7, 20) = 13, which is > (T=3). Nearest cluster is C1 (centroid=1). Distance d(20, 1) = 19. Diameter of C1 if we add 20: max(pairwise distances in {1, 2, 3, 20}) = d(1, 20) = 19, which is > (T=3). No suitable cluster. Start a new cluster C4 = {20}. Mode of C4 = 20.

Final clusters: C1 = {1, 2, 3}, C2 = {7, 8, 9}, C3 = {15, 16}, C4 = {20}. Number of clusters automatically determined as 4.

Key Idea: QT Clustering grows clusters iteratively. It adds points to clusters as long as the cluster diameter remains within the specified threshold (T). If adding a point would violate the diameter threshold, it starts a new cluster. This process automatically determines the number of clusters based on the data and the threshold.

3. Prerequisites and Preprocessing: Getting Ready for QT Clustering

Before using QT Clustering, let’s discuss prerequisites and preprocessing steps.

Prerequisites and Assumptions:

  • Distance Metric: You must define a distance metric that is appropriate for your data. For numerical data, Euclidean distance is common. For categorical data, Hamming distance or other categorical dissimilarity measures are used. The choice of distance metric is critical and affects how “closeness” and cluster diameters are measured.

  • Distance Threshold (T) (Radius/Diameter): You need to choose a suitable distance threshold (T). This is the main hyperparameter of QT Clustering and strongly influences the number and size of clusters. Setting (T) requires careful consideration and often involves experimentation or domain knowledge.

  • Order of Data Points (Somewhat Sensitive, especially for simple QT): The order in which data points are processed in the algorithm can sometimes slightly affect the final clustering, particularly in simple QT Clustering implementations. Data points processed earlier have a higher chance of becoming cluster centroids. More robust implementations might mitigate this order dependency to some extent.

  • Data Types (Numerical or Categorical): QT Clustering can be applied to both numerical and categorical data, as long as you choose an appropriate distance metric. For numerical data, Euclidean distance is used. For categorical data, Hamming distance (or other categorical dissimilarity measures) is used. For mixed numerical and categorical data, you might need to use a distance metric that can handle both types of features (like in K-Prototypes, but adapted for QT framework).

Testing Assumptions (and Considerations):

  • Distance Metric Validation: Ensure that your chosen distance metric meaningfully reflects the similarity or dissimilarity of data points in your domain. Is Euclidean distance appropriate for numerical data? Is Hamming distance suitable for categorical features? Consider alternative distance metrics if needed (e.g., Manhattan distance, cosine distance for numerical data; Jaccard distance for set-based categorical data).
  • Distance Threshold (T) Selection: Choosing a good distance threshold (T) is crucial and often the most challenging aspect of QT Clustering.
    • Domain Knowledge: If you have domain expertise that suggests a reasonable scale for “closeness” in your data, use that to guide the choice of (T). For example, if you know that clusters should have a maximum “diameter” of around 5 units in your feature space, set (T=5).
    • Experimentation and Parameter Sweep: Try different values for (T) and run QT Clustering for each value. Examine the resulting number of clusters and cluster characteristics (sizes, diameters, cluster profiles).
    • Visualization (If low-dimensional data): If your data is low-dimensional (2D or 3D), visualize your data points and visually experiment with different threshold values. Imagine drawing circles (or spheres in 3D) around points with radius (T). How does the clustering change as you adjust (T)?
  • Order Dependency (Consider Robustness): Be aware that simple QT Clustering might have some order dependency. If order sensitivity is a concern, consider running QT Clustering multiple times with different random orders of data points and see if the results are consistent. More robust implementations might use techniques to reduce order dependency.

Python Libraries for QT Clustering Implementation:

  • No widely used, readily available Python library for “pure” Quality Threshold Clustering like K-Means or t-SNE. QT Clustering is less algorithmically standardized in libraries compared to K-Means or hierarchical clustering.

  • Implementation from Scratch or Adaptation: You might need to implement QT Clustering algorithm yourself in Python, based on the algorithm description (as we’ll do in the example section). You can use libraries like NumPy (numpy) for numerical operations, distance calculations, and array manipulations. You might also find specialized clustering packages or code snippets online that implement QT Clustering or related density-based clustering ideas that you could adapt.

# Python Libraries Needed for Implementing QT Clustering
import numpy as np
import pandas as pd # For data handling
import matplotlib.pyplot as plt # For visualization (if applicable)

print("numpy version:", np.__version__)
import pandas
print("pandas version:", pandas.__version__)
import matplotlib
print("matplotlib version:", matplotlib.__version__)

Ensure you have numpy, pandas, and matplotlib installed in your Python environment. Install using pip if needed:

pip install numpy pandas matplotlib

For the implementation example, we’ll write a basic QT Clustering function using NumPy and Pandas, as a direct library for QT Clustering is not as readily available as for algorithms like K-Means.

4. Data Preprocessing: Choosing the Right Distance is Key

Data preprocessing for QT Clustering is less about specific transformations like scaling (which are crucial for some algorithms) and more about choosing and implementing the appropriate distance metric for your data and handling missing values.

Distance Metric: Choose Carefully Based on Data Type

  • Numerical Data: For numerical data features, Euclidean distance is a common and often good default choice. Manhattan distance is another option. Choose the distance metric that is most meaningful for your numerical features and the notion of “closeness” you want to capture.

    • Euclidean Distance: Standard straight-line distance in Euclidean space. Sensitive to magnitude differences and correlations between dimensions. Good general-purpose distance for numerical data.
    • Manhattan Distance: Sum of absolute differences along each dimension. Less sensitive to outliers than Euclidean distance. Might be preferred if you want to emphasize difference in individual dimensions rather than overall magnitude differences.
    • Cosine Distance (less common for QT directly): Cosine distance (or cosine similarity) measures the angle between vectors, ignoring magnitude. Often used for text data, document similarity, or vector embeddings. Less common as a direct distance metric in basic QT Clustering, but could be considered if cosine similarity is more relevant to your notion of “closeness.”

  • Categorical Data: For categorical features, Hamming distance (mismatch count) is the standard and most appropriate distance metric for QT Clustering.

    • Hamming Distance (Mismatch Count): Simply counts the number of features where two categorical data points have different category values. Well-suited for nominal categorical data.
    • Jaccard Distance (for Set-Based Categorical Data - less common for standard QT): Jaccard distance is used for set similarity. If your categorical data can be represented as sets (e.g., sets of words, sets of attributes), Jaccard distance might be considered, but less common in standard QT Clustering for categorical data compared to Hamming distance.
    • Custom Dissimilarity Measures (if needed): For more complex categorical data or specific domain requirements, you might need to define a custom dissimilarity measure that is tailored to your categorical features and the type of similarity you want to capture.

Data Preprocessing Examples (Distance Metric Implementation in Python - Conceptual):

import numpy as np

# Example data points (numerical and categorical)
numerical_point1 = np.array([1.0, 2.5, 3.0])
numerical_point2 = np.array([1.5, 2.8, 3.5])
categorical_point1 = ['Red', 'Medium', 'Casual']
categorical_point2 = ['Blue', 'Medium', 'Formal']

# Euclidean distance (for numerical data) - using numpy
euclidean_dist = np.linalg.norm(numerical_point1 - numerical_point2)
print("Euclidean Distance:", euclidean_dist)

# Hamming distance (for categorical data) - implement function as in previous blog example
def hamming_dissimilarity(data_point1, data_point2): # Same Hamming distance function as before
    distance = 0
    for i in range(len(data_point1)):
        if data_point1[i] != data_point2[i]:
            distance += 1
    return distance

hamming_dist = hamming_dissimilarity(categorical_point1, categorical_point2)
print("Hamming Distance:", hamming_dist)

When can data preprocessing be ignored (Less Strictly Enforced)?

  • Scaling and Normalization (Less relevant for basic QT, especially with non-Euclidean distances): Data scaling in the traditional numerical sense (like standardization or Min-Max scaling) is generally not necessary or directly applicable for QT Clustering, especially when using non-Euclidean distance metrics like Hamming distance for categorical data. Scaling is more crucial for algorithms that rely on Euclidean distance or gradient descent optimization where feature scales can significantly influence calculations. For QT Clustering, the choice of distance metric itself is more important than feature scaling. You focus on defining a meaningful distance measure and a relevant distance threshold.
  • If Data is Already Clean and Well-Formatted: If your data is already well-structured, clean, and in the appropriate format (numerical vectors for Euclidean distance, categorical data for Hamming distance), and you have handled missing values, then extensive preprocessing beyond defining the distance metric and threshold might not be required for basic QT Clustering. However, data cleaning and proper formatting are always good practices.

Best Practice: The most crucial preprocessing for QT Clustering is carefully choosing and correctly implementing the appropriate distance metric for your data type (Euclidean for numerical, Hamming for categorical, or a custom distance metric if needed). Ensure your data is in a format compatible with your distance function and handle missing values appropriately before applying QT Clustering. Traditional numerical data scaling is generally not required for basic QT Clustering, especially when using non-Euclidean distances for categorical data.

5. Implementation Example: QT Clustering with Dummy Data

Let’s implement Quality Threshold (QT) Clustering in Python from scratch using NumPy and Pandas, as a direct library implementation is not as readily available. We’ll use Euclidean distance for simplicity and demonstrate clustering on dummy 2D numerical data.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

def euclidean_distance(point1, point2):
    """Calculates Euclidean distance between two numpy arrays."""
    return np.linalg.norm(point1 - point2)

def quality_threshold_clustering(data, threshold_radius):
    """Performs Quality Threshold Clustering."""
    clusters = [] # List to hold clusters (each cluster is a list of data point indices)
    clustered_indices = set() # Set to keep track of indices already clustered

    for i in range(len(data)): # Iterate through data points
        if i in clustered_indices: # Skip if already clustered
            continue

        new_cluster = [i] # Start a new cluster with current point
        clustered_indices.add(i)
        cluster_centroid = data.iloc[i].values # Use the first point as initial centroid (simple approach)

        # Find points within threshold radius and add to cluster
        for j in range(i + 1, len(data)): # Iterate through remaining points
            if j not in clustered_indices: # Consider only unclustered points
                distance_to_centroid = euclidean_distance(data.iloc[j].values, cluster_centroid)
                if distance_to_centroid <= threshold_radius:
                    is_diameter_within_threshold = True # Assume within threshold initially
                    # Check if adding point j increases cluster diameter beyond threshold
                    for point_index_in_cluster in new_cluster:
                        diameter_check_distance = euclidean_distance(data.iloc[j].values, data.iloc[point_index_in_cluster].values)
                        if diameter_check_distance > threshold_radius:
                            is_diameter_within_threshold = False
                            break # Diameter exceeds threshold, don't add point j
                    if is_diameter_within_threshold:
                        new_cluster.append(j)
                        clustered_indices.add(j)

        clusters.append(new_cluster) # Add the formed cluster to the list of clusters

    return clusters

# 1. Dummy 2D Numerical Data
np.random.seed(42)
data = pd.DataFrame(np.random.randn(50, 2), columns=['X', 'Y']) # 50 points, 2 dimensions

# 2. Set Distance Threshold (Radius - hyperparameter)
threshold_radius = 1.5 # You'd tune this hyperparameter - experiment with different values

# 3. Perform Quality Threshold Clustering
qt_clusters = quality_threshold_clustering(data, threshold_radius)

# 4. Output Results
print("Quality Threshold Clustering Results:")
print("\nNumber of clusters found:", len(qt_clusters))
print("\nCluster assignments (indices of data points in each cluster):")
for i, cluster in enumerate(qt_clusters):
    print(f"  Cluster {i+1}: Points {cluster}")

# 5. Visualization (2D scatter plot of clusters)
plt.figure(figsize=(8, 6))
colors = plt.cm.viridis(np.linspace(0, 1, len(qt_clusters))) # Color map for clusters

for i, cluster_indices in enumerate(qt_clusters):
    cluster_data = data.iloc[cluster_indices]
    plt.scatter(cluster_data['X'], cluster_data['Y'], color=colors[i], label=f'Cluster {i+1}') # Scatter plot for each cluster

plt.title(f'Quality Threshold Clustering (Radius = {threshold_radius})')
plt.xlabel('X')
plt.ylabel('Y')
plt.legend()
plt.grid(True)
plt.show()

# 6. Saving and Loading Cluster Assignments (Example - just saving cluster lists to a file)
import joblib # or pickle

# Save cluster assignments (list of lists of indices)
joblib.dump(qt_clusters, 'qt_clusters_assignments.joblib')
print("\nQT Clustering assignments saved to qt_clusters_assignments.joblib")

# Load cluster assignments
loaded_qt_clusters = joblib.load('qt_clusters_assignments.joblib')
print("\nQT Clustering assignments loaded.")
print("\nLoaded Cluster Assignments (first 2 clusters):", loaded_qt_clusters[:2]) # Print first 2 loaded clusters

Explanation of the Code and Output:

  1. euclidean_distance(point1, point2) Function: Simple function to calculate Euclidean distance between two NumPy arrays (data points).
  2. quality_threshold_clustering(data, threshold_radius) Function: This function implements the QT Clustering algorithm.
    • clusters = [], clustered_indices = set(): Initializes lists to store clusters and track clustered data point indices.
    • Outer loop (for i in range(len(data))): Iterates through each data point.
    • Check if already clustered (if i in clustered_indices): Skips data points already assigned to a cluster.
    • Start New Cluster (new_cluster = [i], …): If a point is not yet clustered, it starts a new cluster with that point.
    • Inner loop (for j in range(i + 1, len(data))): Iterates through the remaining data points to see if they can be added to the current new_cluster.
    • Distance to Centroid Check (distance_to_centroid <= threshold_radius): Checks if a point is within the threshold_radius of the current cluster centroid (in this simple implementation, we use the first point added to the cluster as the centroid).
    • Diameter Check (is_diameter_within_threshold): Crucial QT condition. Before adding a point to a cluster, it checks if adding the point would cause the cluster’s diameter to exceed the threshold_radius. It calculates pairwise distances between the point to be added and all points already in the cluster. If any pairwise distance exceeds the threshold, the point is not added to the cluster (diameter constraint violated).
    • clusters.append(new_cluster): After processing all remaining points, the formed new_cluster (list of indices) is added to the clusters list.
    • Returns: The function returns the clusters list – a list of lists, where each inner list contains the indices of data points belonging to a cluster.

  3. Dummy 2D Numerical Data: We create dummy 2D numerical data using np.random.randn and put it into a Pandas DataFrame.

  4. Set Distance Threshold: We set threshold_radius = 1.5. You would tune this hyperparameter to get different clustering results.

  5. Perform QT Clustering: We call quality_threshold_clustering function to run QT Clustering.

  6. Output Results:
    • len(qt_clusters): Prints the number of clusters automatically found by QT Clustering.
    • qt_clusters: Prints the cluster assignments – lists of data point indices belonging to each cluster.

  7. Visualization: We use matplotlib.pyplot.scatter to create a 2D scatter plot. Each cluster is plotted with a different color, allowing you to visually inspect the clustering results.

  8. Saving and Loading Cluster Assignments:
    • We use joblib.dump to save the qt_clusters list to a file.
    • We use joblib.load to load the saved cluster assignments back from the file and print the first two clusters from the loaded assignments to verify saving and loading.

Interpreting the Output:

When you run the code, you will see output like this (cluster assignments might vary slightly due to point processing order and data randomness):

Quality Threshold Clustering Results:

Number of clusters found: 8

Cluster assignments (indices of data points in each cluster):
  Cluster 1: Points [0, 24, 39]
  Cluster 2: Points [1, 2, 3, 4, 13, 21, 23, 30, 31, 34, 36, 42]
  Cluster 3: Points [5, 6, 10, 17, 22, 40, 44, 46]
  Cluster 4: Points [7, 8, 11, 12, 18, 25, 33, 41, 48]
  Cluster 5: Points [9, 15, 20, 28, 45, 47]
  Cluster 6: Points [14, 16, 26, 37, 38, 43, 49]
  Cluster 7: Points [19, 27, 32, 35]
  Cluster 8: Points [29]

QT Clustering assignments saved to qt_clusters_assignments.joblib

QT Clustering assignments loaded.

Loaded Cluster Assignments (first 2 clusters): [[0, 24, 39], [1, 2, 3, 4, 13, 21, 23, 30, 31, 34, 36, 42]]

  • “Number of clusters found:” This shows the number of clusters automatically determined by QT Clustering for the given threshold_radius. In the example output, it’s 8 clusters. The number of clusters will vary depending on the threshold_radius setting – larger radius generally leads to fewer clusters, smaller radius to more clusters.

  • “Cluster assignments”: This output lists the data point indices that belong to each cluster. For example, Cluster 1 contains data points with indices 0, 24, and 39 (in 0-based indexing). Examine the data point indices in each cluster to see which data points are grouped together.

  • Scatter Plot Visualization: The scatter plot will show the 2D data points, with different colors representing different clusters assigned by QT Clustering. Visually inspect the plot. Do the clusters appear to be reasonably compact and well-separated? Does the clustering seem to make sense visually based on your data distribution and the chosen threshold_radius?

  • Saving and Loading: The output confirms that cluster assignments have been saved to and successfully loaded from the qt_clusters_assignments.joblib file.

No “r-value” or similar in QT Clustering output: QT Clustering is not a predictive model in the regression sense. There isn’t an “r-value” or accuracy score directly outputted in the algorithm itself. The primary output is the cluster assignments (cluster labels for each data point) and, implicitly, the number of clusters determined by the algorithm based on the threshold. Evaluation of QT Clustering is typically based on qualitative visual assessment of the clusters, and potentially quantitative clustering metrics like silhouette score or cluster validity indices (see section 8).

6. Post-Processing: Understanding and Validating QT Clusters

After running QT Clustering, post-processing is crucial to analyze the clusters, understand their characteristics, and validate the quality of the clustering.

Common Post-Processing Steps for QT Clusters:

  • Cluster Visualization (If low-dimensional data):

    • Scatter Plots (for 2D/3D Numerical Data): As in our implementation example, create scatter plots of the data points, color-coded by cluster assignments. Visually examine the clusters. Are they compact, well-separated, and meaningful in the data space? For numerical data in 2D or 3D, visualization is very helpful for assessing cluster quality.

  • Cluster Profiling (Describing Cluster Characteristics):

    • Descriptive Statistics (for Numerical Data): For each cluster, calculate descriptive statistics (mean, median, standard deviation, range, min, max) for each numerical feature within that cluster. Compare these statistics across different clusters. Do clusters show distinct profiles in terms of feature statistics?
    • Category Value Counts (for Categorical Data): For categorical data, calculate the frequency distribution of each category value for each categorical feature within each cluster (as shown in the K-Modes blog post-processing section). This helps you understand the “typical” categorical profile of each cluster.

  • Cluster Size Analysis:

    • Cluster Size Distribution: Examine the size (number of data points) of each cluster. Are the cluster sizes reasonably balanced, or are there very large clusters and very small, potentially outlier clusters? QT Clustering can sometimes produce clusters of very different sizes.
    • Very Small Clusters (Potential Outliers): Be cautious about very small clusters produced by QT Clustering, especially if you set a small threshold (T). Very small clusters might represent noise or outliers, or they could be genuinely very tight, isolated groups of data points. Investigate small clusters to determine if they are meaningful or artifacts of noise or parameter settings.

  • Cluster Diameter Analysis:

    • Check Cluster Diameters: For each cluster, calculate its diameter (maximum pairwise distance within the cluster). Verify if the diameters of all clusters are indeed below or equal to your chosen distance threshold (T), as expected from QT Clustering’s definition. Large diameters within some clusters (close to (T)) might suggest that those clusters are somewhat “stretched” and could potentially be further subdivided with a smaller threshold.

  • External Validation (If possible, using external labels or knowledge): (Same concept as discussed in K-Modes post-processing - compare clusters to external ground truth if available).

  • Qualitative Assessment and Domain Relevance:

    • Domain Expert Review: Involve domain experts to review the cluster profiles, visualizations, and cluster characteristics. Do the clusters make sense in the context of your domain knowledge? Are they meaningful and insightful for your application? Do they reveal new or expected patterns in the data? Qualitative validation and domain relevance are crucial for judging the real-world value of clustering results.

Post-Processing Considerations:

  • Iterative Refinement of Threshold (T): If the initial QT Clustering results are not satisfactory (e.g., too many small clusters, clusters too broad, or not meaningful), you might need to iterate and adjust the distance threshold (T).
    • Increase (T) (larger threshold): Increasing (T) will generally lead to fewer, larger, and looser clusters. Try increasing (T) if you are getting too many small clusters, or if you want to merge smaller clusters into larger, more general groups.
    • Decrease (T) (smaller threshold): Decreasing (T) will generally lead to more, smaller, and tighter clusters. Try decreasing (T) if you are getting clusters that are too broad, overlapping, or if you want to find more fine-grained cluster structure.
    • Experiment and Visualize: Experiment with different values of (T) and visualize the resulting clusters and cluster sizes to find a threshold that produces a clustering that is visually and conceptually meaningful for your data.
  • No Hypothesis Testing or AB Testing Directly on QT Clusters (like for model predictions): QT Clustering is an unsupervised algorithm. You don’t directly apply AB testing or hypothesis testing to the clusters themselves. However, you might use statistical tests or hypothesis testing in post-processing to:
    • Compare Cluster Characteristics Statistically: Test if the feature distributions or statistics (means, variances, category frequencies) are significantly different across different QT clusters. For numerical data, you could use ANOVA or t-tests to compare means. For categorical data, you could use chi-squared tests to compare category distributions.
    • Evaluate External Validation: If you have external labels or ground truth, you can use statistical measures (like adjusted Rand index, normalized mutual information) to quantify the agreement between QT clusters and external labels, and potentially test the statistical significance of this agreement.

In summary: Post-processing for QT Clustering is about analyzing and understanding the clusters found. Use visualizations, cluster profiling (descriptive statistics, category counts), cluster size analysis, and external validation (if possible) to assess the quality, interpretability, and meaningfulness of the QT Clustering results. Hyperparameter tuning (adjusting the distance threshold (T)) and qualitative domain expert review are essential parts of the iterative process of refining and validating QT Clusters.

7. Hyperparameter of QT Clustering: The Quality Threshold (Radius)

The single most important hyperparameter in Quality Threshold (QT) Clustering is the distance threshold (radius or diameter) (T). It directly controls the clustering process and the characteristics of the resulting clusters.

Key Hyperparameter: Distance Threshold (T) (Radius or Diameter)

  • Effect: The distance threshold (T) determines the maximum allowed diameter (or radius) for any cluster. It directly controls:
    • Number of Clusters:
      • Smaller (T): A smaller threshold (T) leads to more clusters. QT Clustering will create more, smaller, and tighter clusters because the diameter constraint is stricter. Points need to be very close to be grouped into the same cluster.
      • Larger (T): A larger threshold (T) leads to fewer clusters. QT Clustering will create fewer, larger, and looser clusters because the diameter constraint is more relaxed. Points can be farther apart within a cluster and still be grouped together.
    • Cluster Size:
      • Smaller (T): Generally leads to smaller clusters (fewer data points per cluster), as clusters need to be more compact to satisfy the tighter diameter constraint.
      • Larger (T): Generally leads to larger clusters (more data points per cluster), as clusters can be more spread out while still meeting the relaxed diameter constraint.
    • Cluster Density/Cohesion:
      • Smaller (T): Clusters are generally more dense and cohesive (points within clusters are very close to each other).
      • Larger (T): Clusters are generally less dense and less cohesive (points within clusters can be more spread out, although still within the diameter threshold).

  • Tuning (T) (Choosing the Right Threshold):

    • No Automated “Optimal” (T): Unlike some clustering algorithms where you might have objective functions to optimize for (e.g., Silhouette score maximization), choosing the “best” (T) in QT Clustering is often more driven by domain knowledge, experimentation, and visualization. There isn’t a single automatic method to determine the “correct” (T) value that works for all datasets and applications.

    • Domain Knowledge as Guide: The best starting point for choosing (T) is your domain knowledge. Think about the scale and units of your distance metric and the notion of “closeness” that is relevant for your problem. What is a “reasonable” maximum diameter (or radius) for a meaningful cluster in your application? Use domain expertise to set an initial range or starting point for (T).

    • Experimentation and Parameter Sweep: Systematically try different values of (T) over a range of values. For each value of (T):
      • Run QT Clustering with that (T).
      • Examine the resulting number of clusters, cluster sizes, cluster visualizations (if low-dimensional data), and cluster profiles (descriptive statistics, category distributions).
      • Calculate quantitative clustering metrics (e.g., Silhouette score, if you can adapt it for your distance).
    • Plotting Metrics vs. (T): Plot quantitative metrics (like silhouette score, average cluster diameter, number of clusters) against different values of (T). Look for trends and patterns in these plots.
      • Elbow Method (for Number of Clusters vs. (T)): Plot the number of clusters found by QT against different (T) values. You might see an “elbow” point in this plot, where increasing (T) beyond that point leads to a slower decrease in the number of clusters. The “elbow” might suggest a threshold value where the rate of change in the number of clusters diminishes.

      • Silhouette Score vs. (T): Plot silhouette score (or another clustering validity index) against (T). Look for a (T) value that maximizes the silhouette score or reaches a reasonably high score.

      • Code Example (Tuning (threshold_radius) and Plotting Number of Clusters - Conceptual):

        import matplotlib.pyplot as plt

threshold_radii_to_test = np.linspace(0.5, 3.0, 10) # Example range of radii to try
num_clusters_found = []

for radius in threshold_radii_to_test:
    qt_clusters_tuned = quality_threshold_clustering(data, radius) # Data from previous example
    num_clusters = len(qt_clusters_tuned)
    num_clusters_found.append(num_clusters)
    print(f"Radius: {radius:.2f}, Number of Clusters: {num_clusters}")

plt.figure(figsize=(8, 6))
plt.plot(threshold_radii_to_test, num_clusters_found, marker='o')
plt.xlabel('Distance Threshold (Radius)')
plt.ylabel('Number of Clusters Found')
plt.title('QT Clustering - Number of Clusters vs. Distance Threshold')
plt.grid(True)
plt.show()

# Examine the plot and choose a radius based on the desired number of clusters or the "elbow" point in the curve.
      • Visual Inspection of Clusters (for different (T) values): Visually examine the clusters (using scatter plots, cluster profiles) for different values of (T). For which (T) value do the clusters appear visually most meaningful, well-separated, and consistent with your data structure and domain understanding?
  • No Single “Optimal” (T): There is no single “best” or automatically determined “optimal” value for (T) in QT Clustering. The “optimal” (T) is often subjective and depends on what you consider to be “good” clusters for your specific data and application. It’s a matter of finding a threshold that balances cluster granularity, interpretability, and validity for your problem.

Hyperparameter Tuning Process Summary for QT Clustering:

  1. Start with Domain Knowledge to guide the range or initial guess for distance threshold (T).
  2. Experiment with a range of (T) values.
  3. For each (T) value, run QT Clustering and evaluate the results.
  4. Use quantitative metrics (like Silhouette score - if adapted for your data) and plot metrics like Number of Clusters and Silhouette Score against (T) to get quantitative guidelines.
  5. Crucially, perform qualitative assessment and visual inspection of the clusters for different (T) values. Choose the (T) value that produces clusters that are most meaningful, interpretable, and useful for your application based on both quantitative and qualitative criteria, and domain expertise.
  6. Iterate and Refine: Hyperparameter tuning for QT Clustering is often an iterative process of trying different thresholds, evaluating results, and adjusting (T) until you find a satisfactory clustering.

8. Accuracy Metrics: Evaluating QT Clustering Results

“Accuracy” in QT Clustering, as with other unsupervised clustering algorithms, is not measured in the same way as classification accuracy. Instead, we evaluate the quality, validity, and usefulness of the clusters found by QT Clustering.

Key Metrics and Approaches for Evaluating QT Clustering Quality:

  • Cluster Diameter (by definition, must be within threshold (T)):

    • Check Cluster Diameters: As QT Clustering explicitly controls cluster diameter to be less than or equal to the threshold (T), verify that the diameters of all resulting clusters indeed satisfy this constraint. You can calculate the maximum pairwise distance within each cluster to check its diameter. If cluster diameters are consistently within (T), it confirms that the algorithm is adhering to its definition.

  • Quantitative Clustering Validity Indices (Adapted for Distance Metric):

    • Silhouette Score (Adapted for Hamming Distance for categorical data, or Euclidean for numerical): (Explained in detail in section 8 of K-Modes blog post, and section 8 earlier in this QT blog post). Calculate silhouette score using the appropriate distance metric (Euclidean for numerical data in our QT example, Hamming distance for categorical data if using QT for categorical data). Higher silhouette score is generally better, indicating well-separated and cohesive clusters.
    • Calinski-Harabasz Index (Variance Ratio Criterion - adapted for distance if needed): (Explained in K-Modes blog post). Higher Calinski-Harabasz index is generally better, indicating a good ratio of between-cluster dispersion to within-cluster dispersion.
    • Davies-Bouldin Index (Lower is Better - adapted for distance if needed): (Explained in K-Modes blog post). Lower Davies-Bouldin index is better, indicating well-separated and compact clusters.

  • Cluster Size Distribution and Analysis:

    • Examine Cluster Sizes: Analyze the distribution of cluster sizes. Are the clusters reasonably sized? Are there any clusters that are excessively small or excessively large? In some applications, you might expect clusters to have roughly balanced sizes. In others, you might expect natural size variations. Investigate the characteristics of very small and very large clusters specifically.
    • Number of Clusters (Implied by (T)): The number of clusters automatically determined by QT Clustering is itself an output that you can evaluate. Is the number of clusters found by QT reasonable for your data and domain knowledge? Experiment with different thresholds (T) and observe how the number of clusters changes.

  • Qualitative Evaluation and Domain Relevance (Crucial - as always for clustering):

    • Visual Inspection of Clusters (if applicable): For low-dimensional data, visual inspection of cluster plots is essential. Do the clusters appear visually compact, well-separated, and consistent with the data distribution?
    • Cluster Profiling and Interpretability: Examine cluster profiles (descriptive statistics for numerical data, category value distributions for categorical data) for each QT cluster. Are the cluster profiles meaningful and interpretable in the context of your domain knowledge? Can you assign clear and descriptive labels to the clusters based on their characteristics? Qualitative assessment of cluster interpretability and domain relevance is paramount for judging the real-world value of QT Clustering.
    • Actionability and Usefulness: Assess the practical usefulness and actionability of the discovered QT clusters for your application. Do they provide insights that are valuable for decision-making, segmentation, or achieving your objectives? In business or research applications, the business or research value of the clusters is the ultimate measure of “accuracy” in a practical sense.

Choosing Evaluation Metrics:

  • For Quantitative Metrics: Use Silhouette score (adapted for your distance metric) as a good general-purpose quantitative metric. Consider Calinski-Harabasz and Davies-Bouldin indices as well. These metrics provide some numerical indication of cluster quality (cohesion and separation).
  • For Qualitative Evaluation (Crucial): Always combine quantitative metrics with visual inspection and qualitative domain expertise-based evaluation. Focus on the interpretability, meaningfulness, and actionability of the QT clusters in the context of your specific problem and domain. There is no single “accuracy score” for clustering; a holistic evaluation approach is essential.

9. Productionizing QT Clustering: Segmentation and Insights

“Productionizing” Quality Threshold (QT) Clustering is often about using it for offline data analysis, exploratory data analysis, and segmentation tasks, rather than real-time online prediction in the same way as supervised models. However, cluster assignments from a trained QT model can be used in production systems for various purposes.

Common Production Scenarios for QT Clustering:

  • Offline Data Segmentation and Reporting: Perform QT Clustering on large datasets offline (e.g., batch processing, scheduled jobs) to segment data into natural groups based on a defined quality threshold. Use the resulting cluster assignments and cluster profiles to generate reports, dashboards, and visualizations for business intelligence, data exploration, or analytical purposes. For example, segment customer data to understand natural customer segments, or segment genes based on expression profiles to identify co-regulated gene groups in biological research.

  • Preprocessing for Downstream Tasks (Feature Engineering): Use QT Clustering as a preprocessing step to create new categorical features (cluster assignments) from your original data. The cluster labels assigned by QT can be used as a new feature that can be input to other machine learning models (e.g., classification, regression, further clustering algorithms). This can be useful for adding cluster-based features to enhance model performance or for simplifying data representation.

  • Anomaly Detection (Identify Outlier Clusters): In some applications, you might use QT Clustering to identify potentially anomalous data points. Data points that end up in very small, isolated clusters, or those not assigned to any cluster (depending on implementation and threshold), could be flagged as potential outliers. This is a less common primary use case for QT Clustering compared to dedicated anomaly detection algorithms, but it can be a side benefit or secondary application in some scenarios.

Productionizing Steps:

  1. Offline Training and Cluster Assignment Saving:

    • Run QT Clustering: Run QT Clustering on your dataset with a chosen distance metric and an appropriate distance threshold (T). Determine the best (T) value using hyperparameter tuning, visualization, and evaluation metrics as discussed in section 7 and 8.
    • Save Cluster Assignments: Save the cluster assignments (cluster labels for each data point, typically as a list or array of cluster indices) to a file (e.g., CSV file, text file, or using joblib.dump in Python). You can also save the entire clustered dataset with the added cluster label column.
    • Save Model Parameters (Optional, if needed for re-clustering or prediction in some QT variations - for basic QT, not always explicitly a “model” to save like in supervised learning): In basic QT Clustering, there isn’t a separate “model” object with learned parameters in the same way as in supervised models like linear regression. However, you might need to save the chosen distance threshold (T) or other parameters you used, if you want to re-run QT Clustering with the same settings or for documentation purposes. If you implement a more complex QT variation that has learned cluster centroids or other parameters, you would save those model artifacts.

  2. Production Environment Setup: (Same as in previous blogs – cloud, on-premise, etc., set up software stack with numpy, pandas, your QT implementation code, and any visualization or reporting libraries).

  3. Data Ingestion and Preprocessing in Production (if using cluster assignments for new data):

    • Data Ingestion Pipeline: Set up your data ingestion pipeline to receive new data that you want to assign to existing QT clusters (if you are using QT for online segmentation). For offline reporting or batch analysis, you might be processing a batch of new data files.
    • Preprocessing (Consistent with Training): Apply any necessary preprocessing steps to the new data consistently, as you did for the data used to derive the QT clusters initially. This primarily involves ensuring data is in the correct format for distance calculations and handling missing values.

  4. Cluster Assignment for New Data (if applicable - for offline segmentation, often you are just analyzing existing clusters):

    • Nearest Cluster Assignment (based on Distance to Cluster Representatives): If you want to assign new data points to the existing clusters found by QT (this is less common in typical QT use cases compared to algorithms like K-Means or K-Modes), you would need to:
      • Represent each QT cluster by a “representative” point (e.g., the first point added to the cluster in our example, or you could calculate a “centroid” of the cluster if meaningful for your data and distance metric).
      • For each new data point, calculate its distance to the representative point of each existing QT cluster.
      • Assign the new data point to the cluster with the nearest representative point (minimum distance). Note that you would typically not check the diameter threshold again when assigning new points to existing QT clusters in production - you are just assigning to the closest cluster among those already formed offline.

  5. Integration into Reporting, Analysis, or Downstream Pipelines:

    • Reporting and Dashboards: Use the cluster assignments (and cluster profiles derived from post-processing) to create reports, dashboards, or visualizations that summarize data segments and provide insights into cluster characteristics, cluster distributions, or trends across segments.
    • Feature Engineering in Downstream ML Pipelines: Use the cluster labels as a new categorical feature in your downstream machine learning pipelines (e.g., add a “Cluster ID” column to your data table). This feature could be used as input to classification, regression, or other models.
    • Triggering Actions Based on Cluster Assignment (less common for QT directly, more for segmentation in general): In some applications, you might set up rules or triggers based on cluster assignments (e.g., trigger a specific marketing action for customers belonging to a certain QT cluster).

Deployment Environments:

  • Cloud Platforms (AWS, Google Cloud, Azure): Cloud services are suitable for handling large datasets and scalable batch processing of QT Clustering for reporting, data analysis, or feature engineering pipelines. Use cloud compute instances, data storage, and data processing services.
  • On-Premise Servers: Deploy on your organization’s servers if required.
  • Local Machines/Workstations: For smaller-scale offline analysis, reporting, or exploratory data analysis, you can run QT Clustering locally on desktop machines or workstations.

Key Production Considerations:

  • Preprocessing Consistency: Ensure consistency in data preprocessing between training (QT clustering) and production (when you might be assigning new data points or using cluster assignments in downstream tasks). Use the same preprocessing logic, distance metric, and handle missing values consistently.
  • Scalability (if needed for large datasets): For very large datasets, basic QT Clustering can be computationally intensive, especially diameter calculation. Consider optimized implementations or approximation techniques if scalability is a major concern. For offline batch processing, cloud compute resources can often handle reasonably large datasets with QT Clustering.
  • Model Versioning: If you are using QT Clustering results in production applications, manage and version control your cluster assignments, chosen distance threshold (T), and any code used for QT Clustering and cluster analysis to ensure reproducibility and track changes.

10. Conclusion: Quality Threshold Clustering – Data-Driven Cluster Discovery

Quality Threshold (QT) Clustering offers a unique approach to clustering, automatically determining the number of clusters based on a distance threshold. It’s particularly useful when you want clusters to have a limited “diameter” or spread, and when you want the data structure to guide the clustering process rather than pre-specifying the number of clusters.

Real-World Problem Solving with QT Clustering:

  • Biological Data Analysis: Discovering clusters of co-regulated genes, grouping proteins with similar functional properties, or identifying distinct cell types in single-cell data.
  • Document and Text Analysis: Automatically grouping documents by topic, identifying thematic clusters in text corpora, and organizing large document collections.
  • Image Segmentation and Object Recognition: Segmenting images into regions of similar color or texture, and potentially identifying objects or regions of interest in images.
  • Exploratory Data Analysis: As a tool for exploratory data analysis to discover natural groupings and structures in data, especially when you don’t have prior knowledge about the number of clusters to expect.

Where QT Clustering is Still Being Used:

QT Clustering, while perhaps less widely used than K-Means or hierarchical clustering in general-purpose machine learning libraries, can be a valuable technique in specific scenarios, especially when:

  • Number of Clusters is Unknown: When you don’t have prior knowledge or strong intuition about the number of clusters that should exist in your data, and you want the algorithm to automatically determine it based on a quality criterion (diameter threshold).
  • Diameter-Constrained Clusters: When it’s important for clusters to be “tight” or have a limited spread, and you want to enforce a maximum diameter constraint for each cluster.
  • Exploratory Analysis for Cluster Discovery: As an exploratory tool to discover natural groupings in data and get insights into the data structure without strong assumptions about the number of clusters.

Optimized and Newer Algorithms:

While QT Clustering provides a distinct approach, several related and alternative clustering algorithms exist, especially density-based clustering methods, which share some concepts with QT Clustering:

  • DBSCAN (Density-Based Spatial Clustering of Applications with Noise): DBSCAN is a widely used density-based clustering algorithm that also automatically determines the number of clusters and is robust to outliers. DBSCAN defines clusters as dense regions separated by sparser regions. It’s often more robust and versatile than basic QT Clustering in handling noise and clusters of varying densities and shapes. Libraries like scikit-learn provide efficient DBSCAN implementations.
  • HDBSCAN (Hierarchical DBSCAN): HDBSCAN is a hierarchical version of DBSCAN that can find clusters of varying densities and is often considered more robust and parameter-free than DBSCAN in many cases. HDBSCAN is also implemented in Python libraries.
  • OPTICS (Ordering Points To Identify the Clustering Structure): OPTICS is another density-based clustering algorithm that is related to DBSCAN but is less sensitive to parameter selection. It creates an ordering of data points that represents the density-based clustering structure, which can be used to extract clusters at different density levels.

Choosing Between QT Clustering and Alternatives:

  • For Automatic Number of Clusters (Diameter-Constrained Clusters): Quality Threshold (QT) Clustering is a direct approach when you want to enforce a maximum cluster diameter constraint and let the data determine the number of clusters based on this threshold.
  • For More Robust Density-Based Clustering and Noise Handling: DBSCAN and HDBSCAN are often preferred over basic QT Clustering in practice as they are generally more robust to noise, can find clusters of varying densities and shapes, and also automatically determine the number of clusters. DBSCAN and HDBSCAN are widely used and have efficient implementations available.
  • For Hierarchical Clustering Structure: Hierarchical clustering is suitable when you want a hierarchical representation of clusters (dendrogram) or need to explore clusters at different levels of granularity.

Final Thought: Quality Threshold Clustering offers a distinct way to approach clustering, driven by a quality threshold for cluster diameter and automatically determining the number of clusters. While less widely used than some other clustering algorithms in general-purpose libraries, it can be a valuable tool for exploratory data analysis, especially when you want to discover clusters that are constrained by a maximum diameter or radius, and when you prefer the data to guide the number of clusters rather than pre-specifying it. For many practical applications, especially when dealing with noise and clusters of varying densities, more robust density-based clustering algorithms like DBSCAN or HDBSCAN might be preferred over basic QT Clustering due to their flexibility and widespread availability in optimized libraries.

11. References and Resources

Here are some references to explore Quality Threshold (QT) Clustering and related techniques further:

  1. Original QT Clustering Paper:
    • Heyer, L. J., Kruglyak, S., & Yooseph, S. (1999). Exploring expression data: identification and analysis of coexpressed genes. Genome research, 9(11), 1106-1115. (Genome Research Link - often accessible via institutional access or search for paper title online) - This is the original research paper that introduced Quality Threshold Clustering, primarily in the context of gene expression data analysis. It provides details of the algorithm, its motivation, and biological applications.

  2. “Data Clustering: Algorithms and Applications” by Charu C. Aggarwal and Chandan K. Reddy (Editors): (Book Link - Search Online) - A comprehensive textbook on data clustering, including chapters discussing various clustering algorithms, including density-based and hierarchical methods, and concepts related to cluster validity and evaluation.

  3. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) Paper:
    • Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd (Vol. 96, No. 34, pp. 226-231). (AAAI Link - often freely available PDF online, or search for paper title) - The original paper that introduced the DBSCAN algorithm, a widely used density-based clustering method that is a strong alternative to QT Clustering and addresses some of its limitations.
  4. HDBSCAN (Hierarchical DBSCAN) Documentation and Website:
    • HDBSCAN Documentation - Documentation for the HDBSCAN Python library, which is a powerful and robust density-based clustering algorithm.
    • HDBSCAN Website - Website explaining how HDBSCAN works in detail.
  5. Online Tutorials and Blog Posts on Density-Based Clustering (DBSCAN, HDBSCAN): Search online for tutorials and blog posts on “DBSCAN clustering Python”, “HDBSCAN tutorial”, “density-based clustering algorithms”. Websites like Towards Data Science, Machine Learning Mastery, and scikit-learn documentation provide excellent resources for learning about DBSCAN, HDBSCAN, and other density-based clustering techniques as alternatives and enhancements to QT Clustering.

These references should provide a solid foundation for understanding Quality Threshold Clustering, its characteristics, applications, and its relation to other density-based clustering methods. Experiment with QT Clustering and compare it to other algorithms like DBSCAN or HDBSCAN to explore different clustering approaches and find the best method for your data and clustering goals!