Programming Collective Intelligence

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

• 
  

Programming Collective Intelligence:

Building Smart Web 2.0 Applications

Toby Segaran

Want to tap the power behind search rankings, product recommendations, social bookmarking, and online matchmaking? This fascinating book demonstrates how you can build Web 2.0 applications to mine the enormous amount of data created by people on the Internet. With the sophisticated algorithms in this book, you can write smart programs to access interesting datasets from other web sites, collect data from users of your own applications, and analyze and understand the data once you've found it.

Programming Collective Intelligence takes you into the world of machine learning and statistics, and explains how to draw conclusions about user experience, marketing, personal tastes, and human behavior in general -- all from information that you and others collect every day. Each algorithm is described clearly and concisely with code that can immediately be used on your web site, blog, Wiki, or specialized application. This book explains:

• Collaborative filtering techniques that enable online retailers to recommend products or media
• Methods of clustering to detect groups of similar items in a large dataset
• Search engine features -- crawlers, indexers, query engines, and the PageRank algorithm
• Optimization algorithms that search millions of possible solutions to a problem and choose the best one
• Bayesian filtering, used in spam filters for classifying documents based on word types and other features
• Using decision trees not only to make predictions, but to model the way decisions are made
• Predicting numerical values rather than classifications to build price models
• Support vector machines to match people in online dating sites
• Non-negative matrix factorization to find the independent features in a dataset
• Evolving intelligence for problem solving -- how a computer develops its skill by improving its own code the more it plays a game
  

Each chapter includes exercises for extending the algorithms to make them more powerful. Go beyond simple database-backed applications and put the wealth of Internet data to work for you.

"Bravo! I cannot think of a better way for a developer to first learn these algorithms and methods, nor can I think of a better way for me (an old AI dog) to reinvigorate my knowledge of the details."
-- Dan Russell, Google

"Toby's book does a great job of breaking down the complex subject matter of machine-learning algorithms into practical, easy-to-understand examples that can be directly applied to analysis of social interaction across the Web today. If I had this book two years ago, it would have saved precious time going down some fruitless paths."
-- Tim Wolters, CTO, Collective Intellect

Product Details

• Paperback: 362 pages
• Publisher: O'Reilly Media; 1 edition (Aug. 26 2007)
• Language: English
• ISBN-10: 0596529325
• ISBN-13: 978-059652932
  

本帖隐藏的内容

Programming Collective Intelligence.rar (2.51 MB, 需要: 20 个论坛币) 本附件包括：

• Programming Collective Intelligence.pdf

2014-8-28 21:40:38 上传

需要: 20 个论坛币  [购买]

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏13 回帖

关键词：Intelligence Programming Collective Program collect Internet enormous programs collect created

1. # A dictionary of movie critics and their ratings of a small
   
2. # set of movies
   
3. critics={'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5,
   
4. 'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5,
   
5. 'The Night Listener': 3.0},
   
6. 'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5,
   
7. 'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0,
   
8. 'You, Me and Dupree': 3.5},
   
9. 'Michael Phillips': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0,
   
10. 'Superman Returns': 3.5, 'The Night Listener': 4.0},
    
11. 'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0,
    
12. 'The Night Listener': 4.5, 'Superman Returns': 4.0,
    
13. 'You, Me and Dupree': 2.5},
    
14. 'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
    
15. 'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0,
    
16. 'You, Me and Dupree': 2.0},
    
17. 'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
    
18. 'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5},
    
19. 'Toby': {'Snakes on a Plane':4.5,'You, Me and Dupree':1.0,'Superman Returns':4.0}}
    
20. 
    
21. 
    
22. from math import sqrt
    
23. 
    
24. # Returns a distance-based similarity score for person1 and person2
    
25. def sim_distance(prefs,person1,person2):
    
26.   # Get the list of shared_items
    
27.   si={}
    
28.   for item in prefs[person1]:
    
29.     if item in prefs[person2]: si[item]=1
    
30. 
    
31.   # if they have no ratings in common, return 0
    
32.   if len(si)==0: return 0
    
33. 
    
34.   # Add up the squares of all the differences
    
35.   sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2)
    
36.                       for item in prefs[person1] if item in prefs[person2]])
    
37. 
    
38.   return 1/(1+sum_of_squares)
    
39. 
    
40. # Returns the Pearson correlation coefficient for p1 and p2
    
41. def sim_pearson(prefs,p1,p2):
    
42.   # Get the list of mutually rated items
    
43.   si={}
    
44.   for item in prefs[p1]:
    
45.     if item in prefs[p2]: si[item]=1
    
46. 
    
47.   # if they are no ratings in common, return 0
    
48.   if len(si)==0: return 0
    
49. 
    
50.   # Sum calculations
    
51.   n=len(si)
    
52.   
    
53.   # Sums of all the preferences
    
54.   sum1=sum([prefs[p1][it] for it in si])
    
55.   sum2=sum([prefs[p2][it] for it in si])
    
56.   
    
57.   # Sums of the squares
    
58.   sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
    
59.   sum2Sq=sum([pow(prefs[p2][it],2) for it in si])        
    
60.   
    
61.   # Sum of the products
    
62.   pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
    
63.   
    
64.   # Calculate r (Pearson score)
    
65.   num=pSum-(sum1*sum2/n)
    
66.   den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
    
67.   if den==0: return 0
    
68. 
    
69.   r=num/den
    
70. 
    
71.   return r
    
72. 
    
73. # Returns the best matches for person from the prefs dictionary.
    
74. # Number of results and similarity function are optional params.
    
75. def topMatches(prefs,person,n=5,similarity=sim_pearson):
    
76.   scores=[(similarity(prefs,person,other),other)
    
77.                   for other in prefs if other!=person]
    
78.   scores.sort()
    
79.   scores.reverse()
    
80.   return scores[0:n]
    
81. 
    
82. # Gets recommendations for a person by using a weighted average
    
83. # of every other user's rankings
    
84. def getRecommendations(prefs,person,similarity=sim_pearson):
    
85.   totals={}
    
86.   simSums={}
    
87.   for other in prefs:
    
88.     # don't compare me to myself
    
89.     if other==person: continue
    
90.     sim=similarity(prefs,person,other)
    
91. 
    
92.     # ignore scores of zero or lower
    
93.     if sim<=0: continue
    
94.     for item in prefs[other]:
    
95.             
    
96.       # only score movies I haven't seen yet
    
97.       if item not in prefs[person] or prefs[person][item]==0:
    
98.         # Similarity * Score
    
99.         totals.setdefault(item,0)
    
100.         totals[item]+=prefs[other][item]*sim
     
101.         # Sum of similarities
     
102.         simSums.setdefault(item,0)
     
103.         simSums[item]+=sim
     
104. 
     
105.   # Create the normalized list
     
106.   rankings=[(total/simSums[item],item) for item,total in totals.items()]
     
107. 
     
108.   # Return the sorted list
     
109.   rankings.sort()
     
110.   rankings.reverse()
     
111.   return rankings
     
112. 
     
113. def transformPrefs(prefs):
     
114.   result={}
     
115.   for person in prefs:
     
116.     for item in prefs[person]:
     
117.       result.setdefault(item,{})
     
118.       
     
119.       # Flip item and person
     
120.       result[item][person]=prefs[person][item]
     
121.   return result
     
122. 
     
123. 
     
124. def calculateSimilarItems(prefs,n=10):
     
125.   # Create a dictionary of items showing which other items they
     
126.   # are most similar to.
     
