[关闭]
@hainingwyx 2016-11-16T06:49:02.000000Z 字数 50066 阅读 3120

写给程序员的数据挖掘实战--读书笔记

数据挖掘 Python

写在之前

本书涉及的源程序和数据都可以在以下网站中找到：http://guidetodatamining.com/。

这本书理论比较简单，书中错误较少，动手锻炼较多，如果每个代码都自己写出来，收获不少。总结：适合入门。

欢迎转载，转载请注明出处，如有问题欢迎指正。

协同过滤

相似用户评判标准：曼哈顿距离、欧氏距离、明氏距离。 

  1. # Manhattan.py
  2. users = {
  3.     "Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5,
  4.                  "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, 
  5.                  "Vampire Weekend": 2.0},
  6.     "Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, 
  7.              "Phoenix": 2.0,"Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
  8.     "Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, 
  9.            "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
  10.     "Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, 
  11.           "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, 
  12.           "Vampire Weekend": 2.0},
  13.     "Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, 
  14.              "The Strokes": 4.0, "Vampire Weekend": 1.0},
  15.     "Jordyn": {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, 
  16.             "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, 
  17.             "Vampire Weekend": 4.0},
  18.     "Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0,
  19.            "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
  20.     "Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0,
  21.                 "Slightly Stoopid": 2.5, "The Strokes": 3.0}
  22.         }
  24. def manhattan(rating1, rating2):
  25.     """Computes the Manhattan distance. Both rating1 and rating2 are dictionaries
  26.        of the form {'The Strokes': 3.0, 'Slightly Stoopid': 2.5}"""
  27.     distance = 0
  28.     commonRatings = False 
  29.     for key in rating1:
  30.         if key in rating2:
  31.             distance += abs(rating1[key] - rating2[key])
  32.             commonRatings = True
  33.     if commonRatings:
  34.         return distance
  35.     else:
  36.         return -1 #Indicates no ratings in common
  38. def computeNearestNeighbor(username, users):
  39.     """creates a sorted list of users based on their distance to username"""
  40.     distances = []
  41.     for user in users:
  42.         if user != username:
  43.             distance = manhattan(users[user], users[username])
  44.             distances.append((distance, user))
  45.     # sort based on distance -- closest first
  46.     distances.sort()
  47.     return distances
  49. def recommend(username, users):
  50.     """Give list of recommendations"""
  51.     # first find nearest neighbor
  52.     nearest = computeNearestNeighbor(username, users)[0][1]
  53.     print nearest
  54.     recommendations = []
  55.     # now find bands neighbor rated that user didn't
  56.     neighborRatings = users[nearest]
  57.     userRatings = users[username]
  58.     for artist in neighborRatings:
  59.         if not artist in userRatings:
  60.             recommendations.append((artist, neighborRatings[artist]))
  61.     # using the fn sorted for variety - sort is more efficient
  62.     return sorted(recommendations, key=lambda artistTuple: artistTuple[1], reverse = True)
  1. # -*- coding: utf-8 -*-
  2. from math import sqrt
  4. users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5, "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, "Vampire Weekend": 2.0},
  5.          "Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
  6.          "Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
  7.          "Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
  8.          "Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
  9.          "Jordyn":  {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
  10.          "Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
  11.          "Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
  12.         }
  14. #明氏距离
  15. def minkowski(rating1,rating2,r):
  16.     distance=0
  17.     commonRatings=False
  18.     for key in rating1:
  19.         if key in rating2:
  20.             distance += pow(abs(rating1[key]-rating2[key]),r)
  21.             commonRatings=True
  22.     distance = pow(distance,1.0/r)
  23.     if commonRatings:
  24.         return distance
  25.     else:
  26.         return -1 #Indicates no ratings in common
  28. def computeNearestNeighbor(username, users):
  29.     """creates a sorted list of users based on their distance to username"""
  30.     distances = []
  31.     for user in users:
  32.         if user != username:
  33.             distance = minkowski(users[user], users[username],3)
  34.             distances.append((distance, user))
  35.     # sort based on distance -- closest first
  36.     distances.sort()
  37.     return distances
  39. def recommend(username, users):
  40.     """Give list of recommendations"""
  41.     # first find nearest neighbor
  42.     nearest = computeNearestNeighbor(username, users)[0][1]
  43.     print nearest
  44.     recommendations = []
  45.     # now find bands neighbor rated that user didn't
  46.     neighborRatings = users[nearest]
  47.     userRatings = users[username]
  48.     for artist in neighborRatings:
  49.         if not artist in userRatings:
  50.             recommendations.append((artist, neighborRatings[artist]))
  51.     # using the fn sorted for variety - sort is more efficient
  52.     return sorted(recommendations, key=lambda artistTuple: artistTuple[1], reverse = True)

但是可能存在常数差别，但是两者爱好相同的问题。

皮尔逊相关系数： 

  1. # Pearson.py
  2. from math import sqrt
  4. users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5, "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, "Vampire Weekend": 2.0},
  5.          "Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
  6.          "Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
  7.          "Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
  8.          "Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
  9.          "Jordyn":  {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
  10.          "Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
  11.          "Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
  12.         }
  14. # 这里为了简单使用近似代替
  15. def pearson(rating1,rating2):
  16.     sum_xy=0
  17.     sum_x=0
  18.     sum_y=0
  19.     sum_x2=0
  20.     sum_y2=0
  21.     n=0
  22.     for key in rating1:
  23.         if key in rating2:
  24.             n += 1
  25.             x = rating1[key]
  26.             y = rating2[key]
  27.             sum_xy += x*y
  28.             sum_x += x
  29.             sum_y += y
  30.             sum_x2 += x**2
  31.             sum_y2 += y**2
  32.     denominnator = sqrt(sum_x2-(sum_x**2)/n)*sqrt(sum_y2-(sum_y**2)/n)
  33.     if denominnator == 0:
  34.         return 0
  35.     else:
  36.         return (sum_xy-(sum_x*sum_y)/n)/denominnator
  38. def cos_like(rating1,rating2):
  39.     innerProd=0
  40.     vector_x=0
  41.     vectoy_y=0
  42.     for key in rating1:
  43.         if key in rating2:
  44.             x=rating1[key]
  45.             y=rating2[key]
  46.             innerProd += x*y
  47.             vector_x += x**2
  48.             vectoy_y += y**2
  49.         denominnator = sqrt(vector_x) * sqrt(vectoy_y)
  50.     if denominnator == 0:
  51.         return 0
  52.     else:
  53.         return innerProd / denominnator

余弦相似度：


总结：如果数据稠密使用欧氏距离；如果数据稀疏，使用余弦相似度；如果用户评级范围不同，使用皮尔逊相关系数。但是如果仅仅是基于一个用户进行推荐，个别用户的怪癖也会被推荐。

