Anja Plakalovic

In the previous blog, we first defined the problem of customer support ticket classification that Atlantbh had the opportunity to solve. After presenting the business goal, we briefly described the proposed approach and obtained results. This blog post serves as a follow-up. We aim to delve into individual steps of the proposed approach, highlighting the best practices and providing insights gained from our experience.  Note that although we will remain in the context of customer support ticket classification, most of the steps described below apply to almost any text classification task, regardless of the specific problem domain. Figure 4. in the previous blog post shows the overview of text classification flow using the ML approach. This figure outlines six steps, from problem definition and business goal to classifier deployment. On the other hand, the figure below shows a more granular flow of text classification by splitting feature engineering and model construction phases into multiple individual steps. Figure 1. Text Classification Flow (Anja Plakalovic) Exploratory Data Analysis Exploratory Data Analysis (EDA) holds significant practical value for any ML task, providing insight into underlying structure and data characteristics. EDA enables the identification of the class distribution and detection of a potentially imbalanced dataset. However, an imbalanced dataset does not necessarily mean a “red flag”. In practice, imbalanced datasets are quite common. This is also the case with our dataset. For example, customers are more likely to report shipping issues than their account settings issues. There are many different ways to “combat” an imbalanced dataset, such as oversampling or undersampling, and many others, but we will not explain each of these techniques in detail here. Nevertheless, it is important to point out that in the case of an imbalanced dataset, selecting the appropriate metrics for model performance evaluation is of great importance. This will be discussed further as we go through the model construction process. EDA can also provide valuable information and basic statistics of text corpus (i.e., unstructured text dataset), such as discovering the various data structures within a dataset. It is important to note that EDA is not a one-time process performed during the project's initial phase, as some may assume by looking at the simplified version of the text classification flowchart. (Figure 1.) On the contrary, there is a feedback loop between EDA and feature engineering steps. (Figure 2.) Figure 2. Feedback Loop Between EDA and Feature Engineering Steps (Anja Plakalovic) Insights gained from the initial EDA directly influence the selection of steps we will perform in the feature engineering phase. Let’s say that we discover through EDA that there are some irrelevant records - it is necessary to remove these records from the dataset in the data cleaning phase. Conversely, the feature engineering steps also affect EDA. As the data goes through various changes in the feature engineering phase, it prompts a re-examination of the EDA to assess the impact of the feature engineering on the dataset and yield new insights. For example, stop word removal or lemmatization changes the previously established characteristics of the text corpus, and it is necessary to re-establish them. This feedback loop between EDA and feature engineering allows the development of a robust text classification model that increases the effectiveness of capturing underlying patterns in text data. Feature Engineering Phase Several fundamental steps are often performed during the feature engineering phase of a text classification task to ensure the quality and relevance of features extracted from raw text data. However, steps such as language translation or certain data cleaning and text preprocessing techniques may vary depending on the dataset characteristics and task-specific requirements. For example, language translation is crucial when dealing with multilingual datasets but is irrelevant for monolingual ones. Similarly, if a dataset contains different data formats, additional steps of data cleaning and text preprocessing may be required to resolve this variability. By recognizing a balance between commonly applicable procedures and task-specific requirements, we can tailor our feature engineering strategies to effectively address the unique challenges given by each NLP task and dataset. Data Cleaning After performing EDA on the initially obtained data, we quickly realized that our dataset contains records in various formats. In addition to plain text, which accounts for most of the dataset, we concluded that around 10% of records represent inquiries in HTML format. In many real-world situations, this often happens. For example, when collecting data from websites or emails, text usually contains HTML tags, which are irrelevant for analysis and may even interfere with further preprocessing steps. Removing these HTML tags and converting such text into plain, readable format was one of the first steps in data cleaning. Beautiful Soup Python library has proven to be a powerful tool to efficiently identify HTML-like messages, while the html2text library demonstrated its effectiveness in converting these messages to plain text. The second part of data cleaning involved identifying and removing duplicates and irrelevant or noisy records from the dataset to ensure the data quality. In our scenario, the dataset included different types of non-standard records, such as test messages or other forms of inquiries that do not contribute to the classification objective, so it was necessary to develop specific conditions for filtering such records. Manual inspection also enabled us to verify and flag potentially irrelevant records. Once identified, such records were excluded from further analysis during the data cleaning process to prevent them from influencing the model training process and compromising classification performance.  Data cleaning usually reduces the dimensionality of the initial dataset by removing irrelevant features and records. In general, by filtering unnecessary columns (i.e., features) and discarding rows (i.e., records), the dataset becomes more streamlined. However, one should be very careful not to overdo the cleaning process, as excessive data removal can result in the loss of potentially valuable information, which can also negatively affect the performance of the classification model. Therefore, finding the right balance between the need for data cleaning and the preservation of relevant data is essential. Language Detection & Translation In the customer support domain, where inquiries may be in different languages, translation is necessary when creating a classification model. Instead of creating different models for each language, using language detection and translation tools is a more cost-effective and pragmatic approach. This strategy consolidates inquiries in multiple languages into a single dataset, facilitating comprehensive analysis. Since we worked with the data of an international company, it is not surprising that our dataset is multilingual. More precisely, our dataset contains customer inquiries in over 20 languages, where about 13% of records are in a language other than English.  When using APIs for language detection and translation, it is critical to consider data confidentiality and security. Ensuring that sensitive information remains protected during the translation is paramount and requires a careful selection of APIs and robust security protocols to protect data integrity and privacy. Text Preprocessing As already mentioned, text preprocessing steps are highly dependent on the specifics of the task and the dataset we are working with. In-depth EDA typically yields an intuitive determination of the necessary text preprocessing steps. We used the power of the Natural Language Toolkit (NLTK) Python library to perform around 15 individual steps as part of the text preprocessing phase. This library is popular and widely used for various NLP tasks. Performed steps range from converting all text to lowercase to removing emojis, URLs, special characters, irrelevant phrases, stop words, and many more. (Figure 3.) Figure 3. Some of the Basic Text Preprocessing Steps (Anja Plakalovic) Here, we will focus on two crucial steps in almost every text classification task: lemmatization and tokenization. Lemmatization Lemmatization is a text preprocessing technique that reduces words to their base or root forms (i.e., lemmas). Applying this preprocessing step leads to text normalization and vocabulary dimensionality reduction. There is another similar text preprocessing technique called stemming. Stemming removes suffixes to find the word root form, which does not necessarily result in valid words. On the other hand, lemmatization considers word context and part of speech, resulting in more precise transformations that represent valid words. (Figure 4.) However, although lemmatization is a more sophisticated approach than stemming, the downside is that it is more computationally intensive and much slower than stemming, which should be kept in mind when working with high-dimensional text datasets. Figure 4. Lemmatization vs. Stemming (Anja Plakalovic) Tokenization The term “tokenization” without specifying any additional context refers to the word tokenization. It is the most commonly used form of tokenization and involves splitting a text into individual words or tokens. However, we should note that there are also other types of tokenization. For example, NLTK also implements the sentence tokenization method. By breaking down text into smaller chunks, tokenization enables more granular analysis and further text data processing. Tokenization is a fundamental technique in every text classification task, as it serves as the preliminary step in converting raw text data into a format suitable for analysis by ML algorithm. Train-Test Split After tokenization, it is time to split the dataset into training and test subsets. This step is always better to perform before vectorization, especially when training our vectorization model rather than using a pre-trained one. We leave the test dataset aside and use it only at the very end to evaluate the performance of the classification model. This way, we ensure that the training and test datasets remain independent, thus preventing any information leakage from the test to the training dataset. In general, the train-test split ratio always hovers around 80/20. This ratio has its roots in the well-known Pareto principle (also known as the 80/20 rule), which states that approximately 80% of consequences come from 20% of causes (the “vital few”). We decided to split our dataset using a 75/25 ratio. In the case of an imbalanced dataset like ours, it is necessary to provide an equal distribution of classes in the training and test datasets. This way, we ensure that the minority class is not included exclusively in the training or test dataset. Fortunately, this can be easily achieved using the “shuffle” and “stratify” arguments of sklearn’s train_test_split method. Vectorization Since ML algorithms cannot directly process text, conversion of text to numerical representation is an essential part of every text classification task. This process is called vectorization and is the final step in the feature engineering phase. We decided to use Word2Vec and train it on our data instead of directly using a pre-trained model. For training the Word2Vec model, we used the power of the Gensim library. This Python library has a module that efficiently implements the Word2Vec family of algorithms. Once trained, Word2Vec is used on both training and test datasets to generate word embeddings for each word in the dataset vocabulary. This way, words are represented as high-dimensional vectors of numbers optimized for our domain-specific semantics. At the same time, Word2Vec ensures that relationships between words are captured so that similar meanings or contexts have similar vector representations. Given that the previously tokenized dataset contains customer inquiries of variable length, word embeddings are first generated for each word and then aggregated to obtain a single vector representation for the entire record. This aggregation combines the information from all words in the record into a fixed-length vector determined by the dimensionality specified during the training of Word2Vec model. One of the most frequently used methods of aggregating is averaging word embeddings. (Figure 5.) This fixed-size vector of numbers captures the semantic information within the record and represents a suitable input to ML models. Figure 5. Text Vectorization (Anja Plakalovic) Model Construction Phase The model construction phase, which follows feature engineering, consists of six steps (Figure 1.). Although these steps are closely related, they are presented separately on the flowchart to underline their importance. In the following sections, we will clarify these steps by emphasizing two decisions: classification algorithm selection and evaluation metrics. Classification Algorithm Selection Choosing the appropriate classification algorithm is a vital decision that is heavily influenced by the data scientist’s experience and domain knowledge. Experienced data scientists use their understanding of the dataset characteristics, the nature of the problem, and the known strengths and limitations of various algorithms to decide which algorithm to use. However, experimenting with different classification algorithms is often convenient as it provides valuable insights into which algorithms work best for a given task. After evaluating the strengths and weaknesses of various algorithms, we chose Support Vector Machine (SVM) as the classification algorithm for its proven effectiveness in different NLP tasks. SVM’s several advantages make it a compelling choice for text classification tasks. Firstly, SVM is well-known for its versatility and robustness. It can handle high-dimensional data and capture complex relationships. SVM has the ability to find the optimal hyperplane for separating classes in a feature space, even in cases where the data is not linearly separable. It achieves this by using different kernel functions (e.g., linear, polynomial, radial basis functions). Moreover, SVM’s regularization parameter allows for fine-tuning the trade-off between model complexity and generalization. This flexibility ensures avoiding overfitting while maintaining good performance on unseen data. Firstly, the baseline SVM model is trained and evaluated to establish a performance benchmark. The performance of this baseline model is then used to estimate the level of improvement in subsequent iterations. Hyperparameter tuning enabled us to determine the optimal SVM model parameters (e.g., kernel type, regularization parameter, and gamma value). More precisely, hyperparameter tuning entails multiple iterations of model training and evaluation using different combinations of hyperparameters. Once the model iterations are complete, the best-performing SVM model is selected. In the case of experimenting with several classification algorithms, the previously described steps are performed for each selected algorithm. Finally, by comparing each of them, the final model is chosen.  It is important to note that if we are not satisfied with the obtained results, we should consider going back to EDA, reviewing the steps performed in the feature engineering phase, modifying some of the preprocessing steps, or perhaps considering using a different algorithm to generate word embeddings. Evaluation Metrics For assessing the performance of a classifier, choosing the right evaluation metrics, especially in the context of imbalanced datasets, is vital. Stakeholder input becomes crucial as their priorities and goals often determine evaluation metrics. In our scenario, the stakeholders’ input primarily focused on accuracy as the key metric. However, we also relied on class-wise metrics such as precision, recall, and F1-score to ensure a comprehensive assessment. In addition, by using micro, macro, and weighted averages, we gained overall insights into model effectiveness. Classifier Deployment After the final model selection, the classifier is deployed in the production environment. Applying the created classifier in production on new customer support tickets (i.e., unseen text) consists of several steps. Firstly, it is necessary to detect the language of the new text and translate it if it is not in English. After that, the exact text preprocessing steps included in the process of classifier construction follow. Finally comes vectorization, which converts the text into a form suitable as input to the created classifier. By applying the classifier, the output is the category of a customer support ticket. Figure 6. Using Text Classifier in a Production In the classifier deployment phase, cooperation between different teams is crucial. Software engineers developing the system are responsible for the seamless classifier integration, while DevOps engineers manage the deployment pipeline and infrastructure. Data scientists who build the model work alongside them to ensure a smooth transition and continuous monitoring of the deployed classifier. Proper implementation of MLOps practices ensures continuous integration, deployment, and monitoring of classifier performance. In addition, client expectations regarding the frequency of retraining should be clearly defined and agreed upon to maintain the model's accuracy and relevance over time. This collaborative effort and adherence to best practices in implementation are essential to achieving sustainable and efficient ML-based solutions in real-world applications.