127.   result={}
     
128.   # Invert the preference matrix to be item-centric
     
129.   itemPrefs=transformPrefs(prefs)
     
130.   c=0
     
131.   for item in itemPrefs:
     
132.     # Status updates for large datasets
     
133.     c+=1
     
134.     if c%100==0: print "%d / %d" % (c,len(itemPrefs))
     
135.     # Find the most similar items to this one
     
136.     scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
     
137.     result[item]=scores
     
138.   return result
     
139. 
     
140. def getRecommendedItems(prefs,itemMatch,user):
     
141.   userRatings=prefs[user]
     
142.   scores={}
     
143.   totalSim={}
     
144.   # Loop over items rated by this user
     
145.   for (item,rating) in userRatings.items( ):
     
146. 
     
147.     # Loop over items similar to this one
     
148.     for (similarity,item2) in itemMatch[item]:
     
149. 
     
150.       # Ignore if this user has already rated this item
     
151.       if item2 in userRatings: continue
     
152.       # Weighted sum of rating times similarity
     
153.       scores.setdefault(item2,0)
     
154.       scores[item2]+=similarity*rating
     
155.       # Sum of all the similarities
     
156.       totalSim.setdefault(item2,0)
     
157.       totalSim[item2]+=similarity
     
158. 
     
159.   # Divide each total score by total weighting to get an average
     
160.   rankings=[(score/totalSim[item],item) for item,score in scores.items( )]
     
161. 
     
162.   # Return the rankings from highest to lowest
     
163.   rankings.sort( )
     
164.   rankings.reverse( )
     
165.   return rankings
     
166. 
     
167. def loadMovieLens(path='/data/movielens'):
     
168.   # Get movie titles
     
169.   movies={}
     
170.   for line in open(path+'/u.item'):
     
171.     (id,title)=line.split('|')[0:2]
     
172.     movies[id]=title
     
173.   
     
174.   # Load data
     
175.   prefs={}
     
176.   for line in open(path+'/u.data'):
     
177.     (user,movieid,rating,ts)=line.split('\t')
     
178.     prefs.setdefault(user,{})
     
179.     prefs[user][movies[movieid]]=float(rating)
     
180.   return prefs

复制代码

1. from pydelicious import get_popular,get_userposts,get_urlposts
   
2. import time
   
3. 
   
4. def initializeUserDict(tag,count=5):
   
5.   user_dict={}
   
6.   # get the top count' popular posts
   
7.   for p1 in get_popular(tag=tag)[0:count]:
   
8.     # find all users who posted this
   
9.     for p2 in get_urlposts(p1['href']):
   
10.       user=p2['user']
    
11.       user_dict[user]={}
    
12.   return user_dict
    
13. 
    
14. def fillItems(user_dict):
    
15.   all_items={}
    
16.   # Find links posted by all users
    
17.   for user in user_dict:
    
18.     for i in range(3):
    
19.       try:
    
20.         posts=get_userposts(user)
    
21.         break
    
22.       except:
    
23.         print "Failed user "+user+", retrying"
    
24.         time.sleep(4)
    
25.     for post in posts:
    
26.       url=post['href']
    
27.       user_dict[user][url]=1.0
    
28.       all_items[url]=1
    
29.   
    
30.   # Fill in missing items with 0
    
31.   for ratings in user_dict.values():
    
32.     for item in all_items:
    
33.       if item not in ratings:
    
34.         ratings[item]=0.0

复制代码

1. import feedparser
   
2. import re
   
3. 
   
4. # Returns title and dictionary of word counts for an RSS feed
   
5. def getwordcounts(url):
   
6.   # Parse the feed
   
7.   d=feedparser.parse(url)
   
8.   wc={}
   
9. 
   
10.   # Loop over all the entries
    
11.   for e in d.entries:
    
12.     if 'summary' in e: summary=e.summary
    
13.     else: summary=e.description
    
14. 
    
15.     # Extract a list of words
    
16.     words=getwords(e.title+' '+summary)
    
17.     for word in words:
    
18.       wc.setdefault(word,0)
    
19.       wc[word]+=1
    
20.   return d.feed.title,wc
    
21. 
    
22. def getwords(html):
    
23.   # Remove all the HTML tags
    
24.   txt=re.compile(r'<[^>]+>').sub('',html)
    
25. 
    
26.   # Split words by all non-alpha characters
    
27.   words=re.compile(r'[^A-Z^a-z]+').split(txt)
    
28. 
    
29.   # Convert to lowercase
    
30.   return [word.lower() for word in words if word!='']
    
31. 
    
32. 
    
33. apcount={}
    
34. wordcounts={}
    
35. feedlist=[line for line in file('feedlist.txt')]
    
36. for feedurl in feedlist:
    
37.   try:
    
38.     title,wc=getwordcounts(feedurl)
    
39.     wordcounts[title]=wc
    
40.     for word,count in wc.items():
    
41.       apcount.setdefault(word,0)
    
42.       if count>1:
    
43.         apcount[word]+=1
    
44.   except:
    
45.     print 'Failed to parse feed %s' % feedurl
    
46. 
    
47. wordlist=[]
    
48. for w,bc in apcount.items():
    
49.   frac=float(bc)/len(feedlist)
    
50.   if frac>0.1 and frac<0.5:
    
51.     wordlist.append(w)
    
52. 
    
53. out=file('blogdata1.txt','w')
    
54. out.write('Blog')
    
55. for word in wordlist: out.write('\t%s' % word)
    
56. out.write('\n')
    
57. for blog,wc in wordcounts.items():
    
58.   print blog
    
59.   out.write(blog)
    
60.   for word in wordlist:
    
61.     if word in wc: out.write('\t%d' % wc[word])
    
62.     else: out.write('\t0')
    
63.   out.write('\n')

复制代码

1. from BeautifulSoup import BeautifulSoup
   
2. import urllib2
   
3. import re
   
4. chare=re.compile(r'[!-\.&]')
   
5. itemowners={}
   
6. 
   
7. # Words to remove
   
8. dropwords=['a','new','some','more','my','own','the','many','other','another']
   
9. 
   
10. currentuser=0
    
11. for i in range(1,51):
    
12.   # URL for the want search page
    
13.   c=urllib2.urlopen(
    
14.   'http://member.zebo.com/Main?event_key=USERSEARCH&wiowiw=wiw&keyword=car&page=%d'
    
15.   % (i))
    
16.   soup=BeautifulSoup(c.read())
    
17.   for td in soup('td'):
    
18.     # Find table cells of bgverdanasmall class
    
19.     if ('class' in dict(td.attrs) and td['class']=='bgverdanasmall'):
    
20.       items=[re.sub(chare,'',str(a.contents[0]).lower()).strip() for a in td('a')]
    
21.       for item in items:
    
22.         # Remove extra words
    
23.         txt=' '.join([t for t in item.split(' ') if t not in dropwords])
    
24.         if len(txt)<2: continue
    
25.         itemowners.setdefault(txt,{})
    
26.         itemowners[txt][currentuser]=1
    
27.       currentuser+=1
    
28.       
    
29. out=file('zebo.txt','w')
    
30. out.write('Item')
    
31. for user in range(0,currentuser): out.write('\tU%d' % user)
    
32. out.write('\n')
    
33. for item,owners in itemowners.items():
    
34.   if len(owners)>10:
    
35.     out.write(item)
    
36.     for user in range(0,currentuser):
    
37.       if user in owners: out.write('\t1')
    
