Stephen G Macdonell
email: smacdone@aut.ac.nz

The Impact of Sampling and Rule Set Size on Generated Fuzzy Inference System Predictive Accuracy: Analysis of a Software Engineering Data Set

Keywords: fuzzy inference, prediction, software size, source code, sampling, sensitivity analysis

Software project management makes extensive use of predictive modeling to estimate product size, defect proneness and development effort. Although uncertainty is acknowledged in these tasks, fuzzy inference systems, designed to cope well with uncertainty, have received only limited attention in the software engineering domain. In this study we empirically investigate the impact of two choices on the predictive accuracy of generated fuzzy inference systems when applied to a software engineering data set: sampling of observations for training and testing; and the size of the rule set generated using fuzzy c-means clustering. Over ten samples we found no consistent pattern of predictive performance given certain rule set size. We did find, however, that a rule set compiled from multiple samples generally resulted in more accurate predictions than single sample rule sets. More generally, the results provide further evidence of the sensitivity of empirical analysis outcomes to specific model-building decisions.

Introduction

Accurate and robust prediction of software process and product attributes is needed if we are to consistently deliver against project management objectives. In recent years fuzzy inference systems (FIS) have gained a degree of traction (with empirical software engineering researchers if not practitioners) as an alternative or complementary method that can be used in the prediction of these attributes [START_REF] Azzeh | Improving Analogy Software Effort Estimation Using Fuzzy Feature Subset Selection Algorithm[END_REF][START_REF] Macdonell | Software Source Code Sizing Using Fuzzy Logic Modeling[END_REF][START_REF] Huang | A Soft Computing Framework for Software Effort Estimation[END_REF][START_REF] Ahmed | Adaptive Fuzzy Logic-based Framework for Software Development Effort Prediction[END_REF].

Empirical software engineering research that has focused on prediction is normally performed using a standard sample-based approach in which a data set is split into two sub-samples, the first, larger set for building a predictive model and the second for non-biased evaluation of predictive performance (for instance, see [START_REF] Azzeh | Improving Analogy Software Effort Estimation Using Fuzzy Feature Subset Selection Algorithm[END_REF]). Any reasonable splitting strategy can be used. Typically, two-thirds of the total sample is randomly allocated to the build subset, leaving one third of the observations to comprise the test subset. Given the incidence of outlier observations and skewed distributions in software engineering data sets [START_REF] Kitchenham | Why Comparative Effort Prediction Studies may be Invalid[END_REF], stratified sampling may be useful, but it has not been widely employed in software engineering analyses. Similarly, where information on the ordering of observations is available this could be used to further inform the sampling strategy. Again, however, such an approach has not been used to any great extent in empirical software engineering research [START_REF] Macdonell | Data Accumulation and Software Effort Prediction[END_REF].

In this paper we analyze the sensitivity of prediction outcomes to systematic changes in two parameters relevant to fuzzy inference model building and testing: data sampling and rule set size. In essence, then, this is a paper focused on the infrastructure of predictive modeling -our intent is to highlight the potential pitfalls that can arise if care is not taken in the building and testing of models. In the next section we describe the empirical work we have undertaken using a software engineering data set. Section 3 reports the results of our analysis. A discussion of the key outcomes is provided in Section 4, after which we briefly address related work. We conclude the paper and highlight opportunities for future research in Section 6.

Empirical Analysis

In this section we describe the empirical analysis undertaken to assess the impact of changes in both data sampling and rule set size on the predictive accuracy of fuzzy inference systems. After providing a description of the data set employed in the analysis we explain the three approaches used in constructing our prediction systems.

The Data Set

The data set we have used here is a simple one in that it involves a small number of variables. This does not detract, however, from its effectiveness in illustrating the impact of sample selection and rule set size, the principal issues of concern in this study. The data were collected in order to build prediction systems for software product size. The independent variables characterized various aspects of software specifications, including the number of entities and attributes in the system data model, the number of data entry and edit screens the system was to include, and the number of batch processes to be executed. As each implemented product was to be built using a 4GL (PowerHouse) our dependent variable was the number of noncomment lines of 4GL source code. The systems, which provided business transaction processing and reporting functionality, were all built by groups of final-year undergraduate students completing a computing degree.

A total of 70 observations were available for analysis. Although this is not a large number, it did represent the entire population of systems built in that environment over a period of five years. It is in fact quite a homogeneous data set -although the systems were built by different personnel over the five-year period they were all constructed using the same methodology and tool support by groups of four people of similar ability. Furthermore, it is quite common in software engineering to have access to relatively small numbers of observations (for example, see [START_REF] Song | Predicting Software Project Effort: A Grey Relational Analysis Based Method[END_REF]), so the data set used here is not atypical of those encountered in the domain of interest.

In a previous investigation [START_REF] Macdonell | Software Source Code Sizing Using Fuzzy Logic Modeling[END_REF] we identified that two of the 8 independent variables were significantly correlated to source code size and were also not correlated to one another. These were the total number of attributes in the system data model (Attrib) and the number of non-menu functions (i.e. data entry and reporting modules rather than menu selection modules) in the system"s functional hierarchy (Nonmenu). We therefore used these two variables as our predictors of size.

FIS Development

We adopted three model-building approaches in order to investigate the impact of sampling and fuzzy rule set size on the coverage and accuracy of source code size predictions. We first built membership functions and rule sets (via the algorithms below) using the entire data set of 70 observations (Full Approach); we also randomly generated ten separate build subsets of 50 cases that we used to build fuzzy prediction systems (Sampled Approach); finally we analyzed the ten rule sets generated by the sampling process to create a "mega" rule set comprising the 50 most frequently generated rules (Top 50 Approach). For each of the three approaches we generated fuzzy inference systems comprising from one to fifty rules. Each FIS was tested against the ten test subsets of 20 observations. While performance was assessed using a variety of accuracy indicators, we report here the results in terms of the sum of the absolute residuals and the average and median residual values, as these are preferred over other candidate measures [START_REF] Kitchenham | What Accuracy Statistics Really Measure[END_REF]. We also assessed the coverage of each FIS i.e. the proportion of the test subsets for which predictions were generated (meaning the rule set contained rules relevant to the test subset observations that were then fired to produce a predicted size value).

Previous research using this data set [START_REF] Macdonell | Software Source Code Sizing Using Fuzzy Logic Modeling[END_REF] had indicated that the three variables of interest were most effectively represented by seven triangular membership functions, mapping to the concepts <VerySmall, Small, SmallMedium, Medium, MediumLarge, Large, VeryLarge>. The membership function extraction algorithm is as follows:

1. select an appropriate mathematically defined function for the membership functions of the variable of interest (i), say ƒ i (x)

2. select the number of membership functions that are desired for that particular variable, m i functions for variable i (m i may set by the user or may be found automatically, to desired levels of granularity and interpretability)

3. call each of the m i functions ƒ ij ([x]) where j = 1… m i and [x] is an array of parameters defining that particular function (usually a center and width parameter are defined, either explicitly or implicitly) 4. using one-dimensional fuzzy c-means clustering on the data set find the m i cluster centers, c ij from the available data (m i may set by the user or may be found automatically, to desired levels of granularity and interpretability) 5. sort the cluster centers c ij into monotonic (generally ascending) order for the given i 6. set the membership function center for ƒ ij , generally represented as one of the parameters in the array [x], to the cluster center c ij 7. set the membership function widths for ƒ

ij in [x] such that ∑ mi n=1 ƒ in ([c in ,…]) = 1,
or as close as possible for the chosen ƒ(x) where this cannot be achieved exactly (for example for triangular membership functions each function can be defined using three points, a, b, and c where a is the center of the next smaller functions and c is the center of the next larger function).

Rules were extracted using the same clustering process with multiple dimensions (matching the number of antecedents plus the single consequent):

1. start with known membership functions ƒ ij ([x]) for all variables, both input and output, where j represents the number of functions for variable i and [x] is the set of parameters for the particular family of function curves 2. select the number of clusters k (which represents the number of rules involving the k-1 independent variables to estimate the single output variable)

3. perform fuzzy c-means clustering to find the centers (i dimensional) for each of the k clusters 4. for each cluster k with center c k (a) determine the k th rule to have the antecedents and consequent ƒ ij for each variable i where ƒ ij (c k ) is maximized over all j (b) weight the rule, possibly as

∏ i n=1 ƒ ij (c k ) or ∑ i n=1 ƒ ij (c k ) 5.
combine rules with same antecedents and consequents, either summing, multiplying, or bounded summing rule weights together 6. (optionally) ratio scale all weights so that the mean weight is equal to 1.0 to aid interpretability.

Results

