In [34]:
# Solution
import numpy as np
import math
def dist(pt1, pt2):
return math.sqrt( (pt1[0] - pt2[0])**2 + (pt1[1] - pt2[1])**2 )
pts1 = [ (25,125), (44,105), (29,97), (35, 63), (55, 63), (42, 57), (23, 40), (64,37), (33,22), (55,20) ]
pts2 = [ (28,145), (38,115), (50,130),(65,140), (55,118), (50, 90), (43, 83), (63,88), (50,60), (50,30) ]
clusters = [ [pt] for pt in pts1]
# simulate pass 1
for pt2 in pts2:
minDist = 9999
minIdx = None
# find the closest centroid
for idx, pt1 in enumerate(pts1):
if minDist > dist(pt1, pt2):
minDist = dist(pt1, pt2)
minIdx = idx
clusters[minIdx].append(pt2)
centroids = [ [ sum(y) / float(len(y)) for y in zip(*parray) ] for parray in clusters]
# print centroids after RECOMPUTATION
print ", ".join([ "({0:.1f} {1:.1f})".format(*pt) for pt in centroids])
In [33]:
def assign_cluster(yellow_centroid, blue_centroid, ul, lr):
if dist(ul, yellow_centroid) <= dist(ul, blue_centroid ) and \
dist(lr, yellow_centroid) <= dist(lr, blue_centroid ) :
print "yellow"
elif dist(ul, yellow_centroid) > dist(ul, blue_centroid ) and \
dist(lr, yellow_centroid) > dist(lr, blue_centroid ) :
print "blue"
else:
print "none clustered"
#option 1
print "Option 1"
assign_cluster((5,10) , (20,5), (6,7), (11,14))
assign_cluster((5,10) , (20,5), (11,5), (17,2))
#option 2
print "Option 2"
assign_cluster((5,10) , (20,5), (6,7), (11,4))
assign_cluster((5,10) , (20,5), (14,10), (23,6))
#option 3
print "Option 3"
assign_cluster((5,10) , (20,5), (3,15), (13,7))
assign_cluster((5,10) , (20,5), (11,5), (17,2))
#option 4
print "Option 3"
assign_cluster((5,10) , (20,5), (3,15), (13,7))
assign_cluster((5,10) , (20,5), (14,10), (23,6))
In [36]:
import numpy as np
mat = np.array([[1, 0, 0], [0, 2, 0], [0, 0, 0]])
pinv = np.linalg.pinv(mat)
print pinv
Ad Bid CTR1 CTR2 CTR3 Budget A $.10 .015 .010 .005 $1 B $.09 .016 .012 .006 $2 C $.08 .017 .014 .007 $3 D $.07 .018 .015 .008 $4 E $.06 .019 .016 .010 $5
The publisher uses the following strategy to allocate the three ad slots:
Either of these events ends one phase of the allocation. If a phase ends because an advertiser ran out of budget, then they are assumed to get all the clicks their budget buys. During the same phase, we calculate the number of click-throughs received by the other two advertisers by assuming that all three received click-throughs in proportion to their respective CTR's for their positions (round to the nearest integer). If click-throughs remain, the publisher reallocates all three slots and starts a new phase.
If the phase ends because all click-throughs have been allocated, assume that the three advertisers received click-throughs in proportion to their respective CTR's (again, rounding if necessary).
Your task is to simulate the allocation of slots and to determine how many click-throughs each of the five advertisers get.
In [49]:
import numpy as np
print "slot 1 ============"
slot1 = .10 * .015
print slot1
slot1 = .09 * .016
print slot1
slot1 = .08 * .017
print slot1
slot1 = .07 * .018
print slot1
slot1 = .06 * .019
print slot1
print "slot 2 ============"
slot2 = .10 * .10
print slot2
slot2 = .09 * .12
print slot2
slot2 = .08 * .14
print slot2
slot2 = .07 * .15
print slot2
slot2 = .06 * .16
print slot2
print "slot 3 ============"
slot3 = .10 * .005
print slot3
slot3 = .09 * .006
print slot3
slot3 = .08 * .007
print slot3
slot3 = .07 * .008
print slot3
slot3 = .06 * .010
print slot3
# Program for simulating the process
In [44]:
clustered_pts = [(0, 0), (10, 10)]
unclustered_pts = [(1,6), (3,7), (4,3), (7,7), (8,2), (9,5)]
def dist(pt1, pt2):
return (pt1[0] - pt2[0])**2 + (pt1[1] - pt2[1])**2
for i in xrange(5):
representative = (0,0)
maxDist = 0
for pt1 in unclustered_pts:
# find the closest centroid
minDist = 9999
for idx, pt2 in enumerate(clustered_pts):
if minDist > float(dist(pt1, pt2)):
minDist = float(dist(pt1, pt2))
if maxDist < minDist:
maxDist = minDist
representative = pt1
print maxDist
print "point ({0}, {1}) added to cluster".format(*representative)
unclustered_pts.remove(representative)
clustered_pts.append(representative)
In [ ]: