Polyxeni Sgouroglou

Christos-Nikolaos Anagnostopoulos

Modification of Colors in Images for Enhancing the Visual Perception of Protanopes

Keywords: Color Modification, Color Quantization, Real-Time Processing

The purpose of this paper is to design and to implement proper color modification methods for enhancing visual perception of digital images for people with protanopia (one of the types of Color Vision Deficiency). This paper proposes one simulation method and two daltonization methods for the modification of digital colored images, implementing the additional step of quantization for a faster modification of colors which are not correctly perceived. In order to avoid color confusion a color checking module is implemented and optimal daltonization parameters are selected. The ultimate objective of this paper is to minimize the total processing time to such an extent that it is possible to apply the proposed methods to real-time sequences (online video). The entire application is tested in a set of artificial and real images, while the performance of the proposed algorithms is evaluated in an appropriately selected set of colored images.

Introduction

Color Vision Deficiency (CVD) is quite common since about 8 -12% of the male population and 0.5% of the female European population show in a certain degree, some type of CVD. Even though there is no known medical method which corrects such deficiencies in human vision, these people are not considered to suffer from a serious malfunction. Nevertheless there are certain cases in everyday life where color confusion may become annoying (e.g. reading a website) or even critical (e.g. road signs). Consequently there is intense research interest around the problematic color perception, resulting in the development of various techniques and algorithms for the digital simulation of such malfunctions. In addition several enhancement/modification methods (daltonization techniques) for the color information in digital images have been proposed in order to reduce in certain cases color confusion.

Many researchers have conducted research for appropriately modeling the visually impaired vision, presenting algorithms to simulate what individuals with vision deficiency see. The problem of color adaptation according to user's perception is also addressed in [START_REF] Ro | Visual Content Adaptation According to User Perception Characteristics‖[END_REF][START_REF] Yang | Visual contents adaptation for color vision deficiency, Image Pro-cessing‖[END_REF]. In [START_REF] Ro | Visual Content Adaptation According to User Perception Characteristics‖[END_REF] paper, among other issues, the problem of tailoring visual content within the MPEG-21 Digital Item Adaptation (DIA) framework to meet users' visual perception characteristics was addressed. The image retrieval aspect for people with CVD was discussed in [START_REF] Kovalev | Towards Image Retrieval for Eight Percent of Color-Blind Men‖[END_REF]. Even a physiologically motivated human color visual system model which represents visual information with one brightness component and two chromatic components was proposed for testing the color perception of people suffering from CVD [START_REF] Martin | Color Blindness and a Color Human Visual System Model[END_REF].

One of the most common techniques is presented in [START_REF] Fidaner | Analysis of color blindness[END_REF], in which the daltonization parameters are selected with a trial-and-error process. In [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF], which was based on the work of [START_REF] Fidaner | Analysis of color blindness[END_REF], a method was proposed for the automatic modification of the daltonization parameters in such a way that no conflict among colors that were daltonized and colors that remained intact is ensured.

Although many algorithms have been proposed for the color modification of images in order to become more visible to people with CVD, relatively few steps have been made in the field of video and specifically in the field of real time processing, due to the high computational time required for the color modification of a single image/frame. For this purpose a color quantization technique is implemented by this paper.

In this paper the proposed methods are subject to the modification of the methods presented in [START_REF] Fidaner | Analysis of color blindness[END_REF] and [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF] and their parallel combination with a color quantization technique. In fact the additional step of color quantization is implemented in [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF] by this paper. Other methods where a color quantization technique has been applied is [START_REF] Kuhn | An Efficient Naturalness -Preserving Image -Recoloring Method for Dichromats[END_REF] although no RGB similarity checking routine is implemented and [START_REF] Doliotis | Intelligent Modification of Colors in Digitized Paintings for Enhancing the Visual Perception of Color-blind View-ers‖[END_REF] although still relatively slow for use in real-time sequences due to the complexity of the selected clustering Fuzzy-C-means algorithm.

In the proposed methods, as presented in [START_REF] Sgouroglou | Modification of Colors in Colored Images for Enhancing the Visual Perception of Protanopes[END_REF], a color reduction technique is initially applied to the image and a smaller set of colors/clusters is created. This smaller set of colors is then divided into two main groups: Colors that a person with protanopia can perceive right and don't need modification and colors that a person with protanopia cannot perceive right and do need modification. The colors of the second set are modified using specific initialization daltonization parameters and are placed in a new set. Then to avoid confusion an rgb similarity checking module is applied, so that there are no similar colors between the set of colors created after the modification and the set of colors that remained intact. If a similarity is found then the daltonization parameters are iteratively modified until similarity is eliminated.

The proposed algorithms were implemented in the programming environment MATLAB. As mentioned, the ultimate objective of this paper is to minimize the total processing time under the perspective of future application in real-time sequences. For this reason as appropriate quantization method the technique used in [START_REF] Spencer | Efficient Inverse Color Map Computation‖, Graphics Gems II[END_REF] was selected, as simpler and faster to use and with relatively reliable and comparable to kmeans results. The daltonization methods described in this paper are focused only on a specific type of color vision deficiency, namely protanopia.

Proposed method

The original adaptive algorithm contains three steps [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF]. Since the original adaptive algorithm is quite time consuming, in order to resolve this problem, the methods of this paper are proposed.

Simulation

Initially the number of the colors in the image is reduced using the color quantization method proposed in [START_REF] Spencer | Efficient Inverse Color Map Computation‖, Graphics Gems II[END_REF]. The resulting palette is an Nx3 matrix ‗map', where the number of rows is equal to the number of quantized colors. Similarly to [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF][START_REF] Fidaner | Analysis of color blindness[END_REF], the proposed methods follow the transformation matrices from RGB to LMS and vice versa. The improvement which is introduced in this paper is that in the methods proposed in this paper the simulation is applied only in the matrix ‗map', and not in every pixel of the image [START_REF] Fidaner | Analysis of color blindness[END_REF]. After performing the simulation for each row in the matrix ‗map' (i.e. N times total), the matrix ‗map_sim' is produced, which is the color palette of the quantized color image as perceived by a person with protanopia.

For each row of matrix ‗map', namely for every color of the color palette, the following steps are repeated:

Transformation of RGB values to LMS values. The transformation from RGB to LMS is achieved by a multiplication with matrix A 1 (1): The linear transformation from RGB to LMS is actually the multiplication described in (2):

    1 TT L M S A R G B  (2)
Finding the modified L'M'S' values. Then a linear transformation [START_REF] Vienot | Digital Video Colourmaps for Checking the Legibility of Displays by Dichromats[END_REF] is applied, in order to reduce the normal color domain (LMS) to the protanope color domain (L p M p S p ). The values that correspond to the loss of color information in the protanope vision are subtracted from the LMS values.

Reverse transformation of L'M'S' values to R'G'B' values.

The conversion from L p M p S p to R p G p B p is again achieved through a multiplication proposed in [START_REF] Vienot | Digital Video Colourmaps for Checking the Legibility of Displays by Dichromats[END_REF]. The new modified R p G p B p values demonstrate the way a protanope perceives each color represented by the corresponding row of the color palette.

After the execution of the described simulation sub-steps for every row of matrix ‗map' (i.e. N times), the result is a matrix which represents the color palette of the color-quantized image, as it is perceived by a protanope.

Daltonization

It consists of the following sub-steps: Calculation of the palette's error matrix. The error matrix is the absolute value of the subtraction between the color palette of the quantized image and the color palette that emerged after the simulation (map -map_sim). Per row we have the following equations ( 3), ( 4), [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF].

p R E R R  (3) p G E G G  (4) p B E B B  (5)
After performing the subtractions for all the rows of the palette (N times total), we get the table ‗error_map'.

1 1 1 1 1 1 ' ' ' _ ' ' ' N N N N N N R R G G B B error map R R G G B B         (6)
Creating sets 'S1' and 'S2'. The first set is called ‗S 1 ' and contains all the colors of the quantized image that do not need modification and are correctly perceived by a person with protanopia. The second set is called ‗S 2 ' and contains the colors of the quantized image that require modification. The separation is based on ( 6) and [START_REF] Kuhn | An Efficient Naturalness -Preserving Image -Recoloring Method for Dichromats[END_REF].

    ,, , R G B p p p true if E c E c E c rightPerceived RGB R G B false otherwise          (7)
There is a subtraction of the components of a color before and after the simulation (RGB and R p G p B p respectively). If the subtraction of the three components is less than 20.48, then the RGB color is correctly perceived by a person with protanopia, not modified and placed in the set ‗S 1 '. Conversely, if the subtraction of even one of the three components is bigger than the value 20.48, then the RGB color is not properly perceived and placed in the set ‗S 2 ' for daltonization. Basically we check if for all three values of each row of the error matrix (error_map) applies <0.08. Simultaneously the matrix ‗error_S 2 ' is created. If a row of the color palette must be placed in ‗S 2 ', then the corresponding row of the error matrix is added into the error matrix of ‗S 2 ' (error_S 2 ).

