What approach other than Tf-Idf could I use for text-clustering using K-Means?

Question

I am working on a text-clustering problem. My goal is to create clusters with similar context, similar talk. I have around 40 million posts from social media. To start with I have written clustering using K-Means and Tf-Idf. The following code suggests what I am doing.

Here are main steps:

• Do some pre-processing
• Create tfidf_matrix while using tokenization and stemming
• Run K-Means on the tf-idf matrix

• Have the result

  csvRows = []
  nltk.download('stopwords')
  
  title = []
  synopses = []
  filename = "cc.csv"
  num_clusters = 20
  pkl_file = "doc_cluster.pkl"
  generate_pkl = False
  
  if len(sys.argv) == 1:
      print("Will use "+pkl_file + " to cluster")
  elif sys.argv[1] == '--generate-pkl':
      print("Will generate a new pkl file")
      generate_pkl = True
  
  
  # pre-process data
  with open(filename, 'r') as csvfile:
      # creating a csv reader object
      csvreader = csv.reader(csvfile)
  
      # extracting field names through first row
      fields = csvreader.next()
  
      # extracting each data row one by one
      duplicates = 0
      for row in csvreader:
      # removes the characters specified
      if line not in synopses:
          synopses.append(line)
          title.append(row[0])
      else:
          duplicates += 1
  
  
  
  stopwords = nltk.corpus.stopwords.words('english')
  stemmer = SnowballStemmer("english")
  
  
  def tokenize_and_stem(text):
      # first tokenize by sentence, then by word to ensure that punctuation is caught as it's own token
      tokens = [word for sent in nltk.sent_tokenize(
      text) for word in nltk.word_tokenize(sent)]
      filtered_tokens = []
      # filter out any tokens not containing letters (e.g., numeric tokens, raw punctuation)
      for token in tokens:
      if re.search('[a-zA-Z]', token):
          filtered_tokens.append(token)
      stems = [stemmer.stem(t) for t in filtered_tokens]
      return stems
  
  
  def tokenize_only(text):
      # first tokenize by sentence, then by word to ensure that punctuation is caught as it's own token
      tokens = [word.lower() for sent in nltk.sent_tokenize(text)
            for word in nltk.word_tokenize(sent)]
      filtered_tokens = []
      # filter out any tokens not containing letters (e.g., numeric tokens, raw punctuation)
      for token in tokens:
      if re.search('[a-zA-Z]', token):
          filtered_tokens.append(token)
      return filtered_tokens
  
  
  totalvocab_stemmed = []
  totalvocab_tokenized = []
  
  for i in synopses:
      # for each item in 'synopses', tokenize/stem
      allwords_stemmed = tokenize_and_stem(i)
      # extend the 'totalvocab_stemmed' list
      totalvocab_stemmed.extend(allwords_stemmed)
  
      allwords_tokenized = tokenize_only(i)
      totalvocab_tokenized.extend(allwords_tokenized)
  
  vocab_frame = pd.DataFrame(
      {'words': totalvocab_tokenized}, index=totalvocab_stemmed)
  
  print 'there are ' + str(vocab_frame.shape[0]) + ' items in vocab_frame'
  
  
  # define vectorizer parameters
  tfidf_vectorizer = TfidfVectorizer(max_df=0.8, max_features=200000,
                             min_df=0.0, stop_words='english',
                             use_idf=True, tokenizer=tokenize_and_stem, ngram_range=(1, 3))
  
  tfidf_matrix = tfidf_vectorizer.fit_transform(synopses)
  terms = tfidf_vectorizer.get_feature_names()
  # dist = 1 - cosine_similarity(tfidf_matrix)
  
  
  km = KMeans(n_clusters=10, max_iter=1000,
          verbose=1).fit(tfidf_matrix)
  
  
  clusters = km.labels_.tolist()
  
  # uncomment the below to save your model
  # since I've already run my model I am loading from the pickle
  
  if(generate_pkl):
      joblib.dump(km,  pkl_file)
      print("Generated pkl file " + pkl_file)
  
  km = joblib.load(pkl_file)
  
  clusters = km.labels_.tolist()
  
  
  films = {'title': title,  'synopsis': synopses, 'cluster': clusters, }
  
  total_count = len(films['synopsis'])
  
  csvRows = []
  
  for idx in range(total_count):
      csvRows.append({
      'title': films['title'][idx],
      'cluster': films['cluster'][idx]
      })
  
  print('Creating cluster.csv')
  
  with open('cluster.csv', 'w') as output:
      writer = csv.DictWriter(output, csvRows[0].keys())
      writer.writeheader()
      writer.writerows(csvRows)
      print("\ncreated cluster.csv")
  

The results are not very satisfactory. They are very average. What could be done to improve my clustering algorithm? I would still want to use K-Means but what another approach could be used in place of Tf-Idf?

Also, if you guys think that there is a better alternative to K-Means, please suggest and it even more helpful, if you could point me to sources/examples, where people have already done similar stuff.

I will always run the clustering on the volume close to 40 Million.

Answer 1

You will likely see an improvement by using an algorithm like GloVe in place of Tf-Idf. Like Tf-Idf, GloVe represents a group of words as a vector. Unlike Tf-Idf, which is a Bag-of-Words approach, GloVe and similar techniques preserve the order of words in a tweet. Knowing what word comes before or after a word of interest is valuable information for assigning meaning. This Article runs through different techniques and gives a good description of each one. Also, This Script on Kaggle shows how to use pretrained word vectors to represent tweets.

For your clustering, I recommend checking out Density-Based clustering. K-means is a decent all-purpose algorithm, but it's a partitional method and depends on assumptions that might not be true, such as clusters being roughly equal in size. This is almost certainly not the case. This Blog has a great discussion on clustering for text. If you go with Density-Based and you use Python, I highly recommend HDBSCAN by Leland McInnes.

Good luck!

Answer 2

You can try using n_grams.

n-grams

n-grams is a feature extraction technique for language based data. It segments the Strings such that roots of words can be found, ignoring verb endings, pluralities etc...

The segmentation works as follows:

The String: Hello World

2-gram: "He", "el", "ll", "lo", "o ", " W", "Wo", "or", "rl", "ld" 3-gram: "Hel", "ell", "llo", "lo ", "o W", " Wo", "Wor", "orl", "rld" 4-gram: "Hell", "ello", "llo ", "lo W", "o Wo", " Wor", "Worl", "orld"

Thus in your example, if we use 4-grams, truncations of the word Hello would appear to be the same. And this similarity would be captured by your features.

Answer 3

K-means require a matrix, in order to improve the performance you should be sure about how you have created it.

TF-IDF is a matrix, Word2Vec What could be done to improve my clustering algorithm? Hyperparameters should be tuned like bigrams.

I would still want to use K-Means but what another approach could be used in place of TF-IDF?

Word2Vec/CBOW