38.       else: out.write('\t0')
    
39.     out.write('\n')

复制代码

1. from PIL import Image,ImageDraw
   
2. 
   
3. def readfile(filename):
   
4.   lines=[line for line in file(filename)]
   
5.   
   
6.   # First line is the column titles
   
7.   colnames=lines[0].strip().split('\t')[1:]
   
8.   rownames=[]
   
9.   data=[]
   
10.   for line in lines[1:]:
    
11.     p=line.strip().split('\t')
    
12.     # First column in each row is the rowname
    
13.     rownames.append(p[0])
    
14.     # The data for this row is the remainder of the row
    
15.     data.append([float(x) for x in p[1:]])
    
16.   return rownames,colnames,data
    
17. 
    
18. 
    
19. from math import sqrt
    
20. 
    
21. def pearson(v1,v2):
    
22.   # Simple sums
    
23.   sum1=sum(v1)
    
24.   sum2=sum(v2)
    
25.   
    
26.   # Sums of the squares
    
27.   sum1Sq=sum([pow(v,2) for v in v1])
    
28.   sum2Sq=sum([pow(v,2) for v in v2])        
    
29.   
    
30.   # Sum of the products
    
31.   pSum=sum([v1[i]*v2[i] for i in range(len(v1))])
    
32.   
    
33.   # Calculate r (Pearson score)
    
34.   num=pSum-(sum1*sum2/len(v1))
    
35.   den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))
    
36.   if den==0: return 0
    
37. 
    
38.   return 1.0-num/den
    
39. 
    
40. class bicluster:
    
41.   def __init__(self,vec,left=None,right=None,distance=0.0,id=None):
    
42.     self.left=left
    
43.     self.right=right
    
44.     self.vec=vec
    
45.     self.id=id
    
46.     self.distance=distance
    
47. 
    
48. def hcluster(rows,distance=pearson):
    
49.   distances={}
    
50.   currentclustid=-1
    
51. 
    
52.   # Clusters are initially just the rows
    
53.   clust=[bicluster(rows[i],id=i) for i in range(len(rows))]
    
54. 
    
55.   while len(clust)>1:
    
56.     lowestpair=(0,1)
    
57.     closest=distance(clust[0].vec,clust[1].vec)
    
58. 
    
59.     # loop through every pair looking for the smallest distance
    
60.     for i in range(len(clust)):
    
61.       for j in range(i+1,len(clust)):
    
62.         # distances is the cache of distance calculations
    
63.         if (clust[i].id,clust[j].id) not in distances:
    
64.           distances[(clust[i].id,clust[j].id)]=distance(clust[i].vec,clust[j].vec)
    
65. 
    
66.         d=distances[(clust[i].id,clust[j].id)]
    
67. 
    
68.         if d<closest:
    
69.           closest=d
    
70.           lowestpair=(i,j)
    
71. 
    
72.     # calculate the average of the two clusters
    
73.     mergevec=[
    
74.     (clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0
    
75.     for i in range(len(clust[0].vec))]
    
76. 
    
77.     # create the new cluster
    
78.     newcluster=bicluster(mergevec,left=clust[lowestpair[0]],
    
79.                          right=clust[lowestpair[1]],
    
80.                          distance=closest,id=currentclustid)
    
81. 
    
82.     # cluster ids that weren't in the original set are negative
    
83.     currentclustid-=1
    
84.     del clust[lowestpair[1]]
    
85.     del clust[lowestpair[0]]
    
86.     clust.append(newcluster)
    
87. 
    
88.   return clust[0]
    
89. 
    
90. def printclust(clust,labels=None,n=0):
    
91.   # indent to make a hierarchy layout
    
92.   for i in range(n): print ' ',
    
93.   if clust.id<0:
    
94.     # negative id means that this is branch
    
95.     print '-'
    
96.   else:
    
97.     # positive id means that this is an endpoint
    
98.     if labels==None: print clust.id
    
99.     else: print labels[clust.id]
    
100. 
     
101.   # now print the right and left branches
     
102.   if clust.left!=None: printclust(clust.left,labels=labels,n=n+1)
     
103.   if clust.right!=None: printclust(clust.right,labels=labels,n=n+1)
     
104. 
     
105. def getheight(clust):
     
106.   # Is this an endpoint? Then the height is just 1
     
107.   if clust.left==None and clust.right==None: return 1
     
108. 
     
109.   # Otherwise the height is the same of the heights of
     
110.   # each branch
     
111.   return getheight(clust.left)+getheight(clust.right)
     
112. 
     
113. def getdepth(clust):
     
114.   # The distance of an endpoint is 0.0
     
115.   if clust.left==None and clust.right==None: return 0
     
116. 
     
117.   # The distance of a branch is the greater of its two sides
     
118.   # plus its own distance
     
119.   return max(getdepth(clust.left),getdepth(clust.right))+clust.distance
     
120. 
     
121. 
     
122. def drawdendrogram(clust,labels,jpeg='clusters.jpg'):
     
123.   # height and width
     
124.   h=getheight(clust)*20
     
125.   w=1200
     
126.   depth=getdepth(clust)
     
127. 
     
128.   # width is fixed, so scale distances accordingly
     
129.   scaling=float(w-150)/depth
     
130. 
     
131.   # Create a new image with a white background
     
132.   img=Image.new('RGB',(w,h),(255,255,255))
     
133.   draw=ImageDraw.Draw(img)
     
134. 
     
135.   draw.line((0,h/2,10,h/2),fill=(255,0,0))   
     
136. 
     
137.   # Draw the first node
     
138.   drawnode(draw,clust,10,(h/2),scaling,labels)
     
139.   img.save(jpeg,'JPEG')
     
140. 
     
141. def drawnode(draw,clust,x,y,scaling,labels):
     
142.   if clust.id<0:
     
143.     h1=getheight(clust.left)*20
     
144.     h2=getheight(clust.right)*20
     
145.     top=y-(h1+h2)/2
     
146.     bottom=y+(h1+h2)/2
     
147.     # Line length
     
148.     ll=clust.distance*scaling
     
149.     # Vertical line from this cluster to children   
     
150.     draw.line((x,top+h1/2,x,bottom-h2/2),fill=(255,0,0))   
     
151.    
     
152.     # Horizontal line to left item
     
153.     draw.line((x,top+h1/2,x+ll,top+h1/2),fill=(255,0,0))   
     
154. 
     
155.     # Horizontal line to right item
     
156.     draw.line((x,bottom-h2/2,x+ll,bottom-h2/2),fill=(255,0,0))        
     
157. 
     
158.     # Call the function to draw the left and right nodes   
     
159.     drawnode(draw,clust.left,x+ll,top+h1/2,scaling,labels)
     
160.     drawnode(draw,clust.right,x+ll,bottom-h2/2,scaling,labels)
     
161.   else:   
     
162.     # If this is an endpoint, draw the item label
     
163.     draw.text((x+5,y-7),labels[clust.id],(0,0,0))
     
164. 
     
165. def rotatematrix(data):
     
166.   newdata=[]
     
167.   for i in range(len(data[0])):
     
168.     newrow=[data[j][i] for j in range(len(data))]
     
169.     newdata.append(newrow)
     
170.   return newdata
     
171. 
     
172. import random
     
173. 
     
174. def kcluster(rows,distance=pearson,k=4):
     
175.   # Determine the minimum and maximum values for each point
     
176.   ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows]))
     
177.   for i in range(len(rows[0]))]
     
178. 
     