k近邻：利用k个最相似的用户确定推荐结果，K和应有有关。利用皮尔逊系数来确定每个人的影响因子。

  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}}
  22. from math import sqrt
  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
  31.   # if they have no ratings in common, return 0
  32.   if len(si)==0: return 0
  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]])
  38.   return 1/(1+sum_of_squares)
  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
  47.   # if they are no ratings in common, return 0
  48.   if len(si)==0: return 0
  50.   # Sum calculations
  51.   n=len(si)
  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])
  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])   
  61.   # Sum of the products
  62.   pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
  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
  69.   r=num/den
  71.   return r
  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]
  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)
  92.     # ignore scores of zero or lower
  93.     if sim<=0: continue
  94.     for item in prefs[other]:
  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
  105.   # Create the normalized list
  106.   rankings=[(total/simSums[item],item) for item,total in totals.items()]
  108.   # Return the sorted list
  109.   rankings.sort()
  110.   rankings.reverse()
  111.   return rankings
  113. def transformPrefs(prefs):
  114.   result={}
  115.   for person in prefs:
  116.     for item in prefs[person]:
  117.       result.setdefault(item,{})
  119.       # Flip item and person
  120.       result[item][person]=prefs[person][item]
  121.   return result
  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
  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( ):
  147.     # Loop over items similar to this one
  148.     for (similarity,item2) in itemMatch[item]:
  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
  159.   # Divide each total score by total weighting to get an average
  160.   rankings=[(score/totalSim[item],item) for item,score in scores.items( )]
  162.   # Return the rankings from highest to lowest
  163.   rankings.sort( )
  164.   rankings.reverse( )
  165.   return rankings
  167. def loadMovieLens(path='C:\Users\WangYixin\Desktop\PCI_Code\PCI_Code Folder\chapter2\data'):
  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
  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. # -*- coding: utf-8 -*-
  2. # 推荐类
  3. import codecs 
  4. from math import sqrt
  6. users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0,
  7.                       "Norah Jones": 4.5, "Phoenix": 5.0,
  8.                       "Slightly Stoopid": 1.5,
  9.                       "The Strokes": 2.5, "Vampire Weekend": 2.0},
  11.          "Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5,
  12.                  "Deadmau5": 4.0, "Phoenix": 2.0,
  13.                  "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
  15.          "Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0,
  16.                   "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5,
  17.                   "Slightly Stoopid": 1.0},
  19.          "Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0,
  20.                  "Deadmau5": 4.5, "Phoenix": 3.0,
  21.                  "Slightly Stoopid": 4.5, "The Strokes": 4.0,
  22.                  "Vampire Weekend": 2.0},
  24.          "Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0,
  25.                     "Norah Jones": 4.0, "The Strokes": 4.0,
  26.                     "Vampire Weekend": 1.0},
  28.          "Jordyn":  {"Broken Bells": 4.5, "Deadmau5": 4.0,
  29.                      "Norah Jones": 5.0, "Phoenix": 5.0,
  30.                      "Slightly Stoopid": 4.5, "The Strokes": 4.0,
  31.                      "Vampire Weekend": 4.0},
  33.          "Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0,
  34.                  "Norah Jones": 3.0, "Phoenix": 5.0,
  35.                  "Slightly Stoopid": 4.0, "The Strokes": 5.0},
  37.          "Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0,
  38.                       "Phoenix": 4.0, "Slightly Stoopid": 2.5,
  39.                       "The Strokes": 3.0}
  40.         }
  44. class recommender:
  46.     def __init__(self, data, k=1, metric='pearson', n=5):
  47.         """ initialize recommender
  48.         currently, if data is dictionary the recommender is initialized
  49.         to it.
  50.         For all other data types of data, no initialization occurs
  51.         k is the k value for k nearest neighbor
  52.         metric is which distance formula to use
  53.         n is the maximum number of recommendations to make"""
  54.         self.k = k
  55.         self.n = n
  56.         self.username2id = {}
  57.         self.userid2name = {}
  58.         self.productid2name = {}
  59.         # for some reason I want to save the name of the metric
  60.         self.metric = metric
  61.         if self.metric == 'pearson':
  62.             self.fn = self.pearson
  63.         #
  64.         # if data is dictionary set recommender data to it
  65.         #
  66.         if type(data).__name__ == 'dict':
  67.             self.data = data
  69.     def convertProductID2name(self, id):
  70.         """Given product id number return product name"""
  71.         if id in self.productid2name:
  72.             return self.productid2name[id]
  73.         else:
  74.             return id
  77.     def userRatings(self, id, n):
  78.         """Return n top ratings for user with id"""
  79.         print ("Ratings for " + self.userid2name[id])
  80.         ratings = self.data[id]
  81.         print(len(ratings))
  82.         ratings = list(ratings.items())
  83.         ratings = [(self.convertProductID2name(k), v)
  84.                    for (k, v) in ratings]
  85.         # finally sort and return
  86.         ratings.sort(key=lambda artistTuple: artistTuple[1],
  87.                      reverse = True)
  88.         ratings = ratings[:n]
  89.         for rating in ratings:
  90.             print("%s\t%i" % (rating[0], rating[1]))
  95.     def loadBookDB(self, path=''):
  96.         """loads the BX book dataset. Path is where the BX files are
  97.         located"""
  98.         self.data = {}
  99.         i = 0
  100.         #
  101.         # First load book ratings into self.data
  102.         #
  103.         f = codecs.open(path + "BX-Book-Ratings.csv", 'r', 'utf8')
  104.         f.readline()                            #read the title
  105.         for line  in f:
  106.             i += 1
  107.             #separate line into fields
  108.             fields = line.split(';')            # still with ""
  109.             user = fields[0].strip('"')         #delete “ in the fields
  110.             book = fields[1].strip('"')
  111.             rating = int(fields[2].strip().strip('"'))
  112.             if user in self.data:
  113.                 currentRatings = self.data[user]
  114.             else:
  115.                 currentRatings = {}
  116.             currentRatings[book] = rating
  117.             self.data[user] = currentRatings
  118.             #line = f.readline()
  119.         f.close()
  120.         #
  121.         # Now load books into self.productid2name
  122.         # Books contains isbn, title, and author among other fields
  123.         #
  124.         f = codecs.open(path + "BX-Books.csv", 'r', 'utf8')
  125.         for line in f:
  126.             i += 1
  127.             #separate line into fields
  128.             fields = line.split(';')
  129.             isbn = fields[0].strip('"')
  130.             title = fields[1].strip('"')
  131.             author = fields[2].strip().strip('"')
  132.             title = title + ' by ' + author
  133.             self.productid2name[isbn] = title
  134.         f.close()
  135.         #
  136.         #  Now load user info into both self.userid2name and
  137.         #  self.username2id
  138.         #
  139.         f = codecs.open(path + "BX-Users.csv", 'r', 'utf8')
  140.         for line in f:
  141.             i += 1
  142.             #print(line)
  143.             #separate line into fields
  144.             fields = line.split(';')
  145.             userid = fields[0].strip('"')
  146.             location = fields[1].strip('"')
  147.             if len(fields) > 3:
  148.                 age = fields[2].strip().strip('"')
  149.             else:
  150.                 age = 'NULL'
  151.             if age != 'NULL':
  152.                 value = location + '  (age: ' + age + ')'
  153.             else:
  154.                 value = location
  155.             self.userid2name[userid] = value
  156.             self.username2id[location] = userid
  157.         f.close()
  158.         print(i)
  161.     def pearson(self, rating1, rating2):
  162.         sum_xy = 0
  163.         sum_x = 0
  164.         sum_y = 0
  165.         sum_x2 = 0
  166.         sum_y2 = 0
  167.         n = 0
  168.         for key in rating1:
  169.             if key in rating2:
  170.                 n += 1
  171.                 x = rating1[key]
  172.                 y = rating2[key]
  173.                 sum_xy += x * y
  174.                 sum_x += x
  175.                 sum_y += y
  176.                 sum_x2 += pow(x, 2)
  177.                 sum_y2 += pow(y, 2)
  178.         if n == 0:
  179.             return 0
  180.         # now compute denominator
  181.         denominator = (sqrt(sum_x2 - pow(sum_x, 2) / n)
  182.                        * sqrt(sum_y2 - pow(sum_y, 2) / n))
  183.         if denominator == 0:
  184.             return 0
  185.         else:
  186.             return (sum_xy - (sum_x * sum_y) / n) / denominator
  189.     def computeNearestNeighbor(self, username):
  190.         """creates a sorted list of users based on their distance to
  191.         username"""
  192.         distances = []
  193.         for instance in self.data:
  194.             if instance != username:
  195.                 distance = self.fn(self.data[username],
  196.                                    self.data[instance])
  197.                 distances.append((instance, distance))
  198.         # sort based on distance -- closest first
  199.         distances.sort(key=lambda artistTuple: artistTuple[1],
  200.                        reverse=True)
  201.         return distances
  203.     def recommend(self, user):
  204.        """Give list of recommendations"""
  205.        recommendations = {}
  206.        # first get list of users  ordered by nearness
  207.        nearest = self.computeNearestNeighbor(user)
  208.        # now get the ratings for the user
  209.        userRatings = self.data[user]
  210.        # determine the total distance
  211.        totalDistance = 0.0
  212.        for i in range(self.k):
  213.           totalDistance += nearest[i][1]
  214.        # now iterate through the k nearest neighbors
  215.        # accumulating their ratings
  216.        for i in range(self.k):
  217.           # compute slice of pie 
  218.           weight = nearest[i][1] / totalDistance
  219.           # get the name of the person
  220.           name = nearest[i][0]
  221.           # get the ratings for this person
  222.           neighborRatings = self.data[name]
  223.           # get the name of the person
  224.           # now find bands neighbor rated that user didn't
  225.           for artist in neighborRatings:
  226.              if not artist in userRatings:
  227.                 if artist not in recommendations:
  228.                    recommendations[artist] = (neighborRatings[artist]
  229.                                               * weight)
  230.                 else:
  231.                    recommendations[artist] = (recommendations[artist]
  232.                                               + neighborRatings[artist]
  233.                                               * weight)
  234.        # now make list from dictionary
  235.        recommendations = list(recommendations.items())
  236.        recommendations = [(self.convertProductID2name(k), v)
  237.                           for (k, v) in recommendations]
  238.        # finally sort and return
  239.        recommendations.sort(key=lambda artistTuple: artistTuple[1],
  240.                             reverse = True)
  241.        # Return the first n items
  242.        return recommendations[:self.n]
  244. ############test code############
  245. #r = recommender(users)
  246. #r.recommend('Jordyn')
  247. #r.recommend('Hailey')
  248. #r.loadBookDB('BX-CSV-Dump/')
  249. #r.recommend('171118')
  250. #r.userRatings('171118', 5)

协同过滤--基于物品的过滤

显示评级：显示给出评级结果，如Youtube的点赞、点差按钮

隐式评级：网站点击轨迹。

基于邻居(用户)的推荐系统计算的次数十分巨大，所以有延迟性。还有稀疏性的问题。也称为基于内存的协同过滤，因为需要保存所有的评级结果来进行推荐。

基于物品的过滤：事先找到最相似的物品，并结合物品的评级结果生成推荐。也称为基于模型的协同过滤，因为不需要保存所有的评级结果，取而代之的随时构建一个模型表示物品之间的相似度。