We now consider the outcomes of each of the three approaches in turn -Full, Sampled and Top 50.

Full Approach

Development of an FIS using the entire set of observations is the most optimistic of the three approaches, and in fact represents more of a model-fitting approach rather than one of unbiased prediction where a hold-out sample is used. We employed this approach, however, to provide a benchmark for comparative model performance. The clustering approaches described above were used to build membership functions and rule sets based on all 70 observations. Essentially this meant that there were fifty distinct FIS produced, comprising from one to fifty rules. These FIS were then tested against each of the ten test subsets produced from the Sampled Approach (described below). Accuracy and coverage were assessed for each FIS, illustrated by the example shown for the sample 4 test subset in Figures 1 and2 and Table 1.

For sample 4 we can see in Figure 1 that predictive accuracy measured using the median residual value taken over the predictions made shows some volatility but is generally stable within the range 150-250 SLOC, once the rule set size reaches a value of around 18. At this point also we can see that coverage becomes stable at close to 100% i.e. rules were fired and predictions made for close to all 20 test subset observations. Further evidence of the generally high degree of test observation coverage is provided in Table 1 and Figure 2. This latter result is not unexpected as in the Full Approach all 70 observations were used to build the FIS, and so the test observations had been "seen" and accommodated during model-building.

Sampled Approach

As stated above, in this approach we randomly allocated 50 of the 70 observations to a build subset and left the remaining 20 observations for testing, repeating this process ten times to create ten samples. FIS development then used only the build subsets, creating FIS comprising an increasing number of rules (from one to fifty, the latter meaning one rule per build observation) for each of the ten samples.

Sampling. We performed t-tests to assess the degree of uniformity across the ten samples, using Size as our variable of interest. These tests revealed that, in particular, sample 10 was significantly different (at alpha=0.05) from samples 3 through 8. This could also be verified informally by looking at the data -build subset 10 comprised a higher proportion of larger systems (and test subset 10 a correspondingly higher proportion of smaller systems) than most of the other samples. As our objective was to illustrate the impact of such sampling on model performance and the rule sets generated, however, we retained the samples as originally produced.

Model performance. Model accuracy varied across the ten samples, and while in general there was a tendency for accuracy to either stabilize or improve as the FIS rule set grew (as per Figure 1 above for the Full Approach) this was not found to always be the case. For instance, prediction of the test subset for sample 2 was quite volatile in spite of good coverage, as shown in Figure 3. The best models achieved for each sample are shown in Tables 2 and3. The first table depicts the results irrespective of coverage whereas the second considers only those FIS that achieved maximum coverage for each test subset. What is evident in both tables is the variation in values for all three accuracy measures -for instance, the median residual value in the best maximum coverage models (Table 3) varies from a low of 139 SLOC (for sample 2) up to 296 SLOC (for sample 8). Rule Distribution. For each of the ten samples we also considered the composition of the generated rule sets, comprising from one to fifty rules each at increments of one, meaning a total of 1275 rules per sample. Each rule was a triple made up of two antecedents and a single consequent e.g. IF <Attrib> IS [Small] AND <Nonmenu> IS [SmallMedium] THEN <Size> IS [Small]. Our analysis considered the frequency of particular memberships in the rule sets for each variable (e.g. count of "<Attrib> IS [VerySmall]"), as well as the frequency of each complete rule across the sets. Space precludes full reporting of the results of this analysis across all ten samples but an example for sample 6 is shown in Figures 4, 5 and6. (Note that in these figures Set Value "1" maps to "VerySmall", "2" maps to "Small", and so on.) For this sample 47 distinct rules of the 343 possible (the latter representing each possible triple from "1,1,1" through to "7,7,7") made up the 1275 rules in the fifty sets, the most frequently occurring rule for this sample being "3,3,4": IF <Attrib> IS [SmallMedium] AND <Nonmenu> IS [SmallMedium] THEN <Size> IS [Medium], with 112 instances over the fifty rule sets (shown as the longest bar in Figure 6). Across the ten samples, the number of distinct rules varied from 45 for sample 8 up to 60 for sample 1, and these sets were distinct in part, meaning that over the ten samples 131 distinct rules were generated from the 343 possible candidates.

Top 50 Approach

The above analysis of the ten samples allowed us to also identify the Top 50 distinct rules across the sampled data sets i.e. the 50 rules that were generated most frequently (where 50 was an arbitrary choice). The most common rule (at 506 instances) was: IF <Attrib> IS [MediumLarge] AND <Nonmenu> IS [MediumLarge] THEN <Size> IS [MediumLarge], whereas the 50 th most common rule, with 89 instances, was IF <Attrib> IS [SmallMedium] AND <Nonmenu> IS [Small] THEN <Size> IS [VerySmall]. We then applied this set of 50 rules to the ten test subsets, in the expectation that over the entire set they may outperform the potentially over-fitted Sampled rule sets generated from each specific build subset. We compare the results obtained from this approach to those derived from the originally Sampled approach.

Comparison of Approaches

As might be expected, the Full approach models performed well across the ten samples. When considered in terms of the sum of absolute residual and average and median residual measures, the Full model was the most accurate in 14 of the 30 cases (30 being 10 samples by 3 error measures). As noted above, however, this does not represent an unbiased test of predictive accuracy as the Full models were built using the entire data set. Our comparison is therefore focused on the Sampled and Top 50 approaches. Figure 7 illustrates one such comparison, based on the median residual measure for sample 3. We can see that in this case the model created from the Top 50 approach performed better than those from the Sampled approach for FIS comprising up to 29 rules, but beyond that the Sampled approach was generally superior. The pattern exhibited for sample 3 was not a common one across the ten samples, however. The data presented in Tables 4 and5 indicate that, in general, the Top 50 model ("Top") outperformed the specific FIS developed with the Sampled approach ("Sam."). Of the 30 comparisons, 9 favored the Sampled approach. (Note that totals can exceed 100% for a sample because the two methods may achieve equivalent performance for a given number of rules, and so are both considered "Best".)

Discussion

The impact of sampling was evident in the t-tests of difference in Size across the ten samples. The mean value for Size varied from 1043 to 1211 SLOC in the build subsets, and from 843 to 1264 in the test subsets, with a significant difference evident in relation to sample ten. Similarly, FIS model performance also varied over the samples in terms of both the residual values and the coverage of the test observations. For example, the outright best model for sample 1 comprised just 19 rules, had an absolute error value of 3100 SLOC and achieved 80% coverage, whereas the sample 4 best model achieved 100% coverage using 34 rules and an absolute residual of 6156 SLOC. No consistent pattern was evident in relation to rule set size even for FIS achieving maximum coverage -across the ten samples the most accurate FIS was obtained from rule sets varying in size from 15 to 49 rules (out of a possible 50 rules). The rules also varied from one sample to the next (aligned with the differences in the data) -131 distinct rules were generated. These outcomes all reinforce the importance of considering multiple samples and aggregating results in cases where there is variance in the data set, rather than relying on a single or small number of splits.

The Top 50 rules (in terms of frequency) generally outperformed the single-sample FIS, struggling only against samples 7 and 10. Overall this is an expected result, as the mega-set of rules was derived from exposure to most if not all 70 observations, albeit across ten samples, and we were already aware that sample 10 was significantly different to the others. The poor performance on sample 7 needs further analysis.

Related Work

As far as we are aware there have been no prior systematic assessments of the impact of these parameters on analysis outcomes in the empirical software engineering community. While several studies have used FIS in software engineering (e.g. [START_REF] Huang | A Soft Computing Framework for Software Effort Estimation[END_REF]) only single splits of the data set have been used, and there has been no specific assessment of the impact of rule set size. That said, [START_REF] Ahmed | Adaptive Fuzzy Logic-based Framework for Software Development Effort Prediction[END_REF] describes the selection of rules based on error thresholds. Related work has also been undertaken in other domains. For instance, [START_REF] Ben-David | Rule Effectiveness in Rule-based Systems: A Credit Scoring Case Study[END_REF] considered the trade-off between a smaller rule set and the accuracy of decisions made in regard to credit scoring, concluding that substantially fewer rules did not lead to proportional reductions in accuracy. The author notes, however, that "[t]he cost in accuracy loss one is willing to pay for the benefit of a smaller rule-base is entirely domain and organization dependent." [9, p.2787]. [START_REF] Cano | On the Combination of Evolutionary Algorithms and Stratified Strategies for Training Set Selection in Data Mining[END_REF] investigated the impact of stratification of training set data in data mining (employing evolutionary algorithms) noting significant differences in classification outcomes. Within the software engineering research community the influence of sampling on data analysis has received some attention, but as this does not relate to fuzzy inference the interested reader is referred to [START_REF] Shepperd | Using Simulation to Evaluate Prediction Techniques[END_REF] for an example of this work.

