Ashraf A Afifi
email: ashraf.afifi@uwe.ac.uk

A Study of Heuristic Evaluation Measures in Fuzzy Rule Induction

Keywords: fuzzy rule induction, heuristic evaluation measures, fuzzy sets

The rule induction process could be conceived as a search process, and hence an evaluation metric is needed to estimate the quality of rules found in the search space and to direct the search towards the best rule. The evaluation measure is the most influential inductive bias in rule learning. It is therefore important to investigate its influence on the induction process and to compare the behaviour of different evaluation measures. Many different evaluation measures have been used to score crisp rules. For some of these measures, fuzzy variations have been designed and used to score fuzzy rules. This paper examines the most popular crisp evaluation measures and demonstrates how they can be adapted into the fuzzy domain. The paper also studies the performance of these measures on a large number of data sets when used in a recently developed fuzzy rule induction algorithm. Results show that there are no universally applicable evaluation measures and the choice of the best measure depends on the type of the data set and the learning problem.

Introduction

Rule induction has proven to be a valuable tool for description, classification and generalisation of data. A variety of methods exist for rule learning using crisp sets [START_REF] Clark | Rule induction with CN2: Some recent improvements[END_REF][START_REF] Michalski | A measure of description quality for data mining and its implementation in the AQ18 learning system[END_REF][START_REF] Pham | RULES-5: A rule induction algorithm for problems involving continuous attributes[END_REF][START_REF] Pham | SRI: A scalable rule induction algorithm[END_REF]. Fuzzy sets are a generalisation of crisp sets providing increased expressive power and comprehensibility. A number of fuzzy rule induction algorithms have been developed as an extension of crisp rule learners [START_REF] Hühn | FURIA: An algorithm for unordered fuzzy rule induction[END_REF][START_REF] Afify | A novel algorithm for fuzzy rule induction in data mining[END_REF]. Recently, Afify [START_REF] Afify | A fuzzy rule induction algorithm for discovering classification rules[END_REF] introduced a novel fuzzy rule induction method called FuzzyRULES (for Fuzzy RULe Extraction System). FuzzyRULES is based on the learning strategy used in the RULES-6 [START_REF] Pham | RULES-6: A simple rule induction algorithm for handling large data sets[END_REF] crisp rule induction algorithm, previously developed by the author. FuzzyRULES preserves all the advantages of RULES-6 such as good comprehensibility and high classification accuracy. Moreover, it incorporates approximate reasoning offered by fuzzy representation, which allows better dealing with inconsistent, inexact, subjective, or noisy data. Rule induction algorithms typically use an evaluation measure to score the performance of rules found during the learning process, and to select the best rules for further exploration. Therefore, the evaluation measure as a search heuristic is very important as it determines to a large extent the performance of the learning algorithm. The selection of the most appropriate evaluation measure for any particular learning algorithm is a critical and difficult task, which is usually carried out empirically. This paper examines the role of several well-known crisp evaluation measures and how they address the specific requirements of the rule forming process. The paper also studies the performance of the fuzzy variants of these measures when applied to fuzzy rule induction algorithms. The aim is to identify the most appropriate measures to be applied in fuzzy rule induction algorithms, especially in FuzzyRULES.

The layout of the paper is as follows. Section 2 reviews the FuzzyRULES algorithm. Section 3 introduces the evaluation measures, and demonstrates the adaptation of these measures to the fuzzy set domain. Section 4 gives an empirical evaluation of the different evaluation measures when used in FuzzyRULES. Section 5 concludes the paper and provides suggestions for future work.

FuzzyRULES

The recently developed FuzzyRULES fuzzy rule induction algorithm will be used in this study to assess the performance of several heuristic evaluation measures. FuzzyRULES is based on the RULES-6 crisp rule induction algorithm. RULES-6 broadly follows the approach of AQ-like [START_REF] Michalski | A measure of description quality for data mining and its implementation in the AQ18 learning system[END_REF] learning algorithms. It employs heuristic search techniques with different learning biases and rule-space pruning strategies that significantly reduce the proportion of the search space examined during the learning process, resulting in substantial performance benefits. FuzzyRULES follows the so-called separate-and-conquer or covering strategy of rule induction algorithms. It creates the rule set one rule at a time. Each rule explains (covers) a part of the training instances. After a rule is generated, the instances covered by it are removed (separated) from the training data set before subsequent rules are learned. The remaining instances are conquered using the same induction procedure until all the instances are covered by at least one rule in the rule set. Figure 1 provides a simplified description of the FuzzyRULES algorithm. A detailed description of the algorithms can be found in [START_REF] Afify | A fuzzy rule induction algorithm for discovering classification rules[END_REF].

Evaluation Measures