为了抵消分数夸大，调整余弦相似度


U表示所有同事对i和j进行过评级的用户组合，表示用户u对物品i的评分，表示用户u对所有物品评分的平均值。可以获得相似度矩阵。

  1. users3 = {"David": {"Imagine Dragons": 3, "Daft Punk": 5,
  2.                     "Lorde": 4, "Fall Out Boy": 1},
  3.           "Matt":  {"Imagine Dragons": 3, "Daft Punk": 4,
  4.                     "Lorde": 4, "Fall Out Boy": 1},
  5.           "Ben":   {"Kacey Musgraves": 4, "Imagine Dragons": 3,
  6.                     "Lorde": 3, "Fall Out Boy": 1},
  7.           "Chris": {"Kacey Musgraves": 4, "Imagine Dragons": 4,
  8.                     "Daft Punk": 4, "Lorde": 3, "Fall Out Boy": 1},
  9.           "Tori":  {"Kacey Musgraves": 5, "Imagine Dragons": 4,
  10.                     "Daft Punk": 5, "Fall Out Boy": 3}}
  12. def computeSimilarity(band1, band2, userRatings):
  13.    averages = {}
  14.    for (key, ratings) in userRatings.items():
  15.       averages[key] = (float(sum(ratings.values()))
  16.                       / len(ratings.values()))
  18.    num = 0  # numerator
  19.    dem1 = 0 # first half of denominator
  20.    dem2 = 0
  21.    for (user, ratings) in userRatings.items():
  22.       if band1 in ratings and band2 in ratings:
  23.          avg = averages[user]
  24.          num += (ratings[band1] - avg) * (ratings[band2] - avg)
  25.          dem1 += (ratings[band1] - avg)**2
  26.          dem2 += (ratings[band2] - avg)**2
  27.    return num / (sqrt(dem1) * sqrt(dem2))

相似矩阵预测：


表示用户u对物品i的预测值

N表示用户u的所有评级物品中每个和i得分相似的物品。

是i和N之间的相识度

是u给N的评级结果，应该在之间取值，可能需要做线性变换


得到新的评级结果为

Slope One算法

  1. 计算偏差

    物品i到物品j的平均偏差为


    是S集合中的元素的个数。X是整个评分集合。是所有对i和j进行评分的用户集合。

    1. def computeDeviations(self):
    2.    # for each person in the data:
    3.    #    get their ratings
    4.    for ratings in self.data.values():        # data:users2, ratings:{song:value, , }
    5.        # for each item & rating in that set of ratings:
    6.        for (item, rating) in ratings.items():
    7.            self.frequencies.setdefault(item, {})   #key is song
    8.            self.deviations.setdefault(item, {})                    
    9.            # for each item2 & rating2 in that set of ratings:
    10.            for (item2, rating2) in ratings.items():
    11.                if item != item2:
    12.                    # add the difference between the ratings to our
    13.                    # computation
    14.                    self.frequencies[item].setdefault(item2, 0)
    15.                    self.deviations[item].setdefault(item2, 0.0)
    16.                    # frequemcies is card
    17.                    self.frequencies[item][item2] += 1    
    18.                    # diviations is the sum of dev of diff users
    19.                    #value of complex dic is dev
    20.                    self.deviations[item][item2] += rating - rating2     
    22.                    for (item, ratings) in self.deviations.items():
    23.                        for item2 in ratings:
    24.                            ratings[item2] /= self.frequencies[item][item2]
    26. # test code for ComputeDeviations(self)
    29. #r = recommender(users2)
    32. #r.computeDeviations()
    35. #r.deviations

    ​

  2. 加权Slope预测


    表示加权Slope算法给出的用户u对物品j的预测 

    1. def slopeOneRecommendations(self, userRatings):
    2.    recommendations = {}
    3.    frequencies = {}
    4.    # for every item and rating in the user's recommendations
    5.    for (userItem, userRating) in userRatings.items():        # userItem :i
    6.        # for every item in our dataset that the user didn't rate
    7.        for (diffItem, diffRatings) in self.deviations.items():    #diffItem : j
    8.            if diffItem not in userRatings and \
    9.            userItem in self.deviations[diffItem]:
    10.                freq = self.frequencies[diffItem][userItem] #freq:c_ji
    11.                # 如果键不存在于字典中，将会添加键并将值设为默认值。
    12.                recommendations.setdefault(diffItem, 0.0)
    13.                frequencies.setdefault(diffItem, 0)
    14.                # add to the running sum representing the numerator
    15.                # of the formula
    16.                recommendations[diffItem] += (diffRatings[userItem] +
    17.                                              userRating) * freq
    18.                # keep a running sum of the frequency of diffitem
    19.                frequencies[diffItem] += freq
    20.                #p(u)j list
    21.                recommendations =  [(self.convertProductID2name(k),          
    22.                                     v / frequencies[k])
    23.                                    for (k, v) in recommendations.items()]
    24.                # finally sort and return
    25.                recommendations.sort(key=lambda artistTuple: artistTuple[1],
    26.                                     reverse = True)
    27.                # I am only going to return the first 50 recommendations
    28.                return recommendations[:50]
    31. # test code for SlopeOneRecommendations
    34. #r = recommender(users2)
    37. #r.computeDeviations()
    40. #g = users2['Ben']
    43. #r.slopeOneRecommendations(g)
    1. def loadMovieLens(self, path=''):
    2.      self.data = {}
    3.      #
    4.      # first load movie ratings
    5.      #
    6.      i = 0
    7.      #
    8.      # First load book ratings into self.data
    9.      #
    10.      #f = codecs.open(path + "u.data", 'r', 'utf8')
    11.      f = codecs.open(path + "u.data", 'r', 'ascii')
    12.      #  f = open(path + "u.data")
    13.      for line in f:
    14.         i += 1
    15.         #separate line into fields
    16.         fields = line.split('\t')
    17.         user = fields[0]
    18.         movie = fields[1]
    19.         rating = int(fields[2].strip().strip('"'))
    20.         if user in self.data:
    21.            currentRatings = self.data[user]
    22.         else:
    23.            currentRatings = {}
    24.         currentRatings[movie] = rating
    25.         self.data[user] = currentRatings
    26.      f.close()
    27.      #
    28.      # Now load movie into self.productid2name
    29.      # the file u.item contains movie id, title, release date among
    30.      # other fields
    31.      #
    32.      #f = codecs.open(path + "u.item", 'r', 'utf8')
    33.      f = codecs.open(path + "u.item", 'r', 'iso8859-1', 'ignore')
    34.      #f = open(path + "u.item")
    35.      for line in f:
    36.         i += 1
    37.         #separate line into fields
    38.         fields = line.split('|')
    39.         mid = fields[0].strip()
    40.         title = fields[1].strip()
    41.         self.productid2name[mid] = title
    42.      f.close()
    43.      #
    44.      #  Now load user info into both self.userid2name
    45.      #  and self.username2id
    46.      #
    47.      #f = codecs.open(path + "u.user", 'r', 'utf8')
    48.      f = open(path + "u.user")
    49.      for line in f:
    50.         i += 1
    51.         fields = line.split('|')
    52.         userid = fields[0].strip('"')
    53.         self.userid2name[userid] = line
    54.         self.username2id[line] = userid
    55.      f.close()
    56.      print(i)
    58. # test code
    61. #r = recommender(0)
    64. #r.loadMovieLens('ml-100k/')
    67. #r.computeDeviations()
    70. #r.slopeOneRecommendations(r.data['1'])
    73. #r.slopeOneRecommendations(r.data['25'])

内容过滤及分类--基于物品属性的过滤

新物品加入，会因为没有被评分过，永远不会被推荐。Pandora是基于基于一种称为音乐基因的项目。

当所用数据挖掘方法基于特征的值来计算 两个对象的距离，且不同特征的尺度不同，就需要使用归一化。一般使用均值和标准差来进行归一化，但这种方法可能会受到离群点的影响，所以引入改进后的归一化：均值用中位数()代替，标准差用绝对标准差(asd)代替。 

  1. # 计算中位数和绝对标准差
  2. def getMedian(self, alist):
  3.      """return median of alist"""
  4.     if alist == []:
  5.         return []
  6.     blist = sorted(alist)
  7.     length = len(alist)
  8.     if length % 2 == 1:
  9.         # length of list is odd so return middle element
  10.         return blist[int(((length + 1) / 2) -  1)]
  11.     else:
  12.         # length of list is even so compute midpoint
  13.         v1 = blist[int(length / 2)]
  14.         v2 =blist[(int(length / 2) - 1)]
  15.         return (v1 + v2) / 2.0
  18. def getAbsoluteStandardDeviation(self, alist, median):
  19.     """given alist and median return absolute standard deviation"""
  20.     sum = 0
  21.     for item in alist:
  22.         sum += abs(item - median)
  23.     return sum / len(alist)
  25. def unitTest():
  26.     list1 = [54, 72, 78, 49, 65, 63, 75, 67, 54]
  27.     list2 = [54, 72, 78, 49, 65, 63, 75, 67, 54, 68]
  28.     list3 = [69]
  29.     list4 = [69, 72]
  30.     classifier = Classifier('data/athletesTrainingSet.txt')
  31.     m1 = classifier.getMedian(list1)
  32.     m2 = classifier.getMedian(list2)
  33.     m3 = classifier.getMedian(list3)
  34.     m4 = classifier.getMedian(list4)
  35.     asd1 = classifier.getAbsoluteStandardDeviation(list1, m1)
  36.     asd2 = classifier.getAbsoluteStandardDeviation(list2, m2)
  37.     asd3 = classifier.getAbsoluteStandardDeviation(list3, m3)
  38.     asd4 = classifier.getAbsoluteStandardDeviation(list4, m4)
  39.     assert(round(m1, 3) == 65)
  40.     assert(round(m2, 3) == 66)
  41.     assert(round(m3, 3) == 69)
  42.     assert(round(m4, 3) == 70.5)
  43.     assert(round(asd1, 3) == 8)
  44.     assert(round(asd2, 3) == 7.5)
  45.     assert(round(asd3, 3) == 0)
  46.     assert(round(asd4, 3) == 1.5)
  48.     print("getMedian and getAbsoluteStandardDeviation work correctly")