Conclusions and Future Work

We have conducted an analysis of the sensitivity of predictive modeling accuracy to changes in sampling and rule set size in the building and testing of fuzzy inference systems for software source code size. Our results indicate that both aspects influence analysis outcomes -in particular, the splits of data across build and test sets leads to significant differences in both predictive accuracy and test set coverage.

We are continuing to work on aspects of prediction infrastructure -in particular, our current work is focused on considering the impact of temporal structure on modeling outcomes as well as the development of more suitable error measures for accuracy assessment. Further research should also address the degree to which stability in predictor variables over the life of a project affects predictions of size, quality and other aspects of project management interest.

Fig. 1 .

 1 Fig. 1. Change in median residual and coverage with increasing rule set size for sample 4.

Fig. 3 .

 3 Fig. 3. Change in median residual and coverage with increasing rule set size for sample 2.

Fig. 4 .

 4 Fig. 4. Membership frequency for Attrib.

Fig. 5 . 6 .

 56 Fig. 5. Membership frequency for Nonmenu. Fig. 6. Rule frequency for sample 6.

Fig. 7 .

 7 Fig. 7. Sample 3 comparison in terms of median residual (Sam.: Sampled, Top: Top 50).

Table 1 .

 1 Overall coverage for sample 4.

	Coverage	Sample 4
	100%	22 44% Mean	86%
	80%-99%	16 32% Med	95%
	60%-79%	9 18%
	40%-59%	1	2%
	20%-39%	2	4%
	0%-19%	0	0%
				Fig.

2. Graphical depiction of coverage.

Table 2 .

 2 Best models for each sample in terms of accuracy measures (when coverage ignored).

	Sample	1	2	3	4	5	6	7	8	9	10
	Coverage	80% 90% 90% 100% 90% 95% 80%	90% 85%	95%
	Minimum rules?	19	23	31	34	18	14	12	35	29	26
	Abs Res	3100 4340 5430	6156 4077 4623 5257 5996 6823	5000
	Ave Res	194	241	302	308	227	243	329	333	401	263
	Med Res	111	118	163	177	159	200	266	288	261	176

Table 3 .

 3 Best models for each sample in terms of accuracy measures (maximum coverage).

	Sample	1	2	3	4	5	6	7	8	9	10
	Coverage	95%	95% 100% 100% 100% 100% 95% 100% 100% 100%
	Minimum rules?	44	36	40	34	50	15	38	49	45	36
	Abs Res	5825 5017	6394	6156	7193	4807 5970	5842	6789	5028
	Ave Res	307	264	320	308	360	240	314	292	339	251
	Med Res	187	139	208	177	274	203	177	296	269	173

Table 4 .

 4 Comparison of model accuracy across the ten samples (best shown in bold type).

	Sample	1		2	3	4	5
	Approach	Sam.	Top	Sam. Top	Sam. Top	Sam. Top	Sam. Top
	Abs Res Best	52% 50% 50% 52% 52% 48% 14% 86% 14%	86%
	Ave Res Best	38% 64% 24% 78% 36% 64% 10% 90%	8%	92%
	Med Res Best	42% 60% 56% 46% 40% 60% 30% 72%	0% 100%
	Sample	6		7	8	9	10
	Approach	Sam.	Top	Sam. Top	Sam. Top	Sam. Top	Sam. Top
	Abs Res Best	16% 84% 82% 20% 26% 74% 30% 72% 70%	30%
	Ave Res Best	24% 76% 74% 28%	6% 94% 20% 82% 62%	38%
	Med Res Best	20% 82% 58% 46% 12% 88% 22% 80% 72%	28%

Table 5 .

 5 Comparison of model accuracy -summary statistics.

	Summary Statistic	Mean		Median
	Approach	Sam.	Top	Sam.	Top
	Abs Res Best	41%	60%	40%	62%
	Ave Res Best	30%	71%	24%	77%
	Med Res Best	35%	66%	35%	66%


Vasilios Papavasileiou

Athanasios Tsadiras
email: tsadiras@econ.auth.gr

Time Variations of Association Rules in Market Basket Analysis

Keywords: Market Basket Analysis, Association Rules, Data Mining, Marketing Strategies, Recommendation Systems

This article introduces the concept of the variability of association rules of products through the estimate of a new indicator called overall variability of association rules (OCVR). The proposed indicator applied to super market chain products, tries to highlight product market baskets, with great variability in consumer behavior. Parameter of the variability of association rules in connection with changes in the purchasing habit during the course of time, can contribute further to the efficient market basket analysis and appropriate marketing strategies to promote sales. These strategies may include changing the location of the products on the shelf, the redefinition of the discount or even policy or even the successful of recommendation systems.

Introduction

Market Basket Analysis

The consumer behavior data collection, for a super market chain, via an appropriate strategy, may lead the company to significant economies of scale. For the same reason, the extension of the use of loyalty cards, constitutes a primary goal for the administration of a super market chain. In particular, the market basket analysis [START_REF] Chen | Market Basket Analysis in a Multiple Store Environment[END_REF] can bring out the combinations of products that are susceptible of marketing strategies and may lead to better financial results. With market basket analysis [START_REF] Shaw | Knowledge Management and Data Mining for Marketing[END_REF], the administration of a super market can understand the behavior and purchasing habits of customers, through combinations of product market [START_REF] Lawrence | Personalization of Supermarket Product Recommendations[END_REF], which is repeated in large or small degree, as a habit. These combinations are called products association rules [START_REF] Margaret | Data Mining Introductory and Advanced Topics[END_REF][START_REF] Agrawal | Mining Association Rules Between Sets of Items in Large Databases[END_REF][START_REF] Ale | An Approach to Discovering Temporal Association Rules[END_REF][START_REF] Bayardo | Mining the Most Interesting Rules[END_REF] and are the result of market basket analysis procedure.

The simplest form of an association rule, shows two products and has the form X > Y, which means that the purchase of product X leads to the purchase of product Y. For rules evaluation there are used three main indicators [START_REF]The Free Encyclopedia[END_REF], which is the degree of confidence, the degree of support and the degree of lift. The degree of confidence expresses the possibility of realization of rule X > Y in the set of transactions involving the purchase of the product X. Respectively, the degree of support expresses the possibility of realization of rule X > Y in the set of all transactions. Finally, lift Indicates how much better the rule is at predicting the "result" or "consequent" as compared to having no rule at all, or how much better the rule does rather than just guessing.

Dataset

The data of this survey are collected from a Greek known super market chain and are related to annual customer transactions [START_REF] Bhanu | Predictive Modeling of Inter-Transaction Association Rules-A Business Perspective[END_REF][START_REF] Brin | Dynamic Itemset Counting and Implication Rules for Market Basket Data[END_REF] for the period from 01/09/2008 to 31/08/2009. Data are sourced from the information system of the company and come exclusively from the customer card transactions through loyalty cards. Every transaction is a record of the purchase of specific products carried out by the customer who makes use of the card at the time of purchase.

As far as data distribution is concerned there has been observed the long tail effect, which belongs to the broader category of low power distributions that appear quite often in nature. The long tail effect has assumed its present connotation and dynamics by Chris Anderson [START_REF] Anderson | The Long Tail: Why The Future of Business Is Selling Less of More[END_REF]. Figure 1 below shows the curve of long tail effect. This term often refers to data products purchase in supermarkets describing their distribution as a long tail in which a small number of products is purchased more frequently whereas a large one is purchased less frequently. This phenomeno creates data sparsity problem and worsens even more their elaboration. For this survey from the total number of transactions there were selected, those that included at least the purchase of 8 products. That is how, to some extent, there was tried to resolve the data sparsity problem and prevent the removal of any market basket product, which may present a risk of information loss.

During the stage of preprocessing [START_REF] Roiger | Data Mining: A Tutorial-Based Premier[END_REF][START_REF] Bose | Business Data Mining -A Machine Learning Perspective[END_REF][START_REF] Chen | Data Mining: An Overview from a Database Perspective[END_REF], the products were grouped into categories and subcategories, depending on their utility and the classification in supermarket shelves. The number of codes of the products sold by the chain is approximately 95.000 and with the categorization applied there was diminished in 247 product subcategories.

