Traditionally, clustering operates on data described by a xed number of (usually numerical) features; this description schema is said propositional or attribute-value. Yet, when the data cannot be described in that way, usual data-mining or clustering algorithms are no longer suitable. In this paper, we consider the problem of discovering similar types of programs in TV streams. The TV data have two important characteristics: 1) they are multi-relational, that is to say with multiple relationships between features; 2) they require background knowledge external to their interpretation. To process the data, we use Inductive Logic Programming (ILP) [MD94]. In this paper, we show how to divert ILP to work unsupervised in this context: from arti cial learning problems, we induce a notion of similarity between broadcasts, which is later used to perform the clustering. Experiments presented show the soundness of the approach, and thus open up many research avenues.
Copyright © by the paper's authors. Copying permitted for private and academic purposes.
In: Nicolas Lachiche, Christel Vrain (eds.): Late Breaking Papers of ILP 2017, Orleans, France, September 4-6, 2017, published at http://ceur-ws.org paper, we propose to de ne a clustering technique suited to our complex data by diverting supervised Inductive Logic Programming (ILP) into a non-supervised technique. ILP makes it possible to easily represent our multirelational data, and a distance between broadcasts is automatically from fake supervised classi cation problems, in the vein of [SH05, CN13]. 2
For classi cation problems, objects are usually described in a propositional form, also said attribute-value or vector-based. In this representation, objects must have the same number of features, and the features are to be considered independently (relations between features are not exploited). In our case, each object is a segment of TV-streams corresponding to a program or an inter-program. But each object may have several occurrences, such as a particular ad which is repeated several times in the stream. The number of occurrences vary from one object to another, which makes the attribute-value description impossible. Moreover, certain relations between occurrences may be very relevant (eg. two occurrences are broadcast on di erent TV channels, two occurrences are broadcast in less than 1 day...). This multi-relational aspect of our data is thus important to consider for the clustering task. Figure 1 shows these di erent relations between occurrences and their feature as arrows with di erent colors (in gray: the class of broadcast, which is unknown in our problem).
ILP is usually used as supervised machine learning technique able to infer rules (eg. Horn clauses) H from examples (E+) and counter-examples E of a concept, and with the help of background knowledge B [MD94]. Figure 2 shows how a program can be described in B (with standard Prolog). One can see how the relations between the occurrences are easily encoded with predicates next occ/2 and next in stream/2.
In B we also de ne the predicates that can be used to infer rules in H, such as prev occ/2 which indicate two occurrences of the same program, one occurring after the other, or such as interval/3 wich indicates the time interval between two occurrences of two program. Here is an example of rule that can be inferred : broadcast(A) :- has occ(A,B), duration(B,3), next occ(B,C), next in stream(B,D), next in stream(C,E), has occ(F,D), has occ(F,E). This rule highlights the interest of the multi-relational representation: it covers every broadcast A having two occurrences B and C, lasting 3 seconds, such as these two occurrences are followed by two occurrences (D,E) from a same program (F). This rule typically covers sponsoring broadcast always appearing before a program. 3 3.1
Our approach aims at deducing distances (or similarities) between two programs from repeated random classications problems with ILP. For a given random classi cation problem, if the two programs are covered by H, it tends to show that they are related. If this is the case for every random classi cation problem, it means that they are very similar. Algorithm 1 gives an overview of the process. As for bagging [Bre96], classi cation is repeated many times with di erent learning parameters: examples (step 3 wichich divides the data into positive Et+rain and EOoB, a out-of-bag set used later), counter-examples (step 4), the hypothesis language (step 5). At each iteration, we record the pairs of programs (xi; xj ) that are covered by the same inferred clauses (called %%% description of the 1st occurrence has occ(broadcast12,b12 occ1). duration(b12 occ1,69). date time(b12 occ1,20,42,1,10,june,2005,friday). channel(b12 occ1,2). next occ(b12 occ1,b12 occ2). next in stream(b12 occ1,b28 occ5). %%% description of the 2nd occurrence has occ(broadcast12,b12 occ2). date time(b12 occ2,24,48,19,10,june,2005,friday). duration(b12 occ2,66). channel(b12 occ2,2). next occ(b12 occ2,b12 occ3). next in stream(b12 occ2,b5 occ19). ... %%% other knowledge / predicate de nition prev occ(Occ1,Occ2) :- next occ(Occ2,Occ1). interval(Occ1,Occ2,Duration) :- date time(Occ1,H1,Min1,S1,D1,M1,Y1, ), date2epoch(H1,Min1,S1,D1,M1,Y1,Epoch1), date time(Occ2,H2,Min2,S2,D2,M2,Y2, ), date2epoch(H2,Min2,S2,D2,M2,Y2,Epoch2), Duration is abs(Epoch1-Epoch2). ... co-covers hereafter) in a matrix Mco-cov. One can give more weight to a clause covering very few examples, and less weight to a clause covering most of the examples (function weight). The last step is simply to use a standard clustering technique on the co-cover matrix, considered as a similarity matrix. In the experiments presented below, we use Markov Clustering [vD00]. Its main advantage compared with k-means/k-medoids is to avoid the need to decide a priori the number of expected clusters.
The strategy at the heart of this approach is to vary the learning biases at each iteration. The rst bias is the set of examples used. In our experiments we use 1/10 of the programs to be used as positive examples. The inferred rules are then applied on the 9/10 remaining programs to nd which one are co-covered. The generation of negative examples is an important step in our algorithm. In our case, it means inventing programs, with their occurrences and features. They have to be realistic enough in order to produce learning problems that will generate discriminative enough clauses, and thus relevant co-covers. In order to generate counter-examples, we randomly copy parts of the description of real programs (with a renaming of the constants in order to produce a coherent set of occurrences and features). The hypothesis language, setting the format of acceptable clauses, Algorithm 1 Clustering with ILP is also di erent at each iteration. In practice, every mode of every predicate is given at the initialization of the algorithm, and a subset is randomly chosen at each iteration. All these machine learning problems on fake supervised tasks brings, through their variety, important properties to the obtained similarity: it mixes complex descriptions, implements feature selection, take into account redundancy between descriptions, and is robust to outliers. 4 4.1
The data use for our experiments are those developed by [NG08]; it consists of a 22-day recording of the French France2 channel in May 2005. The stream is segmented in programs and the di erent occurrences of a same program have been identi ed automatically and manually consolidated [NG08]. To build the groundtruth needed to evaluate our clustering results, we used the manual annotation of the data proposed by [NG08] who tagged the programs according to 6 classes: movie/show, series, commercials, sponsoring, branding (short programs displaying the the name or logo of the channel), trailers (short programs announcing what will be broadcast later). This ground-truth tagging of the stream will be used as reference clusters (cf. Figure 3 for their repartition). The evaluation scores are those commonly used for clustering comparison (the one produced automatically vs. the ground-truth one): Adjusted Purity, Normalized mutual information and Adjusted Rand Index (ARI) [Ran71, HA85, VEB10]. 4.2
An analysis of the inferred rule for each iteration also allow an indirect validation of our approach since they exhibit the multi-relational property of our data. This is the case of the following rule which covers programs broadcast at xed interval: broadcast(A) :- has occ(A,B), next occ(B,C), next occ(C,D), interval(B,C,E), interval(C,D,E). 5
Our clustering approach, relying on ILP, allows us to make the most of the multi-relational aspect of our TV data. It makes it possible to get a notion of distance even in rich description spaces where metrics cannot be de ned a priori. Of course, even if there is no explicit de nition of the distance, other biases from the user are unavailable, such as the way the data are described, the de nition of the modes in the hypothesis language...
Several perspectives are foreseen. For our TV application, the use of a larger dataset (recording several months with several channels) would allow us to limit the errors mentioned in the previous section. Adding multimodal features (logo detection, black frames, speech detection...) would also bring useful information about the content of the TV segment. These features should help the clustering process to distinguish between branding and sponsoring, or to better categorize trailers. More generally, the good results obtained by the ILPbased clustering argues in favor of applying this approach to other problems where the multi-relational aspect in important [DL01, MDP+12].
L. Breiman. Bagging predictors. Machine Learning, 24(2):123{140, 1996.
Vincent Claveau and Abir Ncibi. Dcouverte de connaissances dans les squences par CRF nonsuperviss. In Actes de la confrence TALN 2013, 2013.
S. Dzerosky and N. Lavrac, editors. Relational Data Mining. Berlin: Springer-Verlag, 2001. Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classi cation, 2(1):193{218, 1985. [HFH+09] Mark Hall, Eibe Frank, Geo rey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten.
The WEKA data mining software: An update. SIGKDD Explorations, 11(1):10{18, 2009. Zein Al Abidin Ibrahim and Patrick Gros. Tv stream structuring. ISRN Signal Processing, 2011. A. K. Jain. Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 31(8):651{666, 2010. [Bre96]