assert语句用于软件组件测试的做法是一种常用的技术。产品每一部分分成一段实现代码加上对实现代码的测试代码，这一点十分重要。

  1. # 归一化
  2. def normalizeColumn(self, columnNumber):
  3.        """given a column number, normalize that column in self.data"""
  4.        # first extract values to list, v is vector, clounm is 0/1,col is a list
  5.        col = [v[1][columnNumber] for v in self.data]
  6.        median = self.getMedian(col)
  7.        asd = self.getAbsoluteStandardDeviation(col, median)
  8.        #print("Median: %f   ASD = %f" % (median, asd))
  9.        self.medianAndDeviation.append((median, asd))
  10.        for v in self.data:
  11.            v[1][columnNumber] = (v[1][columnNumber] - median) / asd

算法评估及kNN

10-flod Cross Validation：将数据集分为10份，使用其中9份进行训练，另外1份用作测试，重复该过程10次。

留一法：n-flod Cross Validation。结果是随机的，不是确定值，和数据的划分有关。缺点在于计算机开销很大。分层采样的时候保证样本的均匀性很重要。

混淆矩阵：行表示测试样本的真实类别，列表示预测器所预测出来的类别。可揭示分类器性能。

  1. # divide data into 10 buckets
  2. import random
  4. def buckets(filename, bucketName, separator, classColumn):
  5.     """the original data is in the file named filename
  6.     bucketName is the prefix for all the bucket names
  7.     separator is the character that divides the columns
  8.     (for ex., a tab or comma and classColumn is the column
  9.     that indicates the class"""
  11.     # put the data in 10 buckets
  12.     numberOfBuckets = 10
  13.     data = {}
  14.     # first read in the data and divide by category
  15.     with open(filename) as f:
  16.         lines = f.readlines()
  17.     for line in lines:
  18.         if separator != '\t':
  19.             line = line.replace(separator, '\t')
  20.         # first get the category
  21.         category = line.split()[classColumn]
  22.         data.setdefault(category, [])   #set the value for dic data
  23.         data[category].append(line)     #all the information 
  24.     # initialize the buckets [[], [], ...]
  25.     buckets = []
  26.     for i in range(numberOfBuckets):
  27.         buckets.append([])       
  28.     # now for each category put the data into the buckets
  29.     for k in data.keys():
  30.         #randomize order of instances for each class
  31.         #data[k] is a list of line
  32.         random.shuffle(data[k])
  33.         bNum = 0
  34.         # divide into buckets
  35.         for item in data[k]:
  36.             buckets[bNum].append(item)
  37.             bNum = (bNum + 1) % numberOfBuckets
  39.     # write to file
  40.     for bNum in range(numberOfBuckets):
  41.         f = open("%s-%02i" % ('tmp/'+bucketName, bNum + 1), 'w')
  42.         for item in buckets[bNum]:
  43.             f.write(item)
  44.         f.close()
  46. # example of how to use this code          
  47. buckets("data/mpgData.txt", 'mpgData',',',0)

分类器评价：Kappa统计量。相对于随机分类器而言的分类器效果。


是实际分类器的准确率，是随机分类器的精确率。

Kappa区间 性能
<0 比随机方法性能差
0.01-0.2 轻微一致
0.21-0.4 一般一致
0.41-0.6 中度一致
0.61-0.8 高度一致
0.81-1 接近完美

KNN：当有一个样本是比较特别的时候，使用最近邻可能会导致特别样本的存在而出现误分类。改进的办法就是考察k个邻居。离得越近，影响因子就越大。影响因子可以用距离的倒数来表示。

  1. def knn(self, itemVector):
  2.   """returns the predicted class of itemVector using k
  3.   Nearest Neighbors"""
  4.   # changed from min to heapq.nsmallest to get the
  5.   # k closest neighbors
  6.   neighbors = heapq.nsmallest(self.k,
  7.   [(self.manhattan(itemVector, item[1]), item)
  8.   for item in self.data])
  9.   # each neighbor gets a vote
  10.   results = {}
  11.   for neighbor in neighbors: 
  12.   theClass = neighbor[1][0]
  13.   results.setdefault(theClass, 0)
  14.   results[theClass] += 1
  15.   resultList = sorted([(i[1], i[0]) for i in results.items()], reverse=True)
  16.   #get all the classes that have the maximum votes
  17.   maxVotes = resultList[0][0]
  18.   possibleAnswers = [i[1] for i in resultList if i[0] == maxVotes]
  19.   # randomly select one of the classes that received the max votes
  20.   answer = random.choice(possibleAnswers)
  21.   return( answer)

做工程，数据量大的时候算法的效果越好。做论文还是要研究出一个具有少量性能提高的算法。

概率及朴素贝叶斯

特点：分类并给出概率。

先验概率：P(h)

后验概率/条件概率：P(h/d) 

  1. # 训练
  2. class Classifier:
  3.     def __init__(self, bucketPrefix, testBucketNumber, dataFormat):
  5.         """ a classifier will be built from files with the bucketPrefix
  6.         excluding the file with textBucketNumber. dataFormat is a string that
  7.         describes how to interpret each line of the data files. For example,
  8.         for the iHealth data the format is:
  9.         "attr   attr    attr    attr    class"
  10.         """
  12.         total = 0
  13.         classes = {}
  14.         counts = {}
  17.         # reading the data in from the file
  19.         self.format = dataFormat.strip().split('\t')
  20.         self.prior = {}
  21.         self.conditional = {}
  22.         # for each of the buckets numbered 1 through 10:
  23.         for i in range(1, 11):
  24.             # if it is not the bucket we should ignore, read in the data
  25.             if i != testBucketNumber:
  26.                 filename = "%s-%02i" % (bucketPrefix, i)
  27.                 f = open(filename)
  28.                 lines = f.readlines()
  29.                 f.close()
  30.                 for line in lines:
  31.                     fields = line.strip().split('\t')
  32.                     ignore = []
  33.                     vector = []
  34.                     for i in range(len(fields)):
  35.                         if self.format[i] == 'num':
  36.                             vector.append(float(fields[i]))     #vector!!
  37.                         elif self.format[i] == 'attr':
  38.                             vector.append(fields[i])                           
  39.                         elif self.format[i] == 'comment':
  40.                             ignore.append(fields[i])
  41.                         elif self.format[i] == 'class':
  42.                             category = fields[i]
  43.                     # now process this instance
  44.                     total += 1
  45.                     classes.setdefault(category, 0)     #字典：分类类别计数
  46.                     counts.setdefault(category, {})     #复合字典：每类的每列的具体计数
  47.                     classes[category] += 1
  48.                     # now process each attribute of the instance
  49.                     col = 0
  50.                     for columnValue in vector:
  51.                         col += 1
  52.                         counts[category].setdefault(col, {})
  53.                         counts[category][col].setdefault(columnValue, 0)
  54.                         counts[category][col][columnValue] += 1
  56.         # ok done counting. now compute probabilities
  57.         # first prior probabilities p(h)
  58.         for (category, count) in classes.items():
  59.             self.prior[category] = count / total#字典：先验概率
  61.         # now compute conditional probabilities p(D|h)
  62.         for (category, columns) in counts.items():
  63.               self.conditional.setdefault(category, {})
  64.               for (col, valueCounts) in columns.items():
  65.                   self.conditional[category].setdefault(col, {})
  66.                   for (attrValue, count) in valueCounts.items():
  67.                       self.conditional[category][col][attrValue] = (
  68.                           count / classes[category])        #复合字典：每类的每个属性的条件概率
  69.         self.tmp =  counts               #应该暂时没有用
  1. # 分类
  2.     def classify(self, itemVector):
  3.         """Return class we think item Vector is in"""
  4.         results = []
  5.         for (category, prior) in self.prior.items():
  6.             prob = prior
  7.             col = 1
  8.             for attrValue in itemVector:
  9.                 if not attrValue in self.conditional[category][col]:
  10.                     # we did not find any instances of this attribute value
  11.                     # occurring with this category so prob = 0
  12.                     prob = 0
  13.                 else:
  14.                     prob = prob * self.conditional[category][col][attrValue]
  15.                 col += 1
  16.             results.append((prob, category))
  17.         # return the category with the highest probability
  18.         return(max(results)[1])
  1. # test code
  2. c = Classifier("iHealth/i", 10,"attr\tattr\tattr\tattr\tclass")
  3. print(c.classify(['health', 'moderate', 'moderate', 'yes']))