Occasionally, there have been proposed various algorithms for efficient market basket analysis. The most widely established, is the a priori algorithm, delivered for the first time by Rakesh Agrawal and Ramakrishnan Srikant [START_REF] Agrawal | Fast Algorithms for Mining Association Rules[END_REF]. For the extraction of data there was used the free software Tanagra [START_REF] Tanagra | a free DATA MINING software for academic and research purposes[END_REF]. This specific data mining tool is specialized in market basket analysis and is applied in the a priori algorithm. For compatibility with the program, the sets of data were formatted in binary tables [START_REF] Mild | Collaborative Filtering Methods For Binary Market Basket Data Analysis[END_REF], where each row is a separate transaction and each column represents one of the 247 sub-categories of products.

Each product of a transaction corresponds to 1, when purchased and to 0 when it isn't. Hence, there were formed 12 binary transaction tables respectively to the 12 months of analysis and 1 binary transaction table for the annual purchase data. The market basket analysis was applied to each of the 12 subsets separately, in a subcategory level of products and the results were studied in a association with time.

In table 1 there is the number of transactions elaborated, both for the whole year and the 12 sub-totals. With the indication Month 1 we refer to the total number of all purchasing data for September 2008, while for Month 12, it is implied the total number of purchasing data for August 2009 respectively. 2 Time Variations of Association Rules

Discoveries of Association Rules from Dataset

For all of the data and for each of the subsets there has been activated the procedure of market basket analysis and recorded the results of the three indicators, confidence, support and lift. For every application of a market basket analysis process, the minimum level of confidence, support and lift established in the program, is 0.25, 0.01 and 1.1 respectively. The results of the number of rules that came out, are registered in table 2 and correspond to the level of 247 product subcategories. In an attempt to show the price development of the degree of confidence in months 1, 2 and 12 it comes out the graph of time change of the degree of confidence of association rules. It is also noted that when the confidence of customers is increased for the market basket of rule 5, the same period the confidence of customers for the market basket of rule 6 is reduced. The same but to a lesser extent seems to be the case with rules 5 and 7. In such cases the market baskets between them seem to work as substitute.

As shown by the results in table 3, the values of association rules indicators lift, confidence, support, of super market chain products, present monthly fluctuations. For example, the degree of confidence in the rule 1 appears with percentage 86.84% in September and is reduced to 81.02% in the month of October and is increased to 85.95% the month of August. The option to purchase fruit after the selection of bread and yoghurt in the basket market seems to be less random in September compared to October and more random than that in August. Also on rules 5, 6 and 7, for the first three months under consideration, there are significant changes in levels of confidence in connection with the other rules. In particular, for rule 6 the changes are made to a high degree of confidence.

These monthly fluctuations in prices of lift and confidence are the subject of this research study. The research of rules association products should not be concluded solely on the assessment of the three indicators, without taking account of changes in these prices during the year. Through the assessment of variation in the degree of confidence and lift of a rule, one can draw useful conclusions about the marketing.

The concept of variability has occupied the research of the export association rules geographical and temporal data within the study mainly climatic [START_REF] Hong | Mining Association Rules in Geographical Spatio-Temporal Data[END_REF] and weather [START_REF] Yo-Ping | Using Minimum Bounding Cube to Discover Valuable Salinity/Temperature Patterns from Ocean Science Data[END_REF] phenomena. This article attempts to highlight the term of variability in critical factor in analyzing purchasing data of super markets.

Define of OCVR

For the evaluation of changes in the lift and confidence values of association rules, there has been calculated the statistical indicator of relative variability or standard deviation [START_REF] Papadimitriou | Statistical: Statistical Inference[END_REF]. The indicator of the relative standard deviation, was chosen as the most effective for the comparison of the variability of the rules, as it is the most appropriate to compare the observations expressed in the same units but whose arithmetic average differ significantly. The variability index CV, is defined as the ratio of the standard deviation s by the mean value X .

CV = X s . ( 1
)
For each of the 1803 association rules during the 12 months there has been calculated the index variability lift (CVL) and the index variability confidence (CVC).

In order to aggregate both CVL and CVC indexes and combine these indexes into a single index, we introduced a new indicator the one of the overall variability of association rules (OCVR), as a result of the average variability of lift and confidence.

OCVR = 2 CVC CVL + . ( 2
)

Experimental Study

Table 4 lists the results of price variability index lift (CVL), the index variability confidence (CVC) and the index of overall variance (OCVR) specific association rules. We note that the indicator of overall variability of rule 1 is 4.33% and the corresponding value of confidence for the three months that were presented in table 3, ranges from 81.02% to 86.84%. The indicator of overall variability of rule 2 is 3.46 and the corresponding value of the confidence ranges from 71.89% to 79.41%. This could mean that the rule 1 which is realized by a greater degree of consumer confidence than rule 2, can be changed more easily compared to rule 2, which seems to be more compact and inflexible. The indicator of overall variability of rule 3 is 4.83 and the corresponding value of the confidence ranges from 61.77% to 64.70%. This could mean that the rule 3 which is realized with a lesser extent consumer confidence compared to rule 2, can be changed more easily than rule 2. Rule 3 compared to rule 2 could be perceived as a more sensitive and flexible. We can observe that the form of the distribution of values of OCVR follows the long tail distribution. More specifically, a small number of rules presents a high overall variability. In Figure 4 is shown the histogram of the values of the overall variability. We observe that the majority of the overall variability index values range from 1% of space -30% while there are very few rules between values 30%-100%.

Conclusions

The OCVR allows for the evolution and understanding of the association rules. There might be a particular interest in rules that receive high values of OCVR index. These rules seem to vary systematically and with intense degree, which means that the purchasing behavior of consumers in this particular market basket is not so stable and predefined. However, this does not mean that these rules do not have value for further analysis. On the contrary, this research sustains that association rules products with high OCVR values, are more susceptible of marketing strategies, as the determination and the dedication of the consumer in selecting the specific market basket presents significant variances. At the same time there should be observed the degree of confidence of rules with high OCVR and initially to control those who display a high degree of confidence. By taking action with appropriate marketing strategies it is more likely to change the level of confidence of those rules into a higher level, which already seems to be accomplished randomly and occasionally during the year. To change the location of the products on the shelf, to define the discount policy but also to form recommendation systems, the analysis of OCVR index values can be particularly useful. The evolution of consumer behavior in the course of time can reveal the combinations of products and, in particular, those products that are more suitable for promotion sales strategies.

Summary and Future Work

This research was conducted in Greek market product data and known super market chain, collected from customer purchases through loyalty cards. During the process of market basket analysis there were created 12 subsets of data corresponding to the data collected each month of the year. For each subset there were calculated lift and confidence indicators of association rules and at the same time a new indicator was co-estimated, the one of overall variability (OCVR). The OCVR results from the average of the values of the variability of lift and confidence indicators and describes degree of the overall variability of association rules. Each marketing strategy must be implemented to streamline the consumer behavior and to increase customer confidence. For this reason you must first identify application rules with high values of OCVR and high degree of confidence and attempt with the appropriate marketing strategy to reduce the value of OCVR while increasing the confidence of its customers.

In a future research it would be very interesting to establish an indicator which incorporates and includes the above information. It would also be quite interesting in the evaluation of OCVR to find weight factors for the representation of the variability of the degree of confidence and the degree of lift in the composition of the index. The existence of possible relations of substitution or even complementation between the association rules it may also constitute a subject for further research. Finally, it would be interesting to examine the existence of annual periodicity of the indexes, using additional data of more than one year

Fig. 1 .

 1 Fig. 1. Curve of Long Tail Effect

Fig. 2 .

 2 Fig. 2. Graph of the Time Change Confidence Degree of the Association Rules Rules 5, 6 and 7 present a significant slope owing to the strong variability of the degree of customer confidence in September 2008, October 2008 and August 2009.It is also noted that when the confidence of customers is increased for the market basket of rule 5, the same period the confidence of customers for the market basket of rule 6 is reduced. The same but to a lesser extent seems to be the case with rules 5 and 7. In such cases the market baskets between them seem to work as substitute.As shown by the results in table3, the values of association rules indicators lift, confidence, support, of super market chain products, present monthly fluctuations. For example, the degree of confidence in the rule 1 appears with percentage 86.84% in September and is reduced to 81.02% in the month of October and is increased to 85.95% the month of August. The option to purchase fruit after the selection of bread and yoghurt in the basket market seems to be less random in September compared to October and more random than that in August. Also on rules 5, 6 and 7, for the first three months under consideration, there are significant changes in levels of confidence in connection with the other rules. In particular, for rule 6 the changes are made to a high degree of confidence.These monthly fluctuations in prices of lift and confidence are the subject of this research study. The research of rules association products should not be concluded solely on the assessment of the three indicators, without taking account of changes in these prices during the year. Through the assessment of variation in the degree of confidence and lift of a rule, one can draw useful conclusions about the marketing.

Figure 3

 3 below shows the curve of the overall variance ratio (OCVR) for all of 1803 association rules for products of super market, for the period from 01.09.2008 to 31.08.2009.