Daltonization of 'S2'. Key to the daltonization procedure is not the error matrix of the whole color palette as in [START_REF] Fidaner | Analysis of color blindness[END_REF] and [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF], but the error matrix only of those rows that need modification, namely the rows that belong to ‗S 2 ' (error_S 2 ). Actually the values of the error matrix of ‗S 2 ' are added to the initial values of the color palette of the quantized image, so that the values that indicate a high error level are redistributed to the blue side of the spectrum. This process is achieved with the help of the parameter matrix ‗M' of [START_REF] Fidaner | Analysis of color blindness[END_REF]. In the proposed methods the parameter matrix ‗M' is always initiated according to the values presented in [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF], as seen in ( 8).

Initially a multiplication of matrix ‗M' with every row of ‗error_S 2 ' is executed.

' ' ' R G B R G B TT E E E M E E E          (9)
The modified values E R ', E G ', E B ' which arise after the multiplication in [START_REF] Sgouroglou | Modification of Colors in Colored Images for Enhancing the Visual Perception of Protanopes[END_REF], are added to the values of the three components of the elements of ‗S 2 ', resulting the final daltonized values R d , G d , B d [START_REF] Spencer | Efficient Inverse Color Map Computation‖, Graphics Gems II[END_REF]. ' ' '

d d d R G B R G B R G B E E E            (10)
The colors R d , G d , B d that result after the modification of the elements of ‗S 2 ' are placed in a new set named ‗S 3 '.

RGB similarity checking module

The RGB similarity checking module consists of the following sub-steps: Simulation of 'S3'. For all the colors in ‗S 3 ' a simulation is performed and the new colors which result from the simulation are placed in the set ‗S 3_sim '.

RGB similarity checking module. Then the RGB similarity checking module is applied. It must be ensured that among new daltonized colors there is no color perceived by a person with protanopia, similar to a color that from the beginning remained intact. In other words, we must ensure that there is no similarity between the elements of the sets ‗S 1 ' and ‗S 3_sim '. This requirement is technically expressed by equations ( 11), (12).

    ' , ' , ' , ' ' ' true if R R d G G d B B d similar RGB R G B false otherwise             (11)
   

1 3 _ 1 3 _ , ' ' ' : ( , ' ' ') , sim sim true if RGB S R G B S similar RGB R G B confusion S S false otherwise          (12)
As ‗d' we denote an appropriately chosen threshold, which in this paper has the same value as in [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF]. As similar are considered all the combinations for which applies (r10, g 10, b10). This value in MATLAB corresponds to 0.04 (in the range 0-1). We check the subtraction between the components of each color of ‗S 1 ' and ‗S 3_sim ' (RGB and R΄G΄B΄ respectively). If the subtraction of the three components is below the value 0.04 then the two colors are perceived as identical. Conversely, if the subtraction of even one of the three components is bigger than the value 0.04 then the two colors are perceived as distinct. If even one color in ‗S 1 ' is found similar to a color in ‗S 3_sim ' then the procedure of daltonization is repeated with modified parameters of the matrix ‗M'. At each subsequent iteration the parameter ‗m 4 ' is reduced by amount ‗s', while the parameter ‗m 7 ' increases by the same amount. In this paper we used the same value as in [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF], namely s = 0.05. Thereby the redistribution of the red color in the blue channel increases, while the same amount of green is transferred to the blue channel.

Repetition if necessary. For the repetition of the daltonization routine when the RGB similarity check locates a pair of similar colors between ‗S 1 ' and ‗S 3_sim ' two methods were developed in [START_REF] Sgouroglou | Modification of Colors in Colored Images for Enhancing the Visual Perception of Protanopes[END_REF] and are presented in this paper.

Method 1: Daltonization by modification of entire "S2" and "error_S2". In the first proposed method the entire modified matrix ‗M' and the matrix ‗error_S 2 ' are subjected to the daltonization routine. This method results into more rapid changes of the image, as each time that a pair of similar colors is found, the entire content of ‗S 2 ' is being modified.

Method 2: Daltonization by modification of "S2" and "error_S2" per row. In the second proposed method the entire modified matrix ‗M' and only one row of matrix ‗error_S 2 ' are subjected to the daltonization routine. This row is the one that appears similar to some element of ‗S 1' . The results of this method show milder coloration results in the final image.

Termination condition. The iterative RGB similarity checking routine ends when there is no similar color found between ‗S 1 ' and ‗S 3_sim ' or when the parameter m 4 of matrix ‗M' is ≤ 0.05.

Image reconstruction. Before termination the algorithm proceeds to the creation of the final color palette ‗map 1 ' and reconstructs the image by replacing in the original color palette map all the colors that belong to the set ‗S 2 ' with the respective colors in ‗S 3 '. Finally, the color palette ‗map 1 ' is subjected to a final simulation in order to obtain the final daltonized image, as it will be perceived by a person with protanopia.

Experiments

respective color for the background (color A) is now perceived as (69,69,205), very close to the values of the color of the left ‗1' (color B). At this point we calculate the error of the color palette ‗map' by finding the absolute value of the difference between the palette ‗map_sim' and the original palette ‗map' of the quantized image. The result is stored in the matrix ‗error_map'.

Having defined the error palette, the algorithm continues with the classification of colors to those which are correctly perceived by a protanope and do not need daltonization (S 1 ) and to those which are not correctly perceived and do need daltonization (S 2 ). It is obvious in (14) that only the R component of the first row in the ‗er-ror_map' matrix shows a high value of error and therefore daltonization is necessary. In this way the colors of palette ‗map' are divided into the sets ‗S 1 ' and ‗S 2 ', while the error matrix ‗error_S 2 'of the set ‗S 2 ' is produced. In fact the set ‗S 2 ' contains the color A which is the color of the background, since that color is confused with the color B of the left ‗1' in the case of a protanope.

Thereafter the first iteration of the proposed daltonization algorithm is executed. The ‗error_S 2 ' matrix ( 17) is subjected to the daltonization routine as well as the original values of the ‗M' matrix (18). After daltonization the set ‗S 2 ' is renamed into ‗S 3 ' and its simulation is named ‗S 3_sim '.

As we can see after the first iteration the color of the background is changed into (69,210,255). This color is perceived by a protanope as (194,194,254) very close to the color of middle ‗1', which is now, as shown in figure 1e, not visible.

At this point the rgb similarity checking routine examines if there is any similarity between the one and only element (194,194,254) of ‗S 3_sim ' and the elements of the set ‗S 1 '. The routine detects similarity with the element (193,193,255) of the set ‗S 1 '. It is obvious that if the step of the rgb similarity checking routine was omitted then the final image would be that of figure's 1e and the middle ‗1' would be invisible by a protanope. The parameters of the ‗M' matrix are modified, as shown in (21). Thereafter comes the second iteration of the algorithm, by subjecting to the daltonization routine whether the whole ‗error_S 2 ' matrix (Method 1) or only that row of the matrix which shows the similarity (Method 2). To the daltonization routine we also subject the new matrix ‗M' with the modified parameters (21).

The results of the second iteration are described in the following:

After the second iteration the color of the background is transformed into (69,203,255). This color is perceived by a protanope as (188,188,254). However, once again there is no significant difference compared to the color C of the middle ‗1' which, as shown in figure 1f, remains indistinguishable.

Once more the rgb similarity checking routine is activated and examines whether the color (188,188,254) of the new matrix ‗S 3_sim ' is noticeably different from the elements of the set ‗S 1 '. Once more a similarity with the element (193,193,255) of the ‗S 1 ' is detected. We should remind that according to the rgb similarity checking routine as similar we consider all the color combinations for which stands   10, 10, 10

r g b   
. The parameters of matrix ‗M' are once more adapted as shown in equation ( 24) which results to the third iteration of the algorithm. The results of the third iteration of the algorithm are:

As we see, after the third iteration of the proposed algorithm, the color of the background (A) is changed into the color (69,196,255) which a protanope perceives as (182,182,254).

Once more the rgb similarity checking routine examines if the shade (182,182,254) of ‗S 3_sim ' matrix is considerably different from the elements of the set ‗S 1 '. This time fortunately no similarities are found and the algorithm continues with the reconstruction of the color palette ‗map' by replacing the elements of the set ‗S 2 ' with the elements of the set ‗S 3 '. In this way the palette ‗map 1 ' of the final image is produced (27) which is perceived by a protanope as shown in (28).

Experimental results

The implementation of the proposed algorithm resulted in a very good computational time, which was drastically reduced compared to that of [START_REF] Anagnostopoulos | Intelligent modification for the daltonization process of digitized paintings‖[END_REF]. Indicatively, in an Intel Core Duo, 2 GHz, 2 GHz, each iteration of the proposed algorithm's Method 2 in MATLAB when applied in a 24 bit 400x300 image with quantization to 256 colors, lasts about 0.04 seconds.

Since the computational time show up to 15x10 -3 variance in each execution of the algorithm and in order to determine more clearly if it is suitable for real-time processing in image sequences with the PAL/SECAM standard (25 frames/sec), a function that executes the algorithm 25 times iteratively was created. The results show that the application of Method 2 of the proposed algorithm with quantization to 256 colors, can achieve real-time processing in a live broadcasted video, as for the processing of 25 frames they remain under the threshold of 1 second.