As businesses strive to stay ahead in today’s dynamic market, harnessing the potential of Artificial Intelligence (AI) has become a strategic imperative rather than a choice.  Natural Language Processing (NLP), one of the branches of AI, encompasses a powerful set of techniques with a wide range of applications, especially in the field of customer support. By enabling machines to understand, interpret, and generate human language, NLP breaks down the barriers between technology and human interaction, paving the way for a more intuitive user experience and personalized customer service. Whether you are an experienced organization or a budding entrepreneur, it is important that you understand how NLP can be used to improve your business. Join us as we explore NLP by practically applying it to one common task. In addition, discover the success story of the collaboration of two Atlantbh teams, the development team and a small group of people from the data team, which led to the construction of a customized text classification model and its smooth deployment in production. Using NLP in Customer Service NLP tasks play an important role in automating and optimizing various aspects of customer service, improving the overall user experience and operational efficiency. More and more businesses are developing conversational agents (chatbots) that can interact with customers in natural language, respond to frequently asked questions, or solve basic inquiries. Text summarization techniques can be applied to automatically generate concise summaries in cases of rather long customer inquiries. Speech recognition techniques enable transcribing phone calls or voicemails into text. Real-time translation services provide multilingual customer support and enable smooth communication with customers who speak different languages. There are numerous examples of using different NLP tasks in customer support, but text classification is certainly one of the most common. Problems such as spam filtering, sentiment analysis, ticket triaging, or ticket classification can be considered as variations of the same task: text classification. Figure 1. Examples of Text Classification in Customer Service (Anja Plakalovic) Problem Definition: Customer Support Ticket Classification For any business, customer complaints are important, as they can often indicate shortcomings in their products or services. If these complaints are not resolved quickly, it can lead to customer dissatisfaction, while a recurring trend of dissatisfaction can lead to reduced revenue.  Therefore, solving the problem of automatic classification of customer support tickets has a significant value, both for businesses and for customers. From a business perspective, it leads to a streamlined customer support workflow and improved operational efficiency. On the other hand, from a customer perspective, it ensures that their inquiries are immediately routed to the appropriate team, resulting in faster responses and a smoother user experience. Atlantbh had the opportunity to work on solving the problem of classification of customer support tickets for an international company. We can formally define this problem as follows: Given a set of customer support tickets (i.e., formal records of customer inquiries, issues, or complaints) and a predefined set of categories (e.g., shipping issues, refund issues, account settings issues), the task is to construct a model that can accurately classify each ticket into the appropriate category, depending on the ticket content. Business Goal The existing process for handling customer support tickets relied entirely on manual categorization, where customers were tasked with selecting a specific category before submitting a problem. However, this approach has proven to be error-prone, with frequent occurrences of misclassification. Consequently, customer inquiries were often routed to the wrong support teams, leading to delays in resolution and customer frustration. In addition, support teams spent significant time recategorizing misclassified tickets and routing them to the appropriate teams. This manual reassignment process increased response times and resulted in redundant efforts and inefficiencies across various support teams. Figure 2. Customer Support Ticket Handling Process: Before vs. After (Anja Plakalovic) The proposed support ticket handling process intends to automate ticket categorization using a custom text classification model. This solution eliminates the need for customers to manually select ticket categories by using NLP and ML techniques to automatically classify tickets based on their content. This also simplifies the user interface for reporting problems, allowing users to report problems more quickly without having to decide which category the problem belongs to. (Figure 3.) By implementing this proposed approach, the goal is to achieve a considerable improvement in the accuracy and efficiency of support ticket classification, surpassing the estimated accuracy of the existing solution, which is approximately 80%. This way, we aim to reduce the time teams spend recategorizing misclassified tickets and improve overall customer satisfaction by providing faster solutions to their inquiries. Figure 3. Report a Problem Form: Before vs. After (Anja Plakalovic) Approach The client first approached the development team with a request to create a solution for automatically classifying support tickets. After defining the problem, the development team extracted data from the ticketing system. This way, a labeled dataset was collected, containing the text content of existing tickets (i.e., customer inquiries) and each ticket’s corresponding category or label. The development team tried to solve the problem by applying a rule-based approach. This method is often the initial and simplest strategy for solving text classification problems. A rule-based approach uses predefined rules to classify support tickets based on specific criteria or linguistic patterns. However, despite the team’s efforts, it quickly became apparent that the rule-based approach alone could not adequately address the complexity and variability of ticket content. As a result, the team recognized the need to explore more advanced methodologies, which led to collaboration with the data team and using ML approach to solve this problem. The figure below shows an overview of creating a text classifier using a supervised ML approach, delineating the teams involved and their respective responsibilities. Considering that we already clarified the first two steps, we will henceforth describe the remaining steps included in the used approach. Figure 4. Overview of Text Classification Flow Using ML Approach (Anja Plakalovic) The data team’s first step after being introduced to the problem by the development team was to familiarize themselves with the data and develop a sense of what could be derived from it. This step is formally called Exploratory Data Analysis (EDA). It enabled us to raise awareness of potential challenges and constraints early in the project lifecycle, guiding the appropriate further approaches and risk mitigation. In the context of our customer support ticket classification problem, EDA provided valuable insights regarding customer inquiries. These, among others, include the distribution of ticket categories, the frequency of specific keywords or phrases within each category, and the customer inquiry length distribution. A thorough EDA created a good foundation for defining steps in the feature engineering phase, which ensured converting the raw text data into a format suitable for the ML classification algorithm. Some of the performed feature engineering steps include data cleaning, standard text preprocessing techniques such as stop word removal, lemmatization or tokenization, and text vectorization at the end. Making the strategic decision to use Word2Vec as a text vectorization algorithm ensured we captured semantic relationships and context within the text. Rather than relying on pre-trained models, training Word2Vec on our dataset provided word embeddings tailored to our use case. Before performing text vectorization, we split the dataset into training and test datasets and trained Word2Vec only on training data. Afterward, we saved the trained Word2Vec model to preserve the learned word embeddings and use it to vectorize training and test data. Upon completing the transformation of our raw customer inquiries into a suitable format as input to the ML algorithm, the next step entailed selecting a suitable classification algorithm. Extensive research encompassing a spectrum of classification algorithms, complemented by our profound domain knowledge acquired through the EDA phase and an exhaustive feature engineering endeavor, played a crucial role in this decision-making process. The culmination of these efforts led us to discern the Support Vector Machine (SVM) as the optimal choice for our text classification task. This decision was reinforced by SVM's well-documented prowess in handling high-dimensional and sparse data since these characteristics are common in text classification tasks. Its ability to delineate complex decision boundaries, robustness in handling non-linear relationships, and good generalization performance further solidified its importance in our use case. By implementing hyperparameter tuning, we ensured using the optimal SVM parameters that improve classification performance. After training the model with these parameters on the training dataset, we saved the SVM model. Then, we used it on the test dataset to evaluate the performance of the created model. It is interesting to consider the distribution of time that the Atlantbh data team invested in implementing the previously mentioned phases. It is important to note that the following results represent rough estimates and depend significantly on the nature of the problem and the specific use case. In our scenario, we invested approximately 10% of the total time in EDA. This effort mainly included a thorough familiarization with the dataset at the beginning of the project. On the other hand, the feature engineering phase took the majority share with 60%, showing significant time investment in the data preprocessing before the model training. Model construction, which included ML models’ development and refinement, accounted for the remaining 30%. Figure 5. Time Allocation Overview: EDA, Feature Engineering, and Model Construction (Anja Plakalovic) Results By implementing the proposed approach, our primary goal was to significantly improve the accuracy and operational efficiency of the customer support ticket classification system. We exceeded the estimated accuracy of the existing solution, which was around 80%. More precisely, our approach resulted in an outstanding performance, achieving 93% accuracy when evaluated on the test dataset. After presenting the results to our clients, diligent work and seamless cooperation of different Atlantbh teams enabled the smooth deployment of the proposed model to production. A few months after the model deployment, we evaluated its accuracy in production. It turned out that in production, the proposed model for customer support ticket classification has an accuracy of an impressive 98%, which significantly exceeds even its initially estimated accuracy. This significant improvement not only confirms the effectiveness of our approach but also highlights the commitment and expertise of everyone involved in the process. By surpassing the previous performance, we effectively reduced the time spent recategorizing misclassified tickets, streamlined operational flows, and increased team productivity. Moreover, this improved accuracy further leads to faster and more accurate responses to customer inquiries, which increases customer satisfaction. This success underlines the significant benefits and improvements businesses can achieve using NLP and ML techniques, and Atlantbh's commitment to delivering exceptional results and creating tailored solutions. If you found this blog engaging, we encourage you to read part two: “Comprehensive Guide: Creating an ML-Based Text Classification Model”. As the name suggests, this blog provides an in-depth description of individual steps of the proposed approach.