Fig. 3 .

 3 Fig. 3. Overall Variability Curve of Association Rules

Fig. 4 .

 4 Fig. 4. Histogram of Overall Variability of Association Rules

Table 1 .

 1 Number of Transactions per Year and per Month.

	Time	Year	Month 1 Month 2 Month 3 Month 4	Month 5	Month 6
	Number 183.827	15.603	16.027	14.621	18.141	15.323	15.982
			Month 7 Month 8 Month 9 Month 10 Month11 Month 12
			16.189	15.642	15.907	14.624	13.189	12.579

Table 2 .

 2 Number of Annual and Monthly Association Data Rules.The 1803 rules, at the level of 247 subcategories of products, resulting from the extraction process of overall annual data were used as a base for additional rules analysis at monthly level. For each of the 1803 rules, there have been recorded the values for the three indicators, lift, support and confidence during the 12 months of the year. Thus was created the table 3, with the monthly development of association rules measurement indicators. In table 3, L indicates lift, S is for the value of support and C denotes the value of confidence.

	Time	Year Month 1 Month 2 Month 3 Month 4	Month 5	Month 6
	Number 1.803	2.262	2.221	2.537	2.429	2.440	1.929
			Month 7 Month 8 Month 9 Month 10 Month11 Month 12
			1.619	1.875	2.149	1.696	1.651	2.215
	2.2 Time Development of Association Rules

Table 3 .

 3 Monthly Development of Association Rules Measurement Indicators

			Month 1 (Sept. 2008)		Month 2 (Oct. 2008)
	A/A	Rules	L	S %	C %	L	S %	C %
	1	Yoghurt -Bread > Fruits	1.83 1.27	86.84 1.72	1.49	81.02
	2	Toast-Cereals> Fresh Milk	1.20 2.26	71.89 1.23	2.52	73.81
	3	Fruits -Sweet Biscuits >	1.73 2.63	64.70 1.79	2.44	61.77
		Vegetables
	4	Fruits -Pasta > Fresh Milk	1.83 1.87	40.70 1.84	1.69	36.44
		-Vegetables
	5	Fresh Milk -Beers > Cola	1.86 1.27	40.60 11.2	1.12	66.42
	6	Cola -Salad (Not Packed,	12.8 1.02	79.50 1.14	1.41	68.28
		Packed) > Vegetables
	7	Chicken Not Packed> Fruits 14.1 1.57	53.49 1.17	1.01	30.55
	.	…………………………….. …	…	…	…	…	….
	.	…………………………….. …	…	…	…	…	….
	1803 Fresh Milk -Beef Not	1.63 1.28	33.67 1.73	1.18	34.36
		Packed> Bread
				….. .		Month 12 (Aug. 2009)
			L	S%	C%	L	S%	C%
			…	…	…	1.85	1.26	85.95
			…	…	…	1.38	2.58	79.41
			…	…	….	1.56	2.70	62.62
			…	…	….	1.61	1.53	36.42
			…	…	…	1.69	1.71	37.79
			…	…	…	15.2	1.19	99.34
			…	…	….	1.16	1.26	32.78
			…	…	….	…	…	….
			…	…	….	…	…	….
			…	…	….	1.58	1.34	31.12

Table 4 .

 4 Overall Variability Association Rules

	A/A	Rules	CVL %	CVC %	OCVR %
	1	Yoghurt -Bread> Fruits	4.19	4.46	4.33
	2	Toast-Cereal > Fresh Milk	4.05	2.86	3.46
	3	Fruits -Sweet Biscuits > Vegetables	5.40	4.27	4.83
	4	Fruits -Pasta > Fresh Milk -Vegetables	5.11	5.66	5.39
	.	……………………………	…	…	…
	.	……………………………	…	…	…
	.	……………………………
	1803 Fresh Milk -Beef not Packed > Bread	11.10	24.80	17.95

Acknowledgments

We would like to thank Super Markets "Afroditi" for providing data and for their help.


Harris Papadopoulos
email: h.papadopoulos@frederick.ac.cy

Reliable Probabilistic Prediction for Medical Decision Support

Keywords: Venn Prediction, Probabilistic Classification, Multiprobability Prediction, Medical Decision Support

A major drawback of most existing medical decision support systems is that they do not provide any indication about the uncertainty of each of their predictions. This paper addresses this problem with the use of a new machine learning framework for producing valid probabilistic predictions, called Venn Prediction (VP). More specifically, VP is combined with Neural Networks (NNs), which is one of the most widely used machine learning algorithms. The obtained experimental results on two medical datasets demonstrate empirically the validity of the VP outputs and their superiority over the outputs of the original NN classifier in terms of reliability.

Introduction

Medical decision support is an area in which the machine learning community has conducted extensive research that resulted in the development of several diagnostic and prognostic systems [START_REF] Kononenko | Machine learning for medical diagnosis: History, state of the art and perspective[END_REF][START_REF] Lisboa | A review of evidence of health benefit from artificial neural networks in medical intervention[END_REF]. These systems learn to predict the most likely diagnosis of a new patient based on a past history of patients with known diagnoses. The most likely diagnosis however, is the only output most such systems produce. They do not provide any further information about how much one can trust the provided diagnosis. This is a significant disadvantage in a medical setting where some indication about the likelihood of each diagnosis is of paramount importance [START_REF] Holst | Intelligent computer reporting 'lack of experience': a confidence measure for decision support systems[END_REF].

A solution to this problem was given by a recently developed machine learning theory called Conformal Prediction (CP) [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF]. CP can be used for extending traditional machine learning algorithms and developing methods (called Conformal Predictors) whose predictions are guaranteed to satisfy a given level of confidence without assuming anything more than that the data are independently and identically distributed (i.i.d.). More specifically, CPs produce as their predictions a set containing all the possible classifications needed to satisfy the required confidence level. To date many different CPs have been developed, see e.g. [14, 15, 17-19, 21, 22], and have been applied successfully to a variety of important medical problems such as [START_REF] Bellotti | Qualified predictions for microarray and proteomics pattern diagnostics with confidence machines[END_REF][START_REF] Gammerman | Serum proteomic abnormality predating screen detection of ovarian cancer[END_REF][START_REF] Lambrou | Reliable confidence measures for medical diagnosis with evolutionary algorithms[END_REF][START_REF] Lambrou | Assessment of stroke risk based on morphological ultrasound image analysis with conformal prediction[END_REF][START_REF] Papadopoulos | Reliable diagnosis of acute abdominal pain with conformal prediction[END_REF].

This paper focuses on an extension of the original CP framework, called Venn Prediction (VP), which can be used for making multiprobability predictions. In particular multiprobability predictions are a set of probability distributions for the true classification of the new example. In effect this set defines lower and upper bounds for the conditional probability of the new example belonging to each one of the possible classes. These bounds are guaranteed (up to statistical fluctuations) to contain the corresponding true conditional probabilities. Again, like with CPs, the only assumption made for obtaining this guaranty is that the data are i.i.d.

The main aim of this paper is to propose a Venn Predictor based on Neural Networks (NNs) and evaluate its performance on medical tasks. The choice of NNs as basis for the proposed method was made due to their successful application to many medical problems, see e.g. [START_REF] Anagnostou | Artificial neural networks for decisionmaking in urologic oncology[END_REF][START_REF] Anastassopoulos | Ann for prognosis of abdominal pain in childhood: Use of fuzzy modelling for convergence estimation[END_REF][START_REF] Mantzaris | A soft computing approach for osteoporosis risk factor estimation[END_REF][START_REF] Pattichis | Artificial neural networks in medical imaging systems[END_REF], as well as their popularity among machine learning techniques for almost any type of application. The experiments performed examine on one hand the empirical validity of the probability bounds produced by the proposed method and on the other hand compare them with the probabilistic outputs of the original NN classifier.

The rest of this paper starts with an overview of the Venn Prediction framework in the next section, while in Section 3 it details the proposed Neural Network Venn Predictor algorithm. Section 4 presents the experiments performed on two medical datasets and reports the obtained results. Finally, Section 5 gives the conclusions and future directions of this work.

The Venn Prediction Framework

This section gives a brief description of the Venn prediction framework; for more details the interested reader is referred to [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF]. We are given a training set {(x 1 , y 1 ), . . . , (x l , y l )} of examples, where each x i ∈ IR d is the vector of attributes for example i and y i ∈ {Y 1 , . . . , Y c } is the classification of that example. We are also given a new unclassified example x l+1 and our task is to predict the probability of this new example belonging to each class Y j ∈ {Y 1 , . . . , Y c } based only on the assumption that all (x i , y i ), i = 1, 2, . . . are generated independently by the same probability distribution (i.i.d.).

The main idea behind Venn prediction is to divide all examples into a number of categories and calculate the probability of x l+1 belonging to each class Y j ∈ {Y 1 , . . . , Y c } as the frequency of Y j in the category that contains it. However, as we don't know the true class of x l+1 , we assign each one of the possible classes to it in turn and for each assigned classification Y k we calculate a probability distribution for the true class of x l+1 based on the examples {(x 1 , y 1 ), . . . , (x l , y l ), (x l+1 , Y k )}.

(

) 1
To divide each set (1) into categories we use what we call a Venn taxonomy. A Venn taxonomy is a finite measurable partition of the space of examples. Typically each taxonomy is based on a traditional machine learning algorithm, called the underlying algorithm of the Venn predictor. The output of this algorithm for each attribute vector x i , i = 1, . . . , l + 1 after being trained either on the whole set (1), or on the set resulting after removing the pair (x i , y i ) from [START_REF] Anagnostou | Artificial neural networks for decisionmaking in urologic oncology[END_REF], is used to assign (x i , y i ) to one of a predefined set of categories. For example, a Venn taxonomy that can be used with every traditional algorithm puts in the same category all examples that are assigned the same classification by the underlying algorithm. The Venn taxonomy used in this work is defined in the next section.

After partitioning (1) into categories using a Venn taxonomy, the category T new containing the new example (x l+1 , Y k ) will be nonempty as it will contain at least this one example. Then the empirical probability of each label Y j in this category will be

p Y k (Y j ) = |{(x * , y * ) ∈ T new : y * = Y j }| |T new | . ( 2
)
This is a probability distribution for the label of x l+1 . After assigning all possible labels to x l+1 we get a set of probability distributions that compose the multiprobability prediction of the Venn predictor

P l+1 = {p Y k : Y k ∈ {Y 1 , . . . , Y c }}.
As proved in [START_REF] Vovk | Algorithmic Learning in a Random World[END_REF] the predictions produced by any Venn predictor are automatically valid multiprobability predictions. This is true regardless of the taxonomy of the Venn predictor. Of course the taxonomy used is still very important as it determines how efficient, or informative, the resulting predictions are. We want the diameter of multiprobability predictions and therefore their uncertainty to be small and we also want the predictions to be as close as possible to zero or one.

The maximum and minimum probabilities obtained for each class Y j define the interval for the probability of the new example belonging to Y j : min k=1,...,c

p Y k (Y j ), max k=1,...,c p Y k (Y j ) . (3)
If the lower bound of this interval is denoted as L(Y j ) and the upper bound is denoted as U (Y j ), the Venn predictor finds

j best = arg max j=1,...,c L(Y j ) (4)
and outputs the class ŷ = Y j b est as its prediction together with the interval

[L(ŷ), U (ŷ)] (5)
as the probability interval that this prediction is correct. The complementary interval

[1 -U (ŷ), 1 -L(ŷ)] (6)
gives the probability that ŷ is not the true classification of the new example and it is called the error probability interval.

Venn Prediction with Neural Networks

This section describes the proposed Neural Network (NN) based Venn Prediction algorithm. In this work we are interested in binary classification problems (Y j ∈ {0, 1}) and therefore this algorithm is designed for this type of problems. The NNs used were 2-layer fully connected feed-forward networks with tangent sigmoid hidden units and a single logistic sigmoid output unit. They were trained with the scaled conjugate gradient algorithm minimizing cross-entropy error (log loss). As a result their outputs can be interpreted as probabilities for class 1 and they can be compared with those produced by the Venn predictor.

The outputs produced by a binary classification NN can be used to define an appropriate Venn taxonomy. After assigning each classification Y k ∈ {0, 1} to the new example x l+1 we train the underlying NN on the set (1) and then input the attribute vector of each example in (1) as a test pattern to the trained NN to obtain the outputs o 1 , . . . , o l+1 . These output values can now be used to divide the examples into categories. In particular, we expect that the examples for which the NN gives similar output will have a similar likelihood of belonging to class 1. We therefore split the range of the NN output [0, 1] to a number of equally sized regions λ and assign the examples whose output falls in the same region to the same category. In other words each one of these λ regions defines one category of the taxonomy.

Using this taxonomy we divide the examples into categories for each assumed classification Y k ∈ {0, 1} of x l+1 and follow the process described in Section 2 to calculate the outputs of the Neural Network Venn Predictor (NN-VP). Algorithm 1 presents the complete NN-VP algorithm.

Experiments and Results

Experiments were performed on two medical datasets from the UCI Machine Learning Repository [START_REF] Frank | UCI machine learning repository[END_REF]:

-Mammographic Mass, which is concerned with the discrimination between benign and malignant mammographic masses based on 3 BI-RADS attributes (mass shape, margin and density) and the patient's age [START_REF] Elter | The prediction of breast cancer biopsy outcomes using two CAD approaches that both emphasize an intelligible decision process[END_REF]. It consists of 961 cases of which 516 are benign and 445 are malignant. -Pima Indians Diabetes, which is concerned with forecasting the onset of diabetes mellitus in a high-risk population of Pima Indians [START_REF] Smith | Using the ADAP learning algorithm to forecast the onset of diabetes mellitus[END_REF]. It consists of 768 cases of which 500 tested positive for diabetes. Each case is described by 8 attributes.

In the case of the Mammographic Mass data the mass density attribute was not used as it did not seem to have any positive impact on the results. Furthermore all cases with missing attribute values were removed and the 2 nominal attributes (mass shape and margin) were converted to a set of binary attributes, one for each nominal value; for each case the binary attribute corresponding to the nominal value of the attribute was set to 1 while all others were set to 0. The resulting dataset consisted of 830 examples described by 10 attributes each.

The NNs used consisted of 4 hidden units for the Mammographic Mass data, as this was the number of units used in [START_REF] Elter | The prediction of breast cancer biopsy outcomes using two CAD approaches that both emphasize an intelligible decision process[END_REF], and 10 for the Pima Indians Diabetes data, as this seemed to have the best performance with the original NN classifier. All NNs were trained with the scaled conjugate gradient algorithm minimizing cross-entropy error and early stopping based on a validation set consisting of 20% of the corresponding training set. In an effort to avoid local minima each NN was trained 5 times with different random initial weight values and the one that performed best on the validation set was selected for being applied to the test examples. Before each training session all attributes were normalised setting their mean value to 0 and their standard deviation to 1. The number of categories λ of NN-VP was set to 6, which seems to be the best choice for small to moderate size datasets.

On-line Experiments

This subsection demonstrates the empirical validity of the Neural Networks Venn Predictor (NN-VP) by applying it to the two datasets in the on-line mode. More specifically, starting with an initial training set consisting of 50 examples, each subsequent example is predicted in turn and then its true classification is revealed and it is added to the training set for predicting the next example. Figure 1 shows the following three curves for each dataset:

the cumulative error curve

E n = n i=1 err i , (7)
where err i = 1 if the prediction ŷi is wrong and err i = 0 otherwise, the cumulative lower error probability curve (see [START_REF] Gammerman | Serum proteomic abnormality predating screen detection of ovarian cancer[END_REF])

LEP n = n i=1 1 -U (ŷ i ) (8)
and the cumulative upper error probability curve

U EP n = n i=1 1 -L(ŷ i ). (9)
Both plots confirm that the probability intervals produced by NN-VP are wellcalibrated. The cumulative errors are always included inside the cumulative upper and lower error probability curves produced by the NN-VP. Two analogous plots generated by applying the original NN classifier to the two datasets are shown in Figure 2. In this case the cumulative error curve [START_REF] Holst | Intelligent computer reporting 'lack of experience': a confidence measure for decision support systems[END_REF] for each NN is plotted together with the cumulative error probability curve

EP n = n i=1 |ŷ i -pi |, (10)
where ŷi ∈ {0, 1} is the NN prediction for example i and pi is the probability given by NN for example i belonging to class 1. In effect this curve is a sum of the probabilities of the less likely classes for each example according to the NN. One would expect that this curve would be very near the cumulative error curve if the probabilities produced by the NN were well-calibrated. The two plots of Figure 2 show that this is not the case. The NNs underestimate the true error probability in both cases since the cumulative error curve is much higher than the cumulative error probability curve. To confirm this, the p-value of obtaining the resulting total number of errors E N by a Poisson binomial distribution with the probabilities produced by the NN was calculated for each dataset. The resulting p-values were 0.000179 and 0.000548 respectively. This demonstrates the need for probability intervals as opposed to single probability values as well as that the probabilities produced by NNs can be very misleading.