问题：当存在某个概率为0时，直接主导整个贝叶斯的计算过程，即使其他的独立事件的条件概率接近于1。此外，基于样本集估计出来概率往往是真实概率的偏低估计。

改进：将


修改为

其中是y事件总数，是y中x事件总数，是等效样本容量，通常的确定方法是：m为可选属性的个数值，p是可选属性的概率的先验估计，通常假设均匀分布有

当处理的数据是连续的时候，有两种解决办法。一是离散化，构建类别；一是假设概率分布服从高斯分布，然后计算概率。

样本标准差：


对于样本集而言，样本标准差相对于总体标准差计算公式是总体标准差的更优估计。

  1. # pdf计算实现
  2. def pdf(mean, ssd, x):
  3.    """Probability Density Function  computing P(x|y)
  4.    input is the mean, sample standard deviation for all the items in y,
  5.    and x."""
  6.    ePart = math.pow(math.e, -(x-mean)**2/(2*ssd**2))
  7.    print (ePart)
  8.    return (1.0 / (math.sqrt(2*math.pi)*ssd)) * ePart
  9. ````
  13. <div class="md-section-divider"></div>
  15. ```python
  16. # 连续数据的训练
  17. class Classifier:
  18.     def __init__(self, bucketPrefix, testBucketNumber, dataFormat):
  20.         """ a classifier will be built from files with the bucketPrefix
  21.         excluding the file with textBucketNumber. dataFormat is a string that
  22.         describes how to interpret each line of the data files. For example,
  23.         for the iHealth data the format is:
  24.         "attr   attr    attr    attr    class"
  25.         """
  27.         total = 0
  28.         classes = {}
  29.         # counts used for attributes that are not numeric
  30.         counts = {}
  31.         # totals used for attributes that are numereric
  32.         # we will use these to compute the mean and sample standard deviation for
  33.         # each attribute - class pair.
  34.         totals = {}
  35.         numericValues = {}
  38.         # reading the data in from the file
  40.         self.format = dataFormat.strip().split('\t')
  41.         # 
  42.         self.prior = {}
  43.         self.conditional = {}
  45.         # for each of the buckets numbered 1 through 10:
  46.         for i in range(1, 11):
  47.             # if it is not the bucket we should ignore, read in the data
  48.             if i != testBucketNumber:
  49.                 filename = "%s-%02i" % (bucketPrefix, i)
  50.                 f = open(filename)
  51.                 lines = f.readlines()
  52.                 f.close()
  53.                 for line in lines:
  54.                     fields = line.strip().split('\t')
  55.                     ignore = []
  56.                     vector = []
  57.                     nums = []
  58.                     for i in range(len(fields)):
  59.                         if self.format[i] == 'num':
  60.                             nums.append(float(fields[i]))
  61.                         elif self.format[i] == 'attr':
  62.                             vector.append(fields[i])                           
  63.                         elif self.format[i] == 'comment':
  64.                             ignore.append(fields[i])
  65.                         elif self.format[i] == 'class':
  66.                             category = fields[i]
  67.                     # now process this instance
  68.                     total += 1
  69.                     classes.setdefault(category, 0)
  70.                     counts.setdefault(category, {})
  71.                     totals.setdefault(category, {})
  72.                     numericValues.setdefault(category, {})
  73.                     classes[category] += 1
  74.                     # now process each non-numeric attribute of the instance
  75.                     col = 0
  76.                     for columnValue in vector:
  77.                         col += 1
  78.                         counts[category].setdefault(col, {})
  79.                         counts[category][col].setdefault(columnValue, 0)
  80.                         counts[category][col][columnValue] += 1
  81.                     # process numeric attributes
  82.                     col = 0
  83.                     for columnValue in nums:
  84.                         col += 1
  85.                         totals[category].setdefault(col, 0)
  86.                         #totals[category][col].setdefault(columnValue, 0)
  87.                         totals[category][col] += columnValue
  88.                         numericValues[category].setdefault(col, [])
  89.                         numericValues[category][col].append(columnValue)
  92.         #
  93.         # ok done counting. now compute probabilities
  94.         #
  95.         # first prior probabilities p(h)
  96.         #
  97.         for (category, count) in classes.items():
  98.             self.prior[category] = count / total
  99.         #
  100.         # now compute conditional probabilities p(h|D)
  101.         #
  102.         for (category, columns) in counts.items():
  103.               self.conditional.setdefault(category, {})
  104.               for (col, valueCounts) in columns.items():
  105.                   self.conditional[category].setdefault(col, {})
  106.                   for (attrValue, count) in valueCounts.items():
  107.                       self.conditional[category][col][attrValue] = (
  108.                           count / classes[category])
  109.         self.tmp =  counts               
  110.         #
  111.         # now compute mean and sample standard deviation
  112.         #
  113.         self.means = {}
  114.         self.totals = totals
  115.         for (category, columns) in totals.items():
  116.             self.means.setdefault(category, {})
  117.             for (col, cTotal) in columns.items():
  118.                 self.means[category][col] = cTotal / classes[category]
  119.         # standard deviation
  120.         self.ssd = {}
  121.         for (category, columns) in numericValues.items():
  123.             self.ssd.setdefault(category, {})
  124.             for (col, values) in columns.items():
  125.                 SumOfSquareDifferences = 0
  126.                 theMean = self.means[category][col]
  127.                 for value in values:
  128.                     SumOfSquareDifferences += (value - theMean)**2
  129.                 columns[col] = 0
  130.                 self.ssd[category][col] = math.sqrt(SumOfSquareDifferences / (classes[category]  - 1))              
  1. # 连续数据的分类
  2.     def classify(self, itemVector, numVector):
  3.         """Return class we think item Vector is in"""
  4.         results = []
  5.         sqrt2pi = math.sqrt(2 * math.pi)
  6.         for (category, prior) in self.prior.items():
  7.             prob = prior
  8.             col = 1
  9.             for attrValue in itemVector:
  10.                 if not attrValue in self.conditional[category][col]:
  11.                     # we did not find any instances of this attribute value
  12.                     # occurring with this category so prob = 0
  13.                     prob = 0
  14.                 else:
  15.                     prob = prob * self.conditional[category][col][attrValue]
  16.                 col += 1
  17.             col = 1
  18.             for x in  numVector:
  19.                 mean = self.means[category][col]
  20.                 ssd = self.ssd[category][col]
  21.                 ePart = math.pow(math.e, -(x - mean)**2/(2*ssd**2))
  22.                 prob = prob * ((1.0 / (sqrt2pi*ssd)) * ePart)
  23.                 col += 1
  24.             results.append((prob, category))
  25.         # return the category with the highest probability
  26.         #print(results)
  27.         return(max(results)[1])

贝叶斯和kNN的比较

许多真实数据挖掘问题中，很多属性不是独立的。有时候可以假设独立。之所以称朴素贝叶斯是因为尽管知道不成立仍然假设属性之间是独立的。

朴素贝叶斯和文本

训练阶段：

  1. 将标识为同一假设的文档合并成一个文本文件

  2. 计算词在该文件中的出现次数n,形成一个词汇表

  3. 对于词汇表中的每个词计算器在文本中的出现次数，记为

  4. 对词汇表中的每个词(去除停用词)，计算 

  1. class BayesText:
  3.     def __init__(self, trainingdir, stopwordlist):
  4.         """This class implements a naive Bayes approach to text
  5.         classification
  6.         trainingdir is the training data. Each subdirectory of
  7.         trainingdir is titled with the name of the classification
  8.         category -- those subdirectories in turn contain the text
  9.         files for that category.
  10.         The stopwordlist is a list of words (one per line) will be
  11.         removed before any counting takes place.
  12.         """
  13.         self.vocabulary = {}
  14.         self.prob = {}
  15.         self.totals = {}
  16.         self.stopwords = {}         #停用词字典
  17.         f = open(stopwordlist)
  18.         for line in f:
  19.             self.stopwords[line.strip()] = 1
  20.         f.close()
  21.         categories = os.listdir(trainingdir)
  22.         #filter out files that are not directories
  23.         self.categories = [filename for filename in categories
  24.                            if os.path.isdir(trainingdir + filename)]
  25.         print("Counting ...")
  26.         for category in self.categories:
  27.             print('    ' + category)
  28.             # 计算当前类别的单词和单词数量，单词的总量
  29.             (self.prob[category],
  30.              self.totals[category]) = self.train(trainingdir, category)
  31.         # I am going to eliminate any word in the 所有种类的单词库vocabulary
  32.         # that doesn't occur at least 3 times
  33.         toDelete = []
  34.         for word in self.vocabulary:
  35.             if self.vocabulary[word] < 3:
  36.                 # mark word for deletion
  37.                 # can't delete now because you can't delete
  38.                 # from a list you are currently iterating over
  39.                 toDelete.append(word)
  40.         # now delete
  41.         for word in toDelete:
  42.             del self.vocabulary[word]
  43.         # now compute probabilities
  44.         vocabLength = len(self.vocabulary)
  45.         print("Computing probabilities:")
  46.         for category in self.categories:
  47.             print('    ' + category)
  48.             denominator = self.totals[category] + vocabLength
  49.             for word in self.vocabulary:
  50.                 if word in self.prob[category]:
  51.                     count = self.prob[category][word]
  52.                 else:
  53.                     count = 1
  54.                 # 条件概率计算
  55.                 self.prob[category][word] = (float(count + 1)
  56.                                              / denominator)
  57.         print ("DONE TRAINING\n\n")
  59.     # input：trainingdir训练文件的目录, category训练文件的种类
  60.     # return: (counts, total) (当前文件的单词和单词数量,所有单词的数量)
  61.     def train(self, trainingdir, category):
  62.         """counts word occurrences for a particular category"""
  63.         currentdir = trainingdir + category
  64.         files = os.listdir(currentdir)
  65.         counts = {}
  66.         total = 0
  67.         for file in files:
  68.             #print(currentdir + '/' + file)
  69.             f = codecs.open(currentdir + '/' + file, 'r', 'iso8859-1')
  70.             for line in f:
  71.                 tokens = line.split()
  72.                 for token in tokens:
  73.                     # get rid of punctuation and lowercase token
  74.                     token = token.strip('\'".,?:-')
  75.                     token = token.lower()
  76.                     if token != '' and not token in self.stopwords:
  77.                         self.vocabulary.setdefault(token, 0)
  78.                         self.vocabulary[token] += 1#所有文档的单词和单词数量
  79.                         counts.setdefault(token, 0)
  80.                         counts[token] += 1#当前文件的单词和单词数量
  81.                         total += 1#所有单词的数量
  82.             f.close()
  83.         return(counts, total)
  84. # test code
  85. bT = BayesText(trainingDir, stoplistfile)
  86. bT.prob['rec.motorcycles']["god"]

分类阶段：


如果概率非常小，Python无法计算，可以采用取对数的形式。

停用词：当停用词是噪声时，去掉这些词能减少处理量，提高性能。个别情况下要重新考虑停用词。如性犯罪者会比一般人更多使用me、you这类词语。

  1.     def classify(self, itemVector, numVector):
  2.         """Return class we think item Vector is in"""
  3.         results = []
  4.         sqrt2pi = math.sqrt(2 * math.pi)
  5.         for (category, prior) in self.prior.items():
  6.             prob = prior
  7.             col = 1
  8.             for attrValue in itemVector:
  9.                 if not attrValue in self.conditional[category][col]:
  10.                     # we did not find any instances of this attribute value
  11.                     # occurring with this category so prob = 0
  12.                     prob = 0
  13.                 else:
  14.                     prob = prob * self.conditional[category][col][attrValue]
  15.                 col += 1
  16.             col = 1
  17.             for x in  numVector:
  18.                 mean = self.means[category][col]
  19.                 ssd = self.ssd[category][col]
  20.                 ePart = math.pow(math.e, -(x - mean)**2/(2*ssd**2))
  21.                 prob = prob * ((1.0 / (sqrt2pi*ssd)) * ePart)
  22.                 col += 1
  23.             results.append((prob, category))
  24.         # return the category with the highest probability
  25.         #print(results)
  26.         return(max(results)[1])
  28. # test code
  29. bT.classify(testDir+ 'rec.motorcycles/104673')

10-fold cross

  1. from __future__ import print_function
  2. import os, codecs, math
  4. class BayesText:
  5.     # input:训练文件目录，停用词，忽略的文件子集
  6.     def __init__(self, trainingdir, stopwordlist, ignoreBucket):
  7.         """This class implements a naive Bayes approach to text
  8.         classification
  9.         trainingdir is the training data. Each subdirectory of
  10.         trainingdir is titled with the name of the classification
  11.         category -- those subdirectories in turn contain the text
  12.         files for that category.
  13.         The stopwordlist is a list of words (one per line) will be
  14.         removed before any counting takes place.
  15.         """
  16.         self.vocabulary = {}
  17.         self.prob = {}
  18.         self.totals = {}
  19.         self.stopwords = {}
  20.         f = open(stopwordlist)
  21.         for line in f:
  22.             self.stopwords[line.strip()] = 1
  23.         f.close()
  24.         categories = os.listdir(trainingdir)
  25.         #filter out files that are not directories，in this program, neg and pos
  26.         self.categories = [filename for filename in categories
  27.                            if os.path.isdir(trainingdir + filename)]
  28.         print("Counting ...")
  29.         for category in self.categories:
  30.             #print('    ' + category)
  31.             (self.prob[category],
  32.              self.totals[category]) = self.train(trainingdir, category,
  33.                                                  ignoreBucket)
  34.         # I am going to eliminate any word in the vocabulary
  35.         # that doesn't occur at least 3 times
  36.         toDelete = []
  37.         for word in self.vocabulary:
  38.             if self.vocabulary[word] < 3:
  39.                 # mark word for deletion
  40.                 # can't delete now because you can't delete
  41.                 # from a list you are currently iterating over
  42.                 toDelete.append(word)
  43.         # now delete
  44.         for word in toDelete:
  45.             del self.vocabulary[word]
  46.         # now compute probabilities
  47.         vocabLength = len(self.vocabulary)
  48.         #print("Computing probabilities:")
  49.         for category in self.categories:
  50.             #print('    ' + category)
  51.             denominator = self.totals[category] + vocabLength
  52.             for word in self.vocabulary:
  53.                 if word in self.prob[category]:
  54.                     count = self.prob[category][word]
  55.                 else:
  56.                     count = 1
  57.                 self.prob[category][word] = (float(count + 1)
  58.                                              / denominator)
  59.         #print ("DONE TRAINING\n\n")
  62.     def train(self, trainingdir, category, bucketNumberToIgnore):
  63.         """counts word occurrences for a particular category"""
  64.         ignore = "%i" % bucketNumberToIgnore
  65.         currentdir = trainingdir + category
  66.         directories = os.listdir(currentdir)
  67.         counts = {}
  68.         total = 0
  69.         for directory in directories:
  70.             if directory != ignore:
  71.                 currentBucket = trainingdir + category + "/" + directory
  72.                 files = os.listdir(currentBucket)
  73.                 #print("   " + currentBucket)
  74.                 for file in files:
  75.                     f = codecs.open(currentBucket + '/' + file, 'r', 'iso8859-1')
  76.                     for line in f:
  77.                         tokens = line.split()
  78.                         for token in tokens:
  79.                             # get rid of punctuation and lowercase token
  80.                             token = token.strip('\'".,?:-')
  81.                             token = token.lower()
  82.                             if token != '' and not token in self.stopwords:
  83.                                 self.vocabulary.setdefault(token, 0)
  84.                                 self.vocabulary[token] += 1
  85.                                 counts.setdefault(token, 0)
  86.                                 counts[token] += 1
  87.                                 total += 1
  88.                     f.close()
  89.         return(counts, total)
  92.     def classify(self, filename):
  93.         results = {}
  94.         for category in self.categories:
  95.             results[category] = 0
  96.         f = codecs.open(filename, 'r', 'iso8859-1')
  97.         for line in f:
  98.             tokens = line.split()
  99.             for token in tokens:
  100.                 #print(token)
  101.                 token = token.strip('\'".,?:-').lower()
  102.                 if token in self.vocabulary:
  103.                     for category in self.categories:
  104.                         if self.prob[category][token] == 0:
  105.                             print("%s %s" % (category, token))
  106.                         results[category] += math.log(
  107.                             self.prob[category][token])
  108.         f.close()
  109.         results = list(results.items())
  110.         results.sort(key=lambda tuple: tuple[1], reverse = True)
  111.         # for debugging I can change this to give me the entire list
  112.         return results[0][0]
  114.     # input: 测试文件的分类目录，当前类别， 忽略子集
  115.     # return: 当前类别下的分类结果{0:12,1：23}
  116.     def testCategory(self, direc, category, bucketNumber):
  117.         results = {}
  118.         directory = direc + ("%i/" % bucketNumber)
  119.         #print("Testing " + directory)
  120.         files = os.listdir(directory)
  121.         total = 0
  122.         #correct = 0
  123.         for file in files:
  124.             total += 1
  125.             result = self.classify(directory + file)
  126.             results.setdefault(result, 0)
  127.             results[result] += 1
  128.             #if result == category:
  129.             #               correct += 1
  130.         return results
  132.     # input: 测试文件目录， 忽略的子集文件
  133.     # return: 所有类别的分类结果{1:{0:12,1：23},}
  134.     def test(self, testdir, bucketNumber):
  135.         """Test all files in the test directory--that directory is
  136.         organized into subdirectories--each subdir is a classification
  137.         category"""
  138.         results = {}
  139.         categories = os.listdir(testdir)
  140.         #filter out files that are not directories
  141.         categories = [filename for filename in categories if
  142.                       os.path.isdir(testdir + filename)]
  143.         for category in categories:
  144.             #print(".", end="")
  145.             results[category] = self.testCategory(
  146.                 testdir + category + '/', category, bucketNumber)
  147.         return results
  149. def tenfold(dataPrefix, stoplist):
  150.     results = {}
  151.     for i in range(0,10):
  152.         bT = BayesText(dataPrefix, stoplist, i)
  153.         r = bT.test(theDir, i)
  154.         for (key, value) in r.items():
  155.             results.setdefault(key, {})
  156.             for (ckey, cvalue) in value.items():
  157.                 results[key].setdefault(ckey, 0)
  158.                 results[key][ckey] += cvalue
  159.                 categories = list(results.keys())
  160.     categories.sort()
  161.     print(   "\n       Classified as: ")
  162.     header =    "          "
  163.     subheader = "        +"
  164.     for category in categories:
  165.         header += "% 2s   " % category
  166.         subheader += "-----+"
  167.     print (header)
  168.     print (subheader)
  169.     total = 0.0
  170.     correct = 0.0
  171.     for category in categories:
  172.         row = " %s    |" % category 
  173.         for c2 in categories:
  174.             if c2 in results[category]:
  175.                 count = results[category][c2]
  176.             else:
  177.                 count = 0
  178.             row += " %3i |" % count
  179.             total += count
  180.             if c2 == category:
  181.                 correct += count
  182.         print(row)
  183.     print(subheader)
  184.     print("\n%5.3f percent correct" %((correct * 100) / total))
  185.     print("total of %i instances" % total)
  187. # change these to match your directory structure
  188. prefixPath = "data/review_polarity/"
  189. theDir = prefixPath + "/txt_sentoken/"
  190. stoplistfile = prefixPath + "stopwords25.txt"
  191. tenfold(theDir, stoplistfile)

聚类--群组发现

层次聚类：每次迭代将最相似的两个簇合并，不断重复直至只有一个簇。两个簇距离计算方法不一样，聚类的方法就不一样，合并的过程也不一样。

常规队列：先进先出

优先级队列：去除次序基于队列元素的关联权重，数值越小先去除。

  1. # 从队列中获得数据的最小值
  2. from Queue import PriorityQueue
  4. singersQueue = PriorityQueue()
  5. singersQueue.put((16, 'Suzaka'))
  6. singersQueue.put((14, 'Yui'))
  7. singersQueue.put((15, 'Moa'))
  8. print singersQueue.get()
  9. print singersQueue.get()
  10. print singersQueue.get()
  1. class hClusterer:
  2.     """ this clusterer assumes that the first column of the data is a label
  3.     not used in the clustering. The other columns contain numeric data"""
  5.     def __init__(self, filename):
  6.         file = open(filename)
  7.         self.data = {}
  8.         self.counter = 0
  9.         self.queue = PriorityQueue()
  10.         lines = file.readlines()
  11.         file.close()
  12.         header = lines[0].split(',')
  13.         self.cols = len(header)
  14.         self.data = [[] for i in range(len(header))]
  15.         for line in lines[1:]:
  16.             cells = line.split(',')
  17.             toggle = 0
  18.             # self.data [['Border Collie',...], [20.0,...], [45.0,...]]
  19.             for cell in range(self.cols):
  20.                 if toggle == 0:
  21.                    self.data[cell].append(cells[cell])
  22.                    toggle = 1
  23.                 else:
  24.                     self.data[cell].append(float(cells[cell]))
  25.         # now normalize number columns (that is, skip the first column)
  26.         for i in range(1, self.cols):
  27.                 self.data[i] = normalizeColumn(self.data[i])
  29.         ###
  30.         ###  I have read in the data and normalized the 
  31.         ###  columns. Now for each element i in the data, I am going to
  32.         ###     1. compute the Euclidean Distance from element i to all the 
  33.         ###        other elements.  This data will be placed in neighbors,
  34.         ###        which is a Python dictionary. Let's say i = 1, and I am 
  35.         ###        computing the distance to the neighbor j and let's say j 
  36.         ###        is 2. The neighbors dictionary for i will look like
  37.         ###        {2: ((1,2), 1.23),  3: ((1, 3), 2.3)... }
  38.         ###
  39.         ###     2. find the closest neighbor
  40.         ###
  41.         ###     3. place the element on a priority queue, called simply queue,
  42.         ###        based on the distance to the nearest neighbor (and a counter
  43.         ###        used to break ties.
  47.         # now push distances on queue        
  48.         rows = len(self.data[0])              
  50.         for i in range(rows):
  51.             minDistance = 99999
  52.             nearestNeighbor = 0
  53.             neighbors = {}  #存储所有邻居的对和距离
  54.             for j in range(rows):
  55.                 if i != j:
  56.                     dist = self.distance(i, j)
  57.                     if i < j:
  58.                         pair = (i,j)
  59.                     else:
  60.                         pair = (j,i)
  61.                     neighbors[j] = (pair, dist)
  62.                     if dist < minDistance:
  63.                         minDistance = dist
  64.                         nearestNeighbor = j
  65.                         # nearestNum = j
  66.             # create nearest Pair
  67.             if i < nearestNeighbor:
  68.                 nearestPair = (i, nearestNeighbor)
  69.             else:
  70.                 nearestPair = (nearestNeighbor, i)
  72.             # put instance on priority queue    
  73.             self.queue.put((minDistance, self.counter,
  74.                             [[self.data[0][i]], nearestPair, neighbors]))
  75.             self.counter += 1   #存储对象的数量，先后顺序
  78.     def distance(self, i, j):
  79.         sumSquares = 0
  80.         for k in range(1, self.cols):
  81.             sumSquares += (self.data[k][i] - self.data[k][j])**2
  82.         return math.sqrt(sumSquares)
  85.     def cluster(self):
  86.          done = False
  87.          while not done:
  88.              # 依据 minDistance 取出当前最小距离的对象,应该是两对距离。
  89.              topOne = self.queue.get()
  90.              nearestPair = topOne[2][1]
  91.              if not self.queue.empty():
  92.                  nextOne = self.queue.get()
  93.                  nearPair = nextOne[2][1]       #当等距离时，不一定一样的
  94.                  tmp = []
  95.                  ##
  96.                  ##  I have just popped two elements off the queue,
  97.                  ##  topOne and nextOne. I need to check whether nextOne
  98.                  ##  is topOne's nearest neighbor and vice versa.
  99.                  ##  If not, I will pop another element off the queue
  100.                  ##  until I find topOne's nearest neighbor. That is what
  101.                  ##  this while loop does.
  102.                  ## 
  103.                  # 处理等距离的情况
  104.                  while nearPair != nearestPair:
  105.                      tmp.append((nextOne[0], self.counter, nextOne[2]))
  106.                      self.counter += 1
  107.                      nextOne = self.queue.get()
  108.                      nearPair = nextOne[2][1]
  109.                  ##
  110.                  ## this for loop pushes the elements I popped off in the
  111.                  ## above while loop.
  112.                  ## 放回等距离不配对的对象               
  113.                  for item in tmp:
  114.                      self.queue.put(item)
  116.                  if len(topOne[2][0]) == 1:
  117.                     item1 = topOne[2][0][0]
  118.                  else:
  119.                      item1 = topOne[2][0]
  120.                  if len(nextOne[2][0]) == 1:
  121.                     item2 = nextOne[2][0][0]
  122.                  else:
  123.                      item2 = nextOne[2][0]
  124.                  ##  curCluster is, perhaps obviously, the new cluster
  125.                  ##  which combines cluster item1 with cluster item2.
  126.                  curCluster = (item1, item2)
  128.                  ## Now I am doing two things. First, finding the nearest
  129.                  ## neighbor to this new cluster. Second, building a new
  130.                  ## neighbors list by merging the neighbors lists of item1
  131.                  ## and item2. If the distance between item1 and element 23
  132.                  ## is 2 and the distance betweeen item2 and element 23 is 4
  133.                  ## the distance between element 23 and the new cluster will
  134.                  ## be 2 (i.e., the shortest distance).
  135.                  ##
  137.                  minDistance = 99999
  138.                  nearestPair = ()
  139.                  #nearestNeighbor = ''
  140.                  merged = {}
  141.                  nNeighbors = nextOne[2][2] #所有的邻居对和距离
  142.                  for (key, value) in topOne[2][2].items():
  143.                     if key in nNeighbors:           #只剩下最后一个的时候，不成立
  144.                         if nNeighbors[key][1] < value[1]:
  145.                              dist =  nNeighbors[key]
  146.                         else:
  147.                             dist = value
  148.                         if dist[1] < minDistance:
  149.                              minDistance =  dist[1]
  150.                              nearestPair = dist[0]      #这里的对比较特别，只去了其中一个点
  151.                              #nearestNeighbor = key
  152.                         merged[key] = dist
  154.                  if merged == {}:
  155.                     return curCluster#返回元祖对，用来建立树
  156.                  else:
  157.                     self.queue.put( (minDistance, self.counter,
  158.                                      [curCluster, nearestPair, merged]))
  159.                     self.counter += 1

KMeans

这个算法和爬山法类似，不能保证最后能够找到最有的划分簇。因为算法一开始选择的是随机中心点的集合，所以只能确保找到局部最有划分簇。

误差平方和(sum of squared error,简称SSE)：度量某个簇集合的质量。 

  1. import math
  2. import random 
  4. """
  5. Implementation of the K-means algorithm
  6. for the book A Programmer's Guide to Data Mining"
  7. http://www.guidetodatamining.com
  9. """
  11. def getMedian(alist):
  12.     """get median of list"""
  13.     tmp = list(alist)
  14.     tmp.sort()
  15.     alen = len(tmp)
  16.     if (alen % 2) == 1:
  17.         return tmp[alen // 2]
  18.     else:
  19.         return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2
  22. def normalizeColumn(column):
  23.     """normalize the values of a column using Modified Standard Score
  24.     that is (each value - median) / (absolute standard deviation)"""
  25.     median = getMedian(column)
  26.     asd = sum([abs(x - median) for x in column]) / len(column)
  27.     result = [(x - median) / asd for x in column]
  28.     return result
  31. class kClusterer:
  32.     """ Implementation of kMeans Clustering
  33.     This clusterer assumes that the first column of the data is a label
  34.     not used in the clustering. The other columns contain numeric data
  35.     """
  37.     def __init__(self, filename, k):
  38.         """ k is the number of clusters to make
  39.         This init method:
  40.            1. reads the data from the file named filename
  41.            2. stores that data by column in self.data
  42.            3. normalizes the data using Modified Standard Score
  43.            4. randomly selects the initial centroids
  44.            5. assigns points to clusters associated with those centroids
  45.         """
  46.         file = open(filename)
  47.         self.data = {}
  48.         self.k = k
  49.         self.counter = 0
  50.         self.iterationNumber = 0
  51.         # used to keep track of % of points that change cluster membership
  52.         # in an iteration
  53.         self.pointsChanged = 0
  54.         # Sum of Squared Error
  55.         self.sse = 0
  56.         #
  57.         # read data from file
  58.         #
  59.         lines = file.readlines()
  60.         file.close()
  61.         header = lines[0].split(',')
  62.         self.cols = len(header)
  63.         self.data = [[] for i in range(len(header))]
  64.         # we are storing the data by column.
  65.         # For example, self.data[0] is the data from column 0.
  66.         # self.data[0][10] is the column 0 value of item 10.
  67.         for line in lines[1:]:
  68.             cells = line.split(',')
  69.             toggle = 0
  70.             for cell in range(self.cols):
  71.                 if toggle == 0:
  72.                    self.data[cell].append(cells[cell])
  73.                    toggle = 1
  74.                 else:
  75.                     self.data[cell].append(float(cells[cell]))
  77.         self.datasize = len(self.data[1])
  78.         self.memberOf = [-1 for x in range(len(self.data[1]))]
  79.         #
  80.         # now normalize number columns
  81.         #
  82.         for i in range(1, self.cols):
  83.                 self.data[i] = normalizeColumn(self.data[i])
  85.         # select random centroids from existing points
  86.         random.seed()
  87.         #sample(seq, n) 从序列seq中选择n个随机且独立的元素
  88.         self.centroids = [[self.data[i][r]  for i in range(1, len(self.data))]
  89.                            for r in random.sample(range(len(self.data[0])),
  90.                                                  self.k)]
  91.         self.assignPointsToCluster()
  95.     def updateCentroids(self):
  96.         """Using the points in the clusters, determine the centroid
  97.         (mean point) of each cluster"""
  98.         members = [self.memberOf.count(i) for i in range(len(self.centroids))]#计数列表
  99.         #对centroid类的数据的第k列数据 第i个中心点求和，计算平均        
  100.         self.centroids = [[sum([self.data[k][i]
  101.                                 for i in range(len(self.data[0]))
  102.                                 if self.memberOf[i] == centroid])/members[centroid]
  103.                            for k in range(1, len(self.data))]
  104.                           for centroid in range(len(self.centroids))] 
  108.     def assignPointToCluster(self, i):
  109.         """ assign point to cluster based on distance from centroids"""
  110.         min = 999999
  111.         clusterNum = -1
  112.         for centroid in range(self.k):
  113.             dist = self.euclideanDistance(i, centroid)
  114.             if dist < min:
  115.                 min = dist
  116.                 clusterNum = centroid
  117.         # here is where I will keep track of changing points
  118.         if clusterNum != self.memberOf[i]:      #第一次认为全部变动
  119.             self.pointsChanged += 1
  120.         # add square of distance to running sum of squared error
  121.         self.sse += min**2
  122.         return clusterNum
  124.     def assignPointsToCluster(self):
  125.         """ assign each data point to a cluster"""
  126.         self.pointsChanged = 0
  127.         self.sse = 0
  128.         self.memberOf = [self.assignPointToCluster(i)
  129.                          for i in range(len(self.data[1]))]
  133.     def euclideanDistance(self, i, j):
  134.         """ compute distance of point i from centroid j"""
  135.         sumSquares = 0
  136.         for k in range(1, self.cols):
  137.             sumSquares += (self.data[k][i] - self.centroids[j][k-1])**2
  138.         return math.sqrt(sumSquares)
  140.     def kCluster(self):
  141.         """the method that actually performs the clustering
  142.         As you can see this method repeatedly
  143.             updates the centroids by computing the mean point of each cluster
  144.             re-assign the points to clusters based on these new centroids
  145.         until the number of points that change cluster membership is less than 1%.
  146.         """
  147.         done = False
  149.         while not done:
  150.             self.iterationNumber += 1
  151.             self.updateCentroids()
  152.             self.assignPointsToCluster()
  153.             #
  154.             # we are done if fewer than 1% of the points change clusters
  155.             #
  156.             if float(self.pointsChanged) / len(self.memberOf) <  0.01:
  157.                 done = True
  158.         print("Final SSE: %f" % self.sse)
  160.     def showMembers(self):
  161.         """Display the results"""
  162.         for centroid in range(len(self.centroids)):
  163.              print ("\n\nClass %i\n========" % centroid)
  164.              for name in [self.data[0][i]  for i in range(len(self.data[0]))
  165.                           if self.memberOf[i] == centroid]:
  166.                  print (name)
  168. ##
  169. ## RUN THE K-MEANS CLUSTERER ON THE DOG DATA USING K = 3
  170. ###
  171. # change the path in the following to match where dogs.csv is on your machine
  172. km = kClusterer('data/dogs.csv', 3)
  173. km.kCluster()
  174. km.showMembers()

K-means++通过修改初始中心点的选择方法改进了由于初始的随机性导致的结果非优的缺点。虽然第一个点选择是随机的，但其他的点则优先选择那些彼此距离很远的点。

选择初始中心点的步骤：

  1.     def selectInitialCentroids(self):
  2.         """implement the k-means++ method of selecting
  3.         the set of initial centroids"""
  4.         centroids = []
  5.         total = 0
  6.         # first step is to select a random first centroid
  7.         current = random.choice(range(len(self.data[0])))
  8.         centroids.append(current)
  9.         # loop to select the rest of the centroids, one at a time
  10.         for i in range(0, self.k - 1):
  11.             # for every point in the data find its distance to
  12.             # the closest centroid
  13.             weights = [self.distanceToClosestCentroid(x, centroids) 
  14.                        for x in range(len(self.data[0]))]
  15.             total = sum(weights)
  16.             # instead of raw distances, convert so sum of weight = 1
  17.             weights = [x / total for x in weights]
  18.             #
  19.             # now roll virtual die
  20.             num = random.random()
  21.             total = 0
  22.             x = -1
  23.             # the roulette wheel simulation
  24.             while total < num:
  25.                 x += 1
  26.                 total += weights[x]
  27.             centroids.append(x)
  28.         self.centroids = [[self.data[i][r]  for i in range(1, len(self.data))]
  29.                             for r in centroids]
  31.     def distanceToClosestCentroid(self, point, centroidList):
  32.         result = self.eDistance(point, centroidList[0])
  33.         for centroid in centroidList[1:]:
  34.             distance = self.eDistance(point, centroid)
  35.             if distance < result:
  36.                 result = distance
  37.         return result
  39.     def eDistance(self, i, j):
  40.         """ compute distance of point i from centroid j"""
  41.         sumSquares = 0
  42.         for k in range(1, self.cols):
  43.             sumSquares += (self.data[k][i] - self.data[k][j])**2
  44.         return math.sqrt(sumSquares)
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注