A typical objective of a rule induction algorithm is to find rules that optimise a rule evaluation measure that takes both training accuracy and rule coverage into account so that the rules learned are both accurate and general. Many different measures for evaluating and assigning a score to crisp rules have been proposed in the literature [START_REF] Fürnkranz | An analysis of rule evaluation metrics[END_REF]. For some of these measures, fuzzy variations have been designed and used to score fuzzy rules [START_REF] Van Zyl | Heuristic functions for learning fuzzy conjunctive rules[END_REF]. In this section, the most commonly used rule evaluation measures are discussed and the adaptation of these measures into the fuzzy domain is demonstrated. To derive fuzzy evaluation measures, the cardinality and α-cut operators [START_REF] Klir | Fuzzy Sets and Fuzzy Logic: Theory and Applications[END_REF] will be used to describe the instances matched by the rules. Let A => C denote a candidate rule R, where A is the rule antecedent (a conjunction of conditions) and C is the rule consequent (the value predicted for the goal attribute). The set of instances in the training set T that are covered by a rule R can be defined using the cardinality measure ) (A M , also referred to as the sigma count, as follows:

   T I R I A M ) ( ) (  (1)
where ) (I R  represents the degree of match of a particular instance I with the antecedent of a rule R. For each instance, this degree is computed by a fuzzy AND of the degree of matching between each attribute value in the instance and the corresponding fuzzy condition in the rule. The conventional definition of the fuzzy AND has been used as the minimum operator.

In practice, many of the instances can match a rule antecedent to a small degree, and the summation of all these small degrees of membership can give the false impression that the rule is good, which can undermine the reliability of the evaluation measure. To prevent such instances from being covered, a user-defined α-cut threshold can be applied to the instance memberships. The membership of an instance to a rule,

   ) ( ) ( ) ( T R I R I A M   (2)
where

        ) ( ) ( I T I T R
R contains all instances in the training set T that have a membership grade in R greater than or equal to the specified value of α.

The evaluation measures include different parameters that assess the coverage of the rules. For a particular rule R, the parameters P and N denote the total number of positive instances (instances belonging to the target class) and negative instances (instances not belonging to the target class) in the training set, p(n) the number of positive (negative) instances covered by rule R, and p ( n ) the number of positive (negative) instances covered by rule R , the predecessor (parent) of rule R.

Purity

This measure is utilised in GREEDY3 [START_REF] Pagallo | Boolean feature discovery in empirical learning[END_REF] and SWAP-1 [START_REF] Weiss | Reduced complexity rule induction[END_REF] algorithms. It gives the ratio between the number of positive instances covered by a rule and the total number of covered instances. In the crisp case, the purity measure of a rule R is given by:

n p p R P   ) ( (3)
The purity measure attains its optimal value when no negative instances are covered. Also, it does not aim to cover many positive instances. As a result, this metric tends to select very specific rules covering only a small number of instances. This is undesirable since rules covering few instances are unreliable, especially where there is noise in the data. The accuracy of these rules on the training data does not adequately reflect their true predictive accuracy on new test data.

The purity measure can be fuzzified using the cardinality and α -cut operators as follows:

       ) ( ) ( ) ( ) ( ) ( ) ( ) ( T R I R P R I R I I A M C A M R P     (4)
where

) ( C A M  is the fuzzification of the number of positive instances covered by a rule R (p), ) (A M
is the fuzzification of the number of instances covered by the rule (n + p), and

}, ) ( { ) (       I P I P R R } ) ( { ) (       I T I T R R
are the sets of positive instances and total instances that are α-covered by rule R, respectively.

Information Content

The information content function measures the amount of information contained in the classification of the covered instances. It is originally used in the PRISM inductive learner [START_REF] Cendrowska | PRISM: An algorithm for inducing modular rules[END_REF], and its crisp version is given by:

           n p p R IC 2 log ) ( (5)
The best rule is the one that minimises Equation [START_REF] Hühn | FURIA: An algorithm for unordered fuzzy rule induction[END_REF]. The information content function is basically equivalent to the purity measure and its main advantage is that using a logarithmic scale tends to assign higher penalties to rules with low coverage.

The fuzzy version of the information content function can be expressed as:

                         ) ( ) ( 2 2
) (

) ( log ) ( ) ( log ) ( T R I R P R I R I I A M C A M R IC     (6)

Entropy

The entropy measure is adopted in the original version of the CN2 algorithm [START_REF] Clark | The CN2 induction algorithm[END_REF]. It is the weighted average of the information content of the positive and negative classes.

The entropy measure of a rule R is given by (the lower the entropy, the better the rule):

               n p n n p n n p p n p p R E 2 2 log log ) ( (7)
The entropy measure suffers from similar deficiencies as purity and information content measures. Also, it does not consider whether the majority of instances are positive or not. For example, a rule that covers 100 positive and 10 negative instances is considered of equal quality to another rule that covers 10 positive and 100 negative instances. To assign higher scores to rules with higher coverage, the following function is adopted [START_REF] Van Zyl | Heuristic functions for learning fuzzy conjunctive rules[END_REF].

               n p n n p n n p p n p p p n R E 2 2 log log ) ( (8)
Equation ( 8) can be adapted to the domain of fuzzy sets as follows:

                                                ) ( ) ( 2 ) ( ) ( ) ( ) ( 2 ) ( ) ( ) ( ) ( 2 2 ) ( ) ( log ) ( ) ( ) ( ) ( log ) ( ) ( ) ( ) ( ) ( ) ( log ) ( ) ( ) ( ) ( log ) ( ) ( ) ( ) ( ) ( T R I R N R I R T R I R N R I R T R I R P R I R T R I R P R I R P R I R N R I R I I I I I I I I I I A M C A M A M C A M A M C A M A M C A M C A M C A M R E                     (9)
where ) ( C A M  is the fuzzification of the number of negative instances covered by rule R (n), and

} ) ( { ) (       I N I N R R
is the set of negative instances that are αcovered by rule R.

Information Gain

The information gain measure is originally used in the FOIL relational learner [START_REF] Quinlan | Learning logical definitions from relations[END_REF]. It computes the reduction of the information content in a rule when a new condition is added to it. More precisely, it calculates the difference in the information content of the current rule R and its parent R , multiplied by the number of covered positive instances as a bias for generality. In the crisp case, it is given by:

                                    n p p n p p p R IC R IC p R IG 2 2 log ' ' ' log ) ( ) ( ) ( ( 10
)
The goal is to maximise this measure. The fuzzy information gain can be computed as follows:

                                                                      ) ( ) ( 2 ) ( ) ( 2 2 2 ) ( ) ( log ) ( ) ( log ) ( ) ( log ) ( ) ( log ) ( T R I R P R I R T R I R P R I R I I I I p A M C A M A M C A M p R IG         (11) where ) ( C A M  
is the fuzzification of the number of positive instances covered by rule R ( p ), ) (A M is the fuzzification of the number of instances covered by the rule

( n p   
), and },

) ( { ) (         I P I P R R } ) ( { ) (         I T I T R R
are the sets of positive instances and total instances that are α-covered by rule R , respectively.

Accuracy

This metric is employed in I-REP [START_REF] Fürnkranz | Incremental reduced error pruning[END_REF]. It is the proportion of positive instances that are covered (p) and negative instances that are not covered (Nn), in all instances (P + N).

In the crisp case, the accuracy measure for a rule R is given by:

N P n N p R A     ) ( ) ( (12)
The accuracy measure favours high coverage and scores rules in the range [-∞, ∞], with higher scores given to better evaluations. The problem of the accuracy measure is that this measure sometimes does not lead to a satisfactory behaviour. For example, it favours a rule that covers 2000 positive and 1000 negative instances over another rule that covers 1000 positive and only 1 negative instance.

A fuzzy variant of the accuracy measure can be defined as:

N P I N I N P C A M N C A M R A N R I R P R I R               ) ( ) ( )) ( ( ) ( )) ( ( ) ( ) (     (13)

Laplace

The Laplace estimate penalises rules with low coverage and it is used in CN2 [START_REF] Clark | Rule induction with CN2: Some recent improvements[END_REF] and several other algorithms due to its simplicity and efficiency. The Laplace estimate of a rule R is given by:

k n p p R L     1 ) ( ( 14
)
where k is the number of classes. Rule induction algorithms learn multi-class concepts by learning one class at a time. Thus, k is always 2.

The Laplace estimate has the desirable property of taking into account both accuracy and coverage when estimating rule accuracy. However, it has a problem when learning rules with less than 50% training accuracy. The Laplace estimate does not satisfy the requirement that the rule quality value should rise with increased coverage. Another problem is that the Laplace accuracy estimate is often unrealistic, especially in multiclass decision problems [START_REF] Cestnik | Estimating probabilities: A crucial task in machine learning[END_REF]. This occurred because of the assumption that underlies Laplace accuracy estimate, namely, that the a priori distribution is uniform.

A fuzzy variant of the Laplace estimate can be given by:

2 ) ( 1 ) ( 2 ) ( 1 ) ( ) ( ) ( ) (            T R I R P R I R I I A M C A M R L     (15)

m-estimate

The m-estimate [START_REF] Cestnik | Estimating probabilities: A crucial task in machine learning[END_REF] is a more general version of the Laplace measure and it is defined as follows:

m n p N P P m p R M      ) /( * ) ( (16)
where P/(P+N) is the a priori probability of the target class and m is a domain dependent parameter. The value of m is related to the amount of noise in the domain. m can be small if little noise is expected and should increase if the amount of noise is substantial. m is usually set to k, where k is the number of classes.

The m-estimate is a good choice because it is based on strong theoretical foundations and it meets the requirements of a good evaluation function. The Laplace measure can be obtained from the m-estimate when m is set to 2 and the a priori probability is assumed to be uniform. It should be noted that the m-estimate generalises the Laplace measure so that rules that cover no instances will be evaluated with the a priori probability instead of the value 1/2, which is more flexible and convenient.

The fuzzy variant of the m-estimate can be defined as follows:

k I N P P k I k A M N P P k C A M R M T R I R P R I R              ) ( ) ( ) ( ) ( * ) ( ) ( ) ( * ) ( ) (     (17)

H Measure

This measure is applied in RULES-5 [START_REF] Pham | RULES-5: A rule induction algorithm for problems involving continuous attributes[END_REF]. It is the product of the accuracy (first part) and generality (second part) of a rule.

                    ) 1 )( 1 ( 2 2 2 ) ( N P P n p p N P P n p p N P n p R H ( 18
)
The H measure can be fuzzified as follows:

                                              ) 1 )( ) ( ) ( 1 ( 2 . ) ( ) ( 2 2 ) ( ) 1 )( ) ( ) ( 1 ( 2 . ) ( ) ( 2 2 ) ( ) ( ) ( ) ( ) (
P A M C A M N P P A M C A M N P A M R H T R I R P R I R T R I R P R I R T R I R           (19)

AQ18 Measure

This measure was introduced in AQ18 [START_REF] Michalski | A measure of description quality for data mining and its implementation in the AQ18 learning system[END_REF] and it aims to combine completeness, consistency and consistency gain. This is done by allowing changes in the relative importance of completeness (first part) or consistency gain (second part) and also by changing the value of the parameter w 

[0, 1].   w w N N P N P P n p p P p R Q                               1 ) ( (20)
The fuzzy version of the AQ18 measure can be expressed as:

) 1 ( ) ( ) ( ) ( ) 1 ( . ) ( ) ( . ) ( . ) ( ) ( . ) ( ) (
P A M C A M P C A M R Q                                                                       (21)
The aforementioned evaluation measures have been developed alongside specific algorithms and their performances have not been compared to other metrics when applied to the same rule induction algorithm. As part of this work, the performance of these measures when used in the FuzzyRULES algorithm is evaluated experimentally in the following section.

Experimental Evaluation

This section presents an empirical evaluation of the nine fuzzy heuristic evaluation measures discussed in the previous section. Experimental tests were carried out using the FuzzyRULES algorithm, without applying any pruning procedures because such post processing could mask the real effect of using one or another heuristic. Three criteria were used to evaluate the results, namely, classification accuracy, rule set complexity, and the number of rules examined to obtain the rule set. The complexity of a rule set is measured by the total number of conditions in that rule set. Tests were performed on 30 data sets from the UCI repository of machine learning databases [START_REF] Blake | UCI Repository of Machine Learning Databases[END_REF]. The selected data sets either have only continuous attributes or a mixture of nominal and continuous attributes. The hold-out approach was used to partition the data into training and test data [START_REF] Efron | An Introduction to the Bootstrap[END_REF]. FuzzyRULES was run with the default settings, and the default value of 0.5 was used for the parameter w of the AQ18 measure.

Table 1 shows the classification accuracies obtained with each of the nine evaluation measures. Bold numbers indicate the best performance for a specific data set among the tested measures. In the last row, the total performance over all data sets is shown. A number of results are notable. First, the accuracy obtained with the m-estimate measure over all the data sets was in total higher than that produced with all the other measures. Also, the m-estimate measure produced the best classification results for 14 out of the 30 data sets. The Laplace and information content measures had a very similar total accuracy, but the Laplace measure had the best results overall for a higher number of data sets. The entropy and purity measures yielded the next best total accuracy, followed by the H and AQ18 measures. The accuracy and information gain measures obtained the lowest total accuracy. Second, every evaluation measure obtained the best results overall for some data sets, and the best performing measures had a notable worse performance for some other data sets. This suggests that there will not be a universal solution to all learning problems. The best result is obtained by choosing the evaluation measure that best fits the requirements of a particular learning problem. Table 2 shows the total number of conditions generated with each of the evaluation measures. Bold numbers indicate the smallest number of conditions per rule set for a particular data set. The information gain measure produced significantly fewer conditions in total than the other measures. In addition, it obtained the smallest rule sets for 29 out of the 30 data sets. However, the over-general rule sets created resulted in a deteriorated classification accuracy for most data sets. The AQ18 measure also found simple rule sets but again had poor accuracy performance. The accuracy, m-estimate, H, entropy and Laplace measures created general rules without sacrificing accuracy for most data sets. These measures prefer rules covering more instances, which often helps the learning algorithm to prevent overfitting. The purity and information content measures generated the most complex rule sets, which might be an indication of overfitting. This is most likely due to that these measures prefer more consistent rules and do not favour rules with high coverage.

Table 3 presents the size of the search space examined for each evaluation measure. The bold numbers indicate the smallest search per data set. The number of rules explored during the search process is often directly linked to the rule set complexity. Therefore, the fewer and more general rules created by the information gain measure Table 3. Total number of rules for each evaluation measure when used in FuzzyRULES.

made it to examine the least number of rules. It investigated 98% less rules than the purity method, which inspected the most rules. The amount of search required by the other evaluation measures is also related to the rule set complexity of these measures.

Conclusions and Future Work

This paper has examined the influence of different crisp evaluation metrics and analysed their role during the rule forming process. It has also proposed fuzzy variants of these measures and examined their performance when used in a recently developed fuzzy rule induction algorithm. The paper has demonstrated the strong effect of the evaluation measures on the performance of the learning algorithm. Evaluation measures that prefer more general over more specific rules helped the learning algorithm to determine the correct models for many data sets. However, over-generalisation may also deteriorate performance in problems that require a very specific concept description. The performance of additional evaluation measures, in particular those balancing the complexity and the accuracy of a particular induced model, could be studied on more data sets and other fuzzy rule induction algorithms.

Fig. 1 .

 1 Fig. 1. Overview of the FuzzyRULES algorithm.

  data set and the beam width Initialise the fuzzy rule set to empty While all the instances in the training set are not covered Take a seed instance that has not yet been covered to form a fuzzy rule Add the new fuzzy rule to the fuzzy rule set Return the pruned fuzzy rule set End Mark the instances covered by the new fuzzy rule as covered Induce a new fuzzy rule Prune the fuzzy rule set for each class using the whole training set defined to be zero when it lies below the α-cut threshold value. When the value of ) (I R  is greater than or equal to the specified value of α, rule R is said to α-cover instance I. Using the α-cut operator, the set of instances in the training set T that are α-covered by a rule R can be expressed by redefining Equation (1) as follows:

Table 1 .

 1 Classification accuracies for each evaluation measure when used in FuzzyRULES.

				Information	Information				H
	Data Set Name	Purity Entropy	Content	Gain	Accuracy Laplace m -estimate	Measure AQ18
	Abalone	23.0	24.2	23.0	15.8	21.6	22.9	23.9	25.0	18.8
	Adult	82.0	79.4	81.9	79.8	77.1	81.9	81.8	79.4	80.1
	Anneal	99.0	87.3	99.3	82.3	84.7	97.7	97.7	96.3	84.7
	Australian	80.4	87.0	83.0	86.5	86.5	85.7	85.2	80.3	86.5
	Auto	72.5	65.2	68.1	62.5	59.4	59.4	65.2	62.9	44.9
	Balance-scale	64.6	64.6	64.6	56.9	66.0	64.6	69.6	65.0	66.0
	Breast	95.3	94.8	94.0	92.7	92.7	92.3	94.3	91.9	92.7
	Cleve	75.2	74.3	75.2	74.3	79.2	82.2	82.2	77.3	72.3
	Crx	74.0	81.0	75.0	83.0	83.0	74.5	81.0	80.0	83.0
	Diabetes	64.5	75.0	64.5	72.3	69.5	64.5	75.2	68.2	74.6
	German	70.3	71.2	72.1	69.4	66.0	70.0	75.6	73.1	67.9
	German-organisation	68.5	71.8	66.7	70.9	66.0	69.4	76.4	67.0	71.5
	Glass	52.8	51.4	58.3	49.4	58.3	50.0	64.7	63.9	58.3
	Glass2	78.2	83.6	76.4	76.4	76.4	83.6	83.6	72.7	81.5
	Heart-disease	73.3	67.8	76.7	73.3	72.2	80.0	78.9	73.3	75.6
	Heart-Hungarian	73.5	76.5	98.5	78.6	74.5	76.5	78.6	72.4	75.5
	Hepatitis	80.8	82.7	78.8	73.1	88.5	86.5	84.8	82.7	88.5
	Horse-colic	70.6	82.4	70.6	65.0	79.4	76.5	83.5	76.2	80.9
	Hypothyroid	96.0	98.1	96.0	98.8	97.0	98.4	97.9	94.8	98.7
	Ionosphere	93.2	88.5	92.3	87.8	95.3	92.3	92.3	88.9	95.7
	Iris	96.0	94.0	96.0	94.0	94.0	96.0	96.0	96.0	96.0
	Letter	80.5	76.4	82.2	53.2	71.1	82.1	66.1	60.7	58.3
	Lymphography	74.0	84.0	78.0	56.0	68.0	78.0	76.0	78.0	64.0
	Satimage	81.2	80.6	83.2	60.4	76.3	86.0	84.0	81.8	67.1
	Segment	80.9	82.1	87.7	77.4	80.8	84.8	89.5	88.4	79.0
	Shuttle	97.6	95.4	95.9	94.8	94.8	98.4	98.4	95.9	94.8
	Sick-euthyroid	92.0	90.4	91.8	90.9	9.6	91.9	96.4	91.6	90.4
	Sonar	70.0	70.0	80.0	74.3	77.1	80.0	80.0	68.6	61.4
	Tokyo	91.5	91.3	92.3	91.9	87.3	92.5	92.1	91.4	90.8
	Vehicle	63.1	48.3	63.5	51.7	61.3	64.5	66.0	61.7	53.2
	Total	2314.4 2319.2	2365.6	2193.2	2213.8	2363.0	2416.8	2305.2 2252.8

Table 2 .

 2 Total number of conditions for each evaluation measure when used in FuzzyRULES.

				Information	Information				H
	Data Set Name	Purity Entropy	Content	Gain	Accuracy Laplace m -estimate	Measure AQ18
	Abalone	105	56	103	12	325	108	53	36	15
	Adult	814	137	1134	8	7	286	128	179	30
	Anneal	60	24	47	6	33	49	39	36	63
	Australian	222	6	207	2	2	126	118	52	2
	Auto	69	59	62	7	32	62	48	67	39
	Balance-scale	33	18	33	2	11	33	29	30	14
	Breast	121	9	92	3	12	30	27	22	12
	Cleve	103	30	78	5	10	52	52	47	17
	Crx	173	17	159	5	13	141	151	50	13
	Diabetes	50	34	48	6	9	39	32	26	9
	German	402	125	352	7	73	195	173	341	41
	German-organisation 536	338	471	4	175	222	219	312	45
	Glass	142	79	124	7	34	104	60	96	14
	Glass2	59	11	48	4	6	20	20	27	10
	Heart-disease	136	16	63	3	6	106	60	47	15
	Heart-Hungarian	82	4	72	2	12	42	38	34	16
	Hepatitis	65	13	46	4	12	27	24	51	24
	Horse-colic	135	16	104	3	8	121	107	134	13
	Hypothyroid	89	20	61	5	25	52	49	7	18
	Ionosphere	43	9	34	2	13	32	29	41	28
	Iris	9	3	5	3	3	5	5	5	5
	Letter	7863	3248	5434	31	1997	2573	1073	1307	517
	Lymphography	76	17	61	7	9	54	29	63	17
	Satimage	1844	395	1442	24	220	816	521	678	128
	Segment	621	412	499	13	192	286	121	372	68
	Shuttle	419	61	846	19	36	151	98	76	30
	Sick-euthyroid	163	18	162	9	31	76	53	21	11
	Sonar	49	15	34	2	16	32	31	26	17
	Tokyo	89	13	74	9	15	82	55	77	28
	Vehicle	406	204	402	9	169	360	158	150	61
	Total	14978 5407	12297	223	3506	6282	3600	4410	1320

Acknowledgements:

The author wishes to thank the Department of Engineering, Design and Mathematics, University of the West of England for providing a good environment, facilities and financial means to complete this paper.

Data Set Name

Purity Entropy


Anis Yazidi

Hugo Lewi Hammer

Quantile Estimation Based on the Principles of the Search on the Line

Keywords: Discretized Estimation, Learning Automata, Stochastic Point Location, Quantile Estimation

The goal of our research is to estimate the quantiles of a distribution from a large set of samples that arrive sequentially. We propose a novel quantile estimator that requires a finite memory and is simple to implement. Furthermore, the estimator falls under the family of incremental estimators, i.e., it utilizes the previously-computed estimates and only resorts to the last sample for updating these estimates. The estimator estimates the quantile on a set of discrete values. Choosing a low resolution results in fast convergence and low precision of the current estimate after convergence, while a high resolution results in slower convergence, but higher precision. The convergence results are based on the theory of Stochastic Point Location (SPL). The reader should note that the aim of the paper is to demonstrate its salient properties as a novel quantile estimator that uses only finite memory.

Introduction

An incremental estimator, by definition, resorts to the last observation(s) in order to update its estimate. This is especially true of quantile estimators because they work with the samples as they come from a stochastic distribution. The research on developing incremental quantile estimators is sparse. Probably, one of the outstanding early and unique examples of incremental quantile estimators is due to Tierney, proposed in 1983 [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF], and which resorted to the theory of stochastic approximation. Applications of Tierney's algorithm to network monitoring can be found in [START_REF] Chambers | Monitoring networked applications with incremental quantile estimation[END_REF]. A very limited number of studies have devised incremental quantile estimators including the Frugal estimator due to Ma et al. [START_REF] Ma | Frugal streaming for estimating quantiles[END_REF], the higher fidelity Frugal due to Yazidi et al [START_REF] Yazidi | A higher-fidelity frugal quantile estimator[END_REF] and the DUMIQE estimator due to Yazidi and Hammer [START_REF] Yazidi | Multiplicative update methods for incremental quantile estimation[END_REF].

In order to appreciate the qualities of our estimator, we will present the estimator scheme proposed by Tierney [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF]. Let X be a random variable. Let x(n) be a concrete realization of X at time 'n'. x(n) is drawn from the distribution of X, f X (x). The intention of the exercise is to estimate the q-th quantile, the number Q q such that F X (Q q ) = q. Tierney [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF] achieved this by maintaining a running estimate Q q (n) at time 'n'.

Q q (n + 1) = Q q (n) + d n n + 1 (q -I(x(n) ≤ Q q (n))) (1)
where d n = min( 1 fn(Qq)

, d 0 n a ). Here 0 < a < 1/2, d o > 0, and f n (Q q ) is an estimator of f (Q q ) defined in [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF]. The reason for invoking the min operation in the above expression of d(n) is the fact that the estimated density must be bounded to prevent the correction factor from "exploding". In other words, f n is current estimate of the density of X at the q-th quantile. This is usually done based on maintaining a histogram structure. However, requiring the incremental constructions of local approximations of the distribution function in the neighborhood of the quantiles increases the complexity of the algorithm. Our goal is to present an algorithm that does not involve any local approximations of the distribution function. Recently, a generalization of the Tierney's [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF] algorithm was proposed by [START_REF] Chen | Incremental quantile estimation for massive tracking[END_REF] where the authors proposed a batch update of the quantile, where the quantile is updated every M ≥ 1 observations. A body of research has been focused on quantile estimation from data streams without making any specific assumption on the distribution of the data samples. We shall first review some the related work on estimating quantiles from data streams. However, as we will explain later, these related works require some memory restrictions which renders our work to be radically distinct from them. In fact, our approach requires storing only one sample value in order to update the estimate. The most representative work for this type of "streaming" quantile estimator is due to the seminal work of Munro and Paterson [START_REF] Munro | Selection and sorting with limited storage[END_REF]. In [START_REF] Munro | Selection and sorting with limited storage[END_REF], Munro and Paterson described a p-pass algorithm for selection using O(n 1/(2p) ) space for any p ≥ 2. Cormode and Muthukrishnan [START_REF] Cormode | An improved data stream summary: the countmin sketch and its applications[END_REF] proposed a more space-efficient data structure, called the Count-Min sketch, which is inspired by Bloom filters, where one estimates the quantiles of a stream as the quantiles of a random sample of the input. The key idea is to maintain a random sample of an appropriate size to estimate the quantile, where the premise is to select a subset of elements whose quantile approximates the true quantile. From this perspective, the latter body of research requires a certain amount of memory that increases as the required accuracy of the estimator increases [START_REF] Weide | Space-efficient on-line selection algorithms[END_REF]. Examples of these works are [START_REF] Arasu | Approximate counts and quantiles over sliding windows[END_REF][START_REF] Greenwald | Space-efficient online computation of quantile summaries[END_REF][START_REF] Munro | Selection and sorting with limited storage[END_REF][START_REF] Weide | Space-efficient on-line selection algorithms[END_REF].

In [START_REF] Chen | Incremental quantile estimation for massive tracking[END_REF], the authors proposed a modification of the stochastic approximation algorithm [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF] in order to allow an update similar to the well-known Exponentially Weighted Moving Averages form for updates. This modification is particularly helpful in the case of non-stationary environments in order to cope with non-stationary data. Thus, the quantile estimate is a weighted combination of the new data that has arrived and the previously-computed estimate. Indeed, a "weighted" update scheme is applied to to incrementally build local approximations of the distribution function in the neighborhood of the quantiles. In the experiments results that we report, we consider the cases when data are generated randomly from stationary and non-stationary distributions.

This paper introduces a novel discretized quantile estimator. While we have earlier solved the binomial estimation problem using disretized estimators [START_REF] Yazidi | A stochastic search on the line-based solution to discretized estimation[END_REF], this is the first solution to the quantile estimation.

We submit that the entire phenomenon of utilizing the concepts of disretization in quantile estimation is unexplored, and it is precisely here that we have our primary contributions.

Legacy SPL Solutions

To place our work in the right perspective, we briefly review the state of the art of the SPL problem, whose formulation and solution is central to our approach. The SPL problem, in its most elementary formulation, assumes that there is a Learning Mechanism (LM) whose task is to determine the optimal value of some variable (or parameter), x. We assume that there is an optimal choice for x -an unknown value, say x * ∈ [0, 1). The SPL involves inferring the value x * . Although the mechanism does not know the value of x * , it was assumed that it has responses from an intelligent "Environment" (synonymously, referred to as the "Oracle"), Ξ, that is capable of informing it whether any value of x is too small or too big. To render the problem both meaningful and distinct from its deterministic version, we would like to emphasize that the response from this Environment is assumed "faulty." Thus, Ξ may tell us to increase x when it should be decreased, and vice versa. However, to render the problem tangible, in [START_REF] Oommen | Stochastic searching on the line and its applications to parameter learning in nonlinear optimization[END_REF] the probability of receiving an intelligent response was assumed to be p > 0.5, in which case Ξ was said to be Informative. Note that the quantity "p" reflects on the "effectiveness" of the Environment. Thus, whenever the current x < x * , the Environment correctly suggests that we increase x with probability p. It simultaneously could have incorrectly recommended that we decrease x with probability (1 -p). The converse is true for x ≥ x * .

We can summarize the existing SPL-related literature as follows:

-Oommen [START_REF] Oommen | Stochastic searching on the line and its applications to parameter learning in nonlinear optimization[END_REF] pioneered the study of the SPL when he proposed and analyzed an algorithm that operates on a discretized search space1 while interacting with an informative Environment (i.e., p > 0.5). The search space was first sliced into N sub-intervals at the positions {0, 1 N , 2 N , . . . , N -1 N , 1}, where a larger value of N ultimately implied a more accurate convergence to x * . The algorithm then did a controlled random walk on this space by "obediently" following the Environment's advice in the discretized space. In spite of the Oracle's erroneous feedback, this discretized solution was proven to be -optimal.

-An novel alternate parallel strategy that combined LA and pruning was used in [START_REF] Oommen | Automata learning and intelligent tertiary searching for stochastic point location[END_REF] to solve the SPL. By utilizing the response from the environment, the authors of [START_REF] Oommen | Automata learning and intelligent tertiary searching for stochastic point location[END_REF] partitioned the interval of search into three disjoint subintervals, eliminating at least one of the subintervals from fur-ther search, and by recursively searching the remaining interval(s) until the search interval was at least as small as the required resolution2 . -In a subsequent work [START_REF] Oommen | Parameter learning from stochastic teachers and stochastic compulsive liars[END_REF], Oommen et al. introduced the Continuous Point Location with Adaptive d-ARY Search (CPL-AdS) which was a generalization of the work in [START_REF] Oommen | Automata learning and intelligent tertiary searching for stochastic point location[END_REF]. In CPL-AdS, the given search interval was subdivided into d partitions representing d disjoint subintervals, where d > 3.

In each interval, initially, the midpoint of the given interval was considered to be the estimate of the unknown x * . Each of the d partitions of the interval was independently explored using an -optimal two-action LA, where the two actions were those of selecting a point from the left or right half of the partition under consideration. Thereafter, the scheme proposed in [START_REF] Oommen | Parameter learning from stochastic teachers and stochastic compulsive liars[END_REF] eliminated at least one of the subintervals from being searched further, and recursively searched the remaining pruned contiguous interval until the search interval was at least as small as the required resolution of estimation. Again, this elimination process essentially utilized the -optimality property of the underlying LA and the monotonicity of the intervals to guarantee the convergence. By virtue of this property, at each epoch consisting of a certain number, N ∞ , of iterations, the algorithm could "(1 -)-confidently" discard regions of the search space. -The authors of [START_REF] Huang | A general cpl-ads methodology for fixing dynamic parameters in dual environments[END_REF] proposed a rather straightforward modification of the latter CPL-AdS so as to also track changes in x * . Indeed, to achieve the latter, the authors of [START_REF] Huang | A general cpl-ads methodology for fixing dynamic parameters in dual environments[END_REF] proposed to perform an additional parallel d-ARY search at each epoch on the original search interval. The limitation of this work is that the strategy proposed in [START_REF] Huang | A general cpl-ads methodology for fixing dynamic parameters in dual environments[END_REF] can only track x * under certain conditions relative to the frequency of change in x * and the length of an epoch. However, more importantly, the interesting facet of the solution presented in [START_REF] Oommen | Parameter learning from stochastic teachers and stochastic compulsive liars[END_REF] is that it converges with an arbitrarily high accuracy even if the Oracle is a stochastic compulsive liar who is attempting to stochastically deceive the LM. -Recently Yazidi et al. [START_REF] Yazidi | A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme[END_REF] proposed a hierarchical searching scheme for solving the SPL problem. The solution involves partitioning the line in a hierarchical tree-like manner, and of moving to relatively distant points, as characterized by those along the path of the tree. With regard to its advantages, this solution is an order of magnitude faster than the classical SPL solution [START_REF] Oommen | Stochastic searching on the line and its applications to parameter learning in nonlinear optimization[END_REF]. The marginal drawback, however, is that it works under the premise that p is a constant whose value is larger than the golden ratio conjugate.

Discretized Estimator

Let

Q i = a + i. (b-a)
N and suppose that we are estimating the quantile in interval [a, b], where a > 0. Note Q 0 = a and Q N = b. There is an implicit assumption that the true quantile lies in [a, b]. However, this is not a limitation of our scheme, the proof is valid for any bounded and probably non bounded function.

We suppose that the estimate at each time instant

Q(n) takes values from the N + 1 values Q i = a + i. (b-a)
N , where 0 ≤ i ≤ N . According to whether q is lager or smaller than 1/2, we will have two different estimation schemes.

-Case 1: q < 1 2 If Q(n) ≤ x(n) and rand() ≤ 1 2(1-q) Q(n + 1) ← M in( Q(n) + 1/N, b) (2)
Else

Q(n + 1) ← M ax( Q(n) -1/N, a) (3)
-Case 2: q > 1 2 If Q(n) > x(n) and rand() ≤ 1 2q Q(n + 1) ← M ax( Q(n) -1/N, a) (4)
Else

Q(n + 1) ← M in( Q(n) + 1/N, b) (5)
where M ax(., .) and M in(., .) denote the max and min operator of two real numbers while rand() is a is a random number generated in [0, 1]. Theorem 1. We would like to estimate the q-th quantile to be estimated, i.e, Q * = F X -1 (q). Applying the updating rules (2), ( 3), ( 4) and ( 5), we obtain:

lim n→∞ lim N →∞ E( Q(n)) = Q * .
The proof of the theorem is quite involved and has been omitted here for the sake of space limitation. The full proof can be found in [START_REF] Yazidi | Dicsretized qunatile estimation using the spl theory[END_REF].

Remarks: A few remarks regarding our method for updating the estimates are not out of place. Indeed:

-First of all, it is pertinent to mention that although the rationale for updating is similar to that of the SSL algorithm [START_REF] Oommen | Stochastic searching on the line and its applications to parameter learning in nonlinear optimization[END_REF], there are some fundamental differences. Unlike the latter, which explicitly assumes the existence of an "Oracle", in this case, our scheme simulates such an entity. -Secondly, at this juncture, we emphasize that unlike the work of [START_REF] Oommen | Stochastic searching on the line and its applications to parameter learning in nonlinear optimization[END_REF], the probability that the Oracle suggests the move in the correct direction, is not constant over the states of the estimator's state space. This is quite a significant difference, which basically reduces our model to a Markov Chain with state-dependent transition probabilities.

We compare our estimator to the the EWSA (Exponential weighted Stochastic Approximation) due to Chen et al. [START_REF] Chen | Incremental quantile estimation for massive tracking[END_REF], which is a direct extension of the Stochastic Approximation based quantile estimator proposed by Tierney [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF]. Note that both, our estimator and the EWSA are incremental estimators.

In this section, we compare both estimators for different distributions, under different resolution parameter and in stationary environments. The results are conclusive and demonstrate that the convergence of the algorithms conform to the theoretical results. We use different distributions namely:

-Uniform in [0, 1] -Normal N (0, 1) -Exponential distribution with mean 1 and variance 1 -Chi-square distribution with mean 1 and variance 2.

In all the experiments, we chose a to be -4 and b is fixed to 4. Note that whenever the resolution is N , the estimate is moving with either additive or subtractive step size equal to b-a N . A larger value of the resolution parameter N implies a small step size, while a low value of the resolution parameter N results in a smaller step size.

Initially, at time 0, the estimates for the Discretized Quantile Estimator (DQE) are set to Q N/2 , while for the EWSA the initial value of the estimate is (a + b)/2.

The reader should note that the aim of the paper is to demonstrate its salient properties as a novel quantile estimator that uses only finite memory.

Comparison in Stationary Environments for Different Distributions

In this set of experiments, we examine a stationary environment. We used different resolutions namely N = 30, N = 100 and N = 1000 and as previously mentioned [a, b] = [-4, 4]. Given that the step size is obtained by the formula b-a N , please note that the resulting step sizes of the resolutions N = 30, N = 100 and N = 1000 are 8/30, 8/100 and 8/1000, respectively.

While for the EWSA, we use three different typical values, namely λ = 0.01, λ = 0.05, λ = 0.1, which illustrates the overall properties of this estimator. In fact, a low value of λ permits slow updates of the estimates and is convenient for a stationary environment, while a high value of λ for dynamic environment as it allows faster updates of the estimates.

Figure 1 depicts the case of estimating the 80% quantile for the four different distributions: uniform, normal, exponential and Chi-square. We report the estimation error from an ensemble of 1000 experiments. We observe that our DQE approaches the true value for all the four distributions asymptotically over time. We observe that given a low resolution (N = 30), the error drops very fast but stabilizes on a value between 0.05 and 0.15. Using a higher resolution, the error drops slower, but asymptotically the error becomes much smaller compared to the low resolution alternative. A very intriguing characteristic of our estimator is that by choosing a sufficiently high resolution, we are able to estimate the quantile as precise as we want. This is not possible for traditional off line quantile estimators without using an infinite amount of memory. Comparing the results of EWSA and DQE, it seems that the performance of the EWSA is highly dependent of λ which can be hard to choose. E.g. for the normal distribution EWSA ends up with high errors for all the three values chosen for λ. In comparison the convergence properties of the DQE is far more consistent.

A very intriguing characteristic of our estimator, as the resolution increases, the estimation error diminishes (asymptotically). In fact, the limited memory of the estimator does not permit to achieve zero error, i.e, 100% accuracy. As noted in the theoretical results, the convergence will be centred around the smallest interval [Q z , Q z+1 ] containing the true quantile. Loosely speaking, a higher resolution increases the accuracy while a low resolution decreases the accuracy.

Figures 2, 3 and 4 depict the cases of estimating the 70%, 90%, 95% quantiles respectively for the same four different distributions. In the comparison of the results for the different values of N and for different values of λ for the EWSA scheme, the conclusions are as for the 80% quantile case described above.

Conclusion

In this paper, we have designed a novel incremental discretized quantile estimator based on the theory of stochastic search on the line. We emphasize that the estimator can be easily implemented and that it is much simpler than the state of the art incremental estimator proposed by Tierney [START_REF] Tierney | A space-efficient recursive procedure for estimating a quantile of an unknown distribution[END_REF] as it does not require estimation of the density at the quantile. We have also extended our estimator in order to handle data arriving in a batch mode.

There are different extensions that can be envisaged for future work:

-We worked in finite Markov chain domain, and suppose that the true quantile lies in the interval [a, b]. As a future work, we plan to extend the proof to infinite state Markov chain. -The existing algorithm for quantile estimation is designed for data elements that are added one by one. A possible extension is to generalize our algorithm to handle not only data insertions, but also dynamic data operations such as deletions and updates such as in [START_REF] Cao | Tracking quantiles of network data streams with dynamic operations[END_REF]. -An interesting research direction is to simultaneously estimate more than a single quantile value. To achieve this, our present scheme will have to be modified so as to guarantee the monotonicity property of the quantiles, i.e, maintaining multiple quantile estimates while simultaneously ensuring that the estimates do not violate the monotonicity property.

Some of the existing results about discretized automata are found in[START_REF] Agache | Generalized pursuit learning schemes: New families of continuous and discretized learning automata[END_REF][START_REF] Lanctôt | Discretized estimator learning automata[END_REF][START_REF] Oommen | Continuous and discretized pursuit learning schemes: various algorithms and their comparison[END_REF][START_REF] Oommen | Absorbing and ergodic discretized two-action learning automata[END_REF][START_REF] Oommen | The asymptotic optimality of discretized linear reward-inaction learning automata[END_REF][START_REF] Oommen | Discretized pursuit learning automata[END_REF][START_REF] Thathachar | Discretized reward-inaction learning automata[END_REF]. Indeed, the fastest reported LAs are the discretized pursuit, and discretized maximum likelihood and Bayesian estimator algorithms[START_REF] Agache | Generalized pursuit learning schemes: New families of continuous and discretized learning automata[END_REF][START_REF] Oommen | Continuous and discretized pursuit learning schemes: various algorithms and their comparison[END_REF][START_REF] Oommen | Discretized pursuit learning automata[END_REF].

The logic behind this is explained in the next item, when the authors generalized this scenario for the case when the number of partitions was d >


Liyun Gong
email: lgong@lincoln.ac.uk

Miao Yu

Wenting Duan
email: wduan@lincoln.ac.uk

Xujiong Ye

Kjartan Gudmundsson
email: kgudmundsson@lincoln.ac.uk

Mark Swainson
email: mswainson@lincoln.ac.uk

A novel camera based approach for automatic expiry date detection and recognition on food packages

Keywords: fully convolutional network, stroke width transform, Maximally stable extremal regions, tesseract OCR

There is abundant of information on food packages, which include the food name, the expiry date and the ingredients. These information, especially the expiry date needs to be coded correctly before the products can be released into the market/supply chains. Failure of printing the correct expiry date can lead to both the health issues to the public and financial issues for recalling product back and even reimbursement. In this paper, we develop an automatic system that can achieve the expiry date region detection and recognition in an efficient and effective way. A deep neural network (DNN) based approach is firstly applied to find the expiry date region on the food package. The date characters are then extracted and recognized through the image processing and machine learning methods from the expiry date region. The system is the first camera based automatic system for recognizing expiry date on food packages. And the results tested on different types of food packages show that the system can achieve good performance on both detection and recognition of the expiry date.

Introduction

In the European Union food production is the largest manufacturing sector where it accounts for 13.3% of the total EU-28 manufacturing sector with a reported turnover of 945 billion [1]. Whilst food availability is a primary concern in developing nations and food quality (value) is a focal point in more affluent societies, food safety is a requirement that is common across all food supply chains. Food safety in the sector is typically underpinned by food science and technology and assured by a combination of operational control systems and procedures including Good Manufacturing Practice (GMP) and Hazard Analysis Critical Control Point (HACCP) [2].

The food product information printed on the food package is a vital for the food safety. Prepackaged food product information which are incorrectly labelled, especially the expiry date results in product recalls as the fault/issue could cause a food safety incident such as food poisoning due to the consumption of product which is past its actual safe Use-by date. These recalls are usually at very high financial and reputational cost to food manufacturers. The reasons/root causes for issues or mistakes resulting in label faults on food packaging are many and varied. They include human error and equipment faults. For example, a label printer on a production line can break down and the line carries on running. The faulty packaging therefore needs to be identified and the production line stopped. A common current process line Use-by check approach is to use a human operator to read and verify the packaging label. This check is conducted by either manually picking a pack from the line for inspection or verifying it through an image captured of the pack. However, these methods create mundane and repetitive tasks and therefore place the operator in an errorprone working environment.

Another common approach to control date codes is to use Optical Character Verification (OCV). This involves a supervisory system holding the correct expiry date string and transferring it to both the printer and the vision system. The latter will then verify its read and actions are taken depending on the result. However, OCV systems rely on consistency in expiry date format, packaging and camera view angle. This consistency tends to be hard to achieve in the food and drink manufacturing environment and therefore there is a great need for a more robust solution.

In this work, we have developed an automatic system based on a camera, which can efficiently and effectively recognize the expiry date information printed on different types of food packages. Food packages with wrong expiry date printed on will be picked up. This system will enable far greater control over the accuracy and legibility of critical 'Useby'/'Best Before' dates and also key traceability information in food and drink manufacturing operations, resulting in significantly increased food safety and compliance with related legislation.

To develop such a system, the first step is to identify expiry date regions as the region of interest (ROI) on a recorded food package image. And the expiry date recognition task is then performed within the ROI instead of the whole image. In this way, the computational costs can be saved to a large extent. One straightforward method to determine ROI is applying the text detection method for detecting text regions as ROI on a food package. For text detection, a number of traditional image processing based techniques have been applied, examples include Stroke Width Transform (SWT) based approach [START_REF] Epshtein | Detecting text in natural scenes with stroke width transform[END_REF] and Maximally Stable Extremal Regions (MSER) based approach [START_REF] Chen | Robust text detection in natural images with edge-enhanced Maximally Stable Extremal Regions[END_REF]. With the deep learning techniques having become mainstream in the image processing, computer vision and machine learning communities, different types of deep neural networks have been applied

for the text detection ( [START_REF] Zhou | EAST: An Efficient and Accurate Scene Text Detector[END_REF][START_REF] Zhang | Symmetry-based text line detection in natural scenes[END_REF]) with better results being obtained.

However, if the food package contains too much other text information in addition to the expiry date (that is the usual situation on the food package), the obtained ROI will still be tremendous. Instead of the text region detection for the ROI identification, in our work we apply a deep neural network approach for directly identifying the expiry date region as ROI.

The fully convolutional network (FCN) in [START_REF] Zhou | EAST: An Efficient and Accurate Scene Text Detector[END_REF], which is originally developed for text detection, is fine-tuned by our dateset for expiry date region detection. By adopting such an approach, only the expiry date region can be extracted while other texts on the food package are excluded. The most precise ROI is directly obtained and computational costs can then be further reduced by performing the recognition on only the ROI of the expiry date region.

Based on the extracted ROI, the date characters blobs in the ROI can be directly extracted. Related shape features are then extracted for classification by an efficient nearest neighbour method. In our experiment, we have tested our system for both expiry date region detection and classification on different types of food packages in different captured image formats (colour/grayscale), with good results being obtained.

Method

In this section, we present the methodology for expiry date recognition on the food package, which is divided into two parts: expiry region identification and recognition. The block diagram of the proposed methodology is shown in Fig. 1. Details of every block are presented as follows.

Fig. 1. The block diagram of the proposed system.

Date code region identification

For effectively identifying the expiry date region on the food package which contains different types of pictures/texts contents with different colours, a deep neural network based approach is applied. The deep neural network structure is a fully convolutional network (FCN) as described in [START_REF] Zhou | EAST: An Efficient and Accurate Scene Text Detector[END_REF], which was originally developed for detecting texts. The network is fine-tuned on our food package dataset for detecting the date expiry region. The FCN structure is shown in Fig. 2, which is decomposed into three parts: feature extractor stem, feature-merging branch and output layer. The stem part is a PVANet [START_REF] Kim | PVANET: Deep but lightweight neural networks for realtime object detection[END_REF], with interleaving convolution and pooling layers. Four levels of feature maps, denoted as fi are extracted from the original (1

)
where gi is the merge based as in [START_REF] Zhou | EAST: An Efficient and Accurate Scene Text Detector[END_REF] and hi is the merged feature map. And the operator [;]. represents concatenation along the channel axis. In each merging stage, the feature map from the last stage is first fed to an unpooling layer to double its size, and then concatenated with the current feature map. A conv1×1 bottleneck cuts down the number of channels to reduce computation, followed by a conv3×3 that fuses the information to finally produce the output of this merging stage. Following the last merging stage, a conv3×3 layer produces the final feature map of the merging branch and feed it to the output layer.

The final output layer contains several conv1×1 operations to project 32 channels of feature maps into 1 channel of score map Fs, which gives the likelihood that a pixel belong to the expiry date region as well as a multi-channel geometry map Fg, which could be either rotated box (RBOX) or quadrangle (QUAD) representing different geometries. RBOX geometry map contains a 4-channel map representing 4 distances from every pixel location to the top, right, bottom, left boundaries of a rectangle enclosing the candidate expiry date region, as well as a 1-channel map representing the angle of the related rectangle. QUAD geometry map is a 8-channel map, which contains the coordinate shift from four corner vertices of a quadrangle (representing candidate expiry date region) to every pixel position.

FCN training and testing

For obtaining the network parameters, firstly, a loss function is defined as:

L = Ls + λLg (2)
where Ls and Lg represent losses for score and geometry maps respectively, while λ is a balancing parameter.

The term Ls is defined as:

Ls = -βY * logYˆ -(1 -β)(1 -Y * )log(1 -Yˆ) (3)
where Yˆ and Y * represent the predicted and groundtruth score maps respectively. β is a balancing parameter. While the Lg is defined as scale-invariant IoU loss for RBOX geometry map and scale-normalized smoothed-L1 for the QUAD one as [START_REF] Zhou | EAST: An Efficient and Accurate Scene Text Detector[END_REF]. Based on the defined loss function, the network is trained end-to-end using ADAM optimizer until performance stops improving.

To determine the final expiry date region, first a threshold is set to find positions at which score map values are larger than it. The geometries associated with those positions on the geometry map will then be merged by the localityaware Non-Maximum Suppression (NMS) to determine the final expiry date region, which can achieve lower computational costs compared with the basic NMS algorithm. Under the assumption that the geometries from nearby pixels tend to be highly correlated, the locality-aware NMS is proposed to merge the geometries row by row. And while merging geometries in the same row, the geometry currently encountered will be merged with the last merged one. In this way, the computational costs could be reduced from O(n2) of the original NMS to O(n), where n is the number of candidate geometries. Fig. 3 shows the results of different parts the expiry date region detection procedure.

Expiry date recognition

Expiry date will then be recognized based on the identified region by Tesseract OCR [START_REF]Tesseract-ocr[END_REF].

The Maximally Stable Extrernal Regions (MSER) algorithm will firstly be applied, to make a binarization of the extracted date code region with characters being differentiated from the background (Fig. 4 (b)). Component connected analysis [START_REF] Gonzalez | Digital image processing[END_REF] is then made to find blobs representing different characters, with small noisy blobs being filtered out (Fig. 4 (c)).

As in [START_REF] Smith | An Overview of the Tesseract OCR Engine[END_REF], for each candidate blob, the boundary will be extracted as in Fig. shape features, such as topological and polynomial approximation can be extracted for characters classification. In this work, a simple but effective nearest neighbour (NN) approach is applied for the classification. The features of every blob will be compared with prototypes representing different characters. A blob will be classified as the character for which the related distance is the smallest.

Experimental results

The proposed system is trained and tested on different types of food packages, with representative examples being shown in Fig. 5. We have collected 800 images from stores, among which 70% (560 images) are used for training and 30% (240 images) are used for testing.

Expiry date region detection evaluation

The FCN as mentioned in the previous section is fine tuned for identifying the expiry date region on the food package. We have manually masked the ground truth expiry date regions in the training dataset for tuning the FCN, to transfer it from a text detection network to a date code region detection one. We train the network in the GPU-supported tensorflow environment, with two PASCAL GPUs. The input image patches are resized to 512×512. applied with the batch size is 14 per GPU and the learning rate is set to be 0.0001 in the ADAM optimizer. Fig. 6 shows the comparison results between FCN before and after fine tuning. We can see that after fine-tuning, the original text detection network transfers from a text detection network to a expiry date detection one. The transferred network is tested on captured images of different food packages, with both colour and grayscale formats. Related results are presented in Fig. 7, we can see that the date code regions on different food packages can be successfully identified. For a qualitative analysis, we test the developed FCN on the aforementioned testing dataset containing 240 images. The testing results show that 236 out of 240 images, the date region is correctly identified with 4 out of 240 are missing. A total detection rate of 98 % is obtained.

Expiry date recognition evaluation

Based on the detected expiry date region, the characters within it are extracted and classified. We have applied the Tesseract OCR [START_REF]Tesseract-ocr[END_REF] for classification, which has implemented the characters extraction, feature extraction and classification steps as mentioned in the section 2.2. Some initial results are presented that in Fig. 8. It is shown that the characters on the extracted expiry date region can be successfully recognized; however, some classification mistakes may happen when characters are blurred.

Conclusions

In this work, we have developed a novel food package expiry date recognition system based on the camera. A FCN deep neural network approach is applied to detect the expiry date region. Based on the detection results, the date character blobs will be extracted. Related features will be extracted and classified to particular characters. Such a system will potentially advance the assurance of food quality and safety. The experimental results show that the proposed method can achieve very good performance in identifying the expiry date region and classifying characters correctly when they are clear. However, if the characters are blurred, misclassifications can be made and that will be the future researches which will be investigated.

Fig. 2 .

 2 Fig.2. The FCN structure for the expiry date identification.

Fig. 3 .

 3 Fig.3. The expiry date region detection procedure. (a) Original image (b) Score map output by the FCN (c) Candidate expiry date region results before NMS (d) Expiry date region results after NMS (e) Expiry date patch output

Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .Fig. 8 .

 45678 Fig.4. Extracted expiry date region and related processing. (a) Original date code region (b) Binarization for differentiating character regions from the background (c) Character blobs extraction (d) boundary extraction


Rejab Hajlaoui
email: rejab.hajlaoui@femto-st.fr

Tarek Moulahi
email: tarek.moulahi@femto-st.fr

Hervé Guyennet
email: herve.guyennet@femto-st.fr

A Scatter Search Based Heuristic for Reliable Clustering in Vehicular Ad Hoc Networks

Keywords: Vehicular ad hoc network, communication, heuristic algorithm. 1

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

Introduction

VANET is an extension of the Mobile Ad hoc NETwork (MANET), where the node movements are restricted by the topology of the street, traffic signals and obstacles [START_REF] Hajlaoui | A Survey on Heuristic-Based Routing Methods in Vehicular Ad-Hoc Network: Technical Challenges and Future Trends[END_REF]. The purpose of the Intelligent Transportation System (ITS) is to collect and to share information in order to improve the road safety and to provide comfort to travelers. Despite the fact that vehicles have high computing power and adequate storage capacity, the problem of delay and poor connectivity persists. On the other hand, due to the high mobility in highway scenario and the multitude of obstacles in the urban environments, the links can be broken frequently. In this case network maintenance has to be triggered automatically to ensure stability and to send messages within the deadlines. Under these constraints, keeping a high stability of network is an NP-Complete combinatorial optimization problem. It means that all exact algorithms require exponential execution time to resolve it. Thus, they are unsuitable in practice even for moderately large instances [START_REF] Aadil | CACONET: Ant Colony Optimization (ACO) Based Clustering Algorithm for VANET[END_REF].

For these reasons, several heuristic based researches have been developed to find efficient and adaptable models for routing problems in high mobility networks. Although obtaining an optimal solution is not guaranteed, the use of heuristic methods gives competitive advantages, the most important of which are:

 Approximate the best solutions for the biggest instances.  Define the right solutions within a reasonable calculation time. Indeed, among the ways to improve the performance of an algorithm or to fill some of these gaps is to combine it with another method. This cooperation between approaches makes it possible to exploit their advantages in order to improve the overall performance and to minimize the convergence time. It is obvious that population-based methods are superior in identifying different areas in the search space, while trajectory methods are better in exploring a well-defined area in the search space [START_REF] Eg | A Taxonomy of Hybrid Metaheuristics[END_REF]. In this context, we proposed a Hybrid Scatter Tabu Search model to improve the assignment of ordinary nodes to elected cluster heads. Indeed, the power of this contribution is to unify the advantage of population-based methods with the power of trajectory methods. In this way, there is less chance of missing a good solution compared to population-based methods. In this work, we treated the nodes that exist in common area as shown in "Fig. 1". These nodes are covered by several CH and their assignments is a challenge in itself. Several simulations are conducted to understand and to analyze the performance of our model by comparing it against competitive protocols designed for the same objective.

The remaining of this paper is organized as follows. In Section 2, we presented some existing solutions. Section 3 and 4 describe our proposal including the theoretical foundation. Section 5 discusses the simulation results. Finally, section 6 concludes the paper and draws some directions for future work.

Prior works

Due to the unbounded network size and the dynamic nature of vehicles, the intermittent connectivity is considered as the biggest challenge. Indeed, many researchers used the clustering technique to satisfy the VANET stability and to improve the network life time. For instance, in [START_REF] Shou-Chih | A Multi-Head Clustering Algorithm in Vehicular Ad Hoc Networks[END_REF], authors proposed a multi-head clustering algorithm considering a data sharing application in vehicular network. Each cluster contains a master CH (MCH), and several slave CHs (SCHs). The main goal of using more than one CH is to speed up the data downloading from multiple seed nodes (CHs) based on the bit-torrent downloading mechanism.

Common area

In the same context, Little et al. [START_REF] Little | An information propagation scheme for VANETs[END_REF] used two CHs to extend the MOBIC (MOBIlity metrics Clustering) [START_REF] Basu | Little: A mobility based metric for clustering in mobile ad hoc networks[END_REF] into vehicular environments. The first CH is located at the head and the second is in the tail of a cluster. In [START_REF] Malathi | An Efficient Clustering Algorithm for Vanet[END_REF], authors introduced a new clustering technique which uses velocity and distance to create a stable cluster structure. When more nodes converge to be cluster head, the Cuckoo Search algorithm [START_REF] Xs | Cuckoo search via Le´vy flights[END_REF] is triggered to select the super cluster-head which will be at an optimum distance, minimum delay, more network lifetime and high packet delivery ratio. In [START_REF] Nasr | VANET Clustering Based Routing Protocol Suitable for Deserts[END_REF], M. Nasr et al. presented a novel VANET routing algorithm based on clustering technique (CBVRP). This protocol is appropriate for rugged environments, such as deserts scenarios. Indeed, the CBVRP used the vehicle's equipment, velocity and location in the cluster classifications and the CH election process. When the communication is inside a cluster, the CH selected the relay node which leads to the destination. In contrast, when the communication is between clusters, the CH uses the flooding mechanism towards its cluster members in order to find the nearest vehicles able to communicate with the outside. This route is kept until the cluster structure changes. In [START_REF] Hassanabadi | Clustering in vehicular ad hoc networks using affinity propagation[END_REF], Hassanabadi et al. presented a novel model called "Affinity PROpagation for VEhicular networks" (APROVE). It uses the Affinity Propagation algorithm in a distributed manner to maximize the similarity s(i,j) between the data point i and its chosen exemplar j. In this algorithm, nodes exchanged two types of messages to make decision on independent clustering:  Responsibility message r(i,j): sent from i to candidate exemplar j. It indicates how well suited j is to be i's exemplar.  Availability message a(i,j): sent from candidate exemplar j back to i. It indicates j's desire to be an exemplar for i based on supporting feedback from other data points. In [START_REF] Shea | Mobility-based clustering in VANETs using affinity propagation[END_REF], authors developed a new distributed algorithm to build a stable multi-hop cluster suitable for vehicular networks. With minimum number of cluster head, this model contains three techniques that depend only on the positions of both receiver and transmitter nodes. When the GPS signal is lost, the proposed algorithms switched to use the RSS (Received Signal Strength) of the packet received to decide if the packet should be retransmitted. Given the continuing research in this area, several clustering solutions, including mobility-based clustering, cluster-based MAC protocols, topology-based clustering, weight-based clustering and energy-based clustering, have been proposed [START_REF] Shea | Mobility-based clustering in VANETs using affinity propagation[END_REF], [START_REF] Mammu | Cluster based MAC in VANETs for safety applications[END_REF], [START_REF] Moniruzzaman | Analysis of Topology Based Routing Protocols for Vehicular Ad-Hoc Network (VANET)[END_REF].

3.

Theoretical foundation of the proposed model

Weighted k-medoids clustering approach (WKCA)

The WKCA is a novel clustering algorithm proposed recently [START_REF] Hajlaoui | A Weighted k-Medoids Clustering algorithm for effective stability in Vehicular Ad Hoc Networks[END_REF]. This model based on the k-medoids clustering approach provides an automatic switching from small to large cluster depending on the road conditions. It generates small clusters in dense zone in order to avoid the network congestion, whereas in sparse zone it generates large clusters to ensure large coverage.

A node becomes a cluster head if it has the highest weight based on a several metrics (direction, transmission range, speed and node disconnection frequency). Periodically, each node calculates and sends its weight to the CH. Then, the node having a weight greater than that of the current CH will be announced as the new coordinator. Consequently, the cluster maintenance phase will be triggered immediately. Finally, if a node leaves the coverage area of its CH, it has to join another one. Otherwise, it announces itself as a new cluster head to start its own cluster formation. Indeed, two main phases distinguish this model.

Phase 1 : cluster formation

A vehicle V is assigned to cluster C according to its similarity value (SV).

Where

( ) ( ) ( ) (1)
 D : Boolean variable. It indicates the direction of the node compared to the CH.  ΔS : difference in speed (compared to the CH).  ΔP : proximity to CH. In which w 1 , w 2 and w 3 reflect the relative importance of D, ΔS and ΔP.

Phase 2 : cluster head switching

A vehicle V is elected as a new CH if its weight (W) is greater than the weight of the current CH, provided that its behavior in the past was not wobbling or suspicious. Indeed, the weight (W) is calculated based on four metrics (direction, transmission range, speed and node disconnection frequency).

Scatter Serach (SS)

The Scatter Search is a population-based metaheuristics. It is suitable to solve a wide range of optimization problems including Routing Protocol, Traveling Salesman Problem (TSP), and clustering [START_REF] Scheuerer | A scatter search heuristic for the capacitated clustering problem[END_REF], [START_REF] Yamashita | Scatter search for project scheduling with resource availability cost[END_REF]. Recent studies demonstrate the practical advantages of this approach compared to similar heuristics. The most important is that the SS used an adaptive and an associated memory to be adapted to particular contexts [17][18]. Basically, the SS starts with a set of feasible solutions. At the next step, some of these solutions are extracted and combined. The resulted offspring solutions will be enhanced according to an improving procedure. By the end, these new feasible solutions are evaluated according to some criteria to be included or not in the collections. These steps are presented in the Basic Scatter Search Algorithm below [START_REF] Laguna | Scatter Search: Methodology, Implementations[END_REF].

Basic Scatter Search Algorithm

Input: population of the problem.

Output: the best of solutions.

(1) Initialize the population Pop using a Diversification Generation Method. (2) Apply the Improvement Method to the population.

(3) Reference Set Update Method (Good solutions for RefSet1 and Diversity solutions for RefSet2). ( 4) While (itr < MaxItr) do [START_REF] Little | An information propagation scheme for VANETs[END_REF] While (Reference set is changed) do [START_REF] Basu | Little: A mobility based metric for clustering in mobile ad hoc networks[END_REF] Subset Generation Method [START_REF] Malathi | An Efficient Clustering Algorithm for Vanet[END_REF] While (subset-counter < > 0) do [START_REF] Xs | Cuckoo search via Le´vy flights[END_REF] Solution Combination Method. [START_REF] Nasr | VANET Clustering Based Routing Protocol Suitable for Deserts[END_REF] Improvement Method. [START_REF] Hassanabadi | Clustering in vehicular ad hoc networks using affinity propagation[END_REF] Reference Set Update Method; [START_REF] Shea | Mobility-based clustering in VANETs using affinity propagation[END_REF] End while [START_REF] Mammu | Cluster based MAC in VANETs for safety applications[END_REF] End while [START_REF] Moniruzzaman | Analysis of Topology Based Routing Protocols for Vehicular Ad-Hoc Network (VANET)[END_REF] End while [START_REF] Hajlaoui | A Weighted k-Medoids Clustering algorithm for effective stability in Vehicular Ad Hoc Networks[END_REF] Return the best of solutions

Tabu Search (TS)

Proposed by Glover in 1986, the tabu search is a local search heuristic used to solve complex and large problems. It is an iterative approach starting with an initial feasible solution. Then, from a given position the procedure moves step by step to explore the neighborhood and to select the one that minimizes the objective function. At each iteration, the algorithm chooses the best neighbor not tabu, even if it degrades the cost function. For this reason, the tabu research is known as an aggressive method. The process continues until stopping criteria is met. Unlike other methods, the TS overcomes the problem of local optima using adaptive memory. The basic idea is to save the solutions that are temporarily forbidden to avoid cyclic movements [START_REF] Glover | Tabu Search[END_REF].

Proposed model

The proposed solution that we have developed is based on the clustering technique.

The main challenge is to find the most appropriate cluster for all node in the common area. Indeed, at an instant "t", a vehicle V has to be assigned only to one cluster head. In this work, each cluster is described as a graph G(V, E), as shown in "Fig. 2".  V: represents the set of vehicles defined by an index i, i ϵ {1, 2, 3, …, N}.  C: represents the set of cluster heads defined by an index j, j ϵ {1, 2, 3, ., M}.  E: represents the set of edges. Each edge Eij designs the similarity value (SV) of the node i to the cluster head j. The goal is to maximize the similarity within clusters. It is calculated by the summation of the costs of all edges. In our case, for all pairs of nodes {i,j}, the cost's SVji and SVij are equal, then the problem is said to be symmetric.

Reference set generation

This method is the first step in the SS process. Indeed, the set of starting solutions are not randomly generated, but obtained from the WKCA model detailed in section 3.a.

Evaluation

To know the quality of any potential solution, we used the fitness function (F). It indicates how similar the nodes of a cluster are compared to their cluster head.

∑ ∑ ( )

Subset generation

Several methods are used in the literature to generate the subsets. In our solution, we treated the nodes that can be assigned to more than one cluster as shown in "Fig. 2".

 Let B1 the best solution obtained by the WKCA algorithm.

Combination method

This method is used to combine the elements of the subsets in order to form new solutions. In our case, we used the Path-Relinking combination method (PR) [START_REF] Glover | Fundamentals of scatter search and path relinking[END_REF] to generate new trial solutions. By applying the PR method, each node in the common area is evaluated comparing to all reachable cluster heads. Then the best assignment with high similarity value is selected. To maintain a fair distribution, the density of the two clusters has to be very close and the difference should not exceed a given value "µ". In other words, we avoid having dense clusters compared to other one, resulting in poor bandwidth exploitation and frequent collisions.

For instance, based on the similarity values of border nodes as shown in "Fig. 3", it is more suitable to assign node 4 to cluster C2 instead of cluster C1. Likewise, it is better to move the node D from cluster C2 to cluster C1.

Fig. 3. Similarity values of border nodes

After applying the PR combination method to all nodes, we get C1* and C2* from C1 and C2, as shown in "Fig. 4".

Improvement method

In this step, we used the tabu search to transform the solutions obtained by the combination method into more efficient solutions. In our implementation, the TS treated the border nodes. If the improved solution increases the global similarity within the cluster, then it will be included in the reference set, otherwise, it will be ignored. To avoid the loss of time in case of large number of neighborhood, the selected number of iterations does not exceed 10. Indeed, the "Fig. 5" resumes the steps of the proposed Scatter Tabu Search model as well as the methods associated with it (Path Relinking, WKCA, TS, SV).

Experimental results and analysis

Simulation setup

To evaluate the performance of our algorithm, simulations have been carried out using NS3 [21]. We have set experimentations in highway scenario by varying the density from 40 to 240 vehicles per km and the speed from 20 to 120 kmph. The table below provides the used simulation parameters. Data Type Constant Bit Rate (CBR).

Simulation Results

In order to evaluate the improvement given by the Hybrid Scatter Tabu Search in vehicular networks (HSTS), we have performed a careful analysis according to several metrics [START_REF] Agrawal | Multipath routing in mobile Ad-hoc network using meta-heuristic approach[END_REF]. Our contribution is compared with the basic Weighted Kmedoid Clustering Algorithm (WKCA). Indeed, as we have explained before, the output of the WKCA is used as the initial Reference Set of the Scatter Search. This comparison will show us if the additional work that we have added will improve the results obtained, especially in terms of delay.

a. Packet delivery ratio (PDR): is defined as the ratio of packets successfully delivered to the destination compared to the number of packets sent out by the source

∑ ∑ (3)
Fig. 6. Density VS PDR As observed in "Fig. 6", the HSTS outperforms the WKCA in term of PDR for different densities. The reason behind this superiority is that the obtained clusters are highly similar. Therefore, there is less chance of route failure and the data reaches the destination without any shortage. Indeed, for both models, the high density will create a flood of data to find the appropriate route from source to destination. This broadcast storm will lead to congestion and some packets will be dropped by the master node.

For instance, the abandoned packets by the WKCA reached 35% in dense zone. Whereas, the HSTS maintains its performance regardless of the network status and the average of dropped packet does not exceed 22%. Therefore, about 80% of packets reach the destination even in bad traffic condition. "Fig. 7" presents a comparison between the HSTS and the WKCA protocols in term of E2ED. The result shows that our enhanced model provides less time amount of propagation delay whether for high or low density. Indeed, when the similarity of nodes within clusters is not optimized, the linking path between the source and the destination will contain more relays. This excess number of nodes causes more delay with high bandwidth usage. For example, with low density (40), when the speed reaches 120 kmph, the delay decreases significantly to reach 20 ms for all approaches. However, when the speed decreases and the density becomes the main challenge (240), the delay in the WKCA increases dramatically to reach 67 ms. While the HSTS maintains a high performance and the delay does not exceed 42 ms in the worst case.

∑ ( )

"Fig. 8" compares the impact of the density on the throughput for all schemes. Indeed, the WKCA protocol has the lowest throughputs especially in dense situation due to the inability of the available bandwidth to cope with the large volume of control packets. To deal with this challenge of density, the HSTS formed clusters with high similarity. This procedure will create direct paths with minimum number of relays. Therefore, the throughput has been improved with the scatter search. Mostly, the traffic crowding is a nonlinear function. Thus, any reduction in traffic stream reduces the collisions and allows a significant rise in throughput. With the best road condition, the situation changes rapidly and the rate of successful delivered messages over a communication channel increases gradually. For instance, by reducing the density from 120 to 80 vehicles, the throughput of both HSTS and WKCA is improved by respectively 10% and 7%.

6.

Conclusion

Due to the diversity of routing environments (residential, urban, highway,…) and the high mobility of vehicles, constructing stable networks seems to be the basic challenge. To tackle this problem, we improved the weighted k-medoid clustering algorithm (WKCA) proposed recently. We used a hybrid scatter tabu search to maximize the intra-cluster similarities. We treated the overlapping clustering where a node can simultaneously belong to more than one cluster. As shown in section 5, the proposed model (HSTS) outperforms the basic WKCA in term of PDR, E2ED and throughput in all situations. Finally, we can conclude that the greater the similarity within a cluster, the better the network stability. As a future work, we plan to improve

Fig. 1 .

 1 Fig. 1. Overlapping clusters.

Fig. 2 .

 2 Fig. 2. Clusters representation



  Let B2 the feasible solution very different from the solution B1. (B2 is obtained by switching the nodes of cluster 1 of common area to the cluster 2 and vice versa). Set diff: the difference between the two solutions. It represents the average of nodes switched from C1 to C2, and vice versa. Diff= number of permuted nodes / total number of nodes = 6/16 = 38%

Fig. 4 .Fig. 5 .

 45 Fig. 4. Solutions generated by Combination method



  b. End-to-end Delay: is defined as the needed time to send packet from source to destination. PRT: Packet Reception Time.  PTT: Packet Transmission Time.  RP: Received Packet.

  Fig. 7. Density VS E2ED

Fig. 8 .

 8 Fig. 8. Density VS Throughput

Table 1 .

 1 Simulation setup.

	Parameters	Values
	Simulator	NS3
	Scenario	Highway.
	Nb of lanes	Two-lanes.
	Number of vehicles	40 .. 240.
	Speed	20-120 Kmph.
	Vehicle distribution Randomly
	Transmission range	200m, 300m and 500 m.
	Simulation Time	1500 s.
	MAC Protocol	DSRC.

the behavior of our model based on the Cuckoo Search heuristic especially in urban scenario with the existence of intersections and obstacles.