Batch Experiments

This subsection examines the performance of NN-VP in the batch setting and compares its results with those of the direct predictions made by the original NN classifier. For these experiments both datasets were divided randomly into a training set consisting of 200 examples and a test set with all the remaining examples. In order for the results not to depend on a particular division into training and test sets, 10 different random divisions were performed and all results reported here are over all 10 test sets.

Since NNs output a single probabilistic output for the true class of each example being 1, in order to compare this output with that of NN-VP the latter was converted to the mean of L(1) and U (1); corresponding to the estimate of NN-VP about the probability of each test example belonging to class 1. For reporting these results four quality metrics are used. The first is the accuracy of each classifier, which does not take into account the probabilistic outputs produced, but it is a typical metric for assessing the quality of classifiers. The second is cross-entropy error (log loss):

CE = - N i=1 y i log(p i ) + (1 -y i ) log(1 -pi ), (11)
BS = 1 N N i=1 (p i -y i ) 2 . (12)
The Brier score can be decomposed into three terms interpreted as the uncertainty, reliability and resolution of the probabilities, by dividing the range of probability values into a number of intervals K and representing each interval k = 1, . . . , K by a 'typical' probability value r k [START_REF] Murphy | A new vector partition of the probability score[END_REF]. The fourth metric used here is the reliability term of this decomposition:

REL = 1 N K k=1 n k (r k -φ k ) 2 , (13)
where n k is the number of examples with output probability in the interval k and φ k is the percentage of these examples that belong to class 1. Here the number of categories K was set to 20. Tables 1 and2 present the results of the original NN and NN-VP on each dataset respectively. With the exception of the accuracy on the Pima Indians Diabetes dataset the NN-VP performs better in all other cases. Although the difference between the two methods on the first three metrics is relatively small, the improvement achieved by the VP in terms of reliability is significant. Reliability is the main concern of this work, as if the probabilities produced by some algorithm are not reliable, they are not really useful.

Conclusions

This paper presented a Venn Predictor based on Neural Networks. Unlike the original NN classifiers VP produces probability intervals for each of its predictions, which are valid under the general i.i.d. assumption. The experiments performed in the online setting demonstrated the validity of the probability intervals produced by the proposed method and their superiority over the single probabilities produced by NN, which can be significantly different from the observed frequencies. Moreover, the comparison performed in the batch setting showed that even when one discards the interval information produced by NN-VP by taking the mean of its multiprobability predictions these are still much more reliable than the probabilities produced by NNs.

An immediate future direction of this work is the definition of a Venn taxonomy based on NNs for multilabel classification problems and experimentation with the resulting VP. Furthermore, the application of VP to other challenging problems and evaluation of the results is also of great interest.

Algorithm 1 :

 1 Neural Networks Venn Predictor Input: training set {(x1, y1), . . . , (x l , y l )}, new example x l+1 , number of categories λ. for k = 0 to 1 do Train the NN on the extended set {(x1, y1), . . . , (x l , y l ), (x l+1 , k)}; Supply the input patterns x1, . . . , x l+1 to the trained NN to obtain the outputs o1, . . . , o l+1 ; for i = 1 to λ do Find all examples with NN output between (i -1)/λ and i/λ and assign them to category Ti; end Find the category Tnew ∈ {T1, . . . , T λ } that contains (x l+1 , k); p k (1) := |{(x * ,y * )∈Tnew :y * =1}| |Tnew | ; p k (0) := 1 -p k (1); end L(0) := min k=0,1 p k (0); and L(1) := min k=0,1 p k (1); Output: Prediction ŷ = arg maxj=0,1 L(j); The probability interval for ŷ: [min k=0,1 p k (ŷ), max k=0,1 p k (ŷ)].

Fig. 1 .

 1 Fig. 1. On-line performance of NN-VP on the two datasets. Each plot shows the cumulative number of errors En with a solid line and the cumulative lower and upper error probability curves LEPn and U EPn with dashed lines.

Fig. 2 .

 2 Fig. 2. On-line performance of the original NN classifier on the two datasets. Each plot shows the cumulative number of errors En with a solid line and the cumulative error probability curve EPn with a dashed line.

Table 1 .

 1 Results of the original NN and NN-VP on the Mammographic Mass dataset

		Accuracy	CE	BS	REL
	Original NN	78.83%	3298 0.1596 0.0040
	NN-VP	78.92%	3054 0.1555 0.0023
	Improvement (%)	0.11	7.40	2.57	42.50

Table 2 .

 2 Results of the original NN and NN-VP on the Pima Indians Diabetes dataset N is the number of examples and pi is the probability produced by the algorithm for class 1; this is the error minimized by the training algorithm of the NNs on the training set. The third metric is the Brier score:

		Accuracy	CE	BS	REL
	Original NN	74.56%	3084 0.1760 0.0074
	NN-VP	74.26%	3014 0.1753 0.0035
	Improvement (%)	-0.40	2.27	0.40	52.70

where

Acknowledgments. The author is grateful to Professors V. Vovk and A. Gammerman for useful discussions. This work was supported by the Cyprus Research Promotion Foundation through research contract ORIZO/0609(BIE)/24 ("Development of New Venn Prediction Methods for Osteoporosis Risk Assessment").


Shan Gong

Antonio Artés-Rodríguez
email: antonio@tsc.uc3m.es

Fast Background Elimination in Fluorescence Microbiology Images: Comparison of Four Algorithms

Keywords: Tuberculosis bacilli, background remove, object detection, fluorescence image

In this work, we investigate a fast background elimination front-end of an automatic bacilli detection system. This background eliminating system consists of a feature descriptor followed by a linear-SVMs classifier. Four state-of-the-art feature extraction algorithms are analyzed and modified. Extensive experiments have been made on real sputum fluorescence images and the results reveal that 96.92% of the background content can be correctly removed from one image with an acceptable computational complexity.

Introduction

Tuberculosis is a contagious disease that causes thousands of death every year around the whole word. Sputum specimens are firstly stained with fluorescent dye and fluorescence images can be obtained by scanning these specimens with a fluorescence microscope. Since conventional diagnosis require amount of human efforts, detecting Tuberculosis bacilli automatically has drove many attentions [START_REF] Osman | Colour image segmentation of Tuberculosis bacillus in Ziehl-Neelsen-Stained tissue Images using moving K-Mean clustering procedure[END_REF], [START_REF] Foreo | Automatic identification techniques of tuberculosis bacteria[END_REF], [START_REF] Foreo | Identification of tuberculosis bacteria based on shape and color[END_REF]. All of these systems use a specific segmentation method to highlight the bacilli regions from the original image.

However, all these methods are based on statistical analysis of the profile and color information of bacilli, so they have disadvantages: Poor generalization ability. Stained M. tuberculosis bacilli display in images with varying appearances. Thus in [START_REF] Osman | Colour image segmentation of Tuberculosis bacillus in Ziehl-Neelsen-Stained tissue Images using moving K-Mean clustering procedure[END_REF], [START_REF] Foreo | Automatic identification techniques of tuberculosis bacteria[END_REF], [START_REF] Foreo | Identification of tuberculosis bacteria based on shape and color[END_REF], both color and contour features have been considered. But, statistical knowledge about the shape and color of the labeled bacilli is limited to dataset which is sensitive to experimental conditions such as luminance and camera types. Poor ability dealing with outliers. The contrast between bacilli and the background is regularly manifest given that stained bacilli fluoresce in the range between green and yellow up to white. In this case, color segmentation might be able to produce desired results. Nevertheless, when one bacteria is overlapped by other debris objects such as cells, or when images have been taken under inapplicable luminance conditions, similar segmentation attempts may be proved futile.

Fig. 1. The input original image passes through a front-end quick background subtraction system and drops most of background content. The filtered image (i.e., retained potential bacteria region) will be reanalyzed and reclassified with the purpose of improving the specificity of the whole system.

Instead of getting involved in intricate segmentation algorithm investigation, we propose a quick background subtraction system as a front-end of the M. tuberculosis bacillus detection system shown in Fig. 1. This background elimination system is termed as a coarse feature descriptor followed by a binary classification (i.e., bacillus or background). The essential idea of designing such a front-end is to reduce the computational complexity while maintaining elevated sensibility and compensatory specificity. As the majority of the original image has been disposed by the front-end processor, steps of locating bacilli are only required to take on the retained possible regions which will dramatically accelerate the whole detection process. In section 2, four feature extraction algorithms: SIFT, color SIFT, Haralick Features and Histograms of Colors are modified to suit our M. bacillus recognition task. Section 3 gives experimental results based on real fluorescence images.

Feature Extraction Algorithms

