FANATIC : FA st N oise- A ware T op I c C lustering (2021)

Abstract: Extracting salient topics from a collection of documents can be a challenging task when a) the amount of data is large, b) the number of topics is not known a priori, and/or c) “topic noise” is present. We define “topic noise” as the collection of documents that are irrelevant to any coherent topic and should be filtered out. By design, most clustering algorithms (e.g. k-means, hierarchical clustering) assign all input documents to one of the available clusters, guaranteeing any topic noise to propagate into the result. To address these challenges, we present a novel algorithm, FANATIC, that efficiently distinguishes documents from genuine topics and those that are topic noise. We also introduce a new Reddit dataset to showcase FANATIC as it contains short, noisy data that is difficult to cluster using most clustering algorithms. We find that FANATIC clusters 500k Reddit titles (of which 20% are topic noise) in 2 minutes and achieves an AMI score of 0.59, in contrast with hdbscan (McInnes et al., 2017), a popular algorithm suited for this type of task, which requires over 7 hours and achieves an AMI of 0.03. Finally, we test FANATIC against a Twitter dataset and find again that it outperforms the other algorithms with an AMI score of 0.60. We make our code and data publicly available.

## introduction every minute, millions of social media data such as reddit comments, tweets, facebook comments, and other content are posted online @xcite . a cornucopia of value resides in this online information including product feedback, political beliefs, news, trending topics, and social interactions. however, these topics are generally needles in a haystack of topic noise and require suitable algorithms for extracting them. coherent topic subreddit: /r/hair how do i get this hairstyle? no better feeling than freshly bleached roots! some fun hair i did! (haircut is not my work) is this hair possible for me? topic noise subreddit: /r/thesimpsons the noble spirit embiggens the smallest man. surly says: don't get caught.. or else! guys, meet lisa and that's the end of that chapter the ability to group short-text documents into topics is an increasingly relevant problem, yet few algorithms are effective because: other clustering algorithms better suited to this task are gmeans @xcite and dpmeans @xcite ; instead of specifying the number of clusters one needs only to specify criteria for adding or splitting clusters. gmeans starts with a single cluster and keeps splitting until the child clusters are less gaussian than their parent. dpmeans specifies a distance length λ and creates new clusters when documents are greater than λ from any existing cluster (see algorithm 1 from @xcite . however, most clustering algorithms, including those mentioned above, struggle with topic noise since every input document must be assigned to a cluster. as an example, for the reddit 2 titles shown in one option for handling topic noise is to apply a pre-processing step to filter it out before clustering (e.g., @xcite , but without proper care one can accidentally remove informative "hard-toclassify" documents and/or fail to remove all of the topic noise @xcite . in addition, each dataset will have its own noise profile warranting a new, detailed analysis per dataset. some works (e.g., @xcite have restricted their analyses to clustering on tight coherent topics with zero topic noise; however, such studies are unlikely to generalize to datasets where topic noise is present. instead, a more desirable approach is to add filtering capabilities directly into the clustering algorithm so that clustering and topic noise filtering can be handled together. a key algorithm designed for this purpose is hdbscan @xcite , which we use as a benchmark for our new algorithm, fanatic, in section 5. a significant challenge in developing clustering algorithms for social media data is acquiring reliable ground truth labels. in particular, obtained labels must reliably distinguish documents from coherent topics and those that are topic noise. however, a common practice when using twitter data for example is to use the hashtag(s) as the ground truth label (e.g., @xcite @xcite . since many twitter hashtags are generic (e.g., #tuesdaythoughts), tweets containing such hashtags can have very little in common with one another @xcite . for the reddit do-2 https://www.reddit.com/ main, our contributions in this work are as follows: ## data we evaluate our algorithm's performance on the pushshift reddit dataset @xcite , as it is publicly available and suitable for clustering. specifically, the reddit platform is organized into categories, or subreddits, which generally focus on a single topic, have a title, and contain a large number of user posts. we use the titles of posts from selected subreddits as input documents for clustering, while the cluster labels are derived from the subreddit via an annotation task described below. ## conclusion in this paper we present the fanatic algorithm that is capable of robustly extracting coherent topics, even in the presence of topic noise. we first showed that ami scores for fanatic were consistently high across three experiments, indicating general ability to group similar documents together. second, we showed that pseudo-precision, p * , and pseudo-recall, r * , were consistently high, demonstrating its robustness to detect and filter topic noise. third, we demonstrated that fanatic's consistent performance as the noise fraction, f n , increased over the total number of documents displayed its robustness to different scenarios. as an added advantage, fanatic performed best with zero topic noise. finally, we found fanatic to be two orders of magnitude faster than hdbscan, demonstrating its scalability and efficiency in the nlp domain. we particularly recommend fanatic over other clustering algorithms if the number of documents is large and/or topic noise is present.