Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It looks like to me that you are trying to address two different problems in one, i.e. "syntactic" and "semantic" clustering. They are quite different problems, expecially if you are in the realm of short-text analysis (and Twitter is the king of short-text analysis, of course). </p> <p>"Syntactic" clustering means aggregating tweets that come, most likely, from the same source. Your example of Foursquare fits perfectly, but it is also common for retweets, people sharing online newspaper articles or blog posts, and many other cases. For this type of problem, using a N-gram model is almost mandatory, as you said (my experience suggests that N=2 is good for tweets, since you can find significant tweets that have as low as 3-4 features). Normalization is also an important factor here, removing RT tag, mentions, hashtags might help. </p> <p>"Semantic" clustering means aggregating tweets that share the same topic. This is a much more difficult problem, and it won't likely work if you try to aggregate random sample of tweets, due to the fact that they, usually, carry too little information. These techniques might work, though, if you restrict your domain to a specific subset of tweets (i.e. the one matching a keyword, or an hashtag). LSA could be useful here, while it is useless for syntactic clusters.</p> <p>Based on your observation, I think what you want is syntactic clustering. Your biggest issue, though, is the fact that you need online clustering, and not static clustering. The classical clustering algorithms that would work well in the static case (like hierarchical clustering, or union find) aren't really suited for online clustering , unless you redo the clustering from scratch every time a new tweet gets added to your database. "Averaging" the clusters to add new elements isn't a great solution according to my experience, because you need to retain all the information of every cluster member to update the "average" every time new data gets in. Also, algorithms like hierarchical clustering and union find work well because they can join pre-existant clusters if a link of similarity is found between them, and they don't simply assign a new element to the "closest" cluster, which is what you suggested to do in your post.</p> <p>Algorithms like MinHash (or SimHash) are indeed more suited to online clustering, because they support the idea of "querying" for similar documents. MinHash is essentially a way to obtain pairs of documents that exceed a certain threshold of similarity (in particular, MinHash can be considered an estimator of Jaccard similarity) without having to rely on a quadratic algorithm like pairwise comparison (it is, in fact, <code>O(nlog(n))</code> in time). It is, though, quadratic in space, therefore a memory-only implementation of MinHash is useful for small collections only (say 10000 tweets). In your case, though, it can be useful to save "sketches" (i.e., the set of hashes you obtain by min-hashing a tweet) of your tweets in a database to form an "index", and query the new ones against that index. You can then form a similarity graph, by adding edges between vertices (tweets) that matched the similarity query. The connected components of your graph will be your clusters. </p>
    singulars
    1. This table or related slice is empty.
    1. PODoubts about clustering methods for tweets
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USEmanuele Bezzi
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PODoubts about clustering methods for tweets
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTBountyClose
    1. COThank you for your comment. Yes, I'm more interested in the "syntactic" case given that I'd like to use this for several languages, so issues like stemming or other specific issues would be a lot of extra work. When you say using N-gram with N=2 do you mean chars or words? As I said before, language independence would be needed so generating "words" wouldn't make sense in some languages.
      singulars
      1. PO
      1. USDan
    2. COBTW I did some testing with N=3 but the results weren't that great. Using Jaccard on the same tweets which only differed in the name mentioned (ie. about 14-16 out of 120 chars) gave a similarity of 70%. I presume N=3 adds more noise than needed in cases like this and perhaps N=2 would be a better take. Regarding MinHash, I've been reading about it and looks promising, but could you suggest me some resource that explains what hash generators are best for this? Thank you.
      singulars
      1. PO
      1. USDan
    3. COWith N=2 I mean words. I think a 2-char model will yield a lot of false positives, since the number of possible features will be rather low, and language biased. I have no experience with non-latin languages, therefore I don't know if you can adapt a word model to those languages. As for MinHash, I recommend reading the original paper by A. Broder, which you can find [here](http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf). He uses Rabin fingerprints, but you can also check the simpler [Universal Hashing](http://en.wikipedia.org/wiki/Universal_hashing).
      singulars
      1. PO
      1. USEmanuele Bezzi
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload