Ich arbeite an einem Algorithmus für das automatische Bieten von Werbung (obwohl dies bald in der Vergangenheit sein wird). Es ist überhaupt kein Protokoll gespeichert. Daher hatte ich keine andere Wahl, als Daten zu generieren und die Simulation unvermeidlich durchzuführen.
Die Mehrzweckoptimierung wird in [Buch] beschrieben (http://www.amazon.co.jp/gp/product/4061565109/ref=as_li_tf_tl?ie=UTF8&camp=247&creative=1211&creativeASIN=4061565109&linkCode=as2&tag0-2). Es gibt eine Beschreibung wie folgt.
Berücksichtigen Sie bei der Optimierung mehrerer Ziele die Minimierung mehrerer Zielfunktionen $ \ bf {f} $. Im Idealfall wäre es schön, alle Zielfunktionen $ f_1 $, ..., $ f_k $ gleichzeitig minimieren zu können. Dies bedeutet jedoch, dass es überhaupt nicht notwendig war, es als Mehrzieloptimierung zu lösen. Dies liegt daran, dass durch das Minimieren einer Zielfunktion gleichzeitig die anderen Zielfunktionen minimiert werden. Daher besteht das Problem, das normalerweise bei der Optimierung mehrerer Ziele behandelt werden sollte, darin, dass zwischen den Zielfunktionen $ \ bf {f} $ eine Kompromissbeziehung besteht, sodass der Versuch, eine Zielfunktion kleiner zu machen, dazu führt, dass die anderen Zielfunktionen größer werden. Es gibt einen Fall. (Zitiert aus dem praktischen Leitfaden zur mathematischen Optimierung, S. 110)
Mit anderen Worten, lassen Sie uns den Wert der Zielfunktion in einer Situation minimieren (maximieren), in der "wenn Sie sie einrichten, können Sie hier nicht aufstehen". Grundsätzlich finden Sie eine Pareto-Lösung. Es gibt verschiedene Methoden, und die Methode unterscheidet sich je nachdem, ob die Pareto-Front konvex oder nicht konvex ist. 50 für die Anwendung nützliche Optimierungsprobleme (Anwendungsoptimierungsserie) für bestimmte Methoden = 1211 & creativeASIN = 4254117884 & linkCode = as2 & tag = shimashimao06-22 "> 50 Optimierungsprobleme, die für die Anwendung nützlich sind (Anwendungsoptimierungsserie) ) Wird hilfreich sein. Diesmal habe ich jedoch eine heuristische Methode gewählt, weil ich Berechnungen mit hoher Geschwindigkeit durchführen und für ein ziemlich feines Zeitfenster optimieren wollte.
Klicken Sie hier für Referenzen. Real time bid optimization with smooth budget delivery in online advertising, Lee+, Turn Inc.,'13 [PDF] Den Inhalt finden Sie unter slidshare. .. (Wenn Sie sich das jetzt ansehen, ist der Interpretationsteil ein wenig falsch ... Ich werde ihn korrigieren, wenn Sie Lust dazu haben w)
Der Code wird basierend auf diesem Dokument erstellt. Die Teile, die Zeit zum Generieren von Daten benötigen, werden jedoch weggelassen. Wie ich zu Beginn schrieb, habe ich, da keine Daten vorhanden sind, einen Benutzeragenten und einen Gebotsagenten eingerichtet, um ein Pseudo-Gebot abzugeben. Das Zeitfenster ist auf 1 Minute eingestellt, das Budget wird verteilt und der Gebotsbetrag für jedes Zeitfenster optimiert.
Unten ist der Code, den ich erstellt habe. Da es von einem Nicht-Ingenieur geschrieben wurde, gibt es meiner Meinung nach viele Dinge zu tun, aber bitte haben Sie etwas Geduld.
Erstellen Sie eine Site, damit ein Benutzeragent die Site besuchen kann.
python
# coding: utf-8
import random
class Agent:
def __init__(self,num):
random.seed(num) #Vorkommen von zufälligem Samen
self.ctr = random.uniform(0,1)
def get_ctr(self):
return self.ctr
def get_visiter_ctr(self, pred):
if random.uniform(0,1) > (1-pred):
return self.get_ctr()
else: return False
Erstellen Sie als Nächstes einen Agenten (Konkurrenten), um zu bieten.
python
# coding: utf-8
import random
from math import ceil
class Agent:
def __init__(self,n):
random.seed(n) #Vorkommen von zufälligem Samen
self.ctr = random.uniform(0,1)
self.maxprice = random.randint(40,90)
def get_maxprice(self):
return self.maxprice
def get_bid_price(self, ctr, pred):
price = self.maxprice*ctr*pred
if random.uniform(0,1) > 0.35 :
return ceil(price) + random.randint(0,5)
else:
return False
So schreiben Sie den Code des Optimierungsteils.
python
# coding:utf-8
#cython: boundscheck=False
#cython: wraparound=False
import pyximport; pyximport.install()
from math import sin, cos, pi, fmod, sqrt, floor
import random
import useragent
import bidagent
import numpy as np
cimport numpy as np
cimport cython
DTYPE = np.float64
INTTYPE = np.int64
ctypedef np.float64_t DTYPE_t
ctypedef np.int64_t INTTYPE_t
cdef extern from 'stdlib.h':
ctypedef unsigned long size_t
void *malloc(size_t size)
void free(void *prt)
class CreatePredict:
pi2 = 2*pi
#random.seed(3)
PHI = 2*pi/8 #Darstellung der Phasenverschiebung
# TBit = 10000000.0
def __init__(self, period, agent_num):
self.minbit = 1000*agent_num/1000
self.E = 1250*agent_num/1000
self.PERIOD = period
self.OMEGA = self.pi2/self.PERIOD
self.AGENT_NUM = agent_num
def getvalue(self,period):
"""
Wahrscheinlichkeit, auf die Website zu kommen
sin(theta) = sin(OMEGA*t + phi)
T = 2*pai/OMEGA
60*60*24=86400sec
OMEGA = 2pai/86400
"""
cdef sec
cdef np.ndarray[np.double_t, ndim=1] tmp = np.zeros(period,dtype=np.double)
for sec in xrange(period):
tmp[sec] = self.E * ( sin(self.OMEGA*sec - self.PHI) + 1 ) + self.minbit
return tmp/self.AGENT_NUM #Berechnung von pred
cdef class ComputeBid:
cdef int time, day
gamma = 1.96 #Wird zur Berechnung des Konfidenzintervalls verwendet(95%Angenommen, ein Vertrauensintervall)
beta1=0.3
beta2=0.8
theta_bin = 100
cdef np.ndarray \
bid_num,win_num,cmsp_bag,theta,ctr_hist,mu,sigma
cdef int period, daybuget, gcpc, bidcap, bin_n
cdef double ctrbin, avgprice
def __init__(self,period,daybuget,gcpc,bidcap,ctrbin):
self.period = period
self.ctrbin = ctrbin
self.daybuget = daybuget
self.gcpc = gcpc
self.bidcap = bidcap
self.bid_num = np.zeros(period, dtype=np.int64)
self.theta = np.zeros(self.theta_bin, dtype=np.float64)
#Lagerung von ctr hist Gramm
self.bin_n = int( float(1.0)/ctrbin )
self.ctr_hist = np.zeros((period,self.bin_n), dtype=np.int64)
self.mu = np.zeros(period, dtype=np.float64) #Durchschnittswert für jeden Tau-Slot des Gebotsschwellenwerts
self.sigma = np.zeros(period, dtype=np.float64) #Verteilung des Gebotsschwellenwerts Tau für jeden Slot
self.avgprice = 0.0
def __dealloc__(self):
pass
def output(self, file,user_agent_num,bid_agent_num,days):
cdef int t,n,i,c,b
#Berechnung der Besuchsprognose
pred_creater = CreatePredict(self.period, user_agent_num)
#Auftreten des Benutzeragenten
user_agent = [ useragent.Agent(n) for n in xrange(user_agent_num) ]
#Auftreten des Bid Agent
bid_agent = [ bidagent.Agent(n) for n in xrange(bid_agent_num) ]
for t in xrange(self.period*days):
self.time = fmod(t,self.period)
if fmod(t,self.period)==0:
if self.day!=0: self.avgprice /= sum(self.win_num)
self.bid_num = np.zeros(self.period, dtype=np.int64)
self.win_num = np.zeros(self.period, dtype=np.int64)
self.cmsp_bag = np.zeros(self.period, dtype=np.float64)
self.day+=1
print "progress:",t
#Berechnung der Besuchsprognose
pred = pred_creater.getvalue(self.period)
#Berechnung der Budgetallokation für jeden Slot
slot_bag = self.calc_slot_bag(pred)
#Holen Sie sich Besucher ctr
ctr = []
bidp = []
visit = 0.0
dbidprice = {}
for i in xrange(user_agent_num):
ctr.append( user_agent[i].get_visiter_ctr(pred[self.time]) )
#Berechnung des Gebotsbetrags für jeden Agenten
if ctr[i] == False: continue
visit += 1.0
"""Erstellen Sie ein Histogramm von ctr"""
if self.day==1: self.get_hist(ctr[i])
maxprice = 0.0
for b in xrange(bid_agent_num):
price = bid_agent[b].get_bid_price(ctr[i], pred[self.time])
if price > maxprice:
maxprice = price
bidp.append(maxprice)
"""Zählen Sie die Anzahl der Gebote und bestimmen Sie den Gebotsbetrag"""
#Tempo für die Preisgestaltung_Rate berechnen
if self.bid_num[self.time]==0:
pacing_rate = 0.0
else:
pacing_rate = self.bid_num[self.time]/float(visit)
#Gebotspreisermittlung
bidprice = self.calc_bidprice(self.day, ctr[i], pacing_rate)
print 'price',bidprice
#Beurteilung, ob geboten werden soll oder nicht
if bidprice == False: continue
"""Erstellen eines Wörterbuchs zur Bestätigung des berechneten Gebotsbetrags"""
if str(floor(bidprice)) not in dbidprice: dbidprice[str(floor(bidprice))] = 1
else: dbidprice[str(floor(bidprice))] += 1
#Wenn der Gebotsbetrag die Obergrenze überschreitet, ist dies der Wert der Obergrenze
if bidprice>self.bidcap: bidprice = self.bidcap
#Wenn Sie bieten möchten, überprüfen Sie die Anzahl der Gebote
self.bid_num[self.time] += 1
#Beurteilung des Gebotsgewinns
if bidprice > maxprice:
#Beurteilung, ob geboten werden soll
if slot_bag[self.time] - self.cmsp_bag[self.time] - bidprice > 0:
self.cmsp_bag[self.time] += bidprice
print 'cmsp=',self.cmsp_bag[self.time]
self.calc_theta(bidprice,maxprice)
self.win_num[self.time] += 1
#Berechnung der Durchschnittskosten um 1bid
if self.day==1: self.avgprice += bidprice
print dbidprice
print np.float64(self.win_num)/self.bid_num
num1 = []
num2 = []
for i in xrange(self.period):
num1.append( str(slot_bag[i]) )
num2.append( str(self.cmsp_bag[i]) )
file.write(u'slot bags\n'+u','.join(num1)+u'\n')
file.write(u'comsumption bags\n'+u','.join(num2)+u'\n')
def get_hist(self,ctr):
"""Erstellen Sie ein Histogramm von ctr"""
cdef int bin
for bin in xrange(self.bin_n):
if bin*self.ctrbin<=ctr<(bin+1)*self.ctrbin:
self.ctr_hist[self.time,bin] += 1
break
def calc_bidprice(self, day, ctr, pacing_rate): #ctr[i]
cdef int i
tau = 0.0
if day<2:
if ctr>=0.2:
return random.randint(20,80)
else: return False
else:
if self.cmsp_bag[self.time]!=0.0:
#Vorhersage Imp Berechnung
imps = float(self.cmsp_bag[self.time])/self.avgprice
print 'imps',imps
#Berechnung der erwarteten Anzahl von Geboten
#win_rate = bid_num[self.time]/win_num[self.time]
bids = float(imps*self.bid_num[self.time])/self.win_num[self.time]
print 'bids',bids
#Berechnung der erwarteten Anzahl von Anfragen
print 'pacing_rate',pacing_rate
reqs = bids/pacing_rate
else:
reqs=0.0
print 'reqs',reqs
#Gebotsschwelle abrufen
for i in xrange(len(self.ctr_hist[self.time,:])):
if sum(self.ctr_hist[self.time,-(i+1):]) - reqs >0.0:
tau = float((self.theta_bin-1)-i)/self.theta_bin
break
#Berechnung des Durchschnittswertes
if self.time == 0: t = self.period - 1
else: t = self.time-1 #Da ist t-Auf 1 setzen
div_t = float(1)/(self.time+1)
self.mu[self.time] = self.mu[t]+ div_t*(tau-self.mu[t]) #Möglicherweise müssen Sie den aktuellen und den letzten Steckplatz speichern
#Berechnung der Varianz
self.sigma[self.time] = div_t*t*self.sigma[t] \
+ div_t*(tau-self.mu[t])*(tau-self.mu[self.time])
#Vorläufige Preisentscheidung
u = ctr*self.gcpc # Ui = AR*G(Predictive CTR x Ziel-CPC)
#Bestimmen Sie den Preis anhand der Gebotsrate
# beta1=0.3, beta2=0.Auf 8 setzen
price = self.get_price(pacing_rate,u)
print 'price1',price
#Beurteilung, ob geboten werden soll
return self.judge_bid(pacing_rate,price,tau)
def calc_theta(self,bidprice,secprice):
cdef int b
theta = float(secprice)/bidprice
for b in xrange(100):
if 0.01*b<=theta<=0.01*(b+1):
self.theta[b] += 1
break
def calc_slot_bag(self,pred):
s = sum(pred)
prop = np.array(pred, dtype=DTYPE)/s
return prop*self.daybuget
def get_price(self,pacing_rate,u):
price = 0.0
if pacing_rate<=self.beta1:
s_theta = sum(self.theta)
s = 0.0
for i in xrange(len(self.theta)):
s += self.theta[i]
if float(s)/s_theta>0.01:
return i*(float(3.0)/(2*self.theta_bin))*u #price = self.theta[i]*u
elif pacing_rate>=self.beta2: # pacing_Möglicherweise müssen Wutvorhersagen getroffen werden
lo =1.0 + (self.bidcap/self.avgprice-1.0)/(1.0-self.beta2) \
*(pacing_rate-self.beta2)
return lo*u
else:
return u
def judge_bid(self, pacing_rate, price, tau):
term2 = self.gamma*self.sigma[self.time]/sqrt(self.day)
print 'tau',tau
if tau<self.mu[self.time]-term2: #Ablehnungsgrenze für Gebote
return False
elif tau>=self.mu[self.time]+term2: #Unteres Gebotsannahmegrenze
return price
else:
if pacing_rate>random.uniform(0,1):
return price
else: return False
Da bei Verwendung von Cython eine Kompilierung erforderlich ist, wird vorerst auch setup.py beschrieben.
setup.py
python
# coding: utf-8
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
import numpy as np
setup(
name="CPWOPTcritical",
cmdclass={"build_ext":build_ext},
ext_modules=[Extension("CySimulation",["CySimulation.pyx"])],
include_dirs=[np.get_include()]#Geben Sie hier den Include-Pfad an
)
Da es sich um Cython handelt, ist der Hauptteil getrennt. Es wird unten beschrieben.
main
python
# coding: utf-8
#import pyximport; pyximport.install()
import io
if __name__=='__main__':
import CySimulation
period = 1440 #Anzahl der Slots pro Tag
daybuget = 1000000 #Tägliches Budget
goalcpc = 100 #Ziel cpc
bidcap = 90 #Gebotsbetrag Obergrenze
ctrbin = 0.01 #Größe des CTR-Histogrammfachs
days = 2 #Tage der Datengenerierung
user_agent_num = 600 #Anzahl der Benutzeragenten
bid_agent_num = 100 #Anzahl der Bid Agents
bid = CySimulation.ComputeBid(period, daybuget, goalcpc, bidcap,ctrbin)
with io.open('sin_test','a') as f:
bid.output(f,user_agent_num,bid_agent_num,days)
Es scheint, dass es gut gehen wird, aber ich habe das Gefühl, dass der erwartete Wert nicht in dem Teil herauskommt, in dem die Datengenerierung weggelassen oder der aus den vergangenen Daten vorhergesagte Teil übersprungen wurde. Da die Einstellungen sehr detailliert sind, scheint es schwierig zu sein, ausreichende Ergebnisse zu erzielen, wenn Sie sie nicht genau erstellen.
Es ist eine ziemlich heuristische Methode, aber ich denke, es ist die am besten verwendbare Methode (Papier) unter Bedingungen, bei denen eine Geschwindigkeit von 50 ms oder weniger in Kombination mit einer CVR-Schätzung erforderlich ist. Für diesen Job war das erste Papier, das ich über Gebotsoptimierung gelesen habe, das oben eingeführte. Ich habe einige andere Zeitungen gelesen, aber diese hatte den stärksten Einfluss. Wenn andere Protokolle als IP und Zeitstempel gespeichert sind, wollte ich mit tatsächlichen Daten basierend auf dieser Methode optimieren. Es tut mir Leid.
Wenn Sie etwas Seltsames finden, würden wir uns freuen, wenn Sie darauf hinweisen könnten.