179.   # Create k randomly placed centroids
     
180.   clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0]
     
181.   for i in range(len(rows[0]))] for j in range(k)]
     
182.   
     
183.   lastmatches=None
     
184.   for t in range(100):
     
185.     print 'Iteration %d' % t
     
186.     bestmatches=[[] for i in range(k)]
     
187.    
     
188.     # Find which centroid is the closest for each row
     
189.     for j in range(len(rows)):
     
190.       row=rows[j]
     
191.       bestmatch=0
     
192.       for i in range(k):
     
193.         d=distance(clusters[i],row)
     
194.         if d<distance(clusters[bestmatch],row): bestmatch=i
     
195.       bestmatches[bestmatch].append(j)
     
196. 
     
197.     # If the results are the same as last time, this is complete
     
198.     if bestmatches==lastmatches: break
     
199.     lastmatches=bestmatches
     
200.    
     
201.     # Move the centroids to the average of their members
     
202.     for i in range(k):
     
203.       avgs=[0.0]*len(rows[0])
     
204.       if len(bestmatches[i])>0:
     
205.         for rowid in bestmatches[i]:
     
206.           for m in range(len(rows[rowid])):
     
207.             avgs[m]+=rows[rowid][m]
     
208.         for j in range(len(avgs)):
     
209.           avgs[j]/=len(bestmatches[i])
     
210.         clusters[i]=avgs
     
211.       
     
212.   return bestmatches
     
213. 
     
214. def tanamoto(v1,v2):
     
215.   c1,c2,shr=0,0,0
     
216.   
     
217.   for i in range(len(v1)):
     
218.     if v1[i]!=0: c1+=1 # in v1
     
219.     if v2[i]!=0: c2+=1 # in v2
     
220.     if v1[i]!=0 and v2[i]!=0: shr+=1 # in both
     
221.   
     
222.   return 1.0-(float(shr)/(c1+c2-shr))
     
223. 
     
224. def scaledown(data,distance=pearson,rate=0.01):
     
225.   n=len(data)
     
226. 
     
227.   # The real distances between every pair of items
     
228.   realdist=[[distance(data[i],data[j]) for j in range(n)]
     
229.              for i in range(0,n)]
     
230. 
     
231.   # Randomly initialize the starting points of the locations in 2D
     
232.   loc=[[random.random(),random.random()] for i in range(n)]
     
233.   fakedist=[[0.0 for j in range(n)] for i in range(n)]
     
234.   
     
235.   lasterror=None
     
236.   for m in range(0,1000):
     
237.     # Find projected distances
     
238.     for i in range(n):
     
239.       for j in range(n):
     
240.         fakedist[i][j]=sqrt(sum([pow(loc[i][x]-loc[j][x],2)
     
241.                                  for x in range(len(loc[i]))]))
     
242.   
     
243.     # Move points
     
244.     grad=[[0.0,0.0] for i in range(n)]
     
245.    
     
246.     totalerror=0
     
247.     for k in range(n):
     
248.       for j in range(n):
     
249.         if j==k: continue
     
250.         # The error is percent difference between the distances
     
251.         errorterm=(fakedist[j][k]-realdist[j][k])/realdist[j][k]
     
252.         
     
253.         # Each point needs to be moved away from or towards the other
     
254.         # point in proportion to how much error it has
     
255.         grad[k][0]+=((loc[k][0]-loc[j][0])/fakedist[j][k])*errorterm
     
256.         grad[k][1]+=((loc[k][1]-loc[j][1])/fakedist[j][k])*errorterm
     
257. 
     
258.         # Keep track of the total error
     
259.         totalerror+=abs(errorterm)
     
260.     print totalerror
     
261. 
     
262.     # If the answer got worse by moving the points, we are done
     
263.     if lasterror and lasterror<totalerror: break
     
264.     lasterror=totalerror
     
265.    
     
266.     # Move each of the points by the learning rate times the gradient
     
267.     for k in range(n):
     
268.       loc[k][0]-=rate*grad[k][0]
     
269.       loc[k][1]-=rate*grad[k][1]
     
270. 
     
271.   return loc
     
272. 
     
273. def draw2d(data,labels,jpeg='mds2d.jpg'):
     
274.   img=Image.new('RGB',(2000,2000),(255,255,255))
     
275.   draw=ImageDraw.Draw(img)
     
276.   for i in range(len(data)):
     
277.     x=(data[i][0]+0.5)*1000
     
278.     y=(data[i][1]+0.5)*1000
     
279.     draw.text((x,y),labels[i],(0,0,0))
     
280.   img.save(jpeg,'JPEG')  

复制代码

1. import urllib2
   
2. from BeautifulSoup import *
   
3. from urlparse import urljoin
   
4. from pysqlite2 import dbapi2 as sqlite
   
5. import nn
   
6. mynet=nn.searchnet('nn.db')
   
7. 
   
8. # Create a list of words to ignore
   
9. ignorewords={'the':1,'of':1,'to':1,'and':1,'a':1,'in':1,'is':1,'it':1}
   
10. 
    
11. 
    
12. class crawler:
    
13.   # Initialize the crawler with the name of database
    
14.   def __init__(self,dbname):
    
15.     self.con=sqlite.connect(dbname)
    
16.   
    
17.   def __del__(self):
    
18.     self.con.close()
    
19. 
    
20.   def dbcommit(self):
    
21.     self.con.commit()
    
22. 
    
23.   # Auxilliary function for getting an entry id and adding
    
24.   # it if it's not present
    
25.   def getentryid(self,table,field,value,createnew=True):
    
26.     cur=self.con.execute(
    
27.     "select rowid from %s where %s='%s'" % (table,field,value))
    
28.     res=cur.fetchone()
    
29.     if res==None:
    
30.       cur=self.con.execute(
    
31.       "insert into %s (%s) values ('%s')" % (table,field,value))
    
32.       return cur.lastrowid
    
33.     else:
    
34.       return res[0]
    
35. 
    
36. 
    
37.   # Index an individual page
    
38.   def addtoindex(self,url,soup):
    
39.     if self.isindexed(url): return
    
40.     print 'Indexing '+url
    
41.   
    
42.     # Get the individual words
    
43.     text=self.gettextonly(soup)
    
44.     words=self.separatewords(text)
    
45.    
    
46.     # Get the URL id
    
47.     urlid=self.getentryid('urllist','url',url)
    
48.    
    
49.     # Link each word to this url
    
50.     for i in range(len(words)):
    
51.       word=words[i]
    
52.       if word in ignorewords: continue
    
53.       wordid=self.getentryid('wordlist','word',word)
    
54.       self.con.execute("insert into wordlocation(urlid,wordid,location) values (%d,%d,%d)" % (urlid,wordid,i))
    
55.   
    
56. 
    
57.   
    
58.   # Extract the text from an HTML page (no tags)
    
59.   def gettextonly(self,soup):
    
60.     v=soup.string
    
61.     if v==Null:   
    
62.       c=soup.contents
    
63.       resulttext=''
    
64.       for t in c:
    
65.         subtext=self.gettextonly(t)
    
66.         resulttext+=subtext+'\n'
    
67.       return resulttext
    
68.     else:
    
69.       return v.strip()
    
70. 
    
71.   # Seperate the words by any non-whitespace character
    
72.   def separatewords(self,text):
    
73.     splitter=re.compile('\\W*')
    
74.     return [s.lower() for s in splitter.split(text) if s!='']
    
75. 
    
76.    
    
