Advertisement targeting for an interest topic
An advertising system identifies users associated with an interest topic and generates a list of such users in which all advertising accounts are proportionately represented in the list. Such users are identified by recording user-page access data to each page in a cluster of pages associated with the interest topic. A list of user-account associations is generated by grouping the user-page access data by the advertising account associated with each page. The list is then optimized so a proportion of user-account associations for each advertising account is less than or equal to a predetermined threshold. This ensures that no one advertising account is overrepresented in the list. Using the optimized list, the advertising system can target users associated with the list with advertisements related to the interest topic.
1. A computer-implemented method comprising:
identifying a set of webpages associated with an interest topic, each webpage associated with an advertising account form a set of advertising accounts;
receiving a set of user-webpage accesses for a plurality of users, each user-webpage access indicating a user access to a webpage in the set of webpages;
grouping the user-webpage accesses in the set of user-webpages accesses by advertising account associated with the accessed webpage;
generating an initial list of user-account associations that lists each advertising account and users associated with the advertising account based on the group user-webpage accesses;
reducing the initial list of user-account associations to generate an optimized list of user-account associations, wherein the reducing comprises reducing a portion of user-account associations for each of one or more advertising accounts that have a proportion of user-account associations above a predetermined threshold; and
using the optimized list to target a user with an advertisement associated with the interest topic, wherein using the optimized list comprises:
identifying an advertisement opportunity for the user associated with the optimized list,
identifying the advertisement targeting the optimized list, and
adding the identified advertisement to an advertising auction for the advertisement opportunity.
2. The method of claim 1 , wherein using the optimized list to target the user comprises:
providing the optimized list to an advertiser that uses the optimized list to target the user with the advertisement associated with the interest topic.
3. The method of claim 1 , wherein identifying the set of webpages associated with the interest topic comprises:
identifying seed webpages associated with the interest topic, and assigning the seed webpages to the set of webpages;
extracting a set of features from an unknown webpage;
calculating a statistics using the set of features extracted from the unknown webpage; and
assigning the unknown webpage to the set of webpages associated with the interest topic if the statistic meets a predetermined criteria.
4. The method of claim 3 , wherein the set of features includes any one of keywords, bag of words, or n-grams of the unknown webpage.
5. The method of claim 3 , wherein extracting the set of features comprises extracting a set of keywords from the unknown webpage, and calculating the statistic comprises calculating a probability that the unknown webpage belongs in the set of webpages based on frequencies of the set of keywords in the set of webpages.
6. The method of claim 1 , wherein reducing the initial list of user-account associations comprises:
solving the following integer linear programming problem
max
u
k
∈
N
,
k
=
1
,
2
,
…
,
p
∑
k
=
1
p
u
k
subject
to
u
k
≤
f
·
(
∑
k
=
1
p
u
k
)
,
∀
k
=
1
,
2
,
…
,
p
0
≤
u
k
≤
r
k
,
∀
k
=
1
,
2
,
…
,
p
for u k , where r k is the number of users in the initial list of user-account associations for advertising account k in the set of advertising accounts, f is the predetermined threshold, and u k is the number of users in the optimized list of user-account associations for advertising account k in the set of advertising accounts; and
discarding r k -u k number of user-account associations from advertising account k in the set of advertising accounts.
7. A non-transitory computer-readable medium storing instructions for execution on a processor, the instructions when executed by the processor causing the processor to perform steps comprising:
identifying a set of webpages associated with an interest topic, each webpage associated with an advertising account from a set of advertising accounts;
receiving a set of user-webpage accesses for a plurality of users, each page user-webpage access indicating a user access to a webpage in the set of webpages;
grouping the user-webpage accesses in the set of user-webpage accesses by advertising account associated with the accessed webpage;
generating an initial list of user-account associations that lists each advertising account and users associated with the advertising account based on the grouped user-webpage accesses;
reducing the initial list of user-account associations to generate an optimized list of user-account associations, wherein the reducing comprises reducing a portion of user-account associations for each of one or more advertising accounts that have a proportion of user-account associations above a predetermined threshold; and
using the optimized list to target a user with an advertisement associated with the interest topic, wherein using the optimized list comprises:
identifying an advertisement opportunity for the user associated with the optimized list,
identifying the advertisement targeting the optimized list, and
adding the identified advertisement to an advertising auction for the advertisement opportunity.
8. The non-transitory computer-readable medium of claim 7 , wherein using the optimized list to target the user comprises:
providing the optimized list to an advertiser that uses the optimized list to target the user with the advertisement associated with the interest topic.
9. The non-transitory computer-readable medium of claim 7 , wherein identifying the set of webpages associated with the interest topic comprises:
identifying seed webpages associated with the interest topic, and assigning the seed webpages to the set of webpages;
extracting a set of features from an unknown webpage;
calculating a statistic using the set of features extracted from the unknown webpage; and
assigning the unknown webpage to the set of webpages associated with the interest topic if the statistic meets a predetermined criteria.
10. The non-transitory computer-readable medium of claim 9 , wherein the set of features includes any one of keywords, bag of works or n-grams of the unknown webpage.
11. The non-transitory computer-readable medium of claim 9 , wherein extracting the set of features comprises extracting a set of keywords from the unknown webpage, and calculating the statistic comprises calculating a probability that the unknown webpage belongs in the set of webpages based on frequencies of the set of keywords in the set of webpages.
12. The non-transitory computer-readable medium of claim 7 , wherein reducing the initial list of user-account associations comprises:
solving the following integer linear programming problem
max
u
k
∈
N
,
k
=
1
,
2
,
…
,
p
∑
k
=
1
p
u
k
subject
to
u
k
≤
f
·
(
∑
k
=
1
p
u
k
)
,
∀
k
=
1
,
2
,
…
,
p
0
≤
u
k
≤
r
k
,
∀
k
=
1
,
2
,
…
,
p
for u k , where r k is the number of users in the initial list of user-account association for advertising account k in the set of advertising accounts, f is the redetermined threshold, and u k is the number of users in the optimized list of user-account associations for advertising account k in the set of advertising accounts; and
discarding r k -u k number of user-account associations from advertising account k in the set of advertising accounts.
13. A system comprising:
a processor configured to execute instructions;
a computer-readable medium containing instructions for execution on the processor, the instructions causing the processor to perform steps of:
identifying a set of webpages associated with an interest topic, each webpage associated with an advertising account from a set of advertising accounts;
receiving a set of user-webpage accesses for a plurality of users, each user-webpage accesses indicating a user access to a webpage in the set of webpages;
grouping the user-webpage accesses in the set of user-webpage accesses by advertising account associated with the accessed webpage;
generating an initial list of user-account associations that list each advertising account and users associated with the advertising account based on the grouped user-webpage accesses;
reducing the initial list of user-account associations to generate an optimized list of user-account associations, wherein the reducing comprises reducing a portion of user-account associations for each of one or more advertising accounts that have a proportion of user-account associations above a predetermined threshold; and
using the optimized list to target a user with an advertisement associated with the interest topic, wherein using the optimized list comprises:
identifying an advertisement opportunity for the user associated with the optimized list,
identifying the advertisement targeting the optimized list, and
adding the identified advertisement to an advertising auction for the advertisement opportunity.
14. The system of claim 13 , wherein using the optimized list to target the user comprises:
providing the optimized list to an advertiser that uses the optimized list to target the user with the advertisement associated with the interest topic.
15. The system of claim 13 , wherein identifying the set of webpages associated with the interest topic comprises:
identifying seed webpages associated with the interest topic, and assigning the seed webpages to the set of webpages;
extracting a set of features from an unknown webpage;
calculating a statistic using the set of features extracted from the unknown webpage; and
assigning the unknown webpage to the set of webpages associated with the interest topic if the statistic meets a predetermined criteria.
16. The system of claim 15 , wherein the set of features includes any one of keywords, bag of words, or n-grams of the unknown webpage.
17. The system of claim 15 , wherein extracting the set of features comprises extracting a set of keywords from the unknown webpage, and calculating the statistic comprises calculating a probability that the unknown webpage belongs in the set of webpages based on frequencies of the set of keywords in the set of webpages.
18. The system of claim 13 , wherein reducing the initial list of user-account associations comprises:
solving the following integer linear programming problem
max
u
k
∈
N
,
k
=
1
,
2
,
…
,
p
∑
k
=
1
p
u
k
subject
to
u
k
≤
f
·
(
∑
k
=
1
p
u
k
)
,
∀
k
=
1
,
2
,
…
,
p
0
≤
u
k
≤
r
k
,
∀
k
=
1
,
2
,
…
,
p
for u k , where r k is the number of users in the initial list of user-account associations for advertising account k in the set of advertising accounts, f is the predetermined threshold, and u k is the number of users in the optimized list of user-account associations for advertising account k in the set of advertising accounts; and
discarding r k -u k number of user-account associations from advertising account k in the set of advertising accounts.