活跃农民
- 积分
- 518
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-3-21
- 最后登录
- 1970-1-1
|
"""Utilities for Maps"""
from math import sqrt
from random import sample
# Rename the built-in zip (http://docs.python.org/3/library/functions.html#zip)
_zip = zip
def map_and_filter(s, map_fn, filter_fn):
"""Return a new list containing the result of calling MAP_FUNC on each
element of sequence S for which FILTER_FUNC returns a true value.
>>> square = lambda x: x * x
>>> is_odd = lambda x: x % 2 == 1
>>> map_and_filter([1, 2, 3, 4, 5], square, is_odd)
[1, 9, 25]
"""
return [map_fn(x) for x in s if filter_fn(x)]
def key_of_min_value(d):
"""Returns the key in dict D that corresponds to the minimum value of D.
>>> letters = {'a': 6, 'b': 5, 'c': 4, 'd': 5}
>>> min(letters)
'a'
>>> key_of_min_value(letters)
'c'
"""
return min([k for k in d.keys()], key = lambda x: d[x])
def zip(*sequences):
"""Returns a list of lists, where the i-th list contains the i-th
element from each of the argument sequences.
>>> zip(range(0, 3), range(3, 6))
[[0, 3], [1, 4], [2, 5]]
>>> for a, b in zip([1, 2, 3], [4, 5, 6]):
... print(a, b)
1 4
2 5
3 6
>>> for triple in zip(['a', 'b', 'c'], [1, 2, 3], ['do', 're', 'mi']):
... print(triple)
['a', 1, 'do']
['b', 2, 're']
['c', 3, 'mi']
"""
return list(map(list, _zip(*sequences)))
def enumerate(s, start=0):
"""Returns a list of lists, where the i-th list contains i+start and the
i-th element of the sequence.
>>> enumerate([6, 1, 'a'])
[[0, 6], [1, 1], [2, 'a']]
>>> enumerate('five', 5)
[[5, 'f'], [6, 'i'], [7, 'v'], [8, 'e']]
"""
return zip([i+start for i in range(len(s))],s)
def distance(pos1, pos2):
"""Return the Euclidean distance between POS1 and POS2, which are pairs.
>>> distance([1, 2], [4, 6])
5.0
"""
return sqrt((pos1[0] - pos2[0]) ** 2 + (pos1[1] - pos2[1]) ** 2)
def mean(lst):
"""Return the arithmetic mean of a sequence of numbers.
>>> mean([-1, 3])
1.0
>>> mean([0, -3, 2, -1])
-0.5
"""
assert len(lst) > 0, 'cannot find mean of empty sequence'
return sum(lst) / len(lst)
"""Data Abstractions"""
from utils import mean
# Reviews
def make_review(restaurant_name, rating):
"""Return a review."""
return [restaurant_name, rating]
def review_restaurant_name(review):
"""Return the reviewed restaurant's name (string)."""
return review[0]
def review_rating(review):
"""Return the number of stars given (1 to 5)."""
return review[1]
# Users
def make_user(name, reviews):
"""Return a user."""
return [name, {review_restaurant_name(r): r for r in reviews}]
def user_name(user):
"""Return the USER's name (string)."""
return user[0]
def user_reviews(user):
"""Return a dictionary from restaurant names to reviews by the USER."""
return user[1]
### === +++ USER ABSTRACTION BARRIER +++ === ###
def user_reviewed_restaurants(user, restaurants):
"""Return the subset of restaurants reviewed by USER.
Arguments:
user -- a user
restaurants -- a dictionary from restaurant names to restaurants
"""
names = user_reviews(user).keys()
return {name: restaurants[name] for name in names if name in restaurants}
def user_rating(user, restaurant_name):
"""Return the rating given for RESTAURANT_NAME by USER."""
return review_rating(user_reviews(user)[restaurant_name])
# Restaurants
def make_restaurant(name, location, categories, price, reviews):
"""Return a restaurant, implemented as a dictionary."""
# You may change this starter implementation however you wish, including
# adding more items to the dictionary below.
return {'name': name,
'location': location,
'categories': categories,
'price': price,
'reviews': reviews
}
def restaurant_name(restaurant):
return restaurant['name']
def restaurant_location(restaurant):
return restaurant['location']
def restaurant_categories(restaurant):
return restaurant['categories']
def restaurant_price(restaurant):
return restaurant['price']
def restaurant_ratings(restaurant):
"""Return a list of ratings (numbers from 1 to 5)."""
return [review_rating(r) for r in restaurant['reviews']]
### === +++ RESTAURANT ABSTRACTION BARRIER +++ === ###
def restaurant_num_ratings(restaurant):
"""Return the number of ratings for RESTAURANT."""
return len(restaurant_ratings(restaurant))
def restaurant_mean_rating(restaurant):
"""Return the average rating for RESTAURANT."""
return mean(restaurant_ratings(restaurant))
"""A Yelp-powered Restaurant Recommendation Program"""
from abstractions import *
from utils import distance, mean, zip, enumerate, sample
from visualize import draw_map
from data import RESTAURANTS, CATEGORIES, USER_FILES, load_user_file
from ucb import main, trace, interact
def find_closest(location, centroids):
"""Return the item in CENTROIDS that is closest to LOCATION. If two
centroids are equally close, return the first one.
>>> find_closest([3, 4], [[0, 0], [2, 3], [4, 3], [5, 5]])
[2, 3]
"""
return min([l for l in centroids], key = lambda x: distance(location,x))
def group_by_first(pairs):
"""Return a list of pairs that relates each unique key in [key, value]
pairs to a list of all values that appear paired with that key.
Arguments:
pairs -- a sequence of pairs
>>> example = [ [1, 2], [3, 2], [2, 4], [1, 3], [3, 1], [1, 2] ]
>>> group_by_first(example)
[[2, 3, 2], [2, 1], [4]]
"""
# Optional: This implementation is slow because it traverses the list of
# pairs one time for each key. Can you improve it?
keys = []
for key, _ in pairs:
if key not in keys:
keys.append(key)
return [[y for x, y in pairs if x == key] for key in keys]
def group_by_centroid(restaurants, centroids):
"""Return a list of lists, where each list contains all restaurants nearest
to some item in CENTROIDS. Each item in RESTAURANTS should appear once in
the result, along with the other restaurants nearest to the same centroid.
No empty lists should appear in the result.
"""
return group_by_first([[find_closest(restaurant_location(r), centroids),
r] for r in restaurants ])
def find_centroid(restaurants):
"""Return the centroid of the locations of RESTAURANTS."""
locations = [restaurant_location(r) for r in restaurants]
return[mean([x[0] for x in locations]), mean([x[1] for x in locations])]
def k_means(restaurants, k, max_updates=100):
"""Use k-means to group RESTAURANTS by location into K clusters."""
assert len(restaurants) >= k, 'Not enough restaurants to cluster'
old_centroids, n = [], 0
# Select initial centroids randomly by choosing K different restaurants
centroids = [restaurant_location(r) for r in sample(restaurants, k)]
while old_centroids != centroids and n < max_updates:
old_centroids = centroids
clusters = group_by_centroid(restaurants,old_centroids)
centroids = [find_centroid(r) for r in clusters if len(r)!=0]
n += 1
return centroids
def find_predictor(user, restaurants, feature_fn):
"""Return a rating predictor (a function from restaurants to ratings),
for USER by performing least-squares linear regression using FEATURE_FN
on the items in RESTAURANTS. Also, return the R^2 value of this model.
Arguments:
user -- A user
restaurants -- A sequence of restaurants
feature_fn -- A function that takes a restaurant and returns a number
"""
reviews_by_user = {review_restaurant_name(review): review_rating(review)
for review in user_reviews(user).values()}
xs = [feature_fn(r) for r in restaurants]
ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]
meanx = mean(xs)
meany = mean(ys)
sxx = sum([pow(x - meanx, 2) for x in xs])
syy = sum([pow(y - meany, 2) for y in ys])
sxy = sum([(x-meanx)*(y-meany) for x,y in zip(xs,ys)])
b, a, r_squared = sxy/sxx, meany-sxy/sxx*meanx, pow(sxy, 2)/(sxx*syy)
def predictor(restaurant):
return b * feature_fn(restaurant) + a
return predictor, r_squared
def best_predictor(user, restaurants, feature_fns):
"""Find the feature within FEATURE_FNS that gives the highest R^2 value
for predicting ratings by the user; return a predictor using that feature.
Arguments:
user -- A user
restaurants -- A dictionary from restaurant names to restaurants
feature_fns -- A sequence of functions that each takes a restaurant
"""
reviewed = list(user_reviewed_restaurants(user, restaurants).values())
return max([find_predictor(user, reviewed, f) for f in feature_fns], key = lambda x: x[1])[0]
def rate_all(user, restaurants, feature_functions):
"""Return the predicted ratings of RESTAURANTS by USER using the best
predictor based a function from FEATURE_FUNCTIONS.
Arguments:
user -- A user
restaurants -- A dictionary from restaurant names to restaurants
"""
# Use the best predictor for the user, learned from *all* restaurants
# (Note: the name RESTAURANTS is bound to a dictionary of all restaurants)
predictor = best_predictor(user, RESTAURANTS, feature_functions)
user_reviewed = user_reviewed_restaurants(user, restaurants)
d = {}
for name in restaurants.keys():
if name in user_reviewed.keys():
d[name] = user_rating(user, name)
else:
d[name] = predictor(RESTAURANTS[name])
return d
def search(query, restaurants):
"""Return each restaurant in RESTAURANTS that has QUERY as a category.
Arguments:
query -- A string
restaurants -- A sequence of restaurants
"""
return [r for r in restaurants if query in restaurant_categories(r)]
def feature_set():
"""Return a sequence of feature functions."""
return [restaurant_mean_rating,
restaurant_price,
restaurant_num_ratings,
lambda r: restaurant_location(r)[0],
lambda r: restaurant_location(r)[1]]
@main
def main(*args):
import argparse
parser = argparse.ArgumentParser(
description='Run Recommendations',
formatter_class=argparse.RawTextHelpFormatter
)
parser.add_argument('-u', '--user', type=str, choices=USER_FILES,
default='test_user',
metavar='USER',
help='user file, e.g.\n' +
'{{{}}}'.format(','.join(sample(USER_FILES, 3))))
parser.add_argument('-k', '--k', type=int, help='for k-means')
parser.add_argument('-q', '--query', choices=CATEGORIES,
metavar='QUERY',
help='search for restaurants by category e.g.\n'
'{{{}}}'.format(','.join(sample(CATEGORIES, 3))))
parser.add_argument('-p', '--predict', action='store_true',
help='predict ratings for all restaurants')
args = parser.parse_args()
# Select restaurants using a category query
if args.query:
results = search(args.query, RESTAURANTS.values())
restaurants = {restaurant_name(r): r for r in results}
else:
restaurants = RESTAURANTS
# Load a user
assert args.user, 'A --user is required to draw a map'
user = load_user_file('{}.dat'.format(args.user))
# Collect ratings
if args.predict:
ratings = rate_all(user, restaurants, feature_set())
else:
restaurants = user_reviewed_restaurants(user, restaurants)
ratings = {name: user_rating(user, name) for name in restaurants}
# Draw the visualization
restaurant_list = list(restaurants.values())
if args.k:
centroids = k_means(restaurant_list, min(args.k, len(restaurant_list)))
else:
centroids = [restaurant_location(r) for r in restaurant_list]
draw_map(centroids, restaurant_list, ratings)
|
|
狗仔卡
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