77.   # Return true if this url is already indexed
    
78.   def isindexed(self,url):
    
79.     return False
    
80.   
    
81.   # Add a link between two pages
    
82.   def addlinkref(self,urlFrom,urlTo,linkText):
    
83.     words=self.separateWords(linkText)
    
84.     fromid=self.getentryid('urllist','url',urlFrom)
    
85.     toid=self.getentryid('urllist','url',urlTo)
    
86.     if fromid==toid: return
    
87.     cur=self.con.execute("insert into link(fromid,toid) values (%d,%d)" % (fromid,toid))
    
88.     linkid=cur.lastrowid
    
89.     for word in words:
    
90.       if word in ignorewords: continue
    
91.       wordid=self.getentryid('wordlist','word',word)
    
92.       self.con.execute("insert into linkwords(linkid,wordid) values (%d,%d)" % (linkid,wordid))
    
93. 
    
94.   # Starting with a list of pages, do a breadth
    
95.   # first search to the given depth, indexing pages
    
96.   # as we go
    
97.   def crawl(self,pages,depth=2):
    
98.     for i in range(depth):
    
99.       newpages={}
    
100.       for page in pages:
     
101.         try:
     
102.           c=urllib2.urlopen(page)
     
103.         except:
     
104.           print "Could not open %s" % page
     
105.           continue
     
106.         try:
     
107.           soup=BeautifulSoup(c.read())
     
108.           self.addtoindex(page,soup)
     
109.   
     
110.           links=soup('a')
     
111.           for link in links:
     
112.             if ('href' in dict(link.attrs)):
     
113.               url=urljoin(page,link['href'])
     
114.               if url.find("'")!=-1: continue
     
115.               url=url.split('#')[0]  # remove location portion
     
116.               if url[0:4]=='http' and not self.isindexed(url):
     
117.                 newpages[url]=1
     
118.               linkText=self.gettextonly(link)
     
119.               self.addlinkref(page,url,linkText)
     
120.   
     
121.           self.dbcommit()
     
122.         except:
     
123.           print "Could not parse page %s" % page
     
124. 
     
125.       pages=newpages
     
126. 
     
127.   
     
128.   # Create the database tables
     
129.   def createindextables(self):
     
130.     self.con.execute('create table urllist(url)')
     
131.     self.con.execute('create table wordlist(word)')
     
132.     self.con.execute('create table wordlocation(urlid,wordid,location)')
     
133.     self.con.execute('create table link(fromid integer,toid integer)')
     
134.     self.con.execute('create table linkwords(wordid,linkid)')
     
135.     self.con.execute('create index wordidx on wordlist(word)')
     
136.     self.con.execute('create index urlidx on urllist(url)')
     
137.     self.con.execute('create index wordurlidx on wordlocation(wordid)')
     
138.     self.con.execute('create index urltoidx on link(toid)')
     
139.     self.con.execute('create index urlfromidx on link(fromid)')
     
140.     self.dbcommit()
     
141. 
     
142.   def calculatepagerank(self,iterations=20):
     
143.     # clear out the current page rank tables
     
144.     self.con.execute('drop table if exists pagerank')
     
145.     self.con.execute('create table pagerank(urlid primary key,score)')
     
146.    
     
147.     # initialize every url with a page rank of 1
     
148.     for (urlid,) in self.con.execute('select rowid from urllist'):
     
149.       self.con.execute('insert into pagerank(urlid,score) values (%d,1.0)' % urlid)
     
150.     self.dbcommit()
     
151.    
     
152.     for i in range(iterations):
     
153.       print "Iteration %d" % (i)
     
154.       for (urlid,) in self.con.execute('select rowid from urllist'):
     
155.         pr=0.15
     
156.         
     
157.         # Loop through all the pages that link to this one
     
158.         for (linker,) in self.con.execute(
     
159.         'select distinct fromid from link where toid=%d' % urlid):
     
160.           # Get the page rank of the linker
     
161.           linkingpr=self.con.execute(
     
162.           'select score from pagerank where urlid=%d' % linker).fetchone()[0]
     
163. 
     
164.           # Get the total number of links from the linker
     
165.           linkingcount=self.con.execute(
     
166.           'select count(*) from link where fromid=%d' % linker).fetchone()[0]
     
167.           pr+=0.85*(linkingpr/linkingcount)
     
168.         self.con.execute(
     
169.         'update pagerank set score=%f where urlid=%d' % (pr,urlid))
     
170.       self.dbcommit()
     
171. 
     
172. class searcher:
     
173.   def __init__(self,dbname):
     
174.     self.con=sqlite.connect(dbname)
     
175. 
     
176.   def __del__(self):
     
177.     self.con.close()
     
178. 
     
179.   def getmatchrows(self,q):
     
180.     # Strings to build the query
     
181.     fieldlist='w0.urlid'
     
182.     tablelist=''  
     
183.     clauselist=''
     
184.     wordids=[]
     
185. 
     
186.     # Split the words by spaces
     
187.     words=q.split(' ')  
     
188.     tablenumber=0
     
189. 
     
190.     for word in words:
     
191.       # Get the word ID
     
192.       wordrow=self.con.execute(
     
193.       "select rowid from wordlist where word='%s'" % word).fetchone()
     
194.       if wordrow!=None:
     
195.         wordid=wordrow[0]
     
196.         wordids.append(wordid)
     
197.         if tablenumber>0:
     
198.           tablelist+=','
     
199.           clauselist+=' and '
     
200.           clauselist+='w%d.urlid=w%d.urlid and ' % (tablenumber-1,tablenumber)
     
201.         fieldlist+=',w%d.location' % tablenumber
     
202.         tablelist+='wordlocation w%d' % tablenumber      
     
203.         clauselist+='w%d.wordid=%d' % (tablenumber,wordid)
     
204.         tablenumber+=1
     
205. 
     
206.     # Create the query from the separate parts
     
207.     fullquery='select %s from %s where %s' % (fieldlist,tablelist,clauselist)
     
208.     print fullquery
     
209.     cur=self.con.execute(fullquery)
     
210.     rows=[row for row in cur]
     
211. 
     
212.     return rows,wordids
     
213. 
     
214.   def getscoredlist(self,rows,wordids):
     
215.     totalscores=dict([(row[0],0) for row in rows])
     
216. 
     
217.     # This is where we'll put our scoring functions
     
218.     weights=[(1.0,self.locationscore(rows)),
     
219.              (1.0,self.frequencyscore(rows)),
     
220.              (1.0,self.pagerankscore(rows)),
     
221.              (1.0,self.linktextscore(rows,wordids)),
     
222.              (5.0,self.nnscore(rows,wordids))]
     
223.     for (weight,scores) in weights:
     
224.       for url in totalscores:
     
225.         totalscores[url]+=weight*scores[url]
     
226. 
     
227.     return totalscores
     
228. 
     
229.   def geturlname(self,id):
     
230.     return self.con.execute(
     
231.     "select url from urllist where rowid=%d" % id).fetchone()[0]
     
232. 
     
233.   def query(self,q):
     
234.     rows,wordids=self.getmatchrows(q)
     
235.     scores=self.getscoredlist(rows,wordids)
     
236.     rankedscores=[(score,url) for (url,score) in scores.items()]
     
237.     rankedscores.sort()
     
238.     rankedscores.reverse()
     
239.     for (score,urlid) in rankedscores[0:10]:
     
240.       print '%f\t%s' % (score,self.geturlname(urlid))
     
