The problem of detecting terms that can be interesting to the advertiser is considered. If a company has already bought some advertising terms which describe certain services, it is reasonable to find out the terms bought by competing companies. A part of them can be recommended as future advertising terms to the company. The goal of this work is to propose better interpretable recommendations based on FCA and association rules.
Introduction
First, we recall some basic notions from Formal Concept Analysis (FCA) [
A0 d=ef {m ∈ M | gIm for all g ∈ A},
B0 d=ef {g ∈ G | gIm for all m ∈ B}.
If we have several contexts derivative operator of a context (G, M, I) denoted by (.)I .
The pair (A, B), where A ⊆ G, B ⊆ M , A0 = B, and B0 = A is called a (formal) concept (of the context K) with extent A and intent B (in this case we have also A00 = A and B00 = B). For B, D ⊆ M the implication B → D holds if B0 ⊆ D0.
In data mining applications, an element of M is called an item and a subset of M is called an itemset.
The support of a subset of attributes (an itemset) P ⊆ M is defined as
supp(P ) = |P 0|. An itemset is frequent if its support is not less than a given
minimum support (denoted by min supp). An itemset P is closed if there exists
no proper superset with the same support. The closure of an itemset P (denoted
by P 00) is the largest superset of P with the same support. The task of frequent
itemset mining consists of generating all (closed) itemsets (with their supports)
with supports greater than or equal to a specified min supp. An association rule
is an expression of the form I1 → I2, where I1 and I2 are arbitrary itemsets
(I1, I2 ⊆ A), I1 ∩ I2 = ∅ and I2 6= ∅. The left side, I1 is called antecedent, the
right side, I2 is called consequent. The support of an association rule r : I1 → I2
1 is defined as: supp(r) = supp(I1 ∪ I2). The confidence of an association rule r:
I1 → I2 is defined as the conditional probability that an object has itemset I2,
given that it has itemset I1: conf (r) = supp(I1 ∪ I2)/supp(I1). An association
rule r with conf (r) = 100% is an exact association rule (or implication [
Initial Data and Problem Statement
For experimentation we used data of US Overture [
In our context, the number of attributes per object is bounded as follows:
13 ≤ |g0| ≤ 947. For objects per attribute we have 18 ≤ |m0| ≤ 159. From
1 In this paper we use absolute values, but the support of an association rule r is also
often defined as supp(r) = supp(I1 ∪ I2)/|O|.
this context one had to compute formal concepts of the form (advertisers, bids)
that represent market sectors. Formal concepts of this form can be further used
for recommendation to the companies on the market, which did not buy bids
contained in the intent of the concept. In other words, empty cell (g, m) of the
context can be considered as a recommendation to advertiser g to buy bid m,
if this advertiser bought other bids contained in the intent of any concept. This
can also be represented as association rules of the form “If an advertiser bought
bid a, then one can recommend this advertiser to buy term b” See [
We consider the following context: KF T = (F, T, IF T ), where F is the set of advertising firms (companies), T is the set of advertising terms, or phrases, f IF T t means that firm f ∈ F bought advertising term t ∈ T .
For constructing recommendations we used the following approaches and tools: 1. D-miner algorithm for detecting large market sectors as concepts; 2. Coron system for constructing association rules; 3. Construction of association metarules using morphological analysis; 4. Construction of association metarules using ontologies (thematic catalogs). 4 4.1
Standard approach to rule mining
D-miner is a freely available tool [
We give examples of intents of formal concepts for the case |L| = 53, where L is a concept lattice.
{ affordable hosting web, business hosting web, cheap hosting, cheap hosting site web, cheap hosting web, company hosting web, cost hosting low web, discount hosting web, domain hosting, hosting internet, hosting page web, hosting service, hosting services web, hosting site web, hosting web }.
{ angeles hotel los, atlanta hotel, baltimore hotel, dallas hotel, denver hotel, hotel chicago, diego hotel san, francisco hotel san, hotel houston, hotel miami, hotel new orleans, hotel new york, hotel orlando, hotel philadelphia, hotel seattle, hotel vancouver}
{ call distance long, calling distance long, calling distance long plan, carrier distance long, cheap distance long, company distance long, company distance long phone, discount distance long, distance long, cheap calling distance long, distance long phone, distance long phone rate, distance long plan, distance long provider, distance long rate, distance long service }
{ adipex buy, adipex online, adipex order, adipex prescription, buy didrex, buy ionamin, ionamin purchase, buy phentermine, didrex online, ionamin online, ionamin order, online order phentermine, online phentermine, order phentermine, phentermine prescription, phentermine purchase }
Using the Coron system (see [
Here are some examples of association rules. – {evitamin} → {cvitamin} supp=31 [1.55%]; conf=0.861 [86.11%] – {gif t graduation} → {anniversary gif t}, supp=41 [2.05%]; conf=0.820 [82.00%];
The value supp = 31 of the first rule means that 31 companies bought phrases “e vitamin” and “c vitamin”. The value conf = 0.861 means that 86,1% companies that bought the phrase “e vitamin” also bought the phrase “c vitamin”.
To make recommendations for each particular company one may use an
approach proposed in [
Mining metarules
Each attribute of our context is either a word or a phrase. Obviously, synonymous phrases are related to same market sectors. The advertisers companies have usually thematic catalogs composed by experts, however due to the huge number of advertising terms manual composition of catalogs is a difficult task. Here we propose a morphological approach for detecting similar bids.
Let t be an advertising phrase consisting of several words (here we disregard
the word sequence): t = {w1, w2, . . . , wn}. A stem is the root or roots of a word,
together with any derivational affixes, to which inflectional affixes are added [
In this context we construct rules of the form t → sIT S for all t ∈ T , where i (.)Its denotes the prime operator in the context KT S . Then the a of the context KT S (we call it a metarule, because it is not based on experimental data, but on implicit knowledge resided in natural language constructions) corresponds to t −F−→T sIT S , an association rule of the context KF T = (F, T, IF T ). If the values i of support and confidence of this rule in context KF T do not exceed certain thresholds, then the association rules constructed from the context KF T are considered not very interesting. the consequent with the set of stems being the same as the set of stems of the antecedent. Third, we also propose to consider metarules of the form t1 −F−→T t2, where tI2TS ⊆ tITS . These are rules with the consequent being sets of stems that 1 contain the set of stems of the antecedent.
– t −F−→T sITS
i {last minute vacation} → {last minute travel}
Supp= 19 Conf= 0,90 – t −F−→T S sITS
i i {mail order phentermine} → {adipex online order, adipex order, . . . , phentermine prescription, phentermine purchase, phentermine sale} Supp= 19 Conf= 0,95 – t −F−→T (S si)ITS
i {distance long phone} → {call distance long phone, . . . , carrier distance long phone, distance long phone rate, distance long phone service} Supp= 37 Conf= 0,88
F T – t1 −−→ t2, tI2TS ⊆ tI1TS
{ink jet} → {ink}, Supp= 14 Conf= 0,7 5.2
Here we use simple tree-like ontologies, where the closeness to the root of a tree defines generality of ontology concepts, which are advertisement phrases. For example, we use a manually constructed WordNet-like ontologies of market sectors. In our ontology of the pharmaceutical market the concept “pharmaceutical product” is more general than that of “vitamin.” We introduce two operators acting on the set of advertising words T . Generalization operator gi(.) : T → T takes a concept to a more general concept i levels higher in the generality order. Neighborhood operator n(.) : T → T takes a concept to the set of sibling concepts.
Now we define two types of metarules for ontology: a generalization rule t → gi(t) and a neighborhood rule t → n(t). These rules can also be considered as association rules of the context KF T = (F, T, IF T ), which allows one to understand which of them are good supported by data.
Examples of metarules for pharmaceutical market.
Rule of the form t → n(t), where t = “B V IT AM IN 00.
Experimental Validation For validation of association rules we used an adapted version of cross-validation. The training set was randomly divided into 10 parts, 9 of which were taken as the training set and the remaining part was used as a test set. By A −t→r B we denote an association rule generated on a training context. The confidence of this association rule measured on the test set, i.e., conf (A −t−es→t B) = |AItest ∩ BItest | |AItest | shows the relative amount of companies that bought phrase B having bought phrase A.
We constructed 10 sets of association rules for 10 different training sets 1800 companies each (with min supp = 1, 5% and min conf = 90%. The aggregated quality measure of the obtained rules is the average confidence: average conf (Rulesi) = A→−B∈Rules
|Rulesi| P conf (A −t−es→t B) where Rulesi is the set of association rules obtained on the i-th training set. We also considered rules with min conf ≥ 0.5 and computed averaged confidence, n P average conf(Rulesi) which was again averaged over 10 cases, average conf = i=1 . n ,
The confidence of rules averaged over the test set is almost the same as the min conf for the training set, i.e., (0, 9 − 0, 87)/0, 9 ≈ 0, 03.
Rule type t −F−→T sIT S
i t −F−→T Si siIT S t −F−→T (S si)IT S
i t −F−→T ti, such that tiIT S ⊆ tIT S t −F−→T S ti, such that tiIT S ⊆ tIT S i
Rule types t −F−→T sIT S
i t −F−→T Si siIT S t −F−→T (S si)IT S
i t −F−→T ti such that tiIT S ⊆ tIT S t −F−→T S ti such that tiIT S ⊆ tIT S i
We used confidence measure also for validation of metarules. Support does not have much importance here, since we do not look for large markets or mostly sellable phrases, but stable dependencies of purchases. So, we considered only rules with confidence larger than 0.8 (or 0.9). Confidence and support for metarules are computed for the context KF T = (F, T, IF T ). We present the values of confidence and support in the tables for morphology-based metarules.
We set the minimal support 0,5 and compute the number of rules of each group for which this threshold is exceeded. Table 5 shows that average conf of these metarules is actually much higher (about 0,9). purchases. The rules with low support and confidence may be tested against recommendation systems such as Google AdWords, which uses the frequency of queries for synonyms. For validation of ontological rules we used Google service AdWords. 90% of recommendations (words) were contained in the list of synonyms output by AdWords. 7
Conclusion and further work The obtained results show that a part of dependencies in databases for purchases of advertisement phrases may be detected automatically, with the use of standard means of computer linguistics. Along with methods of data mining, these approaches allows one to improve recommendations and propose good means of ranking, which is very important for making Top-N recommendations. Another advantage of the approach consists in the possibility of detecting related advertisement phrases not given directly in data. Results of FCA-based biclusterization show the possibility of detecting relatively large advertisement markets (with more than 20 participants) given by companies and advertising phrases. To improve the proposed approach we plan to use well-developed ontologies like WordNet for constructing ontology-based metarules. 8
Acknowledgements This work was supported by the Scientific Foundation of Russian State University Higher School of Economics as a part of project 08-04-0022.