Patches are extracted by sliding a local window across the image and classified as positive (i.e., presence of object) or negative (i.e, absence of object). Unlike articulated objects (e.g., pedestrians), bacilli do not contain a lot of structural or intra-class variations, specially scale variations, thus, it is reasonable to use single fixed-size sliding window. Characters based on small sliding window are more discriminative, but computational expensive. On the contrary, big sliding window avoids expensive computations by allowing more flexible moving steps, however, as more background pixels have been included, the results are less reliable. Given that bacillus generally is of size up to 20 × 20, in our experiment the size of patches has been chosen as 36 × 36.

Patch classifier is chosen as SVMs with linear kernel [START_REF] Cortes | Support-vector network[END_REF], [START_REF] Lin | LIBSVM: A library for Support Vector Machines[END_REF].

SIFT and Color Based SIFT

The original SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] descriptor initials with a keypoint detector followed by a local image descriptor. Different with the general image matching problem, in our case, neither multiscale invariability nor distinctive points localization should be necessarily required. Smooth the i-th color component I(x, y, i) of one image with a variable-scale Gaussian mask G(x, y, σ),

L(x, y, i, σ) = G(x, y, σ) * I(x, y, i), 1 ≤ i ≤ c . (1)
G(x, y, σ) = 1 2πσ 2 e -(x 2 +y 2 )/2σ 2 ,
where * is a convolution operator.

Then the gradient of the Gaussian mask smoothed image can be written as

J(x, y, i) = ∇[L(x, y, i, σ)] = ∇[G(x, y, σ) * I(x, y, i)] = [∇G(x, y, σ)] * I(x, y, i), 1 ≤ i ≤ c . ( 2
)
where ∇ is the derivative operator, σ indicates the width of the Gaussian and determines the quantity of smoothing (i.e., the gradient can be obtained by convolving the image with the horizontal and vertical derivatives of the Gaussian kernel function). SIFT features for the i-th color channel of the patch p(u, v; c) are formed by computing the gradient J(u, v, i) at each pixel of the patch. The gradient orientation is then weighted by its magnitude. This patch is then split into 4 × 4 grid, in each tile a gradient orientation histogram is formed by adding the weighted gradient value to one of the 8 orientation histogram bins.

An extension is CI-SIFT which embeds color information to conventional SIFT descriptor by applying the five color invariant sets presented in Table 3 of [START_REF] Geusebroek | Color invariance[END_REF].

Histogram of Color

Color signatures are extracted by using the histograms of color method proposed in [START_REF] Swain | Color indexing[END_REF].

Haralick Features

Based on co-occurrence matrix, several statistics were proposed in [START_REF] Haralick | Textural features for image classification[END_REF], known as Haralick features.

Co-occurrence matrix of a n bits gray-level image is of size 2 n ×2 n . One way to reduce the dimension of this matrix is to quantitate the image. The quantization for images of multidimensional color space can be done with K-means clustering algorithm. In the case of images of unit color component, uniform quantization can be employed.

Patches Classification Experiments

Datasets Description

Images are required from a 20x fluorescence Nikon microscope with a prior automatic slide loader and a Retiga 2000R camera with acquisition time 0.6 sec, gain five and zero offset. For each patient, 200 RGB 1200 × 1600 (8 bits per color) images have been taken and stored. 4,987 bacilli of 952 images of 45 infected patients have been identified and labeled manually by experts. Patches centered at each bacteria haven been extracted. Furthermore, bacilli have been rotated 90, 180 and 270 grades so as to enrich the dataset. Finally, a positive dataset of 19,890 patches has been generated. Regarding the negative dataset, 100,031 negative patch samples haven been created by arbitrarily moving the local windows in images of a couple of healthy patients.

In the following experiments, 3,000 positive as well as negative randomly selected patches are used for training step and all the rest for test. Results are obtained by averaging 100 runs of a linear SVM. Due to space limitation, full detailed results can be found in technical report [START_REF] Shan | Artés-Rodrigués[END_REF].

Experiments

Experiment E01: Without any feature descriptor. For the purpose of comparison, in this experiment none feature extraction processes have been taken. Patches are considered to be of size 20 × 20. PCA has been used to reduce the feature dimension. And, only the BLUE component has been analyzed. As long as the patch is small enough, even without feature extraction, one simple linear-SVM classifier is capable to achieve a sensibility up to 93.6%.

Experiment E02: SIFT. Both the sensibility and specificity are comparable regardless of the color spaces. For white color bacilli surrounded by yellow tissues, BLUE is the only discriminative in the RGB color space, which may explain why BLUE component obtains the optimal results.

Experiment E03: CI-SIFT. In [START_REF] Geusebroek | Color invariance[END_REF], the author stated that the degree of invariance of the five color invariant sets have the following relation:

E ω < W ω < C ω < N ω < H ω .
H ω which is the most robust to changes in imaging condition (see Table 1 in [START_REF] Geusebroek | Color invariance[END_REF]) had the lowest discriminative power while E ω which is the most sensitive to any changes achieved the best recognition precision.

Experiment E04: HF-without Quantization It is always better not to normalize features sets obtained from the four adjacently measurements (see Fig. 2 of [START_REF] Shan | Artés-Rodrigués[END_REF]) regardless of the implemented color spaces.

Experiment E05: HF-with Quantization. Quantization (see section 2.3) is firstly employed for each patch. 1,000 positive as well as negative patches have been picked randomly from the entire data set from which codebooks of colors are constructed with K-means clustering method. Regarding unit dimensional color spaces, uniform quantization method also has been studied. Excluding RGB, sensibility as well as specificity obtained in all the unit dimensional color spaces in this experiment are comparable to or even higher than those obtained in the previous experiment which reveals that quantizations are highly recommended. Furthermore, uniform quantization is much more reliable than K-means quantization. In this paper, we have analyzed the performance of several feature extraction algorithms. In Table 1 are the optimal cases for each algorithm. The BLUE scale state-of-the-art SIFT-like descriptor outperforms the others. The specificity achieved by Histograms of colors method is more than 15% lower than the average level. CI-SIFT as well as HF take use both the geometrical and color signatures and are capable to obtain appealing results. Small patch may contain more discriminative signatures, but we aim to reduce the background as fast as possible which means that with the same accuracy bigger patches are always recommended. Since the computational complexity of most of attributes of the Haralick feature sets are O(number of bits of the image 2 ), the quantization step considerably accelerate the algorithm. Another conclusion we can make is that the BLUE channel is the most robust compared with other color representations. By applying this background elimination process, approximated 96.92% background pixels can be subtracted from the original image. One example is given in Fig. 2.

Conclusion and Future Line

One possible way to improve sensibility without degrading specificity is to use a different evaluation function (such as F-score, AUC) of the linear SVM classifier or add other simple implemented characters into the feature set.

Fig. 2 .

 2 Fig. 2. The left figure is a fluorescence image with one bacteria. The right figure is the filtered image in which the white regions are detected potential bacilli locations, with the real bacteria bounded by the red rectangular for purpose of reference. Parameters used here are: SIFT descriptor on green color channel with step of the moving window equal to 1. Most of the pixels of the image have been classified as background (i.e., the black regions).

Table 1 .

 1 Comparison of all the algorithms = 36, k = 2 8 , kQ = 23 . And for HF the complexity is considered for one single adjacency measurement

	method	parameters	sensibility	specificity	computational complexity (approx-imated number of executions per
					patch)
					+	×	others
	SIFT	Blue	95.199(0.187) 97.234(0.151)	11l 2	12l 2	2l 2
	HoColor	RGB, NumBin = 8 93.418(0.357) 79.672(0.464)	0	0	3l 2
		BLUE, NumBin = 8 91.097(0.484) 75.931(0.525)	0	0	l 2
	CI-SIFT	Eω	94.000(0.272) 96.949(0.167)	30l 2	31l 2	2l 2
	HF	RGB, no normaliza-	95.260(0.312) 93.704(0.256) 75k 2	66k 2	21k 2
		tion
		BLUE, no normaliza-	93.792(0.232) 93.409(0.218) 25k 2	22k 2	7k 2
		tion
	HF	BLUE, codebook =	94.845(0.256) 92.577(0.272) l 2 + 25k 2 Q l 2 + 22k 2 Q	6k 2 Q
		8, uniform Quantiza-
		tion, no normaliza-
		tion
	None feature	BLUE, patch size =	93.617(0.307) 97.046(0.189)	0	0	0
	extraction	20×20, feature vector
		is of size 1 × 400
	where l

This work has been partly supported by Ministerio de Educación of Spain (projects 'DEIPRO, id. TEC2009-14504-C02-01, and 'COMONSENS', id. CSD2008-00010).