From these results we also find that Method 2 of the proposed algorithm is slightly faster than Method 1 and this is especially evident in quantization with more than 128 colors. This is expected as in Method 1 many matrix multiplications are performed at

(a) (b) (c) (d)
each iteration of the rgb similarity checking module, in contrast to Method 2 where in each iteration only one multiplication is performed. Moreover, Method 1 after each iteration requires simulation of the entire ‗S 3 ' matrix, since the entire ‗S 2 ' changes, while in Method 1 simulation needs to be performed only at one row of ‗S 3 ' matrix, namely the one that corresponds to that row in ‗S 2 ' which was modified. Consequently, the minimization of the overall processing time in order to establish real time processing is successfully achieved.

The proposed algorithm could be modified in the future so after the initial daltonization of the image, the iterative daltonization of the RGB similarity checking module would only be performed if there is similarity and adjacency of relatively large areas among similar colors of ‗S 1 ' and ‗S 3_sim '.

In conclusion, the proposed algorithm presents several desirable features such as: (i) It is fast and deterministic (i.e. it always produces the same result for a given input image), (ii) It satisfies a global consistency property (i.e. all pixels of the same color in the original image will be mapped to the same recoloration in the final image), (iii) It preserves the original image luminance and natural appearence (i.e. false colors are avoided) and (iv) It can be efficiently implemented on modern GPUs.

Conclusions

In this paper an improved daltonization algorithm for protanopia is proposed. An intelligent iteration technique is suggested for the selection of the adaptation parameters, incorporating a color quantization technique. Computational time is drastically reduced. Consequently, the minimization of the overall processing time in order to establish real time processing in live broadcasted/streaming videos is successfully achieved.

Figure 2

 2 Figure 2 demonstrates the result of applying both methods in Van Gogh's -Field of Poppies‖. It is evident that Method 1 has more a distinguishable effect from Method 2 and therefore it is considered more adequate to model the color difference for the specific image.

Fig. 2 .

 2 Fig. 2. For quantization to 256 colors: (a) Initial image, (b) Protanope perception, (c) Method 1: Protanope perception, (d) Method 2: Protanope perception.


Manolis Maragoudakis

Katia Lida Kermanidis

Spyros Vosinakis
email: spyrosv@aegean.gr

Extracting Knowledge from Collaboratively Annotated Ad Video Content

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Creative advertising is the process of capturing a novel idea for an ad campaign and designing its implementation. As it constitutes one of the highest-budget enterprises today, several studies have been published regarding the impact of advertising [START_REF] Amos | Exploring the Relationship between Celebrity Endorser Effects and Advertising Effectiveness[END_REF][START_REF] Aitken | Advertising Effectiveness from a Consumer Perspective[END_REF], as well as creativity in advertising [START_REF] Hill | Understanding Creative Service: A Qualitative Study of the Advertising Problem De-lineation, Communication and Response (APDCR) Process[END_REF]. Several tools have been proposed in the literature for supporting the creative brainstorming process of ad design. A number of creativity support tools have been proposed, to help ad designers come up with novel ideas for setting up a new campaign. They usually focus on using creativity templates [START_REF] Goldenberg | The Fundamental Templates of Quality Ads[END_REF], decision making systems, like ADCAD [START_REF] Burke | A Knowledge-based System for Advertising Design[END_REF], linguistic wording schemata [START_REF] Blasko | Creativity in Advertising: A Janusian Perspective[END_REF], databases of predefined concepts and their associations, like IdeaFisher [START_REF] Chen | Computational Intelligence for Decision Support[END_REF]. Idea Expander [START_REF] Wang | Idea Expander: Supporting Group Brainstorming with Conversa-tionally Triggered Visual Thinking Stimuli[END_REF] is a tool for supporting group brainstorming by showing pictures to a conversing group, the selection of which is triggered by the conversation context. [START_REF] Opas | An Investigation into the Development of a Creativity Support Tool for Advertising[END_REF] presents a detailed overview of several advertising support tools.

Based on the belief that total freedom is not the most efficient way for enhancing the creative process, but constraining it with the use of a limited number of idea-forming patterns is, these tools force upon the advertiser a certain restricted way of thinking. Concepts, associations are static and predefined, and the user is guided through the problem entities to make connections between them. Required facts and rules are expert-dependent and usually quite hard to craft. Dictionaries and databases are static and non-expandable. According to [START_REF] Opas | An Investigation into the Development of a Creativity Support Tool for Advertising[END_REF], static, passive, expertdependent knowledge models can hurt creativity.

PromONTotion is a creative advertising support tool that relies on generic, automatically acquired knowledge. The core of the tool is comprised of a semantic thesaurus, i.e. an ontology of terms and concepts that are related to the content, style, genre, artistic features, consumer impact and popularity of television ad videos. These terms and concepts are provided via crowdsourcing by players of a multi-player quiz/combat/action style computer game, House of Ads, developed especially for this purpose and described in detail in [START_REF] Kermanidis | Designing a Support Tool for Creative Advertising by Mining Collaboratively Tagged Ad Video Content: The Architecture of PromONTotion[END_REF].

The present work describes in detail the mining experiments performed on an initial set of annotations. Mining techniques are applied to the provided data for the extraction of correlation information, of interdependencies between various features of the ad, of knowledge related to what increases the ad impact and popularity.

PromONTotion relies on very limited predefined knowledge, i.e. the ontology backbone, its hierarchical structure. The ad knowledge provided by the tool is datadriven and automatically derived making PromONTotion generic, dynamic, scalable, expandable, robust and therefore minimally restricting in the creative process and imposing minimal limitations to ideation or brainstorming.

This article is structured as follows: Section 2 presents a sketch of the ontological backbone used to identify key elements of the advertisement domain, while Section 3 describes the data mining approaches used upon collected data, in order to identify meaningful patterns and associations between objective ad parameters and subjective user feedback. Finally, the paper concludes in section 4.

Modeling The TV Ad Domain

The domain model in this work is represented as a hierarchical ontology of TV ad video concepts and terms. The ontological backbone structure is the only piece of knowledge that is manually crafted, by advertising domain experts. It contains terms and concepts that are related to the video content, the ad style and genre, its production values, its artistic features, as well as its impact and its impression print on consumers. The structure is scalable. Some representative product and services types are included currently, but the list is easily expandable. In detail, the ontology structure and categories are shown in Figure 1. Following the trend of serious games paved by von [START_REF] Von Ahn | Games with a Purpose[END_REF] and game design for ontology populating [START_REF] Siorpaes | Games With A Purpose For The Semantic Web[END_REF], the House of Ads multiplayer browser-based action game [START_REF] Kermanidis | Designing a Support Tool for Creative Advertising by Mining Collaboratively Tagged Ad Video Content: The Architecture of PromONTotion[END_REF] was designed and developed for collaboratively providing ad content annotations, i.e. for ontology populating.

Mining Through Advertisement Terms

An initial set of annotations of 74 videos were used for performing preliminary mining experiments. The data were provided by 21 players. For the preliminary experiments 20 different ad videos were selected and every player was assigned the annotation of 3 to 5 videos. Exploratory as well as predictive data mining is applied to the collected data, for detecting patterns and interdependencies among ad features, as well as their association with the ad's impact on consumers/players and its popularity. All categories proposed by the domain experts are considered features (41 in number) that define the ad domain space, and every ad video constitutes a data instance. It needs to be noted that 13 out of the 41 features present a missing value percentage of more than 80%, due to the hierarchical structure of the ontology. The input of lower-level annotations de-pends on the corresponding value of the parent node in the hierarchy. If the specific parent value is not provided, values of the sub-nodes are missing.

Mining Associations

The Apriori algorithm [START_REF] Liu | Integrating Classification and Association Rule Mining[END_REF] on the Weka1 machine learning workbench was used for extracting association rules from the data. Given the small number of distinct videos involved in the preliminary experiments, rules concerning only the objective (content/style/genre) data regarding the ad, e.g.

Service=telecom=>GenderOfMainCharacter=male(Confidence=1)

TargetGroup=women=>Location=inside( Confidence=1)

have not been given attention. Although they are interesting. the small number of videos does not allow for their generalization. Rules related to the subjective data, however, reveal interesting findings. For example, they show an absolute correlation between the convincing ability of the ad and how the player liked the ad:

Opinion=LikeNo => Convincing=No (Confidence=1) Opinion=LikeALittle => Convincing=So-So (Confidence=1) Opinion=LikeALot => Convincing=ALot (Confidence=1)
A strong correlation between these two features was expected, but the absolute correlation constitutes an interesting finding. These rules emerged after removing attributes (e.g. ProductType) that led to trivial, uninteresting rules, like

Service=telecom => ProductType=service

Classification

Predictive experiments were run on the Weka platform for identifying the correlation of the various ad features with the ad's impact on the players. To this end the Opinion feature denoting how the player liked the ad (with values No, ALittle, Considerably, ALot), the Convincing feature, indicating how persuaded the player felt by the ad (with values No, SoAndSo, ALot), and the Changes feature, that lists the ad features that the player does not like and would change if he could (with values Everything, Nothing, TheCharacters, TheLocation, TheContent, TheMusic, TheGenre, Other), were used as class labels. The main goal of this task is to focus on exploratory data analysis and reveal interesting interdependencies. As the following experiments show, the data is too few, the percentage of missing values too high and the feature space too large to expect high accuracy predictive performance at this phase.

Due to their comprehensibility and their ability to cope with missing values using distribution-based imputation [START_REF] Saar-Tsechansky | Handling Missing Values When Applying Classification Models[END_REF], decision trees are the first algorithm employed for inducing a classification model. Support Vector Machines [START_REF] Cortes | Support-vector Networks[END_REF] were also experimented with, as they have been proven to perform well on problems with few learning items in large feature spaces. The Sequential Minimal Optimization algorithm [START_REF] Platt | Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines[END_REF] is used for training the SVM classifier and a third degree polynomial kernel function is chosen. Tables 1,2 and 3show the results for the three class attributes and the two classification algorithms. All experiments were run using 10-fold cross validation.

For the Changes attribute, the results for the remaining values are zero, or close to zero, due to their sparse occurrence in the data. In the last line of Keeping in mind that the available learning items in these preliminary experiments are very few, the number of features is significant, the percentage of missing values is very high and the classification task is not binary, these results at this stage are quite promising for the experiments to be conducted when the annotation phase has progressed and learning items have accumulated.

The 'simple' SVMs classifier used is in most cases outperformed by C4.5. This is largely attributed to the missing values problem. It has been reported in the literature [START_REF] Pelckmans | Handling Missing Values In Support Vector Machine Classification[END_REF] that SVMs require additive models (e.g. component wise SVMs and LS-SVMs) to cope adequately with missing values.

The attributes that are significant for predicting the convincing power of the ad, included in the decision tree model, include (except the opinion of the player) the fame of the main character (famous characters seem to be more convincing) and the genre of the ad (cartoon ads seem to imprint their message more efficiently on consumers compared to realistic genre ads). Regarding the prediction of the player's opinion of the ad, except for the convincing attribute, the location of the ad story (urban environment, home, country), as well as the artistic features (e.g. music recognition) play an important role. Finally, regarding the prediction of changes the players propose, the opinion is understandably the most important feature, with a negative correlation. The use of taglines and famous logos is also strongly correlated to the prediction of the content value of changes, possibly indicating that they are a communication tool consumers get easily tired of.

Bayes Simulation

For the purpose of our study, Bayesian Networks (BN) are used for modelling of a marketing process. More specifically, subjective advertisement attributes, such as User Opinion, Convincing Level and Changes Required are modelled in parallel with objective attributes, as thoroughly described in Section 2. Unlike classification analysis, BN modelling can support two semantic operations, namely diagnostic inference (i.e. from effects to causes) and causal inference (i.e. from causes to effects) [START_REF] Friedman | Building Classifiers and Bayesian Networks[END_REF]. As regards the former operation, we are mostly interested in providing the most probable value for the subjective attributes, given the values of remaining objective ones and benchmark its performance against the wellknown classification algorithms. Concerning the latter operation, the aim is to model the dependency between input and output parameters, and based on the extracted modelling outcome, calculate the objective input parameters that guarantee an optimal subjective output (i.e. with a maximal probability). The aforementioned task can be accomplished by entering the intended output as evidence and then calculate the most probable instantiation of the remaining input parameters that caused the intended output.

Diagnostic Inference

In this setting, a BN was built from the initial dataset, using the K2 learning approach [START_REF] Cooper | A Bayesian Method for the Induction of Probabilistic Networks from Data[END_REF]. Upon, learning, the BN was used in order to generate data instances. The generation process is as follows: a node without parents is selected as a starting point. According to its conditional probability table (CPT), a value is drawn using a roulette wheel strategy. This value is passed to the child node and again, using the CPT from the BN, a value for that child node is also selected. This process is progressing to all nodes in the BN until a sample containing values for all attributes is generated. The new, augmented dataset was evaluated using a variation of Naïve Bayes classifier which incorporates elements from Bayesian Networks, namely a variation of Tree-Augmented Naïve Bayes (TAN) algorithm [START_REF] Friedman | Bayesian Network Classifiers[END_REF]. In our approach, the class node is kept separately from the other, attribute nodes. A BN is learned and then the class node is placed as the parent of all other nodes in order to favor classification. For comparative analysis, tables 4, 5 and 6 show classification results of TAN against C4.5 and SVMs (parameter setup identical to the previous experiments) with the simulated dataset. The TAN classifier is considered superior than Naïve Bayes [START_REF] Friedman | Bayesian Network Classifiers[END_REF], mainly because of the fact that input attributes are not considered as independent among each other, given the class. On the contrary, the input attributes in a TAN representation form a BN that could explain possible inter-relations found in data.

From the above results, it is clear that Convincing, when used as the class, could provide the most satisfactory outcomes, compared with the other two attributes, Opinion and Changes. The TAN methodology performs slightly better than SVM and is very close to C4.5, although in some cases TAN seem to outperform both learners.

Causal Inference

The aim of this experiment is to model the dependency between input and output parameters, and based on the extracted modeling outcome, to calculate the input parameters that guarantee an optimal output with a maximal probability. The structure of the BN allows for such an operation by entering target values on selected nodes and then estimating the most probable instantiation of the remaining input parameters that provides the entered output.

The exact scenario is as follows: a domain expert is interested in observing the effect that Opinion and Convincing have to the other variables, given that Changes is known. The first scenario (optimistic) assumes that Opinion=Alot and Convinc-ing=Alot given Changes=nothing, while the second scenario (pessimistic) considers the hypothesis that Opinion=No and Convincing=No given Changes=everything.

By measuring the progression of the values for each input variable given the scenario assumptions, one can draw significant conclusions on the effect of each parameter. For reasons of readability, only the variables that belong to the Markov Blanket of the nodes Opinion and Convincing are shown in Tables 7 and8. The Markov Blanket of a node contains the set of parent, children and children's parent of that node. It is proven that any node that is not within the Markov Blanket, is not influencing or not being influenced by that node. Table 7 tabulates the most probable attribute instantiations for the input attributes, given evidence described in scenario 1, while Table 8 shows the same information given the evidence representing the pessimistic scenario.

Taking a closer look at the first scenario, one could observe that when a user has a positive opinion and states that an advertisement is convincing, the most probable product being advertised is a drink. Moreover, the main character is human, middle aged and not a famous actor or celebrity. Since the most probable product is a drink, the advertisement does not promote something novel and moreover, the location is indoor and therefore the photography is neither picturesque nor landscape. Finally, the advertisement is an isolated episode and there are no famous utterances used. On the contrary, using the pessimistic scenario, in which a user holds a negative opinion and is not persuaded by the advertisement, one could observe that the product is not listed (note: the listed products were: electronic services, clothes, drink, electronic device, household, vehicle and store). An interesting remark is that despite what most would assume, the presence of famous persons, young in age and the inclusion of a humoristic scenario do not guarantee user satisfaction in terms of convincement and opinion. On the other hand, these instantiations seem to cause a negative impact. Finally, it is noteworthy that in a pessimistic scenario, the location is a workplace.

Attribute

Attribute

Conclusion

In this paper we described the results of some preliminary mining experiments that were performed on an initial set of ad content annotations. More specifically, Association Discovery, Classification and Bayesian network analysis were incorporated in order to examine potentially meaningful patterns. The major obstacle that the limited amount of training data was confronted by training a Bayesian network and then applying a simulation step that generated a plethora. Experiments with the initial and the augmented dataset using various classifiers showed that classification accuracy may be improved using Bayesian modelling. Moreover, causal inference was also applied using the BN structure, simulating two different scenario settings, which revealed some useful insight on input attributes and their impact on subjective attributes such as User opinion and Convince level. More interesting and confident findings will be revealed after processing an annotation set of significant size, when the annotation process of PromONTotion has progressed. The use of mining algorithms that are better suited to cope with data consisting of a significant percentage of missing values is also planned for future research.

Fig. 1 .

 1 Fig. 1. The Ontology backbone.

Table 1 .

 1 Table 3, the average precision and recall value over all class values is shown instead. Results for the Opinion class.

	Opinion Attribute	C4.5		SVMs
		Precision Recall	Precision Recall
	No	0.389	0.467	0.462	0.4
	ALittle	0.524	0.55	0.464	0.65
	Considerably	0.35	0.412	0.429	0.353
	ALot	0.8	0.545	0.632	0.545
	Convincing	C4.5		SVMs
	Attribute	Precision Recall	Precision Recall
	No	0.579	0.524	0.632	0.571
	SoAndSo	0.718	0.7	0.727	0.8
	ALot	0.5	0.615	0.636	0.538

Table 2 .

 2 Results for the Convincing class.

	Changes Attribute	C4.5		SVMs
		Precision Recall	Precision Recall
	Everything	0.357	0.455	0.3	0.273
	Nothing	0.676	0.758	0.5	0.848
	Content	0.364	0.364	0	0
	Average (all classes)	0.449	0.5	0.268	0.419

Table 3 .

 3 Results for the Changes class.

Table 4 .

 4 Classification results with the simulated dataset for the Opinion class.

	Opinion Attrib-		C4.5		SVMs		TAN
	ute	Precision Recall Precision Recall Precision	Recall
	No	0.553	0.638	0.556	0.542	0.545	0.602
	ALittle	0.452	0.207	0.328	0.321	0.423	0.342
	Considerably	0.386	0.686	0.354	0.329	0.401	0.312
	ALot	0.808	0.619	0.569	0.623	0.762	0.687
	Convincing	C4.5		SVMs		TAN
	Attribute	Precision Recall	Precision Recall	Precision	Recall
	No	0.691	0.732	0.649	0.626	0.661	0.673
	SoAndSo	0.797	0.723	0.689	0.711	0.691	0.715
	ALot	0.665	0.784	0.6	0.577	0.701	0.873

Table 5 .

 5 Classification results with the simulated dataset for the Convincing class.

	Changes Attribute	C4.5		SVMs		TAN
		Precision Recall Precision	Recall	Precision Recall
	Everything	0	0	0.153	0.182	0.134 0.152
	Nothing	0.436	1	0.447	0.522	0.356 0.466
	Content	0	0	0.172	0.181	0.231 0.199
	Average (all classes)	0.19 0.436	0.259	0.292	0.232 0.243

Table 6 .

 6 Classification results with the simulated dataset for the Changes class.

Table 7 .

 7 The most probable attribute instantiations for the optimistic scenario. (i.e. Opini-on=Alot and Convincing=Alot given Changes=nothing)

		Value
	Product	Drink
	Genre	Realistic
	MainCharacter	Human
	Fame	Everyday character
	Age	MiddleAged
	Occupation	Employee
	Humor	noHumor
	SongRecognizable Yes
	Novelty	Known product/service
	Location	Indoor
	Photography	Other
	Structure	Isolated episode
	FamousLines	No famous lines

Table 8 .

 8 The most probable attribute instantiations for the pessimistic scenario. (i.e. Opini-on=No and Convincing=No given Changes=everything)

		Value
	Product	Other
	Genre	Other
	MainCharacter	Human
	Fame	Famous person
	Age	Young
	Occupation	Other
	Humor	Humoristic scenario
	SongRecognizable No
	Novelty	New product/service
	Location	Workplace
	Photography	Notvalid
	Structure	Isolated episode
	FamousLines	No famous lines

http://www.cs.waikato.ac.nz/ml/weka/

Acknowledgements

This Project is funded by the National Strategic Reference Framework (NSRF) 2007-2013: ARCHIMEDES ΙΙΙ -Enhancement of research groups in the Technological Education Institutes.


Fotis E Psomopoulos

Pericles A Mitkas

Algebraic interpretations towards clustering protein homology data

The identification of meaningful groups of proteins has always been a principal goal in structural and functional genomics. A successful protein clustering can lead to significant insight, both in the evolutionary history of the respective molecules and in the identification of potential functions and interactions of novel sequences. In this work we propose a novel metric for distance evaluation, when applied to protein homology data. The metric is based on a matrix manipulation approach, defining the homology matrix as a form of block diagonal matrix. A first exploratory implementation of the overall process is shown to produce interesting results when using a well explored reference set of genomes. Near future steps include a thorough theoretical validation and comparison against similar approaches.

Introduction

In the era of Big Data, the quest for identifying hidden patterns and relationships is becoming an ever increasingly demanding objective, but at the same time, an imperative goal for most researchers. This situation holds particularly true in the fields of structural and functional genomics, where the need to assign potential functions and interactions to a rapidly expanding number of novel protein sequences is increasingly evident [START_REF] Williams | Big Data analysis on autopilot?[END_REF] [START_REF] Overbeek | The use of gene clusters to infer functional coupling[END_REF]. There exist several algorithms in literature that address the issue of protein data clustering, ranging from generally applicable approaches [START_REF] Enright | An efficient algorithm for large-scale detection of protein families[END_REF] [4] [START_REF] Miele | Ultra-fast sequence clustering from similarity networks with SiLiX[END_REF], to highly specialized algorithms tailored for specific studies (i.e. studies focused on particular species [START_REF] Röttger | Density parameter estimation for finding clusters of homologous proteins-tracing actinobacterial pathogenicity lifestyles[END_REF], sets of genomes [START_REF] Fouts | PanOCT: automated clustering of orthologs using conserved gene neighborhood for pan-genomic analysis of bacterial strains and closely related species[END_REF] or groups of molecules [START_REF] Bonet | ArchDB 2014: structural classification of loops in proteins[END_REF]).

A common concept in the vast majority of the clustering algorithms is "protein homology", i.e. the inherent degree of similarity that is assigned to a pair of protein sequences after application of a pair-wise comparison algorithm such as BLAST [START_REF] Altschul | Basic local alignment search tool[END_REF]. This similarity metric is consequently used to define new measures of distance, in order to produce the necessary data partitioning, and therefore, insight into the intrinsic organization of the data involved.

A second key issue in any given clustering algorithm is the number of partitions created. As is often the case with big data, the actual number of "correct" and meaningful clusters is either unknown or hard to evaluate. Therefore there are two main approaches towards this issue; either approximate the number of clusters through external algorithms or parameters (such as in the case of k-means), or allow the clustering algorithm to construct an arbitrary number of clusters, based on its inner design (such as in the case of the popular MCL algorithm [START_REF] Enright | An efficient algorithm for large-scale detection of protein families[END_REF]).

In this work we propose a new algorithm, where the distance metric and an estimate of the clusters to be constructed is directly interpreted from the protein homology data. The rest of the paper is organized as follows: first we define the key concepts and techniques used within the context of the clustering process. The next section outlines the proposed algorithm and formally defines the metrics used. We conclude with the application of the novel metric on a well studied set of target genomes.

Problem Outline and Definitions

Attempting to formally define the protein clustering problem, we first need to provide the definitions of the concepts involved.

Given a set of protein sequences, the homology matrix, a key concept in any protein clustering algorithm, can be defined as an matrix as follows:

, ,

where , is the expect value of the pair-wise sequence comparison of protein sequence and , using the BLAST algorithm. The expect-value, or e-value, is defined as the number of hits (correct alignments) expected to emerge by chance when searching a database of a certain size. At this point it is important to note that matrix is square but not necessarily symmetrical, i.e. , , . A second key aspect of the homology matrix is that it is inherently sparse, i.e , 0, ∀ , ≪ , 0, ∀ , . This qualitative characteristic is quantified through the sparsity metric of the matrix, defined as:

, ,∀ , , ,∀ , (2)
A third aspect of a homology matrix emerges when protein sequences across genomes (where 1) are included in the data set. The sparsity pattern of the matrix reveals a structure reminiscent of a block diagonal matrix. By definition, a block diagonal matrix is a square diagonal matrix in which the diagonal elements are square matrices of any size (possibly even 1 1), and the off-diagonal elements are zero matrices, i.e.:

0 0 ⋯ 0 0 ⋮ ⋱ ⋮ 0 0 ⋯
where each is a square matrix

However, the formal definition of a block diagonal matrix differs with regard to the case of a homology matrix produced from sequences across genomes. The difference lies in the fact that the off-diagonal elements are not zero, but exhibit significantly higher sparsity percentage compared to the diagonal elements.

With the above definitions, the problem we are attempting to address can be formally defined as follows: given a homology matrix , define an appropriate distance metric applied directly on , which will be consequently used within an agglomerative clustering process in order to produce a segmentation of based on the , values.

Methods

The algorithm comprises three distinct stages. The first pre-processing stage transforms the pair-wise comparison data into a full homology matrix. This is a necessary step as the standard output of the BLAST algorithm cannot be readily used in matrix manipulations, mainly due to the missing values and the scoring system employed. The second stage uses the constructed matrix in order to identify the target number of clusters. Finally, the proposed distance metric is applied through a standard agglomerative clustering process.

At this point it must be noted that the proposed method does not aim to replace the BLAST algorithm or to provide similar functionality. Instead, by directly utilizing the output of BLAST, we aim to construct a singular analysis method that evaluates this information in the form of clusters.

Pre-processing stage

The pair-wise alignment algorithm BLAST, employs a scoring system based on the expect value (e-value). Therefore, by definition, given two sequences and , the respective e-value would be: , missing value , when cannot be aligned with 0 , when there exist a valid alignment 0 , when the two sequences are identical

In order to produce the homology matrix , we apply the following transformation: , 0

, when , log , , when , 0 large constant c , when , 0

This linear transformation in essence changes only the range of values that appear in matrix without affecting the attributes and characteristics of the data involved. With regard to the large constant, in our case we have set 1000, but any sufficiently large number can be used

Cluster number estimation

As stated earlier, one of the key issues in data clustering is the definition of the number of clusters to be produced. In our case, this number is estimated directly from the characteristics of the homology matrix .