241.     return wordids,[r[1] for r in rankedscores[0:10]]
     
242. 
     
243.   def normalizescores(self,scores,smallIsBetter=0):
     
244.     vsmall=0.00001 # Avoid division by zero errors
     
245.     if smallIsBetter:
     
246.       minscore=min(scores.values())
     
247.       return dict([(u,float(minscore)/max(vsmall,l)) for (u,l) in scores.items()])
     
248.     else:
     
249.       maxscore=max(scores.values())
     
250.       if maxscore==0: maxscore=vsmall
     
251.       return dict([(u,float(c)/maxscore) for (u,c) in scores.items()])
     
252. 
     
253.   def frequencyscore(self,rows):
     
254.     counts=dict([(row[0],0) for row in rows])
     
255.     for row in rows: counts[row[0]]+=1
     
256.     return self.normalizescores(counts)
     
257. 
     
258.   def locationscore(self,rows):
     
259.     locations=dict([(row[0],1000000) for row in rows])
     
260.     for row in rows:
     
261.       loc=sum(row[1:])
     
262.       if loc<locations[row[0]]: locations[row[0]]=loc
     
263.    
     
264.     return self.normalizescores(locations,smallIsBetter=1)
     
265. 
     
266.   def distancescore(self,rows):
     
267.     # If there's only one word, everyone wins!
     
268.     if len(rows[0])<=2: return dict([(row[0],1.0) for row in rows])
     
269. 
     
270.     # Initialize the dictionary with large values
     
271.     mindistance=dict([(row[0],1000000) for row in rows])
     
272. 
     
273.     for row in rows:
     
274.       dist=sum([abs(row[i]-row[i-1]) for i in range(2,len(row))])
     
275.       if dist<mindistance[row[0]]: mindistance[row[0]]=dist
     
276.     return self.normalizescores(mindistance,smallIsBetter=1)
     
277. 
     
278.   def inboundlinkscore(self,rows):
     
279.     uniqueurls=dict([(row[0],1) for row in rows])
     
280.     inboundcount=dict([(u,self.con.execute('select count(*) from link where toid=%d' % u).fetchone()[0]) for u in uniqueurls])   
     
281.     return self.normalizescores(inboundcount)
     
282. 
     
283.   def linktextscore(self,rows,wordids):
     
284.     linkscores=dict([(row[0],0) for row in rows])
     
285.     for wordid in wordids:
     
286.       cur=self.con.execute('select link.fromid,link.toid from linkwords,link where wordid=%d and linkwords.linkid=link.rowid' % wordid)
     
287.       for (fromid,toid) in cur:
     
288.         if toid in linkscores:
     
289.           pr=self.con.execute('select score from pagerank where urlid=%d' % fromid).fetchone()[0]
     
290.           linkscores[toid]+=pr
     
291.     maxscore=max(linkscores.values())
     
292.     normalizedscores=dict([(u,float(l)/maxscore) for (u,l) in linkscores.items()])
     
293.     return normalizedscores
     
294. 
     
295.   def pagerankscore(self,rows):
     
296.     pageranks=dict([(row[0],self.con.execute('select score from pagerank where urlid=%d' % row[0]).fetchone()[0]) for row in rows])
     
297.     maxrank=max(pageranks.values())
     
298.     normalizedscores=dict([(u,float(l)/maxrank) for (u,l) in pageranks.items()])
     
299.     return normalizedscores
     
300. 
     
301.   def nnscore(self,rows,wordids):
     
302.     # Get unique URL IDs as an ordered list
     
303.     urlids=[urlid for urlid in dict([(row[0],1) for row in rows])]
     
304.     nnres=mynet.getresult(wordids,urlids)
     
305.     scores=dict([(urlids[i],nnres[i]) for i in range(len(urlids))])
     
306.     return self.normalizescores(scores)

复制代码

1. from math import tanh
   
2. from pysqlite2 import dbapi2 as sqlite
   
3. 
   
4. def dtanh(y):
   
5.     return 1.0-y*y
   
6. 
   
7. class searchnet:
   
8.     def __init__(self,dbname):
   
9.       self.con=sqlite.connect(dbname)
   
10.   
    
11.     def __del__(self):
    
12.       self.con.close()
    
13. 
    
14.     def maketables(self):
    
15.       self.con.execute('create table hiddennode(create_key)')
    
16.       self.con.execute('create table wordhidden(fromid,toid,strength)')
    
17.       self.con.execute('create table hiddenurl(fromid,toid,strength)')
    
18.       self.con.commit()
    
19. 
    
20.     def getstrength(self,fromid,toid,layer):
    
21.       if layer==0: table='wordhidden'
    
22.       else: table='hiddenurl'
    
23.       res=self.con.execute('select strength from %s where fromid=%d and toid=%d' % (table,fromid,toid)).fetchone()
    
24.       if res==None:
    
25.           if layer==0: return -0.2
    
26.           if layer==1: return 0
    
27.       return res[0]
    
28. 
    
29.     def setstrength(self,fromid,toid,layer,strength):
    
30.       if layer==0: table='wordhidden'
    
31.       else: table='hiddenurl'
    
32.       res=self.con.execute('select rowid from %s where fromid=%d and toid=%d' % (table,fromid,toid)).fetchone()
    
33.       if res==None:
    
34.         self.con.execute('insert into %s (fromid,toid,strength) values (%d,%d,%f)' % (table,fromid,toid,strength))
    
35.       else:
    
36.         rowid=res[0]
    
37.         self.con.execute('update %s set strength=%f where rowid=%d' % (table,strength,rowid))
    
38. 
    
39.     def generatehiddennode(self,wordids,urls):
    
40.       if len(wordids)>3: return None
    
41.       # Check if we already created a node for this set of words
    
42.       sorted_words=[str(id) for id in wordids]
    
43.       sorted_words.sort()
    
44.       createkey='_'.join(sorted_words)
    
45.       res=self.con.execute(
    
46.       "select rowid from hiddennode where create_key='%s'" % createkey).fetchone()
    
47. 
    
48.       # If not, create it
    
49.       if res==None:
    
50.         cur=self.con.execute(
    
51.         "insert into hiddennode (create_key) values ('%s')" % createkey)
    
52.         hiddenid=cur.lastrowid
    
53.         # Put in some default weights
    
54.         for wordid in wordids:
    
55.           self.setstrength(wordid,hiddenid,0,1.0/len(wordids))
    
56.         for urlid in urls:
    
57.           self.setstrength(hiddenid,urlid,1,0.1)
    
58.         self.con.commit()
    
59. 
    
60.     def getallhiddenids(self,wordids,urlids):
    
61.       l1={}
    
62.       for wordid in wordids:
    
63.         cur=self.con.execute(
    
64.         'select toid from wordhidden where fromid=%d' % wordid)
    
65.         for row in cur: l1[row[0]]=1
    
66.       for urlid in urlids:
    
67.         cur=self.con.execute(
    
68.         'select fromid from hiddenurl where toid=%d' % urlid)
    
69.         for row in cur: l1[row[0]]=1
    
70.       return l1.keys()
    
71. 
    
72.     def setupnetwork(self,wordids,urlids):
    
73.         # value lists
    
74.         self.wordids=wordids
    
75.         self.hiddenids=self.getallhiddenids(wordids,urlids)
    
76.         self.urlids=urlids
    
77. 
    
78.         # node outputs
    
79.         self.ai = [1.0]*len(self.wordids)
    
80.         self.ah = [1.0]*len(self.hiddenids)
    
