In [10]:
import json
import os
import codecs
import operator
pagesLCS = json.load(codecs.open('./pages_LCS.json', 'r', 'utf-8'))
similar = {}
for page in pagesLCS:
p1, p2 = page.split('_')
if p1 in similar:
similar[p1][p2] = 1 - pagesLCS[page]
else:
similar[p1] = {p1: 0, p2: 1 - pagesLCS[page]}
with open('./similar_distance.json', 'w', encoding='utf8') as json_file:
json.dump(similar, json_file, ensure_ascii=False, sort_keys=True)
json_file.close()
similar_rank = {}
for page in similar:
similar_rank[page] = sorted(similar[page].items(), key=lambda x: x[1])
similar_rank[page] = [page for (page, distance) in similar_rank[page]]
out = open('similar.txt', 'w')
for page in similar_rank:
print(page, similar_rank[page][1], pagesLCS[page+'_'+similar_rank[page][1]])
out.write(str(page)+' '+str(similar_rank[page][1])+' '+str(pagesLCS[page+'_'+similar_rank[page][1]])+'\n')
out.close()
216698465032151 105545149477125 0.09333333333333334
540412076095692 289023717931699 0.11226252158894647
1419818298230500 1522018888083950 0.3
386314964858506 289023717931699 0.09859154929577464
569973146410364 116451508389016 0.07222222222222222
491301524314363 274177245975887 0.1889763779527559
191063592130 108278499242201 0.11092985318107668
255007834581384 815695648473554 0.13402061855670103
465278773538786 347531965339561 0.09399075500770417
199811256813007 538624313005886 0.15434782608695652
591797137565255 205437996183472 0.128125
110405899022540 507215539303375 0.10126582278481013
382234085212504 229198730561050 0.17406143344709898
287284994724109 343419232339399 0.11893203883495146
151226998381159 426856224013300 0.08250355618776671
468425719873216 218013741876047 0.6
206239186203525 1689066257989797 0.10761154855643044
232248973462063 208067196022874 0.18303571428571427
127820127275752 140233409407304 0.052941176470588235
1249879941786518 1689066257989797 0.1680327868852459
482368755113431 611205092299538 0.11734693877551021
86575789916 190315537669464 0.11036789297658862
1159270450790969 101870389895334 0.17647058823529413
1405715926394069 109176185826729 0.11607142857142858
1377648855890489 555284231162605 0.1688888888888889
234436663237719 347531965339561 0.16580310880829016
41322676186 80329313253 0.08947368421052632
212027428936253 610650075627697 0.12090163934426229
834742146604404 289023717931699 0.14054054054054055
210403188990915 693019877446799 0.12826603325415678
156497504559146 343419232339399 0.14285714285714285
844326262293996 1419837788230877 0.17543859649122806
128947083784021 373445712817040 0.1273100616016427
842759152469328 1408784476004937 0.14067278287461774
555284231162605 208067196022874 0.13986013986013987
388125357933815 1689066257989797 0.13457556935817805
119243644772011 180004174892 0.1406926406926407
444372432288248 452843211589379 0.11363636363636363
140297072649041 854546371318792 0.12941176470588237
505897169441991 230277370619 0.1099476439790576
461496017303150 160500577320453 0.11538461538461539
1568806943367154 191977730842670 0.1166936790923825
614655208612882 820044538105541 0.0847457627118644
534780330019072 1563921000486116 0.11484593837535013
190315537669464 693019877446799 0.11202185792349727
1629539270669220 423559277818930 0.12133891213389121
114562181900948 1419837788230877 0.09973045822102426
465374246921091 139771366109945 0.1534090909090909
123873980984159 380331072040399 0.1092896174863388
118333574851335 289023717931699 0.13191489361702127
1409656432603181 527863447283088 0.09494949494949495
188203728181380 1639201256301520 0.12745098039215685
139188202817559 801280139992222 0.10576923076923077
898665433580000 109664335761247 0.22549019607843138
361254023932689 423559277818930 0.15056818181818182
662688547224470 1723788574551552 0.08491228070175438
197747943620827 1689066257989797 0.12239583333333333
136971732995778 353243144714101 0.19708029197080293
611205092299538 482368755113431 0.10900473933649289
197107420061 408969379164188 0.13703703703703704
191256677929793 139289596121879 0.12213740458015267
772275819464530 176566195692285 0.1111111111111111
130839263634699 101811116527527 0.08144796380090498
598604200229003 1731304453750777 0.10885341074020319
354343431295511 128947083784021 0.38461538461538464
211982968849377 710234179063682 0.21739130434782608
322940647865674 815695648473554 0.1320754716981132
258296243537 289023717931699 0.11131725417439703
143908108977420 710234179063682 0.05121638924455826
109176185826729 801280139992222 0.10526315789473684
573163832816948 1689066257989797 0.11278195488721804
109659209119087 672057092824275 0.17218543046357615
303224496458910 41322676186 0.05694760820045558
309225189372 538338459619512 0.10888252148997135
876746295670054 538338459619512 0.08695652173913043
195624117135236 1408784476004937 0.17751479289940827
382572141940509 182105958621541 0.18303571428571427
100957993764080 208067196022874 0.15076923076923077
1408784476004937 241704489292376 0.13092979127134724
412674492211861 1546981542180430 0.12435233160621761
217967811552648 166973750029327 0.10672853828306264
1594756864162746 156261024747269 0.13075060532687652
257428887711266 128999347123451 0.08163265306122448
369202419826832 105719312802440 0.13513513513513514
251425431621499 1199074646844517 0.12403100775193798
196321930396277 115137298591136 0.14046822742474915
546364602117464 176566195692285 0.10903873744619799
184675181585506 1405172736421791 0.14285714285714285
197427340298532 103932529657678 0.12295081967213115
1629626160626907 160500577320453 0.11298482293423272
897500820295426 373445712817040 0.11602209944751381
1704606696448937 1123184674393171 0.15522388059701492
216583255039003 863519910413984 0.1981981981981982
612530492205981 138959932830440 0.11826086956521739
158289357629532 444304632326874 0.14655172413793102
627208337308053 922498367842780 0.12903225806451613
630785640398305 139771366109945 0.1303030303030303
450243618472283 607774789317523 0.375
216917188358257 194218180769569 0.07924528301886792
427071670643918 527863447283088 0.05649241146711636
947181031967716 331008656971590 0.16176470588235295
234861513629757 291315244250856 0.22807017543859648
156927077428 1671847899714197 0.12459016393442623
138398943007584 157123397777485 0.13670411985018727
498173277013353 139771366109945 0.23636363636363636
147374232028715 922498367842780 0.17088607594936708
731632196883480 170972093097920 0.12910284463894967
220711858140080 1477561755803059 0.11574697173620457
155599231146036 206239186203525 0.12921348314606743
146406732438 1689066257989797 0.1453900709219858
171184692941905 588897847851618 0.13257575757575757
140516489486805 1409656432603181 0.09770114942528736
1433815936882512 160500577320453 0.16774193548387098
232780660840 557825984256733 0.14803625377643503
129643877242538 513567562058753 0.1424802110817942
291315244250856 1689066257989797 0.13003663003663005
588897847851618 1468677143445838 0.1338432122370937
429082863791945 182105958621541 0.1773049645390071
169049806445459 157123397777485 0.1080773606370876
104163463021826 226018220908005 0.14336917562724014
248047082025533 103932529657678 0.17435897435897435
158946047608783 112582352208845 0.10666666666666667
208067196022874 693019877446799 0.12094395280235988
759635894067517 166973750029327 0.16013071895424835
1123184674393171 815695648473554 0.14375987361769352
1509543916021132 100957993764080 0.5
33641865377 259022110879068 0.11538461538461539
1424426044440890 966354356825969 0.1572052401746725
173209342767140 388125357933815 0.16363636363636364
221693124678812 139771366109945 0.2116788321167883
252545044793468 1405715926394069 0.375
351665144970683 171345406093 0.16326530612244897
577719525603542 1494890627449188 0.10751445086705202
1423447227907326 193430274009219 0.13024282560706402
801280139992222 139188202817559 0.11418685121107267
102030733249307 538338459619512 0.1513157894736842
6569469259 139188202817559 0.0847457627118644
373583899415718 577719525603542 0.10215053763440861
499332696776281 142765199078274 0.16964285714285715
786690411418404 242645762532524 0.09082969432314411
276478795882536 161967123880519 0.2222222222222222
232367350440745 347531965339561 0.12254901960784313
108499152642849 1731304453750777 0.107981220657277
1438649073110678 540847772617757 0.18614718614718614
229199143854836 1647890402098855 0.36363636363636365
450512788348294 834742146604404 0.10357815442561205
203911012959998 162199300487822 0.12222222222222222
140233409407304 158946047608783 0.1774193548387097
170736923096528 141108613290 0.10725552050473186
131603936871744 538338459619512 0.11328125
869639369745978 712500972180544 0.1453900709219858
227957877539331 1052780614747030 0.18618618618618618
1405172736421791 112582352208845 0.06442577030812324
426856224013300 1494890627449188 0.12745098039215685
468983709913391 41322676186 0.15625
165767303459849 116451508389016 0.09965635738831616
115922758503528 1026326337463718 0.14893617021276595
121778711349337 309225189372 0.1509433962264151
368841703128230 1574455939492691 0.1598173515981735
335254516552098 128947083784021 0.1443850267379679
260813957412700 151226998381159 0.13618677042801555
380331072040399 1579259628964371 0.13078470824949698
135012586656978 176566195692285 0.1536231884057971
642658102439515 426856224013300 0.124
352824124833736 419786675322 0.10192307692307692
744584535599124 183722548340699 0.20652173913043478
1077568658937300 176566195692285 0.12401574803149606
362172090498776 592279297527138 0.20454545454545456
1582306038712573 1574455939492691 0.15845070422535212
1083221118452157 1689066257989797 0.10306406685236769
105719312802440 1689066257989797 0.08843537414965986
332794266914951 452843211589379 0.14705882352941177
123462194338513 316755021768365 0.1657142857142857
274098406064785 693019877446799 0.11212814645308924
710234179063682 552580508224925 0.06791569086651054
308763179202522 1494890627449188 0.10457516339869281
137710369601260 169712752619 0.11144578313253012
815695648473554 493219530713993 0.11934673366834171
563065163835002 113370048688923 0.04295366795366795
235913503118661 459128137583975 0.18882978723404256
1540938496124910 1494890627449188 0.11653116531165311
170972093097920 242645762532524 0.11600429645542427
874950299215309 1433815936882512 0.13877551020408163
140569536068280 191063592130 0.0990990990990991
223910962197 532891723437086 0.09950248756218906
364395900324212 557825984256733 0.16167664670658682
421859467977721 199811256813007 0.17326732673267325
124169337611251 159267807570941 0.125
328973740451495 1574455939492691 0.12702702702702703
162478710481676 298234686953639 0.2222222222222222
170667696286699 101870389895334 0.13488372093023257
1727459227512547 272385739598280 0.0967741935483871
357755571031957 262336633797230 0.1424581005586592
116311708027 153966281324610 0.10962566844919786
101855326672940 1419837788230877 0.11755485893416928
978448518842067 160500577320453 0.1172291296625222
485914018089950 1419837788230877 0.12470588235294118
151079018398909 347531965339561 0.1048951048951049
184775651572579 262549277132338 0.2903225806451613
1600903373477205 693019877446799 0.1404109589041096
443875559088933 1500140420240098 0.14715719063545152
727236617367141 588897847851618 0.18556701030927836
1672631373021621 140733978544 0.11734693877551021
668740866508358 513567562058753 0.135632183908046
488881677840118 353243144714101 0.12956810631229235
684199848276518 362065616073 0.11440677966101695
452843211589379 1477561755803059 0.09060118543607112
281798851970726 110059273284 0.1712707182320442
1546981542180430 194806427323026 0.13373253493013973
602063783150371 218225131704700 0.16923076923076924
514515618632390 362065616073 0.12738853503184713
758241727530390 153966281324610 0.13228699551569506
1522018888083950 130839263634699 0.1130952380952381
271153079578185 122952084411802 0.1569767441860465
1052780614747030 580667262006261 0.15481171548117154
500319673400049 109176185826729 0.12365591397849462
392892097431364 190315537669464 0.16766467065868262
109664335761247 346459745437010 0.1297709923664122
328332417346503 191977730842670 0.13636363636363635
419786675322 538338459619512 0.10167130919220056
448330565343552 316755021768365 0.1497326203208556
595508857146066 347531965339561 0.08681672025723473
180797605341122 854546371318792 0.0873015873015873
479057355465967 316755021768365 0.12559241706161137
143683670539 194806427323026 0.0838150289017341
193490537441538 452843211589379 0.08777969018932874
249537878735603 693019877446799 0.1282051282051282
289889657810502 448330565343552 0.17333333333333334
379172625480987 237010953051383 0.10380622837370242
348964338480021 840893449254902 0.11904761904761904
922498367842780 286716024817933 0.18376068376068377
1118895718138524 1647890402098855 0.19523809523809524
1487399144862421 125504737481862 0.16161616161616163
1641393576100366 152077151520923 0.128
242914945729623 108278499242201 0.109375
412041815531212 190315537669464 0.14121037463976946
176566195692285 1723788574551552 0.1144578313253012
218225131704700 194806427323026 0.07964601769911504
245838582123372 1173454286014108 0.16333333333333333
117620251653448 1564062570484273 0.12287334593572778
68799690218 419786675322 0.0973630831643002
303484746395681 160500577320453 0.09743589743589744
679822232137150 386546978078312 0.20833333333333334
1502685290026738 1594756864162746 0.1837837837837838
212648685549332 245600025548352 0.16587677725118483
312519091124 279215218760954 0.15028901734104047
276272065761834 1689066257989797 0.1717557251908397
152808094736124 227555953956302 0.1079646017699115
423559277818930 513567562058753 0.2766439909297052
767484610013236 1399818406939046 0.1170018281535649
107036952782150 513567562058753 0.12903225806451613
172131842912578 153966281324610 0.09323116219667944
1572950279585094 141791915925731 0.09761388286334056
304663692992915 588897847851618 0.1407185628742515
913197215405395 1574455939492691 0.13468013468013468
421151494632907 1515387322118924 0.12403100775193798
223623184355028 513567562058753 0.16158536585365854
1374947439394342 801280139992222 0.07297297297297298
43810818350 131502193574244 0.2391304347826087
350260868436465 1494890627449188 0.07916666666666666
672057092824275 1568806943367154 0.11917098445595854
229197530424932 116451508389016 0.07736389684813753
113538112189249 343419232339399 0.11594202898550725
132670103558087 1515387322118924 0.08193979933110368
232910783956 1494890627449188 0.12
182105958621541 815695648473554 0.1329639889196676
1516980721851388 115429251032 0.1509433962264151
1839225226314450 693019877446799 0.16560509554140126
115429251032 101870389895334 0.09913793103448276
351934174852859 252775368181361 0.16666666666666666
161572254039658 176566195692285 0.13090909090909092
183098781729698 538338459619512 0.11303344867358708
137627742981450 227555953956302 0.15267175572519084
239167659478659 161067697262603 0.1172291296625222
298234686953639 316755021768365 0.1382716049382716
402243239868984 662688547224470 0.1366906474820144
119159351432460 196945910429334 0.20967741935483872
1723788574551552 435691919844078 0.09583074051026758
422767954421660 160500577320453 0.14859437751004015
1558453351063626 151226998381159 0.17419354838709677
473332559524751 316755021768365 0.1589041095890411
127809730632516 595508857146066 0.13043478260869565
334236760084743 1647890402098855 0.2
1726791267542346 1731304453750777 0.15286624203821655
803042033087344 493219530713993 0.1232876712328767
423078901209982 227740397401689 0.12915129151291513
225152760951350 1546981542180430 0.13851351351351351
693019877446799 157123397777485 0.128099173553719
966354356825969 716408615053745 0.13994910941475827
104003099656697 229198730561050 0.203125
993296297348530 611950542183357 0.20192307692307693
1512534755682844 347531965339561 0.20261437908496732
264937883552528 169712752619 0.12896405919661733
477063055791396 268497963354748 0.1214574898785425
286548828134144 274177245975887 0.15168539325842698
727306074021422 1419837788230877 0.12094763092269327
763000923760796 112582352208845 0.12631578947368421
345238678886278 151226998381159 0.1522491349480969
1417702438445142 187216948084405 0.11058823529411765
1702709833340928 710234179063682 0.08620689655172414
116003088469479 241704489292376 0.15838509316770186
174363965915077 232367350440745 0.09782608695652174
190581777753115 347531965339561 0.1382488479262673
236332659882728 612530492205981 0.16455696202531644
786715381395749 116201948521593 0.1836734693877551
244891225707334 1494890627449188 0.12155388471177944
360688234004533 538338459619512 0.14424635332252836
231216780238863 101811116527527 0.0684931506849315
595976397208523 124510714381439 0.6363636363636364
348811465219019 316755021768365 0.12470023980815348
167430153320685 110059273284 0.20481927710843373
362065616073 161067697262603 0.08134490238611713
278137519138 452843211589379 0.09152542372881356
1089248847769284 291315244250856 0.14285714285714285
1625767417699490 218225131704700 0.21818181818181817
171345406093 538338459619512 0.12043795620437957
150108621732715 110602052308408 0.14957264957264957
772748752858769 1563353597318719 0.10559006211180125
877436765668496 1647890402098855 0.16810344827586207
125504737481862 428117280647877 0.10574948665297741
203353129703413 551271348268105 0.14285714285714285
161804123902801 345238678886278 0.15432098765432098
268631400006087 1494890627449188 0.11475409836065574
281613428640827 569973146410364 0.0798611111111111
1647890402098855 139970839777 0.13506493506493505
263253950515536 33641865377 0.13043478260869565
252775368181361 1689066257989797 0.15
854637801213747 218225131704700 0.16176470588235295
428117280647877 125504737481862 0.13770053475935828
194176943960328 360688234004533 0.1211453744493392
287041424809561 241704489292376 0.11728395061728394
1689066257989797 538338459619512 0.11542730299667037
209313619221921 1494890627449188 0.12807881773399016
1630575400536730 1689066257989797 0.1377245508982036
121600191207052 272385739598280 0.11442786069651742
650807701626519 41322676186 0.18181818181818182
209351802768160 225152760951350 0.2
1451341655082271 113370048688923 0.175
392711807556044 513567562058753 0.145
937887682888434 101870389895334 0.13053613053613053
596754363684947 114562181900948 0.13089005235602094
275021082576999 1671847899714197 0.10795454545454546
229198730561050 1563921000486116 0.13953488372093023
143473012336657 116201948521593 0.08231707317073171
444176385675870 157123397777485 0.5555555555555556
716850641674372 151226998381159 0.1167192429022082
232880803425159 1584409648477751 0.08465608465608465
587840021328415 1563921000486116 0.19463087248322147
218360704879455 426856224013300 0.14666666666666667
341847786156947 221757371312307 0.14908256880733944
1519938018257271 1399818406939046 0.1504424778761062
122952084411802 108278499242201 0.11371237458193979
820044538105541 347531965339561 0.10698689956331878
1574455939492691 1584409648477751 0.11374407582938388
557825984256733 199394156383 0.11827956989247312
813476262083241 693019877446799 0.09215686274509804
519812998096416 169712752619 0.14652014652014653
597505910353778 208067196022874 0.11420612813370473
1626748197601736 555284231162605 0.14953271028037382
246404228850615 538338459619512 0.12962962962962962
592279297527138 157123397777485 0.1218568665377176
268157116890134 1574455939492691 0.13937282229965156
136538423089223 284005851690208 0.025703794369645042
151703251513057 194806427323026 0.09744214372716199
339673995623 253555804661007 0.1351931330472103
360065781053 157123397777485 0.1208955223880597
153966281324610 193430274009219 0.13818722139673106
122219067827057 1468677143445838 0.1162227602905569
611950542183357 1574455939492691 0.1476923076923077
109100059125975 1579259628964371 0.11494252873563218
710356519010372 283899755107967 0.15822784810126583
551271348268105 428117280647877 0.09062980030721966
1431488670479820 157123397777485 0.08210526315789474
203964966359072 100957993764080 0.14925373134328357
382962558441459 441456492635913 0.1267605633802817
142261325791050 151079018398909 0.11387900355871886
165462730590308 298542666857522 0.0855106888361045
1515387322118924 125504737481862 0.08243243243243244
102676389854371 863519910413984 0.13304721030042918
496488130391111 316755021768365 0.12529002320185614
202211843164890 511438592279170 0.09641873278236915
112523559082289 229197530424932 0.11956521739130435
157580257639804 232910783956 0.16129032258064516
392699500920994 1563921000486116 0.1501597444089457
183144711760638 208067196022874 0.17333333333333334
161067697262603 108278499242201 0.1
225257419014 127820127275752 0.029197080291970802
1743165085908098 155599231146036 0.18309859154929578
745150592237114 208067196022874 0.11330049261083744
881682581849449 335254516552098 0.13742690058479531
677636295678096 226018220908005 0.16
1121313334664817 668740866508358 0.14184397163120568
892355350886009 507215539303375 0.12682926829268293
614863751860026 493219530713993 0.09240407204385279
256733854390475 1653252078230326 0.1645021645021645
114445768581954 101811116527527 0.10638297872340426
942171772580147 206239186203525 0.13238770685579196
99005207953 139771366109945 0.11547344110854503
453272418150729 100957993764080 0.22857142857142856
670232653088455 1647890402098855 0.1875
435691919844078 1723788574551552 0.05985231247570929
464510183617438 218225131704700 0.2097902097902098
138959932830440 614863751860026 0.13278008298755187
150314051704565 1405172736421791 0.06349206349206349
103977703121161 161067697262603 0.12990196078431374
507215539303375 316755021768365 0.10263157894736842
178880375546453 153966281324610 0.1310116086235489
552580508224925 710234179063682 0.07945205479452055
1606756286232530 199811256813007 0.15193370165745856
234076983294652 206239186203525 0.23076923076923078
329701998064 143683670539 0.08496732026143791
453791191413243 801280139992222 0.19083969465648856
1836675556562340 193430274009219 0.13815789473684212
1085407991570325 1494890627449188 0.10837988826815642
756819654377206 1671847899714197 0.0946073793755913
264877176917295 1574455939492691 0.1659919028340081
198980176914540 662688547224470 0.08643815201192251
691885324257302 139188202817559 0.09876543209876543
858015854257493 347531965339561 0.13196480938416422
156403724380227 1419837788230877 0.13170731707317074
1796234590602664 1408784476004937 0.07772020725388601
113936128781560 116201948521593 0.16
547179928716011 298234686953639 0.1780821917808219
1176359702374365 1419837788230877 0.09771986970684039
1480444838900129 1731304453750777 0.11864406779661017
1111925358883046 1460163874267523 0.09238031018206339
728845667250612 268631400006087 0.12127659574468085
262336633797230 1419837788230877 0.09915356711003627
371708416229838 978448518842067 0.049689440993788817
147481531978504 1405172736421791 0.10294117647058823
590216161058043 131603936871744 0.12313432835820895
444304632326874 1731304453750777 0.1349036402569593
346212252163733 510284302406680 0.11746987951807229
243283842531861 103977703121161 0.10451977401129943
436953693002317 206239186203525 0.128
175618445817950 316755021768365 0.1532258064516129
502554316442433 143683670539 0.024691358024691357
1419213555000123 1494890627449188 0.12727272727272726
316921241653926 493219530713993 0.11262798634812286
257603931029172 298234686953639 0.2608695652173913
323889714435445 183618218405165 0.14225941422594143
963902503636281 151226998381159 0.15100671140939598
368908053375 170972093097920 0.12944162436548223
1466677966973237 280381605668792 0.13013698630136986
137282442960698 580667262006261 0.1543026706231454
821182777954496 1568806943367154 0.5
619202881423565 115429251032 0.11009174311926606
380226175398223 130839263634699 0.16666666666666666
1732357040325180 216917188358257 0.13445378151260504
460587520648705 787689677914729 0.15714285714285714
549651081740923 1574455939492691 0.25675675675675674
1725871517670091 614863751860026 0.11755952380952381
240763106130265 605583392876962 0.26
205902566171901 208067196022874 0.19101123595505617
222288647793004 183098781729698 0.13793103448275862
648526978552009 167090343625658 0.17567567567567569
226018220908005 510284302406680 0.1351981351981352
202586923170539 426856224013300 0.1303030303030303
373080029513950 194806427323026 0.12420785804816223
248795661989435 1083221118452157 0.09836065573770492
283899755107967 235913503118661 0.1314878892733564
142693215811296 178803602185808 0.057208237986270026
554189794694434 173087833154565 0.1419491525423729
236785626505504 1689066257989797 0.20634920634920634
325735520921941 1574455939492691 0.23232323232323232
168531616676712 103932529657678 0.1518987341772152
330015423685873 190315537669464 0.16374269005847952
159267807570941 1689066257989797 0.1196319018404908
285482004900192 298234686953639 0.21428571428571427
160649177404116 136538423089223 0.10857142857142857
155676674461979 693019877446799 0.13781512605042018
689023577829745 419786675322 0.1864406779661017
1589365954636781 840893449254902 0.25609756097560976
951654351553736 1731304453750777 0.16494845360824742
686264231422297 194806427323026 0.11980830670926518
395127123873438 298234686953639 0.17164179104477612
292994117567639 392699500920994 0.18791946308724833
218183464973185 122884317761791 0.18497109826589594
264386906876 538624313005886 0.15714285714285714
335680096583533 202211843164890 0.5
279616242057888 1564062570484273 0.09131736526946108
1448559655443933 237010953051383 0.09698996655518395
399107496814983 190315537669464 0.152
325429457552507 114562181900948 0.23529411764705882
312788018905823 113370048688923 0.15030674846625766
168604352869 167976249908207 0.12434691745036573
863519910413984 854546371318792 0.07865168539325842
276133749091622 274098406064785 0.145985401459854
314556245305848 486704024831288 0.14655172413793102
505388972961135 139970839777 0.14659685863874344
1527630557471626 493219530713993 0.14749262536873156
380344342045920 396623023741258 0.21428571428571427
163734943674630 157123397777485 0.11351351351351352
364851713566241 538338459619512 0.13533834586466165
120430854692085 537585129595198 0.13701431492842536
194335480681445 151226998381159 0.11598746081504702
1591610927796167 1574455939492691 0.1013745704467354
418670774881399 527863447283088 0.12105263157894737
229176130442231 834742146604404 0.13612565445026178
124503967714779 1689066257989797 0.15789473684210525
274367719608378 1647890402098855 0.11363636363636363
330415020475231 915836148479218 0.12096774193548387
227555953956302 176566195692285 0.11490683229813664
116960661656339 115137298591136 0.07655502392344497
543784899005713 169712752619 0.13063063063063063
1538960036386438 1546981542180430 0.32558139534883723
703275913091814 614655208612882 0.02127659574468085
427558300653850 510284302406680 0.14285714285714285
490586851101969 113370048688923 0.12559241706161137
477219915649770 527863447283088 0.06272129489124936
426150234146595 241704489292376 0.12311015118790497
697583236982344 316755021768365 0.14722222222222223
1039119579484813 1546981542180430 0.15204678362573099
280381605668792 347531965339561 0.13106796116504854
297640516936620 1689066257989797 0.12345679012345678
1421225274845366 235913503118661 0.14988290398126464
1399818406939046 538338459619512 0.0842754367934224
211767714887 122952084411802 0.1325
1306501022714998 1173454286014108 0.12237762237762238
174853160851 176566195692285 0.1303501945525292
685395598159022 388125357933815 0.13261648745519714
51620386454 289023717931699 0.15030674846625766
436075479927868 1494890627449188 0.14678899082568808
1564062570484273 614863751860026 0.12229299363057325
208631422498510 1405172736421791 0.1794871794871795
667686543361144 1689066257989797 0.11188811188811189
108618205960585 227555953956302 0.13768115942028986
314073998960234 206239186203525 0.1272264631043257
1647604062160947 138959932830440 0.1125
205437996183472 280989872089314 0.11353711790393013
356196707924530 152632038133843 0.13333333333333333
230097320524876 1500140420240098 0.13350785340314136
1437478363150880 978448518842067 0.0975609756097561
258532244271250 1604504463125711 0.12478632478632479
1046853448691451 165767303459849 0.12807881773399016
272074389496925 1574455939492691 0.17363344051446947
1485623941733575 1419837788230877 0.11733333333333333
151922823908 257855401000765 0.2641509433962264
1563921000486116 208067196022874 0.15113871635610765
116373061722109 122952084411802 0.1342685370741483
166973750029327 113370048688923 0.09831460674157304
242645762532524 1494890627449188 0.1033175355450237
1899441200274738 1574455939492691 0.10982658959537572
128999347123451 194806427323026 0.1076923076923077
1579259628964371 403805216490826 0.12585034013605442
180004174892 1123184674393171 0.13680781758957655
510284302406680 157123397777485 0.11958146487294469
455914297758265 221757371312307 0.13385826771653545
152297201135 1176359702374365 0.12802768166089964
222505344491146 289023717931699 0.13549618320610687
159369930790732 428117280647877 0.1414141414141414
141108613290 403805216490826 0.13001605136436598
168969886771344 347531965339561 0.07885906040268456
221994451161630 590216161058043 0.1575091575091575
114014168612719 6569469259 0.1
196945910429334 1494890627449188 0.1330049261083744
605583392876962 316755021768365 0.16300940438871472
1677828372501845 1723788574551552 0.08627450980392157
1572694813007656 380331072040399 0.16483516483516483
742776705755862 392699500920994 0.19767441860465115
1779036445648199 153966281324610 0.10256410256410256
1449886151916610 157123397777485 0.11909650924024641
1026326337463718 139771366109945 0.12745098039215685
115278891923304 158946047608783 0.03164556962025317
429245233809012 380331072040399 0.13665943600867678
1671847899714197 756819654377206 0.08223684210526316
319921861479845 1173454286014108 0.1384083044982699
1713752478840194 169049806445459 0.007042253521126761
223569484441649 152808094736124 0.1511111111111111
167090343625658 915836148479218 0.1495601173020528
230277370619 105545149477125 0.11390532544378698
108278499242201 161067697262603 0.08695652173913043
765542590141017 580667262006261 0.09411764705882353
152077151520923 176566195692285 0.11703703703703704
180995181949343 452843211589379 0.18518518518518517
284005851690208 710234179063682 0.08540925266903915
799407796756184 1494890627449188 0.0979020979020979
516461878390039 208067196022874 0.15441176470588236
263416137034907 513567562058753 0.1323529411764706
428296830666916 426856224013300 0.12589928057553956
146277882133118 208067196022874 0.15040650406504066
702107769831174 116960661656339 0.06878306878306878
296109920473776 194806427323026 0.11509433962264151
643882542395790 1574455939492691 0.18248175182481752
203329913014359 1647890402098855 0.14244186046511628
119542611468000 1494890627449188 0.10625
315784085182798 176566195692285 0.06743940990516333
412939388896038 380331072040399 0.1836734693877551
1053263171395979 730840223722204 0.15229885057471265
532891723437086 540847772617757 0.09666666666666666
232043196864682 693019877446799 0.12147505422993492
313424235468145 1731304453750777 0.13972055888223553
289409824428693 347531965339561 0.1245674740484429
129836913780889 153966281324610 0.11089494163424124
423932164311742 684199848276518 0.17647058823529413
999142940190243 820044538105541 0.12110726643598616
293983457380794 241704489292376 0.11699779249448124
1468677143445838 452843211589379 0.07920792079207921
342981182415442 119542611468000 0.08979591836734693
1443478292598907 787689677914729 0.11750599520383694
346459745437010 289023717931699 0.1206896551724138
462762305243 139188202817559 0.11731843575418995
286716024817933 382234085212504 0.17716535433070865
538624313005886 162199300487822 0.08596300326441784
1078016215546255 1584409648477751 0.1597222222222222
116201948521593 803042033087344 0.10876623376623376
179751313972 116451508389016 0.12863070539419086
257855401000765 1494890627449188 0.1284153005464481
194218180769569 289023717931699 0.09467455621301775
567734506728589 182105958621541 0.20666666666666667
218013741876047 316755021768365 0.14206128133704735
160500577320453 538338459619512 0.10401891252955082
712500972180544 444304632326874 0.136
396623023741258 538338459619512 0.08737864077669903
158137614222284 854546371318792 0.1060126582278481
1653252078230326 1574455939492691 0.14035087719298245
1749053471991935 913197215405395 0.19718309859154928
108839102486538 130839263634699 0.09926470588235294
1374262062897616 167387533298529 0.08254716981132075
179141501852 152077151520923 0.11611374407582939
248106245333687 1568806943367154 0.13937282229965156
1731304453750777 1477561755803059 0.09711538461538462
610650075627697 191977730842670 0.1103448275862069
255085928370 172131842912578 0.116751269035533
116190681727467 141791915925731 0.1346938775510204
443689202408538 167976249908207 0.11544461778471139
491452930867938 801280139992222 0.12903225806451613
426589374089125 257428887711266 0.15060240963855423
193430274009219 153966281324610 0.14307692307692307
1566646833571875 662688547224470 0.11196911196911197
842370685890191 241704489292376 0.10668789808917198
541059486010275 158946047608783 0.10071942446043165
183618218405165 196945910429334 0.15562913907284767
347531965339561 513567562058753 0.09227467811158799
1356712637682900 208067196022874 0.15561959654178675
121251951220038 165462730590308 0.09655172413793103
7945687618 143908108977420 0.10294117647058823
112414102173261 229198730561050 0.17525773195876287
373962699371581 716850641674372 0.2619047619047619
128856323839212 122952084411802 0.08767123287671233
165436840538238 540412076095692 0
140281166135875 316755021768365 0.155
201004716673412 388125357933815 0.18548387096774194
493219530713993 614863751860026 0.08885542168674698
141437149364801 165462730590308 0.09782608695652174
110059273284 141791915925731 0.14854111405835543
139382602810804 1419837788230877 0.0669683257918552
330417367092347 1123184674393171 0.1315240083507307
119651704759937 408969379164188 0.08933002481389578
1031164496899466 665804156808926 0.13793103448275862
495634787188259 662688547224470 0.11764705882352941
127121034032549 580667262006261 0.0975609756097561
165599467123016 272074389496925 0.19161676646706588
250582028311992 298234686953639 0.24
1868705696681544 610650075627697 0.10267857142857142
431383406951825 1419837788230877 0.13312202852614896
948186481887159 176566195692285 0.12436115843270869
1752174138375797 428117280647877 0.1187800963081862
221757371312307 527863447283088 0.11848341232227488
386546978078312 161067697262603 0.09840810419681621
907022122651535 122952084411802 0.1159090909090909
112074978953976 227555953956302 0.12751677852348994
80329313253 710234179063682 0.07570422535211267
276071069075297 180004174892 0.12224108658743633
272385739598280 435691919844078 0.08956982911019445
394334193973618 176566195692285 0.126953125
576623602350684 188203728181380 0.23728813559322035
237010953051383 123110954555066 0.0851581508515815
113370048688923 373445712817040 0.062303335431088736
143482385679217 513567562058753 0.10852713178294573
169467799732700 493219530713993 0.15833333333333333
227740397401689 1579259628964371 0.13429752066115702
719841841413084 151226998381159 0.13392857142857142
138343202858798 298542666857522 0.10679611650485436
683061648428857 1689066257989797 0.12240184757505773
315439911809907 235913503118661 0.12705882352941175
101870389895334 193430274009219 0.09681697612732096
1153393404676936 712500972180544 0.16498316498316498
821068938006729 128999347123451 0.4444444444444444
419002571536737 1477561755803059 0.0915032679738562
915836148479218 510284302406680 0.12612612612612611
202794560089125 120430854692085 0.2222222222222222
1494890627449188 1723788574551552 0.08573388203017833
486704024831288 538338459619512 0.13592233009708737
305512749626201 1199074646844517 0.17064846416382254
233259360029541 116451508389016 0.09016393442622951
180304782017009 291315244250856 0.1416184971098266
1173454286014108 241704489292376 0.11409395973154363
1425680167661719 1419837788230877 0.1362397820163488
152632038133843 693019877446799 0.100418410041841
268804973206677 218225131704700 0.08673469387755102
165313966921153 116451508389016 0.10964912280701754
245600025548352 212648685549332 0.1590909090909091
639844446082078 331008656971590 0.13372093023255813
21547400499 114562181900948 0.017902813299232736
269925279709965 158289357629532 0.18592964824120603
364977463563490 113936128781560 0.18571428571428572
385861145127411 116201948521593 0.1875
645397092165337 241704489292376 0.11333333333333333
150540241750381 162199300487822 0.115234375
110602052308408 170972093097920 0.16230366492146597
347878058756152 305512749626201 0.2345679012345679
369011356471717 316755021768365 0.15492957746478872
139965336070372 108080895911317 0.1527777777777778
449969825047677 428117280647877 0.1282798833819242
1639201256301520 1494890627449188 0.09073359073359073
140345789312504 151079018398909 0.07675438596491228
116451508389016 151079018398909 0.05830903790087463
1564754203752998 161067697262603 0.12138728323699421
233727919984719 41322676186 0.1111111111111111
1584409648477751 242645762532524 0.13175230566534915
191977730842670 610650075627697 0.11461318051575932
1604504463125711 538338459619512 0.13353566009104703
433183180107798 151079018398909 0.08203125
10150103156550556 496488130391111 0.11904761904761904
574469755972316 783139551775483 0.09663865546218488
578426292233728 672057092824275 0.15725806451612903
101811116527527 130839263634699 0.0851063829787234
1605457326343593 801280139992222 0.10843373493975904
607774789317523 330417367092347 0.1306532663316583
844523235571967 168969886771344 0.06463878326996197
187216948084405 360065781053 0.10641891891891891
738735629503410 493219530713993 0.09579667644183773
107235216024674 169049806445459 0.11804008908685969
745293045548235 347531965339561 0.10569105691056911
137411776275948 242645762532524 0.10152284263959391
459128137583975 235913503118661 0.2720306513409962
453209555507 419786675322 0.10160427807486631
1678326075777035 1419837788230877 0.11583011583011583
206616599362013 139382602810804 0.11976047904191617
477571809077858 127121034032549 0.32142857142857145
142115602738 108278499242201 0.08349514563106795
665804156808926 664595856899790 0.11203814064362336
13844228987 112582352208845 0.12101910828025478
148489678578745 876746295670054 0.22535211267605634
298651560320609 693019877446799 0.09543010752688172
445913858762180 122952084411802 0.09655172413793103
101994566563782 176566195692285 0.11550151975683891
157123397777485 693019877446799 0.09205642167780252
118181084999024 1574455939492691 0.20540540540540542
309681779207248 289023717931699 0.13319672131147542
128923847150124 113370048688923 0.12582781456953643
1531152543819223 157123397777485 0.1291139240506329
190757521017080 1584409648477751 0.11510791366906475
384381901588038 114014168612719 0.14925373134328357
369778986423852 693019877446799 0.12448132780082988
1681966512061978 289023717931699 0.10690121786197564
343419232339399 170972093097920 0.11509433962264151
175107755915795 801280139992222 0.18867924528301888
251387421718846 129643877242538 0.1443850267379679
266956990100551 210403188990915 0.13953488372093023
527863447283088 1477561755803059 0.10368144252441773
261248760644413 141791915925731 0.14184397163120568
316755021768365 241704489292376 0.1291866028708134
134922193248677 1374947439394342 0.0782122905027933
205299123240774 388125357933815 0.18571428571428572
642243705797767 227555953956302 0.14093959731543623
139970839777 289023717931699 0.1243432574430823
184768288231046 125504737481862 0.09164969450101833
1023104071094428 1689066257989797 0.1292929292929293
348892151974913 138959932830440 0.1541501976284585
298542666857522 165462730590308 0.13432835820895522
1500140420240098 834742146604404 0.13861386138613863
403805216490826 538338459619512 0.10859188544152745
156364837894700 1689066257989797 0.10344827586206896
1544162702483088 459128137583975 0.15987460815047022
108080895911317 180004174892 0.1342281879194631
105545149477125 199394156383 0.09048723897911833
547703278609883 403805216490826 0.11270125223613596
103932529657678 1671847899714197 0.10451977401129943
1477561755803059 263056233887383 0.08702975856260528
268497963354748 190315537669464 0.13978494623655913
188069131228489 199394156383 0.11818181818181818
131502193574244 139771366109945 0.15613382899628253
730840223722204 493219530713993 0.14769975786924938
486127281425566 227740397401689 0.1503267973856209
192347530836014 121600191207052 0.09302325581395349
130423737037819 538338459619512 0.07650273224043716
104645842964390 1088007581234333 0.13120567375886524
892329730840071 139771366109945 0.14361702127659576
1883483658544009 299520330059900 0.09375
703910556335910 441456492635913 0.10971223021582734
1631230223774081 1584409648477751 0.17625899280575538
787689677914729 101870389895334 0.14437367303609341
1018746744812903 834742146604404 0.14713896457765668
140733978544 125504737481862 0.125
123110954555066 232880803425159 0.09578544061302682
1526415970966495 242645762532524 0.16747572815533981
155925621271126 127820127275752 0.007874015748031496
342361585804203 444304632326874 0.44
359235917794935 386546978078312 0.14173228346456693
127494713927669 151079018398909 0.08115942028985507
1577691122490871 157123397777485 0.17355371900826447
441456492635913 513567562058753 0.11320754716981132
315236215158099 143683670539 0.13991769547325103
1419837788230877 493219530713993 0.09141494435612083
299503200237984 139571912754174 0.171875
537585129595198 120430854692085 0.12593984962406016
209114399128259 158289357629532 0.18627450980392157
148356295337263 1563921000486116 0.1563517915309446
1612636368984302 429245233809012 0.19161676646706588
124510714381439 316755021768365 0.13983050847457626
158974101135140 465278773538786 0.08637873754152824
139223596102079 279616242057888 0.1601423487544484
169712752619 157123397777485 0.11060606060606061
117447438287046 1681966512061978 0.11860940695296524
258071800968555 1419837788230877 0.10107816711590296
1657141181169592 229198730561050 0.1702127659574468
199394156383 1419837788230877 0.11936936936936937
369426936469264 235913503118661 0.11416490486257928
293765427326738 1868705696681544 0.04065040650406504
843513572405960 574469755972316 0.08547008547008547
200780326624627 183144711760638 0.16463414634146342
333544303363017 176566195692285 0.1384180790960452
316946865051767 176566195692285 0.09436619718309859
947355362064519 1568806943367154 0.15128205128205127
191417357668277 1574455939492691 0.1640378548895899
148526905750 178803602185808 0.09502262443438914
253555804661007 339673995623 0.17073170731707318
759684417475316 1176359702374365 0.12442396313364056
142765199078274 313424235468145 0.12690355329949238
523038221051030 217651414941757 0.049069373942470386
164504490292220 459128137583975 0.15486725663716813
1460163874267523 263056233887383 0.10239651416122005
263056233887383 1477561755803059 0.09942270686337396
246009652092956 1176359702374365 0.13978494623655913
298202347031361 210403188990915 0.17872340425531916
1627194667563087 176566195692285 0.1080669710806697
180813728744807 232880803425159 0.12320916905444126
139289596121879 435691919844078 0.09570154095701541
358839384230016 86575789916 0.14655172413793102
543209025719472 110602052308408 0.19776119402985073
166255983424675 693019877446799 0.125
217651414941757 523038221051030 0.11740890688259109
437882833038511 289023717931699 0.20192307692307693
723976930999139 316755021768365 0.1210762331838565
308945857094 1083221118452157 0.14603174603174604
348708128597826 477219915649770 0.12259194395796848
233937193370951 121600191207052 0.09558823529411764
373445712817040 614863751860026 0.09005947323704333
220431984683727 112582352208845 0.07042253521126761
141791915925731 176566195692285 0.11078717201166181
241704489292376 854546371318792 0.11375661375661375
158321050880514 122952084411802 0.10746268656716418
171149299676206 1752174138375797 0.1450381679389313
198122116994360 387774511318031 0.15625
526493767415532 801280139992222 0.12077294685990338
168718703306566 978448518842067 0.11423550087873462
195789230507956 123110954555066 0.3023255813953488
571733356350561 810479975707658 0.25
296933170726024 1689066257989797 0.13550135501355012
477297935656565 178880375546453 0.1423948220064725
131188180256757 396623023741258 0.09863013698630137
378342648860546 123110954555066 0.12650602409638553
139571912754174 1689066257989797 0.12814070351758794
202094046803662 190315537669464 0.12191103789126853
399098936807344 728845667250612 0.1388101983002833
162654480425686 140733978544 0.10313075506445672
527015580663289 1118895718138524 0.18439716312056736
289023717931699 1494890627449188 0.11566018423746162
173087833154565 1494890627449188 0.1274787535410765
161967123880519 115137298591136 0.1583710407239819
849051415125241 392699500920994 0.17365269461077845
580667262006261 538338459619512 0.11155378486055777
810479975707658 151226998381159 0.08791208791208792
854546371318792 527863447283088 0.07662538699690402
538338459619512 309225189372 0.10070671378091872
158146914248666 330417367092347 0.18143459915611815
262549277132338 386546978078312 0.12598425196850394
168640986524207 176566195692285 0.11293634496919917
143968298975832 538338459619512 0.15976331360946747
685611318201690 263056233887383 0.11757990867579908
127582937299872 588897847851618 0.14838709677419354
118527848157414 108839102486538 0.1
320017001493004 136538423089223 0.11666666666666667
466813953347275 423559277818930 0.17989417989417988
438861486206864 221693124678812 0.2112676056338028
178803602185808 347531965339561 0.06504854368932039
353243144714101 143683670539 0.09814814814814815
150587944970421 108278499242201 0.06339468302658487
664595856899790 665804156808926 0.08952380952380952
191338370463 552580508224925 0.08366533864541832
280989872089314 1671847899714197 0.11220472440944881
534452399953827 403805216490826 0.09861325115562404
1156025554433391 642658102439515 0.5384615384615384
1483447468549914 1052780614747030 0.1256544502617801
268062724729 386314964858506 0.0880503144654088
783139551775483 693019877446799 0.09074733096085409
114994931859230 137627742981450 0.2571428571428571
468031846740993 1731304453750777 0.10410958904109589
500170940113501 493219530713993 0.1069182389937107
1498455247060088 153966281324610 0.12244897959183673
275066866026017 1500140420240098 0.15948275862068967
1462015697360276 347531965339561 0.07524271844660194
368290076687905 351934174852859 0.42857142857142855
1404727629768259 113370048688923 0.09404990403071017
110378789009338 143683670539 0.18085106382978725
171299092921612 1494890627449188 0.13148148148148148
224025267661635 1689066257989797 0.08823529411764706
540847772617757 1689066257989797 0.12954545454545455
331008656971590 513567562058753 0.09510869565217392
377175508973193 103932529657678 0.125
33391900957 199394156383 0.12144702842377261
293955560695469 139970839777 0.13636363636363635
310083122348540 1546981542180430 0.17857142857142858
217123185292544 153966281324610 0.09595959595959595
644455368984442 801280139992222 0.11403508771929824
1407865602780315 1494890627449188 0.11346444780635401
1088007581234333 298234686953639 0.14915254237288136
36238527458 155544267811998 0.08078602620087336
115137298591136 183722548340699 0.15865384615384615
948622795180277 313424235468145 0.18807339449541285
167367646696618 316755021768365 0.1598639455782313
199187186816187 611950542183357 0.16363636363636364
179649788745145 298234686953639 0.11471321695760599
1727583250800050 227555953956302 0.12668463611859837
161653610553364 115137298591136 0.1494661921708185
273250047329 801280139992222 0.12568306010928962
633397416749454 362065616073 0.09779614325068871
208286859514448 157123397777485 0.1225071225071225
427332363990827 232367350440745 0.34615384615384615
440159086039538 208067196022874 0.1070840197693575
112582352208845 233259360029541 0.10181818181818182
373591039343920 693019877446799 0.15210355987055016
162199300487822 1419837788230877 0.12034383954154727
266746373728813 272074389496925 0.2072072072072072
288070931526392 131188180256757 0.1510791366906475
100868257073399 1018746744812903 0.25925925925925924
716408615053745 1689066257989797 0.11451612903225807
513567562058753 423559277818930 0.1598951507208388
125894397756740 1626748197601736 0.18354430379746836
171887916244 113370048688923 0.11515151515151516
1808347739453631 309225189372 0.12921348314606743
128758817177518 161653610553364 0.18604651162790697
259022110879068 101811116527527 0.06924643584521385
150117845033336 41322676186 0.09401709401709402
840893449254902 577719525603542 0.10437710437710437
274177245975887 160500577320453 0.1286549707602339
387774511318031 1500140420240098 0.11083743842364532
885080744852208 1052780614747030 0.1341991341991342
380715378756682 113370048688923 0.08215962441314555
382654928780158 403805216490826 0.144
203965556618485 496488130391111 0.17435897435897435
167976249908207 527863447283088 0.1014370245139476
230065907198836 249537878735603 0.1471698113207547
100321510018083 1639201256301520 0.15789473684210525
282966718483475 347531965339561 0.11454545454545455
150239271828801 157123397777485 0.10277777777777777
1429196407300816 1574455939492691 0.13172043010752688
394418884053947 242645762532524 0.12727272727272726
1488261941413456 176566195692285 0.12672811059907835
139771366109945 614863751860026 0.13651315789473684
183722548340699 115137298591136 0.12406015037593984
250998878395027 362065616073 0.12211221122112212
194806427323026 1723788574551552 0.07804878048780488
552894334754267 196945910429334 0.19298245614035087
200642259980249 151079018398909 0.048109965635738834
1601823920029109 1579259628964371 0.1388888888888889
572396812781675 169049806445459 0.21739130434782608
383095048410111 493219530713993 0.13953488372093023
214147661979588 1574455939492691 0.15302491103202848
443165549044747 298234686953639 0.28125
741680912514426 161067697262603 0.15030674846625766
141179435910975 157123397777485 0.11525029103608847
497022410320180 351934174852859 0.22972972972972974
463812053767846 115137298591136 0.1206896551724138
598394796887763 588897847851618 0.15012106537530268
1747488872205439 343419232339399 0.22043010752688172
740885522645256 316755021768365 0.2
345332025507019 444304632326874 0.15343915343915343
1199074646844517 538338459619512 0.11485451761102604
155544267811998 36238527458 0.07597535934291581
116201195193718 194806427323026 0.15217391304347827
136662106403401 316755021768365 0.1532567049808429
279215218760954 426856224013300 0.11467889908256881
170194439665786 1419837788230877 0.1274787535410765
511438592279170 428117280647877 0.08759124087591241
1709317042636543 1123184674393171 0.11512027491408934
163994350311417 1671847899714197 0.08302354399008674
1563353597318719 1584409648477751 0.14009661835748793
165687076814093 299520330059900 0.13178294573643412
1055598184511954 180004174892 0.11895161290322581
644851632192363 1409656432603181 0.09165808444902163
1402894846626786 712500972180544 0.18803418803418803
859381394090978 386314964858506 0.10256410256410256
281176591946550 183098781729698 0.1485148514851485
1394743067512240 347531965339561 0.18627450980392157
568956523226407 1563921000486116 0.21052631578947367
167387533298529 194806427323026 0.09398496240601503
156261024747269 1477561755803059 0.11406096361848574
299520330059900 161067697262603 0.10874704491725769
516973695057318 1564062570484273 0.15
155086501227386 538338459619512 0.1144927536231884
122884317761791 1574455939492691 0.15789473684210525
408969379164188 153966281324610 0.1163141993957704
169739143041172 217967811552648 0.20833333333333334
452197764845865 693019877446799 0.10727969348659004
In [2]:
def distance(page1, page2):
return similar[str(page1)][str(page2)]
In [3]:
from __future__ import print_function, unicode_literals, division
import copy
import random
import sys
try:
import numpy
except ImportError:
pass
from nltk.cluster.util import VectorSpaceClusterer
class KMeansClusterer(VectorSpaceClusterer):
"""
The K-means clusterer starts with k arbitrary chosen means then allocates
each vector to the cluster with the closest mean. It then recalculates the
means of each cluster as the centroid of the vectors in the cluster. This
process repeats until the cluster memberships stabilise. This is a
hill-climbing algorithm which may converge to a local maximum. Hence the
clustering is often repeated with random initial means and the most
commonly occurring output means are chosen.
"""
def __init__(self, num_means, distance, repeats=1,
conv_test=1e-6, initial_means=None,
normalise=False, svd_dimensions=None,
rng=None, avoid_empty_clusters=False):
"""
:param num_means: the number of means to use (may use fewer)
:type num_means: int
:param distance: measure of distance between two vectors
:type distance: function taking two vectors and returing a float
:param repeats: number of randomised clustering trials to use
:type repeats: int
:param conv_test: maximum variation in mean differences before
deemed convergent
:type conv_test: number
:param initial_means: set of k initial means
:type initial_means: sequence of vectors
:param normalise: should vectors be normalised to length 1
:type normalise: boolean
:param svd_dimensions: number of dimensions to use in reducing vector
dimensionsionality with SVD
:type svd_dimensions: int
:param rng: random number generator (or None)
:type rng: Random
:param avoid_empty_clusters: include current centroid in computation
of next one; avoids undefined behavior
when clusters become empty
:type avoid_empty_clusters: boolean
"""
VectorSpaceClusterer.__init__(self, normalise, svd_dimensions)
self._num_means = num_means
self._distance = distance
self._max_difference = conv_test
assert not initial_means or len(initial_means) == num_means
self._means = initial_means
assert repeats >= 1
assert not (initial_means and repeats > 1)
self._repeats = repeats
self._rng = (rng if rng else random.Random())
self._avoid_empty_clusters = avoid_empty_clusters
self.inertia = 0
def cluster_vectorspace(self, vectors, trace=False):
if self._means and self._repeats > 1:
print('Warning: means will be discarded for subsequent trials')
meanss = []
for trial in range(self._repeats):
if trace: print('k-means trial', trial)
if not self._means or trial > 1:
self._means = self._rng.sample(list(vectors), self._num_means)
self._cluster_vectorspace(vectors, trace)
meanss.append(self._means)
if len(meanss) > 1:
# sort the means first (so that different cluster numbering won't
# effect the distance comparison)
for means in meanss:
means.sort(key=sum)
# find the set of means that's minimally different from the others
min_difference = min_means = None
for i in range(len(meanss)):
d = 0
for j in range(len(meanss)):
if i != j:
d += self._sum_distances(meanss[i], meanss[j])
if min_difference is None or d < min_difference:
min_difference, min_means = d, meanss[i]
# use the best means
self._means = min_means
def _cluster_vectorspace(self, vectors, trace=False):
if self._num_means < len(vectors):
# perform k-means clustering
converged = False
while not converged:
# assign the tokens to clusters based on minimum distance to
# the cluster means
clusters = [[] for m in range(self._num_means)]
for vector in vectors:
index = self.classify_vectorspace(vector)
clusters[index].append(vector)
if trace: print('iteration')
#for i in range(self._num_means):
#print ' mean', i, 'allocated', len(clusters[i]), 'vectors'
# recalculate cluster means by computing the centroid of each cluster
self.inertia = 0
new_means = list(map(self._centroid, clusters, self._means))
# measure the degree of change from the previous step for convergence
difference = self._sum_distances(self._means, new_means)
if difference < self._max_difference:
converged = True
# remember the new means
self._means = new_means
def classify_vectorspace(self, vector):
# finds the closest cluster centroid
# returns that cluster's index
best_distance = best_index = None
for index in range(len(self._means)):
mean = self._means[index]
dist = self._distance(vector, mean)
if best_distance is None or dist < best_distance:
best_index, best_distance = index, dist
return best_index
def num_clusters(self):
if self._means:
return len(self._means)
else:
return self._num_means
def means(self):
"""
The means used for clustering.
"""
return self._means
def _sum_distances(self, vectors1, vectors2):
difference = 0.0
for u, v in zip(vectors1, vectors2):
difference += self._distance(u, v)
return difference
def _centroid(self, cluster, mean):
if self._avoid_empty_clusters:
centroid = copy.copy(mean)
for vector in cluster:
centroid += vector
return centroid / (1+len(cluster))
else:
if not len(cluster):
sys.stderr.write('Error: no centroid defined for empty cluster.\n')
sys.stderr.write('Try setting argument \'avoid_empty_clusters\' to True\n')
assert(False)
min_dis = -1
for v1 in cluster:
sum_dis = 0
for v2 in cluster:
sum_dis += distance(v1, v2)
if sum_dis < min_dis or min_dis == -1:
min_dis = sum_dis
centroid = v1
self.inertia += min_dis
return copy.copy(centroid)
def __repr__(self):
return '<KMeansClusterer means=%s repeats=%d>' % \
(self._means, self._repeats)
In [4]:
import numpy
pages = [numpy.array(page) for page in similar]
k_inertia_arr = []
file = open('inertia.txt')
for line in file:
a,b,c = line.split()
k_inertia_arr.append(float(c))
file.close()
In [5]:
import math
for k in range(1,301):
if k < len(k_inertia_arr):
print(k,'Inertia:',math.sqrt(k_inertia_arr[k-1]))
continue
means = []
for i in range(k):
means += [pages[i]]
kmeans = KMeansClusterer(k, distance, initial_means=means)
clusters = kmeans.cluster(pages, True, trace=False)
# print('Clustered:', pages)
# print('As:', clusters)
# print('Means:', kmeans.means())
print(k,'Inertia:',kmeans.inertia)
k_inertia_arr.append(kmeans.inertia*kmeans.inertia)
1 Inertia: 757.5000000000022
2 Inertia: 728.9999999999991
3 Inertia: 734.7239316239314
4 Inertia: 700.6752136752123
5 Inertia: 690.9483516483502
6 Inertia: 692.2229548229536
7 Inertia: 684.5811355311344
8 Inertia: 679.3077089577077
9 Inertia: 729.8274447774468
10 Inertia: 809.1791259451176
11 Inertia: 806.1974721983476
12 Inertia: 796.2494346738516
13 Inertia: 794.9725860379913
14 Inertia: 794.6025106914741
15 Inertia: 792.0985009275048
16 Inertia: 791.0985009275048
17 Inertia: 831.0136029028247
18 Inertia: 828.3907233489915
19 Inertia: 826.5054529841653
20 Inertia: 822.9580905110311
21 Inertia: 822.9580905110311
22 Inertia: 818.1544757307599
23 Inertia: 817.7377999893201
24 Inertia: 818.1560224947777
25 Inertia: 817.0104511684565
26 Inertia: 814.7766709147121
27 Inertia: 817.7797965598668
28 Inertia: 817.3862457238189
29 Inertia: 817.7543140772224
30 Inertia: 816.1890103631441
31 Inertia: 819.1298697523641
32 Inertia: 815.673440015879
33 Inertia: 815.0441808235763
34 Inertia: 815.3619799450922
35 Inertia: 815.4510395344041
36 Inertia: 814.4428106740626
37 Inertia: 812.8633823501037
38 Inertia: 813.6970003585192
39 Inertia: 813.4133700549642
40 Inertia: 814.173262444961
41 Inertia: 813.173262444961
42 Inertia: 812.142306710084
43 Inertia: 810.9765506037907
44 Inertia: 809.9565998777252
45 Inertia: 809.0225950149797
46 Inertia: 806.9486828018793
47 Inertia: 808.5838937646582
48 Inertia: 807.6608168415813
49 Inertia: 809.6152067211364
50 Inertia: 808.7913587378063
51 Inertia: 809.2998239193975
52 Inertia: 804.4661907914115
53 Inertia: 801.6488946726943
54 Inertia: 800.7756552360746
55 Inertia: 810.4650158149542
56 Inertia: 809.8650158149542
57 Inertia: 808.9599063259031
58 Inertia: 808.0110012164141
59 Inertia: 808.3873650592127
60 Inertia: 814.2650760403164
61 Inertia: 813.3514957934028
62 Inertia: 803.9713694156576
63 Inertia: 804.8462784598512
64 Inertia: 790.3226970886404
65 Inertia: 792.6494275228347
66 Inertia: 813.1885144929888
67 Inertia: 812.7189483444572
68 Inertia: 811.7777718738689
69 Inertia: 810.7619396842829
70 Inertia: 809.7456960954796
71 Inertia: 808.8730239883442
72 Inertia: 807.9102961391152
73 Inertia: 806.3765635935691
74 Inertia: 806.0020107094459
75 Inertia: 805.1705781095601
76 Inertia: 803.734718398682
77 Inertia: 795.5516991089911
78 Inertia: 790.9851177780578
79 Inertia: 798.2306152173435
80 Inertia: 798.3154134474987
81 Inertia: 796.9020564636834
82 Inertia: 797.4698468173299
83 Inertia: 797.4368185120857
84 Inertia: 792.9795585504872
85 Inertia: 791.1781453574138
86 Inertia: 801.7920888245199
87 Inertia: 801.1067162309117
88 Inertia: 799.4762395951185
89 Inertia: 798.4444561332004
90 Inertia: 797.013055770955
91 Inertia: 795.6139449998338
92 Inertia: 795.299715481968
93 Inertia: 794.1314107942974
94 Inertia: 793.2314107942973
95 Inertia: 792.1860201527671
96 Inertia: 783.7575840069653
97 Inertia: 782.7836709834053
98 Inertia: 783.0595979425714
99 Inertia: 782.1241140716037
100 Inertia: 781.2451925842315
101 Inertia: 786.6321430827309
102 Inertia: 786.0627217285273
103 Inertia: 783.5610566656264
104 Inertia: 776.3853530334588
105 Inertia: 775.475658169179
106 Inertia: 787.0807335488606
107 Inertia: 786.3147376574935
108 Inertia: 784.8069430249027
109 Inertia: 783.6575142754216
110 Inertia: 782.7478554688637
111 Inertia: 780.2379183592657
112 Inertia: 781.1951598058536
113 Inertia: 773.5717827765749
114 Inertia: 773.9229946980766
115 Inertia: 772.5810301333896
116 Inertia: 769.5920895393425
117 Inertia: 768.658387881884
118 Inertia: 767.753778920921
119 Inertia: 766.7704573599813
120 Inertia: 765.7167145344658
121 Inertia: 772.8757519835048
122 Inertia: 770.7037329153463
123 Inertia: 768.5231625870586
124 Inertia: 768.9942140948363
125 Inertia: 767.997051659215
126 Inertia: 767.0270594950193
127 Inertia: 765.8115331237377
128 Inertia: 766.2335741413957
129 Inertia: 765.1916635383365
130 Inertia: 764.1652217100723
131 Inertia: 763.2231572650538
132 Inertia: 762.2532334206044
133 Inertia: 758.141280366215
134 Inertia: 758.6478173937353
135 Inertia: 757.7129061511318
136 Inertia: 756.8433409337406
137 Inertia: 755.000044259969
138 Inertia: 754.1168268898546
139 Inertia: 753.3472789609218
140 Inertia: 752.406980453459
141 Inertia: 751.4536202032288
142 Inertia: 750.5184850680936
143 Inertia: 749.4817101039032
144 Inertia: 748.2498691869275
145 Inertia: 751.3376317517495
146 Inertia: 744.5479701557913
147 Inertia: 755.1545028876197
148 Inertia: 746.10441989724
149 Inertia: 745.1445984686684
150 Inertia: 744.2818624911203
151 Inertia: 743.2525397236814
152 Inertia: 742.3735838700165
153 Inertia: 741.5883757847254
154 Inertia: 740.027958405652
155 Inertia: 740.5914394200736
156 Inertia: 739.265298993536
157 Inertia: 738.3338473806326
158 Inertia: 737.5648064548149
159 Inertia: 737.8700955764195
160 Inertia: 740.5743682327009
161 Inertia: 738.4412943887099
162 Inertia: 737.6037859330124
163 Inertia: 736.6750889159956
164 Inertia: 735.7392600389902
165 Inertia: 734.8017600389902
166 Inertia: 733.8543601025518
167 Inertia: 737.298074127171
168 Inertia: 736.3695026985995
169 Inertia: 735.9277709062166
170 Inertia: 735.0171041736934
171 Inertia: 734.1370831956345
172 Inertia: 732.6961244643518
173 Inertia: 731.8432562699276
174 Inertia: 726.3192173459939
175 Inertia: 724.6451199008636
176 Inertia: 724.0317049317675
177 Inertia: 723.9100122325137
178 Inertia: 722.9848785426742
179 Inertia: 722.0622266089725
180 Inertia: 721.2448570568594
181 Inertia: 718.5283695438171
182 Inertia: 717.6400114425367
183 Inertia: 716.9966158633518
184 Inertia: 716.882951614698
185 Inertia: 715.36604856088
186 Inertia: 714.4423844387427
187 Inertia: 713.5170113044144
188 Inertia: 716.2992617496128
189 Inertia: 714.9529770303435
190 Inertia: 714.1274901164078
191 Inertia: 713.1325770326881
192 Inertia: 712.1222219881099
193 Inertia: 711.2229682567666
194 Inertia: 710.1739542252981
195 Inertia: 709.2223303606686
196 Inertia: 708.4134592359279
197 Inertia: 708.4152454963673
198 Inertia: 707.4033160460676
199 Inertia: 710.3944457564415
200 Inertia: 709.4351729574986
201 Inertia: 710.525143796075
202 Inertia: 705.6869418517136
203 Inertia: 704.6855324461943
204 Inertia: 703.8673422006827
205 Inertia: 702.9965395077313
206 Inertia: 702.4006144671405
207 Inertia: 701.5487626152885
208 Inertia: 701.2323359484673
209 Inertia: 699.5946380208976
210 Inertia: 698.6711260781107
211 Inertia: 697.8491745899587
212 Inertia: 696.9314530709714
213 Inertia: 696.0867256665115
214 Inertia: 695.3672087139325
215 Inertia: 693.9787652612995
216 Inertia: 693.3933995420413
217 Inertia: 692.6423407135226
218 Inertia: 691.2687978165279
219 Inertia: 690.3260497249248
220 Inertia: 689.3951795690547
221 Inertia: 687.9605123794737
222 Inertia: 686.8788520687865
223 Inertia: 686.1105809487891
224 Inertia: 685.1750970778214
225 Inertia: 686.7572435091449
226 Inertia: 685.8744846358917
227 Inertia: 684.8953037623305
228 Inertia: 683.7707700984167
229 Inertia: 682.8185516683826
230 Inertia: 681.8758035767795
231 Inertia: 681.0118579985482
232 Inertia: 680.1171683590402
233 Inertia: 679.5115695681486
234 Inertia: 678.5141038261811
235 Inertia: 675.8438079456582
236 Inertia: 674.9239266400202
237 Inertia: 674.1858084296563
238 Inertia: 673.2003843014174
239 Inertia: 674.0462980508994
240 Inertia: 672.828301033889
241 Inertia: 671.8890942197952
242 Inertia: 670.96847494423
243 Inertia: 669.1272148225063
244 Inertia: 667.807705848697
245 Inertia: 666.9367381067615
246 Inertia: 666.7290865370047
247 Inertia: 665.7343915767926
248 Inertia: 664.8199178925821
249 Inertia: 666.1151513766096
250 Inertia: 665.2337700352548
251 Inertia: 665.854990653863
252 Inertia: 664.9049079701825
253 Inertia: 664.5461430906945
254 Inertia: 663.3908656892964
255 Inertia: 662.5479545471708
256 Inertia: 661.6825699317861
257 Inertia: 660.764343654414
258 Inertia: 659.9804485678281
259 Inertia: 658.9870726413232
260 Inertia: 658.1119308034475
261 Inertia: 657.1262303012817
262 Inertia: 654.4072501890114
263 Inertia: 653.5226348043959
264 Inertia: 652.6004609834279
265 Inertia: 651.6377233950918
266 Inertia: 650.7157768075548
267 Inertia: 649.7414886971907
268 Inertia: 648.9241303370258
269 Inertia: 647.971266304402
270 Inertia: 647.0709739803356
271 Inertia: 646.1906320999936
272 Inertia: 645.3851413986549
273 Inertia: 644.5546604435797
274 Inertia: 643.5233909775222
275 Inertia: 642.3374014494142
276 Inertia: 641.3525286051748
277 Inertia: 640.4637079060051
278 Inertia: 639.5530933808654
279 Inertia: 638.4723816119255
280 Inertia: 637.5479970904593
281 Inertia: 636.6238485174814
282 Inertia: 635.7555206457581
283 Inertia: 634.8191811232117
284 Inertia: 633.9702302569086
285 Inertia: 633.249631340828
286 Inertia: 632.2860670985805
287 Inertia: 631.392565058477
288 Inertia: 630.6643286205463
289 Inertia: 629.7622844503236
290 Inertia: 629.091319895566
291 Inertia: 629.7200853772895
292 Inertia: 628.8609944681987
293 Inertia: 625.4653331293696
294 Inertia: 624.5600712044769
295 Inertia: 622.4563360244323
296 Inertia: 621.5329910766972
297 Inertia: 620.6113609826532
298 Inertia: 619.7636801727472
299 Inertia: 618.8596076943513
300 Inertia: 619.4561856838161
In [6]:
import matplotlib.pyplot as plt
plt.plot(k_inertia_arr)
plt.ylabel('inertia^2')
plt.show()
out = open('inertia.txt', 'w')
for i in range(len(k_inertia_arr)):
out.write(str(i)+' Inertia: '+str(k_inertia_arr[i])+'\n')
out.close()
print('Complete')
Complete
In [7]:
k = 8
means = []
for i in range(k):
means += [pages[i]]
kmeans = KMeansClusterer(k, distance, initial_means=means)
clusters = kmeans.cluster(pages, True, trace=False)
In [8]:
if 'clusters' in locals():
out = open('cluster.txt', 'w')
for i in range(len(pages)):
out.write(str(pages[i])+' '+str(clusters[i])+'\n')
out.close()
print('Complete')
Complete
In [ ]:
Content source: chitly852456/SeniorProject_Python
Similar notebooks: