置信区间上界算法-Python

随机投放

1、导入标准库

代码：

# Importing the libraries
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

2、投放规则

虚拟数据.PNG

实际中我们不可能通过在网页上轮番投放广告，统计用户会点击某个广告，不会点击某个广告，所以这里我们生成虚拟数据模拟用户的行为，数据代表10000个用户，对于这10个广告的选择。
代码：

# Implementing Random Selection
import random
N = 10000
d = 10
ads_selected = []
total_reward = 0
for n in range(0, N):
    ad = random.randrange(d)
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    total_reward = total_reward + reward

这里我们计算通过随机投放广告，用户总的点击率。

ads_select.PNG

这里记录的是对于每个用户投放的广告，广告是随机投放的。

total_rewards.PNG
这里记录是总的点击次数。

3、可视化

可视化代码：

# Visualising the results
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()

广告投放分布.PNG

这里可以看到每一个广告投放的概率差不多一样。

UCB算法投放

1、数据预处理

代码：

# Importing the libraries
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# Importing the dataset
dataset = pd.read_csv('Ads_CTR_Optimisation.csv')

2、UCB算法实现

置信区间上界算法步骤.PNG

代码：

# Implementing UCB
import math
N = 10000
d = 10
ads_selected = []
numbers_of_selections = [0] * d
sums_of_rewards = [0] * d
total_reward = 0
for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    for i in range(0, d):
        if (numbers_of_selections[i] > 0):
            average_reward = sums_of_rewards[i] / numbers_of_selections[i]
            delta_i = math.sqrt(3/2 * math.log(n + 1) / numbers_of_selections[i])
            upper_bound = average_reward + delta_i
        else:
            upper_bound = 1e400
        if upper_bound > max_upper_bound:
            max_upper_bound = upper_bound
            ad = i
    ads_selected.append(ad)
    numbers_of_selections[ad] = numbers_of_selections[ad] + 1
    reward = dataset.values[n, ad]
    sums_of_rewards[ad] = sums_of_rewards[ad] + reward
    total_reward = total_reward + reward

算法解析：
这里的第一个循环是遍历10000个用户，第二个循环是遍历10个广告。
我们通过置信区间上界的取值决定投放的广告。
为什么置信区间上界的值要足够大：
因为在第一次遍历广告的时候，会确定选择第一个广告，第一个广告被投放过一次后，它的置信区间上界肯定比第二个小，这样一开始投放的就是前10个广告，它置信区间的算法与该广告的投放点击率，投放广告的轮数，以及该广告的投放轮数有关。

UCB总点击率.PNG

可以看出广告的总点击率比随机投放提升了一倍。

3、可视化

代码：

# Visualising the results
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()

UCB投放策略.PNG
可以看出，根据每一个用户的点击结果得到的投放策略，比随机投放的点击率要多很多。
我们不仅仅是要算出每一个广告的点击率，而且要使点击总量达到最大。
tip：本宝宝是学控制的，这跟我们的反馈控制很像呢，根据输出调节输入。