# Which algorithm to use for clustering word occurences?

I'd like to know whether the occurence of certain keywords in a long document is representative or is it limited to a few paragraphs and the primary topic of the document is something different. I think this can be verified by clustering the locations of the keyword matches in the document. We can use a word index for that: for example the 15th or the 56th word of the document. If we have a few small clusters compared to the size of the whole document, then the primary topic of the document is probably something unrelated. If we have many small clusters or a few really big clusters, then we can assume that the whole document is about the keywords. I am not that educated in statistics, I just learned k-means and I know there are many other algorithms for clustering. I'd like to know from an expert, what do you think, for this kind of data what are the best algorithms?

Clustering is not the best tool here.

First of all, you only have one variable, position. On such data - which is ordered - there exist much more powerful techniques.

Instead of clustering, what I assume you really are trying to do is a hypothesis test. Your hypothesis is that the word locations are clustered. And an appropriate null hypothesis then probably is that the locations are uniformly distributed. So take the word positions, and test whether you can reject a uniform distribution. But be prepared to find out that most of the time, you won't be able to reject uniformness in a significant way, the texts will often be too short.

• I am not sure how to do that. But I guess I have to rethink the whole problem. For example if I have a long article or a book with "a,b,c" chapters and "a" and "c" chapter are about the actual term, while "b" isn't, then the occurences are not evenly distributed, but still 2/3 of the text is about the term we are looking for... – inf3rno Mar 27 '18 at 2:55
• If it's a long enough text, that will likely pass as "not uniform distributed". – Has QUIT--Anony-Mousse Mar 27 '18 at 5:38

I don't know about clustering, but one commonly used method called TextRank does something similar automatically.

TextRank proceeds by constructing a graph $G$ on words given some proximity measure (for example $(v, w)$ is an edge if $v$, $w$ occur in text in a window of some length, or occur in one sentence) and then runs PageRank on the resulting graph. The idea is that ranks from PageRank can be used to measure overall importance.

For concrete examples you can see this notebook from gensim's documentation.

By the way, if you want to explore your idea of using clustering, you can use the graph that is constructed in TextRank's intermediate steps. I haven't heard about such an approach, but it seems interesting to try graph clustering methods (there are methods for that, for example Power Iteration Clustering or Spectral Clustering).

• Actually I try to improve the BM25 algorithm: en.wikipedia.org/wiki/Okapi_BM25 , which is an improved version of TextRank according to your link. As far as I know this one does not use any graph, it just counts how many times a word occurs in a text. This graph clustering idea sounds interesting, I'll read more about it. :-) – inf3rno Mar 26 '18 at 8:17
• BM25 is a scoring function for Bag of Words model (it's sort of improved cosine similarity), not an improved version of TextRank. – Jakub Bartczuk Mar 26 '18 at 8:19
• Second paragraph of the article you linked: "This summarizer is based on the "TextRank" algorithm, from an article by Mihalcea et al. This algorithm was later improved upon by Barrios et al. in another article, by introducing something called a "BM25 ranking function"". – inf3rno Mar 26 '18 at 8:21
• That's because in original TextRank you rank sentences, and it's common to use their pairwise BM25 scores as weights in graph – Jakub Bartczuk Mar 26 '18 at 8:22