81.         self.ao = [1.0]*len(self.urlids)
    
82.         
    
83.         # create weights matrix
    
84.         self.wi = [[self.getstrength(wordid,hiddenid,0)
    
85.                     for hiddenid in self.hiddenids]
    
86.                    for wordid in self.wordids]
    
87.         self.wo = [[self.getstrength(hiddenid,urlid,1)
    
88.                     for urlid in self.urlids]
    
89.                    for hiddenid in self.hiddenids]
    
90. 
    
91.     def feedforward(self):
    
92.         # the only inputs are the query words
    
93.         for i in range(len(self.wordids)):
    
94.             self.ai[i] = 1.0
    
95. 
    
96.         # hidden activations
    
97.         for j in range(len(self.hiddenids)):
    
98.             sum = 0.0
    
99.             for i in range(len(self.wordids)):
    
100.                 sum = sum + self.ai[i] * self.wi[i][j]
     
101.             self.ah[j] = tanh(sum)
     
102. 
     
103.         # output activations
     
104.         for k in range(len(self.urlids)):
     
105.             sum = 0.0
     
106.             for j in range(len(self.hiddenids)):
     
107.                 sum = sum + self.ah[j] * self.wo[j][k]
     
108.             self.ao[k] = tanh(sum)
     
109. 
     
110.         return self.ao[:]
     
111. 
     
112.     def getresult(self,wordids,urlids):
     
113.       self.setupnetwork(wordids,urlids)
     
114.       return self.feedforward()
     
115. 
     
116.     def backPropagate(self, targets, N=0.5):
     
117.         # calculate errors for output
     
118.         output_deltas = [0.0] * len(self.urlids)
     
119.         for k in range(len(self.urlids)):
     
120.             error = targets[k]-self.ao[k]
     
121.             output_deltas[k] = dtanh(self.ao[k]) * error
     
122. 
     
123.         # calculate errors for hidden layer
     
124.         hidden_deltas = [0.0] * len(self.hiddenids)
     
125.         for j in range(len(self.hiddenids)):
     
126.             error = 0.0
     
127.             for k in range(len(self.urlids)):
     
128.                 error = error + output_deltas[k]*self.wo[j][k]
     
129.             hidden_deltas[j] = dtanh(self.ah[j]) * error
     
130. 
     
131.         # update output weights
     
132.         for j in range(len(self.hiddenids)):
     
133.             for k in range(len(self.urlids)):
     
134.                 change = output_deltas[k]*self.ah[j]
     
135.                 self.wo[j][k] = self.wo[j][k] + N*change
     
136. 
     
137.         # update input weights
     
138.         for i in range(len(self.wordids)):
     
139.             for j in range(len(self.hiddenids)):
     
140.                 change = hidden_deltas[j]*self.ai[i]
     
141.                 self.wi[i][j] = self.wi[i][j] + N*change
     
142. 
     
143.     def trainquery(self,wordids,urlids,selectedurl):
     
144.       # generate a hidden node if necessary
     
145.       self.generatehiddennode(wordids,urlids)
     
146. 
     
147.       self.setupnetwork(wordids,urlids)      
     
148.       self.feedforward()
     
149.       targets=[0.0]*len(urlids)
     
150.       targets[urlids.index(selectedurl)]=1.0
     
151.       error = self.backPropagate(targets)
     
152.       self.updatedatabase()
     
153. 
     
154.     def updatedatabase(self):
     
155.       # set them to database values
     
156.       for i in range(len(self.wordids)):
     
157.           for j in range(len(self.hiddenids)):
     
158.               self.setstrength(self.wordids[i],self. hiddenids[j],0,self.wi[i][j])
     
159.       for j in range(len(self.hiddenids)):
     
160.           for k in range(len(self.urlids)):
     
161.               self.setstrength(self.hiddenids[j],self.urlids[k],1,self.wo[j][k])
     
162.       self.con.commit()

复制代码

1. import math
   
2. 
   
3. people=['Charlie','Augustus','Veruca','Violet','Mike','Joe','Willy','Miranda']
   
4. 
   
5. links=[('Augustus', 'Willy'),
   
6.        ('Mike', 'Joe'),
   
7.        ('Miranda', 'Mike'),
   
8.        ('Violet', 'Augustus'),
   
9.        ('Miranda', 'Willy'),
   
10.        ('Charlie', 'Mike'),
    
11.        ('Veruca', 'Joe'),
    
12.        ('Miranda', 'Augustus'),
    
13.        ('Willy', 'Augustus'),
    
14.        ('Joe', 'Charlie'),
    
15.        ('Veruca', 'Augustus'),
    
16.        ('Miranda', 'Joe')]
    
17. 
    
18. 
    
19. def crosscount(v):
    
20.   # Convert the number list into a dictionary of person:(x,y)
    
21.   loc=dict([(people[i],(v[i*2],v[i*2+1])) for i in range(0,len(people))])
    
22.   total=0
    
23.   
    
24.   # Loop through every pair of links
    
25.   for i in range(len(links)):
    
26.     for j in range(i+1,len(links)):
    
27. 
    
28.       # Get the locations
    
29.       (x1,y1),(x2,y2)=loc[links[i][0]],loc[links[i][1]]
    
30.       (x3,y3),(x4,y4)=loc[links[j][0]],loc[links[j][1]]
    
31.       
    
32.       den=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)
    
33. 
    
34.       # den==0 if the lines are parallel
    
35.       if den==0: continue
    
36. 
    
37.       # Otherwise ua and ub are the fraction of the
    
38.       # line where they cross
    