In linear algebra terms, the use of a block matrix corresponds to having a linear mapping thought of in terms of corresponding sets of basis vectors. This can be further viewed as having separate direct sum decompositions of both the domain and the range of the matrix. By completeness purposes, for any arbitrary matrices and , the direct sum of A and B is denoted by A  B and defined as:

A  B , ⋯ , ⋮ ⋱ ⋮ , ⋯ , 0 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ 0 0 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ 0 , ⋯ , ⋮ ⋱ ⋮ , ⋯ , (6)
Given the fact that the matrix is square, we can also interpret the mappings as an endomorphism of an n-dimensional space V, i.e. a linear map such as ƒ: V → V. In that regard, the block structure is of importance as it corresponds to having a single direct sum decomposition on V.

However, we must take under consideration the fact that the homology matrix is an approximation of a block diagonal matrix. In order to evaluate the potential num-ber of blocks existent within , we employ the eigenvalues of the matrix as the functional characteristic degree for the final segmentation.

Distance metric

The final stage in the clustering process requires the definition of an adequate distance metric. There are two key points that should be taken under consideration:

─ Both dimensions of the homology matrix directly correspond to an ordered list of protein sequences. For the purposes of this work, the ordering of the protein sequences is based on the relative position of the respective genes on the genome chromosome. ─ As can be also surmised from Equation ( 5), the distribution of values of matrix is heavily biased on two ends, corresponding to the two cases of protein sequence alignment; no similarity (hence the sparsity of matrix) and complete identity.

Therefore, special care has be taken to include those attributes into the proposed metric, as seen in the equation below:

, , ,

| , && , , , && , , , && , && |
where | | and an arbitrary constant satisfying

∑ , , , ,∀ ,
.

The metric clearly defines four distinct states in the homology matrix :

1. closely located genes within the same range of similarity. In this case, as the genes are expected to be linked at some level, the distance takes into account only the homology values but with a bias towards smaller distance. 2. closely located genes with significant difference in homology. In this case, the respective genes are expected to belong to different functional groups, and therefore the distance is biased towards larger values. 3. distant genes within the same range of similarity. This is a very interesting case, as it should contain genes across different species that exhibit a high level of similarity. 4. distant genes with significant difference in homology. This is the most distant case of gene similarity, therefore the maximum distance is assigned.

The function shown in Equation ( 7) is used in the clustering process in order to produce the distance matrix and, consequently, the required clusters.

Results

In order to evaluate the effectiveness of the proposed metric, we employed a wellstudied group containing the following five genomes ( [START_REF] Freilich | Stratification of co-evolving genomic groups using ranked phylogenetic profiles[END_REF], [START_REF] Psomopoulos | Detection of genomic idiosyncrasies using fuzzy phylogenetic profiles[END_REF]):

1. Mycoplasma genitalium, G-37 [START_REF] Fraser | The minimal gene complement of Mycoplasma genitalium[END_REF] (Bacteria; Firmicutes; Mollicutes; Mycoplasmatales) 479 genes, COGENT code: MGEN-G37-01. 2. Ureaplasma urealyticum, serovar 3 [START_REF] Glass | The complete sequence of the mucosal pathogen Ureaplasma urealyticum[END_REF] (Bacteria; Firmicutes; Mollicutes; Mycoplasmatales) 613 genes, COGENT code: UURE-SV3-01. [START_REF] Ferretti | Complete genome sequence of an M1 strain of Streptococcus pyogenes[END_REF] (Bacteria; Firmicutes; Bacilli; Lactobacillales) 1696 genes, COGENT code: SPYO-SF3-01. 4. Buchnera aphidicola, SG [START_REF] Shigenobu | Genome sequence of the endocellular bacterial symbiont of aphids Buchnera sp[END_REF] (Bacteria; Proteobacteria; Gammaproteobacteria; Enterobacteriales) 545 genes, COGENT code: BAPH-XSG-01. 5. Nanoarchaeum equitans, Kin4-M [START_REF] Waters | The genome of Nanoarchaeum equitans: insights into early archaeal evolution and derived parasitism[END_REF] (Archaea; Nanoarchaeota) 563 genes, COGENT code: NEQU-N4M-01.

Streptococcus pyogenes M1, SF370

The phylogenetic relationships of the species is represented by the dendrogram in Fig. 1. In order to produce the initial matrix containing the expect value of the sequence similarities, we employed the BLAST algorithm with the default parameters. The homology matrix is produced directly from the e-values, through the preprocessing step (Equation 5, where 1000). A visual representation of the final matrix is shown in Fig. 2 below.

It must be noted that Fig. 2 showcases only the sparsity of the homology matrix, and does not take into account the actual values of the non zero elements. However, even this simplified representation is sufficient to evaluate the patterns that emerge from the genome-wide sequence comparison.

Fig. 2.

Visual representation of the homology matrix. A non-zero value is denoted with a blue dot, whereas a zero value is denoted with a white dot. The purple lines show the limits of the five species in the dataset (same on both axes).

It is also critical to evaluate the initial assumption of the similarity between the homology matrix and a block diagonal matrix. To this end, Fig. 3 shows the sparsity value of the sub-matrices, using Equation (2) for the metric evaluation. Before applying the distance metric for the clustering process, we calculate the eigenvalues of the input matrix in order to set the number of clusters to be produced. Finally, inserting the proposed distance metric into the clustering process, we can produce a clustering of the protein sequences as shown in the following figures (Fig. 4. and Fig. 5.).

[a]

[b] There are mainly two observations that can be made from the produced clusters; (i) the proposed distance metric allows for the discrimination of the different levels of homology, and (ii) the differentiation of the pair-wise genome comparisons (i.e. the different "cells" of the matrix) is not following closely the expected relationships.

Regarding the first observation, we can further infer from the results that there exist three distinct clusters containing the low value homology scores (green, yellow and cyan clusters), two correspond only to the high level similarity (red and magenta), and only one (blue cluster) that is constrained within a specific area of mid-level similarity. Specifically, this area corresponds to the two genome comparisons; Streptococcus pyogenes (SPYO) -Mycoplasma genitalium (MGEN) and Streptococcus pyogenes (SPYO) -Buchnera aphidicola (BAPH).

Discussion

In this work we propose an alternate distance metric for clustering protein sequences through a direct application on the corresponding homology matrix. Both the metric and the underlying concepts are based on the assumption that a homology matrix can be interpreted as a block diagonal matrix. This assumption is further explored and exploited through the estimate of the expected clusters and the definition of the distance metric.

We have provided some preliminary results by applying the proposed method in order to cluster data from a well-studied set of protein sequences. Although the results are very encouraging, by showing significant differentiation of the various levels evident within the homology matrix, it is still a work in progress, requiring rigorous testing and validation. To this end, future work includes extensive comparison of the proposed method against similar algorithms, both from within the Machine Learning community and the Bioinformatics community.

Finally, an equally important issue to be explored is the scalability of the implemented algorithm. The problem of efficient and meaningful clustering of protein data is an open research issue which promises to become a key issue in next generation sequencing data analysis.

Fig. 1 .

 1 Fig. 1. Simplified dendrogram of the five species in the input dataset. The COGENT codes are used for genome representation.

Fig. 3 .

 3 Fig. 3. Sparsity value of the homology matrix. Each sub-matrix corresponds to a pair of genomes.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Clustering of the homology matrix across the three dimensions, where x and y correspond to the ordered protein sequences and z corresponds to the homology value of the respective sequence comparison. [a] shows the clustering on the two dimensions (i.e. ignoring the z axis) and [b] shows the clustering on all three dimensions.


Gerasimos Razis
email: razis@dib.uth.gr

Ioannis Anagnostopoulos

InfluenceTracker: Rating the impact of a Twitter account

Keywords: Twitter, Influence, Information Diffusion 1

This paper describes a methodology for rating the influence of a Twitter account in this famous microblogging service. Then it is evaluated over real accounts, under the belief that influence is not only a matter of quantity (amount of followers), but also a mixture of quality measures that reflect interaction, awareness, and visibility in the social sphere. The authors of this paper have created "InfluenceTracker", a publicly available website 1 where anyone can rate and compare the recent activity of any Twitter account.

Introduction

Microblogging is a form of Online Social Network (OSN) which attracts millions of users on daily basis. Twitter is one of these microblog services. Their users vary from citizens to political persons and from news agencies to huge multinational companies. Independent of the type of the user and of the degree of influence on other users, all share the same need; to spread their messages to as many users as possible. The messages, which are regarded as pieces of information, can be spread in two ways, either directly or indirectly. A case of direct message is when a company reveals information about a new product to its followers. When such a follower decides to share it among his or her own followers, then that is a case of indirect information dissemination. In this paper, we propose a methodology for calculating the importance and the influence of a user in Twitter, as well as a framework, which describes the maximization of diffusion of information in such a network.

The remainder of this paper is organized as follows. In the next section, we provide an overview over the related work on discovering influential users and on information diffusion in OSNs. Then, in Section 3 we describe the proposed methodology and the basic steps of the framework we use. In Section 4 real case scenarios are presented, in order to clearly show how we calculate the dissemination of information in Twittersphere, while in parallel we present the results along with their assessment. Finally, Section 5 provides the conclusions of our work by summarizing the derived outcomes, while providing considerations on our future directions.