Nowadays, we live in a world of data, which means we are constantly surrounded by enormous amounts of data. Data is generated by everything we do, both online and offline, from our internet activities and purchases to our physical motions and interactions. This data contains valuable insights and knowledge that can be used to enhance our lives.  It is safe to say that companies that can efficiently collect, analyze, and exploit data will be the most successful in the digital age. Data has become an immensely valuable resource, with governments, businesses, and individuals using it to make data-driven decisions that can be more accurate and reliable than ones based on intuition or assumptions.  Data analysis certainly plays an indispensable role in today’s data-driven world. It can be explained as the process of examining large datasets in order to discover patterns, correlations, and trends. One of the data analysis techniques that focuses on gaining valuable insights and finding patterns in data is clustering. In this Tech Bite, we will first define what clustering is and then explain two density-based clustering algorithms: DBSCAN and OPTICS. What is Clustering? Machine learning establishes a clear distinction between supervised (e.g., classification) and unsupervised (e.g., clustering) tasks. The main difference is that classification requires labeled data to predict the class of input, while clustering uses unlabelled data and groups similar inputs together based on their characteristics. Generally speaking, we can say that clustering is a more challenging problem than classification.  Clustering is commonly defined as the process of discovering structure in data by grouping related objects together, and the resulting groups are referred to as clusters. A cluster is a group of objects that are more similar to each other than to objects in other clusters. If we think of those objects as points in data space, we can represent their similarity using a certain distance measure. In this way, points closer to each other are more likely to be grouped in the same cluster, while points far apart are more likely to be assigned to different clusters. There are many different types of clustering algorithms, some of them are centroid-based clustering, hierarchical clustering, distribution-based clustering, and density-based clustering. Each type of clustering algorithm has its strengths and weaknesses and is suitable for different data types.  DBSCAN The term “density-based clustering” refers to a group of clustering algorithms that group data points based on their closeness to dense regions. In other words, the main concept behind these types of algorithms is pretty straightforward: given the input set of data points, group data in a way that accurately reflects the underlying data density. Some of the main strengths of these algorithms are their capability to find arbitrarily-shaped clusters, handling different amounts of noise, and not requiring any prior information about setting the number of clusters. One of the most used density-based clustering algorithms is certainly DBSCAN (‘Density-Based Spatial Clustering of Applications with Noise’). [1] Understanding DBSCAN DBSCAN requires two main hyperparameters, namely: Epsilon (ε) - the maximum distance between two points for one to be considered as in the neighborhood of the other. A distance can be defined as any type of distance function (e.g., Euclidean distance).  minPoints - the minimum number of points in a neighborhood for a point to be considered as a core point (this includes the point itself). Using these hyperparameters, DBSCAN classifies the dataset points into: Core points - a point p is called a core point if at least minPoints (including itself) are within distance ε of it. Directly reachable points - a point q is directly reachable from point p if point q is within distance ε from core point p. Reachable points - a point q is reachable from point p if there is a set of points that form a path from point p to point q and are directly reachable from point p. This means that all points that form a path, along with a point p, must be core points. Noise points (or outliers) - if a point is not reachable from any other point, it is considered to be an outlier or noise point. Figure 1. DBSCAN point classification (Anja Plakalovic) Abstract version of the DBSCAN algorithm The DBSCAN algorithm starts with a random point p and finds its ε-neighborhood. If p is a core point, then it is assigned to a new cluster that is expanded by assigning all its neighboring points to this cluster. If an additional core point is found in this cluster, then the neighborhood is also expanded to include all its neighboring points. The process is repeated until no more points can be assigned to the cluster, and then we can say that the cluster is complete. The remaining points are then processed, and if another core point can be found, then a new cluster is created, and the process repeats. The algorithm terminates once all points have been processed. Figure 2. Demo of DBSCAN algorithm (Anja Plakalovic) Introducing OPTICS: an Extension of DBSCAN The inability to detect clusters of varying density represents a significant limitation of DBSCAN. This disadvantage stems from the fact that DBSCAN uses one constant distance value (ε) together with one density threshold (minPoints) to determine whether a point is in a dense neighborhood. In this way, the DBSCAN algorithm actually assumes that the densities of different clusters are equal. However, many real-world datasets share the common property that their internal cluster structure cannot be characterized by global density parameters.  It did not take long for influential scientists to identify this deficiency and propose a suitable solution. In 1999, three years after the DBSCAN algorithm was published, some of its authors developed OPTICS as a particular form of DBSCAN extension. [2] The main difference between DBSCAN and OPTICS is that OPTICS generates a hierarchical clustering result for a variable neighborhood radius.  Understanding OPTICS OPTICS (‘Ordering Points To Identify Clustering Structure’) is an augmented ordering algorithm which means that instead of assigning cluster memberships, it stores the order in which the points are processed. OPTICS requires the same ε and minPoints hyperparameters as DBSCAN, but with one important difference - the ε parameter is theoretically unnecessary. Explicitly setting the value of this parameter is only used for the practical purpose of reducing the algorithm’s runtime complexity. In the following examples, we will assume that the epsilon parameter is set to a very large value (i.e. ), as this is the case in many implementations of the OPTICS algorithm. In addition to the concepts mentioned above of the DBSCAN algorithm, OPTICS introduces two more terms, namely: Core distance - the minimum distance required for a data point p to be considered as a core point. If the p is not a core point, then its core distance is undefined.  Reachability distance - the reachability distance of point q with respect to another point p is the smallest distance such that q is directly reachable from p if p is a core point. This distance cannot be smaller than the core distance of point p, since for smaller distances there are no points that are directly reachable from point p. If p is not a core point, then the reachability distance of point q with respect to point p is undefined.  Figure 3. OPTICS core and reachability distances (Anja Plakalovic) Reachability Plot OPTICS algorithm generates the reachability plot, which represents a sorted list of points based on their reachability distance. In order to build a reachability plot, OPTICS begins with an empty seed-list and picks a random point p, finds its ε-neighborhood, and determines its core distance. The reachability distance of this first point is set to undefined, and current point p is written to the output list. If point p is not a core point, then the algorithm simply picks another random point from the input dataset. If point p is a core point, then the reachability distance of each neighboring point q with respect to point p is calculated. All neighboring points are then inserted into the seed-list, and the list is sorted in ascending order by the reachability distance value.  In the next iteration, OPTICS takes the point that is at the top of the seed-list and, in case it is a core point, finds its ε-neighborhood, determines its core distance, and calculates the reachability distance for each of its neighboring points. If the newly calculated reachability distance of some unprocessed point is smaller than the one present in the seed-list, the value is updated to a smaller value, and the seed-list is sorted. If the current point is not a core point, then OPTICS moves to the next point from the seed-list. The process continues until each point is processed and the seed-list is empty. Figure 4. Demo of OPTICS algorithm (Anja Plakalovic) The ordering output from the OPTICS algorithm can be visualized using a reachability plot which is a special form of a dendrogram. It is a 2-D plot with points in the ordering returned by the OPTICS algorithm on the x-axis and their reachability distances on the y-axis. Figure 5. Reachability plot (Anja Plakalovic) Extracting Clusters from the Reachability Plot There are two basic ways to extract clusters from the reachability plot - manual and automatic using different algorithms. The manual way refers to either setting the range on the x-axis or using the threshold on the y-axis after performing the visual inspection of the reachability plot. Generally, clusters appear as valleys on the reachability plot so that deeper valleys represent dense clusters, while shallow valleys represent sparse clusters.  On the other hand, various algorithms attempt to extract clusters by detecting valleys by steepness, knee detection, or local maxima. For example, in Python and R, two algorithms can be used to extract clusters automatically:  DBSCAN - performs ‘cutting’ the reachability plot using the specified eps_cl threshold. Xi - extracts clusters by detecting valleys by steepness using the specified xi threshold. In the above examples of the DBSCAN algorithm, we used =0.5. Using the same value for the eps_cl threshold when extracting clusters from the reachability plot generated by the OPTICS algorithm, we get the same result as when using the DBSCAN algorithm. On the other hand, when using, say, the Xi method with a threshold of 0.1, we get a different result - all points belong to the same cluster, and there are no outliers. Figure 6. Extracting clusters using different methods (Anja Plakalovic) DBSCAN vs. OPTICS: Practical Example in Python After we have explained how DBSCAN and OPTICS algorithms work, we can move on to a practical example in Python. In the code below, we first generate synthetic two-dimensional data using the make_blobs function from Python's scikit-learn library. In this way, three clusters with different densities are created. Further, we define the necessary parameters: eps (ε), min_samples (minPoints), and distance metric. We then perform DBSCAN and OPTICS clustering using the appropriate methods from the scikit-learn Python library and visualize the results using the user-defined plot_clusters function. This function allows us to create customized clustering plots. In the end, we generate the reachability plot using the created reachability_plot function. from sklearn.datasets import make_blobs from sklearn.preprocessing import StandardScaler import matplotlib.pyplot as plt import pandas as pd import numpy as np from sklearn.cluster import DBSCAN, OPTICS plt.style.use("ggplot") colors = ["#00ADB5", "#FF5376", "#724BE5", "#FDB62F"] plt.rcParams.update({"font.size": 15}) def plot_clusters(algorithm, _df, _min_samples, _eps=""): unique_labels = set(_df.labels) for k, col in zip(unique_labels, colors[0:len(unique_labels)]): # Use black color for noise if k == -1: col = "k" # Use different color per cluster and add labels plt.plot( _df.loc[_df.labels == k].x, _df.loc[_df.labels == k].y, "o", color=col, markeredgecolor="k", markersize=15, label=(f"Cluster {k+1}" if k != -1 else "Noise") + f" ({_df.loc[_df.labels == k].shape[0]})", ) # Add legend and title plt.legend(loc="upper right") plt.title( f"{algorithm}: " + (f"eps={_eps}, " if _eps != "" else _eps) + f"min_samples={_min_samples}" ) plt.show() def reachability_plot(_df, model): # Get reachability distances and cluster labels reachability = model.reachability_[model.ordering_] labels = model.labels_[model.ordering_] unique_labels = set(labels) space = np.arange(len(_df)) # Generate reachability plot using different color per cluster for k, col in zip(unique_labels, colors): xk = space[labels == k] rk = reachability[labels == k] plt.plot(xk, rk, col) plt.fill_between(xk, rk, color=col, alpha=0.5) # Ordering in x-axis plt.xticks(space, _df.index[model.ordering_], fontsize=10) # Plot outliers plt.plot(space[labels == -1], reachability[labels == -1], "k.", alpha=0.3) # Add y-label and title plt.ylabel("Reachability Distance") plt.title("Reachability Plot") plt.show() if __name__ == "__main__": # Generate data centers = [[1, 1], [-2, -4], [5, -7]] data = make_blobs( n_samples=[30, 20, 10], centers=centers, cluster_std=[0.8, 1, 1.5], random_state=0, )[0] data = StandardScaler().fit_transform(data) df = pd.DataFrame(dict(x=data[:, 0], y=data[:, 1])) # Define parameters eps = 0.5 min_samples = 5 metric = "euclidean" # Perform DBSCAN clustering and visualize results dbscan = DBSCAN(eps=eps, min_samples=min_samples, metric=metric).fit(df) df["labels"] = dbscan.labels_ plot_clusters("DBSCAN", df, str(min_samples), str(eps)) # Perform OPTICS clustering and visualize results optics = OPTICS(min_samples=min_samples, metric=metric).fit(df) df["labels"] = optics.labels_ plot_clusters("OPTICS", df, str(min_samples)) reachability_plot(df, optics) It is interesting to mention that in this particular case, even if we had not specified a single parameter of the DBSCAN method, we would have obtained the same results because the default values are the same as the ones we used in our example: eps=0.5, min_samples=5 and metric=‘euclidean’. In the figure below, we can see that DBSCAN managed to identify two clusters with a higher density and only marked one point of the first cluster as noise. On the other hand, it failed to find the third sparse cluster. This is an example that illustrates the essential drawback of the DBSCAN algorithm that we have already mentioned, which is that it does not give good results in the case of clusters with varying densities. A simple solution could be to increase the value of the eps parameter in order to identify the third cluster correctly. However, this is a very naive approach because it can very likely lead to the incorrect merging of the first two clusters into one. Figure 7. DBSCAN clustering result (Anja Plakalovic) When using the OPTICS algorithm, it is sufficient to specify only the min_samples parameter. In order to ensure that the same metric is used in both DBSCAN and the OPTICS algorithm, it is necessary to explicitly specify the Euclidean distance as a metric for the OPTICS algorithm because the default metric is the Minkowski distance. From the figure below, we can see that in this particular example, the OPTICS algorithm gives a convincingly better result than the DBSCAN algorithm and correctly identifies all three clusters.  Figure 8. OPTICS clustering result (Anja Plakalovic) Since no cluster method was explicitly specified, the default Xi extraction method with a parameter xi=0.05 was used to extract clusters using the calculated reachability and ordering. The reachability plot showing the ordering returned by the OPTICS algorithm visibly has 3 valleys corresponding to the three identified clusters. We can see that the densest cluster 2 has the deepest valley, while the sparsest cluster 3 has the shallowest valley. Figure 9. OPTICS: Reachability plot (Anja Plakalovic) Conclusion Clustering is the process of grouping related objects together based on their common characteristics. Although we may initially think that this is a simple task, that is not the case. Clustering indeed is one of the processes in which humans outperform deterministic approaches or computers. Humans, in fact, can visually cluster data remarkably well without any prior training. Clustering, although being pretty effortless and fast for humans, represents a challenging task for computers. Over the years, different clustering approaches have been developed with varying performance levels. Among these approaches, density-based clustering algorithms stand out with their capability of finding clusters with various scales, shapes, and densities without requiring any prior information about setting the number of clusters. The two most frequently used density-based clustering algorithms are DBSCAN and OPTICS. The DBSCAN algorithm finds core points of high density and expands clusters from them. This algorithm performs well on data that contains clusters of similar density. Unlike DBSCAN, OPTICS generates a hierarchical clustering result for a variable neighborhood radius and is better suited for usage on large datasets containing clusters of varying density. However, it is important to note that OPTICS has certain disadvantages compared to the DBSCAN algorithm. The two most significant disadvantages are memory cost and runtime complexity. The real challenge of clustering lies in finding the appropriate algorithm and setting the optimal values of its parameters, especially in the case of high-dimensional data. In this blog, the simplest examples involving the use of two-dimensional data are used. In high-dimensional data, the distance between dataset points becomes less informative. This is often referred to as one of the "curses of dimensionality." In the real world, the generated data is usually high-dimensional, which further often requires a certain type of data preprocessing prior to using clustering algorithms. Some preprocessing techniques can be used are dimensionality reduction, feature selection, or feature extraction. Clustering can be used in a range of applications. For example, a hospital might utilize clustering to identify patient subgroups depending on their medical conditions. This can assist doctors to tailor treatments to the specific needs of each patient subgroup. Clustering can also be used in e-commerce to segment customers based on their buying behaviors. This can help the retailer to target specific customer groups with personalized marketing campaigns and promotions. References [1] M. Ester, H. P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise”, KDD, vol. 96, no. 34, pp. 226-231, 1996. [2] M. Ankerst, M. M. Breunig, H. P. Kriegel, and J. Sander, “OPTICS: ordering points to identify the clustering structure”, ACM Sigmod record 28, no. 2, pp. 49-60, 1999. "Clustering Algorithms: DBSCAN vs. OPTICS" Tech Bite was brought to you by Anja Plakalović, Junior Data Analyst at Atlantbh. (more…)