39.       ua=((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/den
    
40.       ub=((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/den
    
41.       
    
42.       # If the fraction is between 0 and 1 for both lines
    
43.       # then they cross each other
    
44.       if ua>0 and ua<1 and ub>0 and ub<1:
    
45.         total+=1
    
46.     for i in range(len(people)):
    
47.       for j in range(i+1,len(people)):
    
48.         # Get the locations of the two nodes
    
49.         (x1,y1),(x2,y2)=loc[people[i]],loc[people[j]]
    
50. 
    
51.         # Find the distance between them
    
52.         dist=math.sqrt(math.pow(x1-x2,2)+math.pow(y1-y2,2))
    
53.         # Penalize any nodes closer than 50 pixels
    
54.         if dist<50:
    
55.           total+=(1.0-(dist/50.0))
    
56.         
    
57.   return total
    
58. from PIL import Image,ImageDraw
    
59. 
    
60. def drawnetwork(sol):
    
61.   # Create the image
    
62.   img=Image.new('RGB',(400,400),(255,255,255))
    
63.   draw=ImageDraw.Draw(img)
    
64. 
    
65.   # Create the position dict
    
66.   pos=dict([(people[i],(sol[i*2],sol[i*2+1])) for i in range(0,len(people))])
    
67. 
    
68.   for (a,b) in links:
    
69.     draw.line((pos[a],pos[b]),fill=(255,0,0))
    
70. 
    
71.   for n,p in pos.items():
    
72.     draw.text(p,n,(0,0,0))
    
73. 
    
74.   img.show()
    
75. 
    
76. 
    
77. domain=[(10,370)]*(len(people)*2)

复制代码

1. import time
   
2. import random
   
3. import math
   
4. 
   
5. people = [('Seymour','BOS'),
   
6.           ('Franny','DAL'),
   
7.           ('Zooey','CAK'),
   
8.           ('Walt','MIA'),
   
9.           ('Buddy','ORD'),
   
10.           ('Les','OMA')]
    
11. # Laguardia
    
12. destination='LGA'
    
13. 
    
14. flights={}
    
15. #
    
16. for line in file('schedule.txt'):
    
17.   origin,dest,depart,arrive,price=line.strip().split(',')
    
18.   flights.setdefault((origin,dest),[])
    
19. 
    
20.   # Add details to the list of possible flights
    
21.   flights[(origin,dest)].append((depart,arrive,int(price)))
    
22. 
    
23. def getminutes(t):
    
24.   x=time.strptime(t,'%H:%M')
    
25.   return x[3]*60+x[4]
    
26. 
    
27. def printschedule(r):
    
28.   for d in range(len(r)/2):
    
29.     name=people[d][0]
    
30.     origin=people[d][1]
    
31.     out=flights[(origin,destination)][int(r[d])]
    
32.     ret=flights[(destination,origin)][int(r[d+1])]
    
33.     print '%10s%10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin,
    
34.                                                   out[0],out[1],out[2],
    
35.                                                   ret[0],ret[1],ret[2])
    
36. 
    
37. def schedulecost(sol):
    
38.   totalprice=0
    
39.   latestarrival=0
    
40.   earliestdep=24*60
    
41. 
    
42.   for d in range(len(sol)/2):
    
43.     # Get the inbound and outbound flights
    
44.     origin=people[d][1]
    
45.     outbound=flights[(origin,destination)][int(sol[d])]
    
46.     returnf=flights[(destination,origin)][int(sol[d+1])]
    
47.    
    
48.     # Total price is the price of all outbound and return flights
    
49.     totalprice+=outbound[2]
    
50.     totalprice+=returnf[2]
    
51.    
    
52.     # Track the latest arrival and earliest departure
    
53.     if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
    
54.     if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])
    
55.   
    
56.   # Every person must wait at the airport until the latest person arrives.
    
57.   # They also must arrive at the same time and wait for their flights.
    
58.   totalwait=0  
    
59.   for d in range(len(sol)/2):
    
60.     origin=people[d][1]
    
61.     outbound=flights[(origin,destination)][int(sol[d])]
    
62.     returnf=flights[(destination,origin)][int(sol[d+1])]
    
63.     totalwait+=latestarrival-getminutes(outbound[1])
    
64.     totalwait+=getminutes(returnf[0])-earliestdep  
    
65. 
    
66.   # Does this solution require an extra day of car rental? That'll be $50!
    
67.   if latestarrival>earliestdep: totalprice+=50
    
68.   
    
69.   return totalprice+totalwait
    
70. 
    
71. def randomoptimize(domain,costf):
    
72.   best=999999999
    
73.   bestr=None
    
74.   for i in range(0,1000):
    
75.     # Create a random solution
    
76.     r=[float(random.randint(domain[i][0],domain[i][1]))
    
77.        for i in range(len(domain))]
    
78.    
    
79.     # Get the cost
    
80.     cost=costf(r)
    
81.    
    
82.     # Compare it to the best one so far
    
83.     if cost<best:
    
84.       best=cost
    
85.       bestr=r
    
86.   return r
    
87. 
    
88. def hillclimb(domain,costf):
    
89.   # Create a random solution
    
90.   sol=[random.randint(domain[i][0],domain[i][1])
    
91.       for i in range(len(domain))]
    
92.   # Main loop
    
93.   while 1:
    
94.     # Create list of neighboring solutions
    
95.     neighbors=[]
    
96.    
    
97.     for j in range(len(domain)):
    
98.       # One away in each direction
    
99.       if sol[j]>domain[j][0]:
    
100.         neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:])
     
101.       if sol[j]<domain[j][1]:
     
102.         neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])
     
103. 
     
104.     # See what the best solution amongst the neighbors is
     
105.     current=costf(sol)
     
106.     best=current
     
107.     for j in range(len(neighbors)):
     
108.       cost=costf(neighbors[j])
     
109.       if cost<best:
     
110.         best=cost
     
111.         sol=neighbors[j]
     
112. 
     
113.     # If there's no improvement, then we've reached the top
     
114.     if best==current:
     
115.       break
     
116.   return sol
     
117. 
     
118. def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
     
119.   # Initialize the values randomly
     
120.   vec=[float(random.randint(domain[i][0],domain[i][1]))
     
121.        for i in range(len(domain))]
     
122.   
     
123.   while T>0.1:
     
124.     # Choose one of the indices
     
125.     i=random.randint(0,len(domain)-1)
     
126. 
     
127.     # Choose a direction to change it
     
128.     dir=random.randint(-step,step)
     
129. 
     
130.     # Create a new list with one of the values changed
     
131.     vecb=vec[:]
     
132.     vecb[i]+=dir
     
133.     if vecb[i]<domain[i][0]: vecb[i]=domain[i][0]
     
134.     elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1]
     
135. 
     
136.     # Calculate the current cost and the new cost
     
137.     ea=costf(vec)
     
138.     eb=costf(vecb)
     
139.     p=pow(math.e,(-eb-ea)/T)
     
140. 
     
141.     # Is it better, or does it make the probability
     
142.     # cutoff?
     
143.     if (eb<ea or random.random()<p):
     
144.       vec=vecb      
     
145. 
     
146.     # Decrease the temperature
     
147.     T=T*cool
     
148.   return vec
     
149. 
     
150. def geneticoptimize(domain,costf,popsize=50,step=1,
     
151.                     mutprob=0.2,elite=0.2,maxiter=100):
     
152.   # Mutation Operation
     
153.   def mutate(vec):
     
154.     i=random.randint(0,len(domain)-1)
     
155.     if random.random()<0.5 and vec[i]>domain[i][0]:
     
156.       return vec[0:i]+[vec[i]-step]+vec[i+1:]
     
157.     elif vec[i]<domain[i][1]:
     
158.       return vec[0:i]+[vec[i]+step]+vec[i+1:]
     
159.   
     
160.   # Crossover Operation
     
161.   def crossover(r1,r2):
     
162.     i=random.randint(1,len(domain)-2)
     
163.     return r1[0:i]+r2[i:]
     
164. 
     
165.   # Build the initial population
     
166.   pop=[]
     
167.   for i in range(popsize):
     
168.     vec=[random.randint(domain[i][0],domain[i][1])
     
169.          for i in range(len(domain))]
     
170.     pop.append(vec)
     
171.   
     
172.   # How many winners from each generation?
     
173.   topelite=int(elite*popsize)
     
174.   
     
175.   # Main loop
     
176.   for i in range(maxiter):
     
177.     scores=[(costf(v),v) for v in pop]
     
178.     scores.sort()
     
179.     ranked=[v for (s,v) in scores]
     
180.    
     
181.     # Start with the pure winners
     
182.     pop=ranked[0:topelite]
     
183.    
     
184.     # Add mutated and bred forms of the winners
     
185.     while len(pop)<popsize:
     
186.       if random.random()<mutprob:
     
187. 
     
188.         # Mutation
     
189.         c=random.randint(0,topelite)
     
190.         pop.append(mutate(ranked[c]))
     
191.       else:
     
192.       
     
193.         # Crossover
     
194.         c1=random.randint(0,topelite)
     
195.         c2=random.randint(0,topelite)
     
196.         pop.append(crossover(ranked[c1],ranked[c2]))
     
197.    
     
198.     # Print current best score
     
199.     print scores[0][0]
     
200.    
     
201.   return scores[0][1]

复制代码