Spectral clustering in Python and data file.

circles.dat

1.61670043216 -0.0203610961994
0.677786021618 0.103232085098
0.750251761452 0.0903840429982
1.37915137033 0.0922255880313
0.883210412493 0.312245351224
1.05984814845 0.00049339926668
0.89106560153 0.0519917674471
1.00898354076 0.0938901919983
0.996244967171 0.164690477096
0.808339606021 0.441320631401
1.19617642342 0.0704935124358
1.15362203748 0.230989406365
1.23609799565 0.332884885348
1.26269037759 0.479088774309
0.517431628621 0.3644250922
0.794845339974 0.72715041119
0.529078492947 0.652959964912
0.78634393395 0.647963619489
1.08816583854 0.913531283031
0.737638233498 0.862294886483
0.890844972237 1.01716338665
1.04029393389 0.915187209777
0.542961588491 0.711280810387
0.926336313457 0.762033496014
0.697677793912 1.29212509261
0.537284540665 0.871564827206
0.0699501295131 0.993301591299
0.11780670192 0.687544166628
0.492078520561 1.16290999962
0.281889061563 0.909354420312
0.330810982169 0.963912654319
0.0663861225198 0.713783627865
0.593442618378 0.844955308152
0.287429039995 0.539419594658
0.219025137643 0.808346942155
0.453046727966 1.16607917252
0.0390048673328 1.24056768118
0.0228378498091 0.526141672802
-0.394464210823 0.47994228224
-0.359331711769 0.918912642317
-0.438041146443 0.764632931855
-0.324178931618 1.16970063599
-0.599289834965 0.714930152921
0.131351207892 1.18521164086
-0.552832284504 1.18077334995
-0.0433283915687 0.823014801524
-0.634157617047 1.06045814296
-0.26459050444 0.852123849364
-0.306882317283 0.52366013931
-0.471208293891 1.15235609439
-0.477228324671 1.08969414398
-0.277654880037 0.432387394057
-0.558701871613 0.88335767341
-0.35498909021 1.20614461765
-0.78231314117 0.779540335386
-0.451603037338 0.943467661352
-0.653270195461 0.902869150134
-0.847106381747 0.455880144729
-0.963184651201 0.510155220328
-0.777090986858 0.494377814841
-1.30826330097 0.758998904336
-0.604996876266 0.183288889828
-1.16897196146 0.615611727977
-1.01358162606 0.562463462861
-0.826767946413 0.639273696629
-0.714610427122 0.215970623747
-1.27214945173 0.0117530279051
-1.32015942776 0.202365430923
-1.08749936532 -0.00626271680853
-1.13887982971 0.378390418584
-0.803632138809 0.20912993022
-1.10606787438 0.586638843617
-0.876186784605 0.52140575374
-1.33087439572 -0.163709913996
-1.09296070947 0.170316629343
-1.06249032476 -0.116383213741
-1.09864947658 -0.367006361982
-1.10536053153 -0.2192256621
-0.946903628204 -0.118138435622
-1.21791556371 -0.281265546976
-0.564522735337 0.0611895681428
-1.04181996566 -0.403239948299
-0.792828750585 -0.321062684033
-0.70467218625 -0.519402349914
-0.974948923681 -0.590825462702
-0.949917713781 -0.53691616725
-1.04664466881 -0.147772287546
-0.915630039393 -0.928471498216
-0.737065228226 -0.215664117797
-0.413204912023 -0.553284319989
-0.888566780005 -0.575236244178
-0.865266847127 -0.738384793084
-0.674350143033 -0.85611866092
-0.513397840431 -0.867286129239
-0.196522768303 -0.460399779717
-1.00287568722 -0.786907901707
-0.486819690253 -0.476926181681
-0.0775596439891 -0.384593805208
0.0883444645266 -0.851906092722
-0.372680823634 -0.685884646056
-0.851277404893 -0.946542047549
-0.167225616899 -1.04951964272
-0.334054637429 -0.924796267456
-0.182694994584 -0.876694013769
-0.0636207045563 -0.829272083858
-0.355496767109 -0.996890302904
-0.0841420547448 -0.905253156678
0.372934344804 -1.22209961151
-0.145391727418 -0.931106607221
0.149156539317 -1.24536467814
-0.234711886488 -1.69081041505
-0.169109354784 -1.18069470762
0.0944593545636 -1.02490577403
0.293366272524 -1.05667496964
-0.604364238142 -1.12220602548
-0.0937558631288 -0.0857099263085
0.403611046132 -1.06214063678
0.0384504799653 -1.14365032127
0.599881889858 -0.629269733372
0.223655206775 -0.893730404612
0.360070461204 -1.19847831281
0.199999449574 -1.31690671512
0.842393086855 -1.3770200882
0.546921281827 -0.811502583792
0.408890771704 -1.06057605632
0.435522654977 -1.14528323785
0.494849000088 -0.939676465726
0.586531875418 -0.818082291367
0.667078210754 -0.950266331739
0.198357513882 -0.713711634437
0.548153382662 -0.590575709195
0.381722248583 -0.647210232321
1.1431766179 -1.21645364156
0.596927454726 -0.240117053235
0.491838277067 -0.877857151353
0.936703100471 -0.42038114733
0.805054179651 -0.10460618723
0.601728844929 -0.357807906006
0.829667320179 -0.644061236523
1.07245670571 -0.468630079891
0.776637514192 -0.783156524009
1.12356372561 -0.63159755364
0.788376948959 -0.409403609907
0.98249967621 -0.31515501915
0.990105709888 -0.188565539308
0.649382131471 -0.554647098656
1.29143966003 -0.424077315041
0.785923465979 -0.423199834344
0.810595494379 0.146636751505
0.843408480186 -0.0732615463772
2.41379862916 0.170200491919
2.65250773757 0.0491082028016
3.01838787354 -0.127682520383
2.37897576305 0.767834648838
2.87993050811 0.0447961286214
2.23322280593 0.457077501128
2.35297004972 0.458148325036
2.61390523606 0.575740274017
2.33673134868 0.776439978193
2.33030340551 1.09062732376
2.48563103038 0.836923882708
2.96881612707 1.36716348693
2.27948485781 1.93756667681
2.58004205073 1.19436762733
1.85022399365 1.5712283179
2.12513410205 1.65770807613
2.14663522325 1.64099079204
2.0941229675 1.73006649332
1.88663424145 1.90074636849
1.5204071405 2.50421627512
1.92109179252 2.00997060195
2.21753610734 2.18444094097
1.79245687578 2.63600917148
1.6517698254 1.84514048379
0.958348766567 2.34553789802
1.24739237126 2.59599487751
1.01225454237 2.62286558563
1.31730371542 2.31588688271
1.3857175969 2.51411810631
0.934695884876 2.47065972441
1.19783915594 2.31265769272
0.704156029102 2.91997646487
0.350138637159 3.01496444878
0.715057529106 3.21283105996
0.203103269024 2.57247117113
0.106202768197 3.08209863764
0.308535784533 2.35945069465
-0.190889657533 2.32713810429
0.350437065555 2.75748848773
-0.459926560436 2.84608964627
-0.232929387892 2.93187491955
-0.550025185293 2.78136608982
-0.211976218678 2.72824546715
-0.346284059517 2.78191897467
-1.10343665289 2.71805760278
-0.993257733089 2.41674862429
-0.691430625159 2.81781254372
-1.21397887453 2.04577167911
-1.09195184473 2.57198030155
-0.859951186752 2.41368087322
-1.54465333925 2.61460116438
-1.37341290812 1.99839011879
-1.7662261781 2.26731978649
-1.49399620232 1.93716930801
-1.88816320859 1.78791702117
-1.47264252573 2.40172865821
-2.17865670197 2.26095617169
-1.51273654277 1.99779924361
-2.32132017685 1.78511369259
-2.14462355943 2.0857878529
-2.68962742195 1.95562409038
-2.56172089896 1.31732843629
-2.86014398422 1.51658626948
-2.64570383915 0.874455633852
-2.37347301866 1.1148207271
-2.42000606959 1.28209645643
-2.63275959329 0.975982867614
-2.54572309952 0.951117430382
-2.60243943685 0.679696683799
-2.82944952539 0.392057997745
-2.41054039763 0.928649890926
-2.94599323056 0.653042567517
-3.04329153069 0.141084088091
-2.28235775524 0.377874520631
-2.71688304812 -0.0985148586846
-2.93463336116 -0.253505564389
-2.66445993818 -0.103890102712
-3.40240288607 -0.422633766184
-2.65275422359 -0.138259337644
-2.55852726349 -0.108010096427
-2.55312268219 0.0382727492348
-2.5613673661 -1.13573535102
-3.22386424574 -0.718887418649
-2.69589337563 -0.19168511215
-2.09175711778 -0.928873578515
-2.57638246596 -0.937694381716
-2.92733636876 -1.44173691766
-2.27504274863 -1.21981531149
-2.26707892808 -1.40240003619
-2.07374051864 -1.33361647919
-2.05621333628 -1.48105172576
-2.43119298344 -1.26968606604
-2.24016142403 -1.62757760914
-2.01101885707 -1.99176982138
-1.77417768767 -1.85845590995
-1.89836916985 -2.24378040341
-1.69674798866 -2.19961197416
-1.42609459964 -1.96119389165
-1.58971823582 -2.2993444054
-1.29670596171 -2.12418156995
-1.42368467224 -1.86899850995
-1.77408355612 -2.39419025314
-1.03762478061 -2.30169689504
-1.26094512622 -2.4181827854
-0.861422408815 -2.75351115625
-0.795718038737 -2.76686201034
-1.05094388811 -2.36185456067
-0.646910130716 -3.04828407783
-0.67127953041 -2.6581529907
-0.612746974093 -2.78212493577
-0.620159775794 -2.77846527498
-0.210212141826 -2.55352845881
0.140990063665 -2.92318812461
-0.162006219356 -2.3842139707
0.228151629473 -3.14475025092
0.194090257311 -2.79167669081
0.169363422605 -2.721193732
0.36053302661 -2.55030130523
0.912075672834 -2.53394604993
0.903567339665 -2.77706319035
1.13893229665 -2.77545482762
0.683810384544 -2.74191090303
0.850788841542 -2.54506542859
1.23077882 -2.94532510215
1.64022503005 -1.98650360711
1.54373192898 -2.30298171949
1.60410801812 -2.75885333033
1.72179519692 -2.38982702466
2.1253641701 -2.16569445083
1.39577963371 -2.34965591447
1.86193278407 -2.58144576736
2.50236360424 -2.26489165916
2.73026209504 -2.03816082205
2.21620265832 -2.25757742005
1.94120790274 -1.49342748326
2.17737760139 -1.70707779913
2.17291340947 -1.42049032539
2.37232565291 -1.25667319389
2.39942530566 -1.48808526387
2.57026154847 -1.38407208623
2.67942372906 -1.13941048092
2.22460998097 -1.16545582956
2.15895577561 -0.763684840206
2.31353275063 -0.853138101561
2.96428454749 -0.701728389101
2.85104659739 -0.52371094734
2.44383041423 -0.279253779274
2.8188079081 -0.401588908847
3.18540265236 -0.604003725658
2.82795815925 0.00571184112235
5.24011100281 -0.0610862028065
5.08873504118 0.159498441112
4.76973406867 0.243985903342
5.08948283653 0.611825179371
5.02367472119 1.01139607369
5.32821508955 0.402962898819
4.8314044387 1.43596420181
4.99546748567 1.16891344755
4.5716470357 1.26041288399
4.29686068172 2.08039800959
5.0342653394 1.99567587648
4.28101291715 1.78437407718
4.04397976553 2.4672465529
4.43494856535 2.62837310659
4.13751386232 2.28381124125
3.54359080533 2.98243975294
3.49522874366 3.1908745866
3.99337898 3.76113682722
4.09676715905 3.43644863652
3.29691647971 2.95378050805
3.21886433847 3.80390572268
3.05652918168 4.0657949276
3.12358650623 4.31292192948
3.13392846567 4.16142099867
2.49982215998 4.47949343565
2.28296033423 4.16585279655
2.38464981233 4.6556008645
1.94409518221 4.18823195449
2.25209119067 4.79189854987
1.17297679643 4.30252085087
1.51871937426 4.99705940207
1.40786912494 4.83644951998
1.30659078816 4.71224352136
0.852265507058 5.2614819617
0.779009568513 5.22991990493
0.735024899688 5.03063771577
0.79081958005 5.35309860201
0.722327844602 5.42801192734
0.314072576832 5.00301423426
-0.0367774670299 4.56504410042
-0.447819838432 4.64394927229
-0.764195667157 5.43478863623
-0.976224732726 4.68084053977
-1.14374583503 5.09641333408
-1.39912639132 4.89344547249
-1.30448726799 4.54494884444
-1.46697077582 4.76851782898
-2.32255179374 4.73907855515
-2.25598169722 4.58454117402
-2.5321355698 4.33762165412
-2.30059427946 4.43632043951
-2.34568789437 4.53506191165
-3.59161229576 4.26897743598
-3.30611720902 4.49216564648
-2.92390446163 4.32246373739
-3.37081622184 3.8029507189
-3.77127675619 3.50934123666
-3.14005182276 2.96524522125
-3.70513189234 3.46509619809
-3.58370142617 2.81633095418
-4.23552775114 3.22236311497
-4.57401790112 2.51818130413
-4.56181260793 2.59326855947
-4.63474164519 2.35259954765
-4.44916618566 1.97675539151
-4.71051759538 1.8160080917
-4.94390035301 1.32595106237
-4.82215837651 1.96114935002
-4.54997428991 1.68644171996
-4.74584313848 1.15528513937
-4.35382736381 0.647790665907
-4.60504632048 0.879600030069
-4.80728774412 0.806257538332
-5.28250204704 0.716564630661
-4.6944898936 0.272262258339
-5.53936000274 0.0736353554812
-4.52768001479 -0.315017350837
-4.42492745223 -0.0574219351779
-4.70459080943 -0.148424170492
-4.69913063508 -0.730453787819
-4.80208456074 -1.13165922033
-4.78277939941 -0.757441400459
-5.03229521983 -1.4441257713
-4.74583970637 -1.30030060387
-4.74662006321 -2.01644682625
-4.35205846153 -2.36183096759
-4.62246935913 -2.0182641855
-4.45341256699 -2.55342255749
-4.17960243172 -2.50902075911
-4.23669681092 -2.37475756732
-3.79051966829 -2.92917110751
-4.04365833886 -3.19611190766
-4.01478620392 -3.04135509334
-4.07448886517 -3.76835551636
-3.8297797026 -3.42286202498
-3.45026569296 -3.999150214
-3.16533029707 -4.00080905218
-2.84965517139 -4.47287350943
-3.40442354188 -3.76950971058
-2.79523624094 -4.41007824409
-2.33899252208 -4.15110458866
-2.04971774208 -4.36288906961
-2.17942985673 -4.56693259235
-2.05560669997 -4.51133325381
-1.74008032693 -4.88991137193
-1.80029862737 -4.78922971393
-0.72399802622 -4.60345263937
-1.18136602729 -4.96302241907
-0.900326305255 -5.27923113925
-0.875954811931 -4.61511115247
-0.64920302368 -4.96796126444
-0.0766826887076 -4.6936365796
-0.473168402752 -4.91736509926
-0.00937283697573 -5.21924304907
0.730266390118 -4.97940185007
0.711462579834 -5.15707330896
0.568527942765 -4.66352696229
1.19801104781 -4.89492183295
0.887386699343 -4.75849838992
1.28723439138 -5.03898007848
1.57390346553 -4.82900995828
1.70531865509 -4.50576814717
1.8051346969 -4.77831209725
2.51354924433 -4.62191871608
2.3350299207 -5.03854051494
2.56220117153 -4.30194696502
2.83874280713 -4.26639516352
2.69418363171 -4.288843921
3.33222689851 -4.05350490728
3.54552350896 -3.81949323709
3.29848031307 -3.74868030635
3.8813293539 -3.61918724831
3.39160713069 -2.52007157394
3.85443447735 -3.23598056731
3.49853554121 -2.88742624963
4.10062707239 -3.01034489885
3.94999087416 -2.79952824787
4.5034331688 -2.29849033178
4.26064175486 -2.48587257512
4.80459412013 -1.88821060549
4.99771403281 -1.91029730034
4.84344638374 -1.5880619637
4.52786245806 -1.5473570891
4.68037277142 -1.19456532088
4.65725747179 -1.49382949595
5.40579565909 -1.07925728317
5.07172667128 -0.826169069524
4.60459931621 -0.823479399723
4.95165274618 -0.484274057074
5.46764245666 0.0786119717926

spectral_clustering_short.py

#!/usr/bin/env python

from numpy import *
from scipy.linalg import eig
from scipy.cluster.vq import kmeans2
from scipy.spatial.kdtree import KDTree
from pylab import *

ps = array([map(float,l.split()) for l in file("circles.dat")])
kt = KDTree(ps)
knn = [[((lambda a,b:exp((-(sqrt(dot(a-b,(a-b).conj()))**2))/1.5))(p,ps[nb]),nb) for nb in kt.query(p,16)[1] if i!=nb] for i,p in enumerate(ps)]
W = zeros([len(knn)]*2)
_ = [W[p].__setitem__(nb,d) for p,nn in enumerate(knn) for d,nb in nn if p in zip(*knn[nb])[1]]
w,v = map(real,eig(diag([sum(Wi) for Wi in W])-W))
Y = array([e[1] for e in sorted(zip(w,v.T))[:3]]).T
res,idx = kmeans2(Y,3,minit='random')
_ = [plot(p[0],p[1],('ro','go','bo')[i]) for p,i in zip(ps,idx)]
show()