CODEWITHSUNDEEP
graphmachine-learningcluster-analysissvm
adam sakli
adam sakli

Reputation: 31

SVM Clustering Using Graph Data

I try to make clustering with using SVM. I have social networks graph data. In my data nodes connect to each others. I want to use graph adjacency matrix as SVM input data. My SVM input data is below. My main problem is community detection in graph data.

Is it possible to cluster graph data with using SVM. Could you offer me some methods to do this. I am a beginner at SVM. 

1 1:0 2:1 3:1 4:1 5:1

2 1:1 2:0 3:1 4:1 5:0

3 1:1 2:1 3:0 4:1 5:0

4 1:1 2:1 3:1 4:0 5:0

5 1:1 2:0 3:0 4:0 5:0

Upvotes: 2

Views: 2495

Answers (4)

Kingz
Kingz

Reputation: 5286

There were couple of papers that talked about Support Vector Clustering; here is one that I am trying to evaluate: http://jmlr.org/papers/volume2/horn01a/rev1/horn01ar1.pdf

Also, found an R package here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.190.9809

Upvotes: 0

3xCh1_23
3xCh1_23

Reputation: 1499

You can do the following:

  1. Apply as many clustering algorithms as you want to your data.

  2. Decide how many clusters you need to have (or use a number of clusters from any of the generated clusters).

  3. Optimize the output produced so that output from the clustering algorithms matches the desired numbers of clusters (and those exact clusters). This is a tricky part!

  4. Feed the SVM the data produced by the clusters such as centroids, mean-values etc.

  5. Finally, use the trained SVM to generate the clusters based on your originally inputted data.

Therefore, the idea is to develop a general clustering model with SVMs, based on other clustering models... that way, you can have the unsupervised SVM clustering. A thing to note is that you would need as many clustering data-rows as possible to make SVMs work (otherwise, SVMs would output the single number for each input you give).

Source: Currently working on this approach.

Edited: grammar, etc.

Upvotes: 0

lejlot
lejlot

Reputation: 66775

In general SVM is for classification, as many have pointed out. Although there exists SVM based clustering algorithm, which, similarly to the oridinal SVM, can use the kernel trick, which allows you to work on various types of data, including graphs (graph kernels). Adjcacency matrix is rather bad representation of graph similarity (unless you are actually interested in very simple phenomena, but then using SVM based approach seems like a bit too much. Believe in the Ockham's razor - the simplest approaches are the best ones, I would suggest looking/using simplier clustering methods, and if they will be unsufficient, then consider switching to the SVM clustering.

I strongly suggest reading papers on this topic, as it is not as easy as it could seem, yet it is wellresearched topic:

  • Presentation regarding graph mining and graph kernels
  • Michel Neuhaus, Horst Bunke: A Random Walk Kernel Derived from Graph Edit Distance. SSPR/SPR 2006: 191-199
  • S.V.N. Vishwanathan, Karsten M. Borgwardt, Nicol N. Schraudolph: Fast Computation of Graph Kernels. NIPS 2006:1449-1456

For the implementation itself, matlab library (already mentioned) is located here: https://sites.google.com/site/daewonlee/research/svctoolbox

Upvotes: 1

Fabien GUILLAUME
Fabien GUILLAUME

Reputation: 11

SVM cannot do clustering, you can find multiclass SVM and other variation. On the other hand, Support Vector Clustering exists it is a slightly different approach than SVM but close. I don't know any package providing this algorithm, it is not very famous so far.

Upvotes: 1

Related Questions