Introduction

Contextual Internet advertising is a form of e-commerce. The largest revenues of the major players at this market, like search systems, are obtained from the so-called search sensitive advertisement, i.e, advertisement in a sense close to user queries. Here we consider the problem of detecting terms that can be interesting to an advertiser. Assume that a company F has already bought some advertising terms which describe certain services. As a rule, there are already competing companies at the market, therefore it is reasonable to find terms bought by them. These terms can be compared to those bought by F and part of them can be recommended as future advertising terms to F . The goal of this work is to propose well-interpretable recommendations based on FCA. The rest of the paper is organized as follows: First we recall main definitions from FCA and rule mining. Then we consider experimental data and the problem statement. Afterwards, we propose morphology-based and ontology-based metarules that can be derived without experimental data. We conclude the paper with experiments and their discussion.

Main definitions

First, we recall some basic notions from Formal Concept Analysis (FCA) [1]. Let G and M be sets, called the set of objects and attributes, respectively, and let I be a relation I ⊆ G × M : for g ∈ G, m ∈ M , gIm holds iff the object g has the attribute m. The triple K = (G, M, I) is called a (formal) context. If A ⊆ G, B ⊆ M are arbitrary subsets, then the Galois connection is given by the following derivation operators: In data mining applications, an element of M is called an item and a subset of M is called an itemset.

A def = {m ∈ M | gIm for all g ∈ A}, B def = {g ∈ G | gIm for all m ∈ B}.

The support of a subset of attributes (an itemset) P ⊆ M is defined as supp(P ) = |P |. 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 ) 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 I 1 → I 2 , where I 1 and I 2 are arbitrary itemsets (I 1 , I 2 ⊆ A), I 1 ∩ I 2 = ∅ and I 2 = ∅. The left side, I 1 is called antecedent, the right side, I 2 is called consequent. The support of an association rule r : I 1 → I 21 is defined as: supp(r) = supp(I 1 ∪ I 2 ). The confidence of an association rule r: I 1 → I 2 is defined as the conditional probability that an object has itemset I 2 , given that it has itemset I 1 : conf (r) = supp(I 1 ∪ I 2 )/supp(I 1 ). An association rule r with conf (r) = 100% is an exact association rule (or implication [1]), otherwise it is an approximate association rule. An association rule is valid if supp(r) ≥ min supp and conf (r) ≥ min conf . An itemset P is a generator if it has no proper subset Q(Q ⊂ P ) with the same support. Let F CI be the set of frequent closed itemsets and let F G be the set of frequent generators. The informative basis for approximate association rules:

IB = {r : g → (f \ g)|f ∈ F CI ∧ g ∈ F G ∧ g ⊂ f }.

Initial Data and Problem Statement

For experimentation we used data of US Overture [2], which were first transformed in the standard context form. In the resulting context K = (G, M, I) objects from G stay for advertising companies (advertisers) and attributes from M stay for advertising terms (bids), gIm means that advertiser g bought term m. In the context |G| = 2000, |M | = 3000, |I| = 92345.

In our context, the number of attributes per object is bounded as follows: 13 ≤ |g | ≤ 947. For objects per attribute we have 18 ≤ |m | ≤ 159. From 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 [3] for the use of association rules in recommendation systems.

We consider the following context:

K F T = (F, T, I F T )

, where F is the set of advertising firms (companies), T is the set of advertising terms, or phrases, f I F 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 Standard approach to rule mining 4.1 Detecting large market sectors with D-miner. D-miner is a freely available tool [4], [5] which constructs the set of concepts satisfying given constraints on sizes of extents and intents (icebergs and dual icebergs). D-miner takes as input a context and two parameters: minimal admissible extent and intent sizes and outputs a "band" of the concept lattice: all concepts satisfying constraints given by parameter values (|intent| ≥ m and |extent| ≥ n, where m, n ∈ N, see table 1). We give examples of intents of formal concepts for the case |L| = 53, where L is a concept lattice.

Hosting market.

effective way of representing the whole set of association rules. The results are given in table 2. 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 [3]. For company f we find all association rules, the antecedent of which contain all the phrases bought by the company, then we construct the set T u of unique advertising phrases not bought by the company f before. Then we order these phrases by decreasing of confidence of the rules where the phrases occur in the consequences. If buying a phrase is predicted by several rules (i.e., the phrase is in the consequences of several rules), we take the largest confidence.

Mining metarules

Morphology-based 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 = {w 1 , w 2 , . . . , w n }. A stem is the root or roots of a word, together with any derivational affixes, to which inflectional affixes are added [8]. The stem of word w i is denoted by s i = stem(w i ) and the set of stems of words of the phrase t is denoted by stem(t) = i stem(w i ), where w i ∈ t. Consider the formal context K T S = (T, S, I T S ), where T is the set of all phrases and S is the set of all stems of phrases from T , i.e. S = i stem(t i ). Then tIs denotes that the set of stems of phrase t contains s.

In this context we construct rules of the form t → s I T S i for all t ∈ T , where (.) Its denotes the prime operator in the context K T S . Then the a of the context K T 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 − − → s I T S i

, an association rule of the context K F T = (F, T, I F T ). If the values of support and confidence of this rule in context K F T do not exceed certain thresholds, then the association rules constructed from the context K F T are considered not very interesting. Metarules of the following forms seem also to be reasonable. First, one can look for rules of the form t

F T − − → i s I T S i

, i.e., rules, the consequent of which contain all terms containing at least one word with the stem common to a word in the antecedent term. Obviously, constructing rules of this type may result in the fusion of phrases related to different market sectors, e.g. "black jack" and "black coat". Second, we considered rules of the form t 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 g i (.) : 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 → g i (t) and a neighborhood rule t → n(t). These rules can also be considered as association rules of the context K F T = (F, T, I F 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 .

{B V IT AM IN } → {B COM P LEX V IT AM IN, B12 V IT AM IN, C V IT AM IN, . . . D V IT AM IN, DISCOU N T V IT AM IN, E V IT AM IN, M IN ERAL V IT AM IN, . . . M U LT I V IT AM IN, SU P P LEM EN T V IT AM IN, V IT AM IN } Rules of the form t → g 1 (t), where t = "B V IT AM IN , g 1 (t) = "V IT AM IN S . {B V IT AM IN } → {V IT AM IN S}.

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 tr − → 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

test −−→ B) = |A Itest ∩ B Itest | |A Itest |

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 (Rules i ) = A− →B∈Rules conf (A test −−→ B) |Rules i | ,

where Rules i 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, which was again averaged over 10 cases, average conf 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.

= n P i=1 average conf (Rulesi) n .

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 K F T = (F, T, I F 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). From tables 6 and 7one can easily see that most confident and supported rules are of the form t 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.

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.