Concept-Based Biclustering for Internet Advertisement

Abstract

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. On the other hand, the company, that provides context advertisement, wants to discover prospective markets, the advertisers. It can be done by means of so called biclustering. For binary relation firms terms the most natural bicluster definition is a tuple of two subsets of firms and terms respectively, where each firm from the first component buys each term from the second one. To solve this task there is a well-developed notion of formal concept which has almost equivalent definition to such a bicluster in terms of object-attribute tables in Formal Concept Analysis. However, the number of formal concepts (biclusters) for a given dataset can be of exponential size in the worst case. To avoid this difficulty we proposed a new concept-based biclustering method. The new bicluster definition, (dense) object-attribute bicluster or simply oa-bicluster, is a relaxation of formal concept notion. Our findings shows that the number of (dense) oa-biclusters is no greater than the number of non-empty cells of initial binary relation. The paper contains experimental results on applying the proposed algorithm to contextual Internet advertisement data in comparison with some FCA algorithms and additional results on so-called morphological metarules for term recommendation task on the same data.