Related Work

The calculation of the impact a user has on social networks, as well as the discovery of influencers in them is not a new topic. It covers a wide range of sciences, ranging from sociology to viral marketing and from oral interactions to Online Social Networks (OSNs). In the related literature the term "influence" has several meanings and it is differently considered most of the times.

Romero et al. [START_REF] Romero | [END_REF] utilize a large number of tweets containing at least one URL, their authors and their followers in order to calculate how influential or passive, in terms of activity, the Twitter users are. The produced influence metric depends on the "Follower-Following" relations of the users as well as their retweeting behavior. The authors state that the number of followers a user has is a relatively weak predictor of the maximum number of views a URL can achieve. As our work has shown (Section 3.2), through the retweet functionality information can be diffused to audience not targeted.

Cha et al. [START_REF] Cha | Measuring User Influence in Twitter: The Million Follower Fallacy[END_REF] introduce for each Twitter user three types of influence, namely "Indegree" (number of followers), "Retweet" (number of user generated tweets that have been reweeted) and "Mention" influence (number of times the user is mentioned in other users' tweets). A necessary condition for the computation of these influence types is the creation of at least ten tweets per user. The authors claim that "Retweet" and "Mention" influence correlate well with each other, while the "Indgree" does not. Therefore they suggest that users with high such influence type are not necessarily influential.

A topic oriented study on the calculation of influence in OSNs is presented in (Weng et al. 2010). The authors propose an algorithm which takes into consideration both the topical similarity between users and their link structure. It is claimed that due to homophily, which is the tendency of individuals to associate and bond with others having similar interests, most of the "Follower-Following" relations appear. This work also suggests that the active users are not necessarily influential.

Another approach which defines influence in terms of copying what the directly related do is presented by [START_REF] Goyal | Learning influence probabilities in social networks[END_REF]. In this work, the authors propose an influenceability score, which represents how easily a user is influenced by others or by external events. It is built on the hypothesis that a very active user performs actions without getting influenced by anyone. That type of users are regarded as responsible for the overall information dissemination in the network.

Yang and Counts (Yang and Counts, 2010) attempt to measure how topics propagate in Twitter. They constructed a diffusion network based on user mentioning, with constrains on topical similarities in the tweets. The authors state that given the lack of explicit threading in Twitter, this is the optimal approach of a network diffusing information about a specific topic. Moreover, the mention rate of the person tweeting is a strong predictor regarding the information diffusion in Twitter. Lerman and Ghosh (Lerman and Ghosh, 2010) studied the diffusion of information in two social networks, Digg and Twitter. They conclude that the structure of these networks affects the dynamics of information flow and spread. According to the authors, information in denser and highly interconnected networks, such as of Digg's, reaches nodes faster compared to sparser networks, such as of Twitter's. Because of this structure information is spread slower, but it continues spreading at the same rate as time passes and penetrates the network further.

The authors in [START_REF] Yang | [END_REF] propose a Linear Influence Model by calculating the influence of a node on the rate of diffusion through the network. For each influenced node an influence function quantifies how many subsequent ones can be by that node. This is based on the assumption that the number of newly influenced nodes depends on which other nodes were influenced before. The study concludes that the diffusion of information is governed by the influence of individual nodes.

Another influence-oriented study is the one presented by [START_REF] Kimura | Tractable Models for Information Diffusion in Social Networks[END_REF]. It is based on the Independent Cascade Model. This model is a stochastic process in which information propagates from a node to its neighboring ones according to a probabilistic rule. Similarly to the previous study, the problem lies in discovering influential nodes in a social network based on the computation of the expected number of influenced nodes. Two information diffusion models are proposed for the efficient calculation.

The study of (Bakshy et al., 2012) examines the information diffusion regarding exposure to signals about friends' information sharing on Facebook. It is suggested that the users who are aware of that information are significantly more likely to share it and in less time compared to those who are not. The authors suggest that, although the stronger ties are individually more influential, the weak ties, which surpass them in numbers, are responsible for the propagation of information. [START_REF] Kwak | What is Twitter, a social network or a news media?[END_REF] examine the "retweet" functionality offered by Twitter and study the information diffusion as a result of this action, as it has the power to spread information broader. The authors state that the retweets counters are measurements of the popularity of the tweets and consequently of their authors. According to the study, once a message gets retweeted it will almost instantly be spread up to 4 hops away from the source, leading in fast diffusion after the 1st retweet. That popularity measurement has been utilized in our work (Section 3.1).

All the related studies have shown that the most active users or those with the most followers are not necessarily the most influential. This fact has also been spotted by our work. Our Influence Metric depends on a set of factors (Section 3.1) and the activity of a user is only one of them. Therefore it can affect the result but the overall value of the Metric is not dependent directly on it.

Contrary to the aforementioned studies, for the calculation of our Influence Metric we neither set a lower threshold on the number of the user-generated tweets, nor we utilize only a subset of these tweets which fulfill certain criteria (i.e. those which contain URL). All Twitter accounts can be used as seed for the calculation of the Influence Metric. Our work also differentiates in the fact that our Influence Metric does not deal with the mentions of the examined user in other users' tweets or the topical similarity in the "Follower-Following" relations. It is concentrated on the characteris-tics of the Twitter account. In the future we plan to utilize the way in which other users interact with the examined user's tweets (marked as favorites or being retweeted) as a quality measurement of their content.Most of the presented studies related with the information diffusion aim in identifying nodes of high influence as responsible for affecting neighboring ones to behave the same, in terms of spreading information of the same topic. As the results show (Section 4.2) our proposed Influence Metric succeeds in indentifying the nodes as to maximize the information diffusion in an OSN.

Methodology

As already mentioned, the contribution of this paper is twofold. Firstly, a methodology is proposed for calculating the importance and the influence of an account in Twitter. Secondly, a framework is described regarding its evaluation.

Calculation of account's Importance and Influence

Twitter accounts form a Social Network. If depicted in a graph, they would be represented by nodes. The edges that connect these nodes are the relations of "Follower-Following", introduced by Twitter. Obviously, some accounts are more influential than others. The methodology of calculating the importance and influence that an account has in an OSN is presented here. That measurement should not depend merely on the number of "Followers" of an account, even if that number is big enough and the account's tweets are received by a large number of other accounts (followers). In case that the number of "Following" is larger, then the user could be characterized as a "passive" one. That type of users are regarded as those who are keener on viewing or being informed through tweets rather than composing new ones. Therefore, a suitable factor is the ratio of "Followers to Following" (FtF ratio).But this ratio is also not sufficient. Another important factor is the tweets creation rate (TCR). For example, let us see the case where two accounts have nearly the same FtF ratio. Obviously the account with the higher TCR has more impact on the Network. In our methodology, in order to calculate that rate, we process the accounts' latest 100 tweets according to the Twitter API. That leads to the TCR, and consequently the Influence Metric, being dynamic as it depends on the most recent accounts' activity in Twitter. The proposed Influence Metric depends on all of the aforementioned characteristics of the examined account, as defined in Equation 1. The FtF ratio is placed inside a base-10 log for avoiding outlier values. Moreover, the ratio is added by 1 so as to avoid the metric being equal to 0 in cases that the value of "Followers" is equal to the "Following".

where OOM: Order Of Magnitude

(1)

Each Tweet is associated with several other kinds of information. Two of them are the "Retweets" and "Favorites" counts which represent how many times a Tweet has been retweeted or marked as favorite by other users. In our methodology, we utilize these counts in order to calculate the h-index of the retweets and favorites counts over the last 100 tweets of an examined account. Their aim of these measurements is to provide a quality overview of the tweets of a Twitter account in terms of likeability and impact. These indexes are based on the established h-index (Hirsch, 2005) measurement and are named "ReTweet h-index -Last 100 Tweets" and "Favorite h-index -Last 100 Tweets". The most important factor regarding them is that they reflect other users' assessment of the content of the tweets.

Consequently, a Twitter account has "ReTweet h-index -Last 100 Tweets" h, if h over the last Nt tweets have at least h retweets each, and the remaining (Nt -h) of these tweets have no more than h retweets each (max. Nt=100).

The "ReTweet h-index -Daily" and the "Favorite h-index -Daily" are two similar metrics which represent the estimated daily value of "ReTweet and Favorite h-index" during the lifespan of a Twitter account over the last Nt tweets.

These h-index values are separately calculated and presented in influencetracker.com web site. However, we are currently working towards incorporating them in Equation 1, and more specifically on the evaluation of their impact over the proposed Influence Metric.

Information Diffusion/Tweet Transmission

An important functionality offered by Twitter is the "Retweet". It allows users to repost a received tweet to their Followers. This results in viewing the tweets of accounts that are not being directly followed. That fact leads in the diffusion of information to users not targeted (to the followers of their followers). The same process can be repeatedly take place by the new viewers of the message and so on.

The most important factor which affects the transmission of the tweets is the followers' probability of retweeting. The higher this value is, the higher the probability of transmitting tweets to other users, initially not targeted by the source. Another dependency of the transmission of the tweets is the followers' TCR. The value of this rate includes both the accounts' generated tweets, as well as their retweets. The final dependency of that measurement is the "TCR of Follower to TCR of Account" ratio. Increased values of that ratio lead in bigger flow of tweets between these Twitter accounts. The Tweet Transmission measurement depends on all of the aforementioned characteristics of the directly related accounts and it is defined in Equation 2.

(2)

Proposed evaluation framework

In order to evaluate the above metrics we employ the evaluation framework illustrated at Figure 1. The framework is split into seven Phases, presented in Figure 1. During the 1st Phase of the process, the Twitter account under examination is selected. In Phase 2, we fetch a large number of Followers (N f ) and their Twitter-related characteristics. These are necessary in order to calculate their Influence Metric measurement (Equation 1).

In Phase 3, the Followers are placed in two categories. The first one is classified by the value of our Influence Metric, while the second one by the absolute amount of followers each follower has. Both of these categories are sorted in descending format. After that, we select the top-k followers of these two categories.

Similarly, for these top-k accounts, Phases 2 and 3 are repeated. This process is continued until a specified distance threshold (layers) between Twitter accounts is reached (Phase 4). In computer networks, this distance is expressed by the Time-To-Live value (TTL) and corresponds to the amount of hops between different nodes a transmitted packet can perform before being rejected by the network. For the purposes of this work this threshold is set equal to 3.

The examined account, all the followers, as well as their relations and characteristics are modeled as a separate network. Nodes depict accounts, while edges depict their relations containing specific attributes. As a result of that process, two structures of the initial account and the followers of followers are created. The one depicts the top-k accounts by Influence, while the other one the top-k accounts by Followers. An example of such graph is presented in Figure 2.

In Figure 2 a 3-layered structure graph is displayed. The blue node represents the initial examined account. This account is connected to the yellow nodes, which stand for the top-3 followers either by the Influence Metric or by the amount of their followers (1st layer of distance). The process is iteratively continued with these nodes. The green and red nodes, 2nd and 3rd layer respectively, represent the followers of the previously examined followers and so on. We should note here, that a node can be connected with others, independent if they belong to the same layer or not. When all previous phases are completed, the sixth and final Phase is initiated. Its purpose is to discover all the paths, starting from the initial examined account (blue node) and ending to the sink (black node) and consist of exactly 4 steps. The number of 4 steps is very important, since it is the necessary and sufficient condition in order to find all the shortest paths between the initial account and the sink, which contain exactly one node belonging to every layer.

Furthermore, that number of steps ensures us that any possible loops will be avoided during the traversal of the networks from the initial account to the sink. A possible case of loop is when the examined Twitter account appears as a follower of another account. In such a case the examined account could also appear at the first (as a yellow node) or the second layer (as a green node).

The Tweet Transmission (TT) value, presented in Equation 2, is calculated for each layer of every shortest path. Then the TT value of the shortest path for all layers is calculated. This process is repeated until the TT values of all shortest paths of the two networks are computed. The network with the higher Total Tweet Transmission (TTT) value is considered the one with the higher disseminated information.

Evaluation results

In this section, we will present and analyze the results and the evaluation concerning the calculation of the importance and influence of a user in an OSN, and of the framework regarding the maximization of diffusion of information. As case study, we evaluate six real Twitter accounts. Three belong to political persons (@AdonisGeorgiadi, @IliasKasidiaris,and @PanosKammenos), one belongs to the Hellenic Fire Brigade (@Pyrosvestiki), and the rest belong to a Greek news media channel (@SkaiGr) and to the international information network of activists and hacktivists named Anonymous (@YourAnonNews).

The experiments took place between 14/12/2013 and 31/1/2014. For each account four separate samplings were made, during which the number of the followers and the top-k accounts were gradually increased. The distance threshold, which defines the number of layers as described in Section 3.3, was set equal to 3.

4.1

Accounts' Influence

In this section, we present the Influence Metric measurements in respect to the examined Twitter accounts. We also provide the sampling date, the value of the Influence Metric, as well as other metrics are depicted in Table 1.

As we can see, the Influence Metric is directly dependant of the accounts' activity, which is measured by the TCR value. Account's "@SkaiGr" Influence value during the first three samplings (SG1 to SG3) is approximately the same (nearly 35 Millions). However, during the fourth sampling (SG4) that value was almost the half. This was caused by the fact that the TCR value was dropped to half, despite that the "Followers to Following" ratio was slightly increased. In the case of the account named "@YourAnonNews", during the first 3 samplings (YAN1 to YAN3) the Influence Metric value is nearly equal to 341 Millions. During the last sampling, YAN4, this value is dropped to approximately 329 Millions. This is explained due to the smaller value of "Followers to Following" ratio (the amount of following accounts increased during the period of the last sampling).

We should note here, that for the calculation of the Influence Metric, we consider the latest 100 accounts' tweets directly from the Twitter API. This enables the measurement to be dynamic and in accordance to the latest trend activity of the examined Twitter account.

ID

Information Diffusion/Tweet Transmission

In this section, the TTT values of the created networks in respect of the examined accounts are presented. Table 2 is divided in four parts. Each part refers to the separate samplings mentioned above, while the related information per part is:

• the number of followers that is iteratively fetched,

• the number of top-k followers of the two generated categories, these are "by Influence Metric" and "by Followers", which are used for the creation of the respective layered networks, • the distance threshold value that reflects the layers of the examined account's networks (TTL), • the account which is the root of the two resulting networks (the six examined accounts),

• the TTT values of the two networks, according to the "by Influence Metric" and "by Followers", and finally • the difference of the above TTT values for both generated networks. Table 2: The tables containing the details of each sampling set

In addition, the green-highlighted values in column "Difference" correspond to the cases where the TTT value is larger in the "By Influence" category, thus indicating that our approach manages to create a network of followers who are more influential in comparison to the network of category "By Followers". Red-highlighted values reflect to the opposite cases. As we can see the wider the examined networks are in terms of the top-k accounts and their followers up to the third layer, the more influential network of accounts we have.

As can be observed from Table 2, the TTT values of the two networks are escalated as both the numbers of the followers and of the top-k accounts are also increased. The results of the use cases used for the evaluation of the influence metric calculation, show that the number of followers an account has, is not solely sufficient to guarantee the maximum diffusion of information in Twitter (and practically to any similar OSN). This is because, these followers should not only be active Twitter accounts, but also have impact on the network. The latter is calculated by the Influence Metric value.

Conclusions and Future Work

In this paper, we proposed a methodology for calculating the importance and the influence of a Twitter account, as well as a methodology regarding the maximization of diffusion of information. For evaluation purposes a framework was applied. As a case study, we evaluated six real Twitter accounts. experiments took place between 14/12/2013 and 31/1/2014 and for each account four separate samplings were made.

The results of the use cases show that the number of followers an account has, is not sufficient to guarantee the maximum diffusion of information in Twitter (and practically to any similar OSN). This is because, these followers should not only be active Twitter accounts, but also have impact on the network. The latter is calculated by our Influence Metric.

Ongoing research is performed on how the proposed Influence Metric can be improved. We are currently working towards incorporating the "ReTweet h-index -Daily" and the "Favorite h-index -Daily" in Equation 1 and more specifically on the evaluation of their impact over the proposed Influence Metric.

Additionally effort is conducted over the evaluation of how conversational a Twitter account is ("Reply Percentage" in InfluenceTracker, which indicates the percentage of the account's latest tweets which are replies to other accounts' tweets). The work of [START_REF] Leavitt | The Influentials: New Approaches for Analyzing Influence on Twitter[END_REF] concluded that news media are better at spreading content, while celebrities are better at making conversation. So, for example we can use the aforementioned metric in order to categorize the Twitter accounts in news/blogs media (with automated content) and user ones (human generated content). Also if combined with the "Daily h-indexes" measurements, representing the quality of the content, spam accounts can also be discovered.

Figure 1 :

 1 Figure 1: The seven phases of the proposed framework

Figure 2 :

 2 Figure 2: A 3-layered structure graph of the initial account and the top-3 followers of followersDuring the fifth Phase an ending node (sink) is added to each of the two generated networks. This node is connected with all the accounts-followers of the last layer. These are the red nodes of Figure2which belong to the 3rd layer. That results in a fixed starting and ending point of the network. Figure3presents the network illustrated in Figure2including the sink node (black node in the center).

Figure 3 :

 3 Figure 3: A 3-layered structure graph with a sink node

Figure 4 :

 4 Figure 4: Calculation of a TT value Figure 4 displays an example of a path derived from the network illustrated in Figure 3. This path consists of four edges (Examined AccountàA, AàB, BàC, and CàSink). For this path, three TT values are calculated, namely from the Examined Account to A (TT ExaminedAccount à A ), from A to B (TT A à B ), and finally from B to C (TT B à C ). The total TT value of the whole path is the multiplication of these three calculated values and is assigned to the sink node. Figure 4 depicts the calculation of TT A à B .

Followers

http://www.influencetracker.com