Ronnie Cheung
email: ccheung@acm.org

Hassan B Kazemian
email: h.kazemian@londonmet.ac.uk

Adaptive Service Composition for Meta-Searching in a Mobile Environment

Keywords: meta-searching, adaptive service composition, mobile computing 1

The underlying technologies driving the World Wide Web are largely based on the assumption of wired communications and powerful desktop hardware. This is not true when a user is accessing the Web pages and documents using a PDA and moving from wireless network in a mall to a neighboring office environment. Taking into consideration on the information needs of the user, we have developed a meta-search application that can be executed on mobile devices with limited hardware capabilities. By running in the auto-configuration mode, the system detects the dynamic contextual information, and presents the results of meta-searching in a suitable format to cope with the limitations of the mobile stations. This is achieved by an adaptive service composition that is defined according to the adaptation model defined in a system configuration file.

Introduction

With the rapid development of the World Wide Web, many search engines are developed to facilitate information retrieval and filtering [START_REF] Belkin | Information Filtering and Information Retrieval: Two Sides of the Same Coin?[END_REF]. A meta-search engine is a kind of search engine that do not maintain its own databases, but search those of other engines [START_REF] Zhao | A Meta-search Method with Clustering and Term Correlation[END_REF]. Metacrawler, for instance, searches the databases of: Lycos, WebCrawler, Excite, Altavista, and Yahoo. It queries the other search engines, organizes the results in a uniform format, ranks them by relevance, and returns them to the user. In this paper, we describe the development of a meta-search engine that provides flexible and adaptive Web meta-searching service in a mobile environment. Compare with the fixed and wired network, the wireless mobile environment has smaller bandwidth, higher latency and higher error rates. A meta-search engine for mobile devices facilitates efficient web access by consolidating the search results from different search engines, and formats the results according to the requirements of mobile devices. A major issue is that many of the mobile devices have limited capabilities. For example, the size of screen, available memory and the depth of color are usually deficient. Conventional meta-search engines return the search results by using a single presentation format. In order to reduce the cost and increase the efficiency, and to provide a desirable Web meta-searching experience for the mobile users, a Web meta-searching system for adaptive mobile environment is developed in this project.

The WebPADS system is employed as the underlying Web proxy framework to facilitate the adaptation requirements. Unlike other agent-based Web proxy systems, the WebPADS system offers a more flexible and adaptive platform for developing the meta-searching services. The details of the WebPADS platform are described in Section 2 of this paper. In the system, the client station acquires the contextual information by a service program running in the mobile node. The embedded service program then sends the updated information to the server periodically. Based on the dynamic contextual information of the mobile clients, the meta-search proxy server composes the service chains according to the dynamic requirements for adaptive service composition for meta-searching in a mobile environment. The client application is a user-friendly graphical user interface that is developed by Java technology. Users can interact with the system by submitting their specific requirements with a few steps. Most of the complicated tasks are processed in the proxy server. In the auto configuration mode, the users are only required to submit the keyword for the queries. The system can improve the efficiency and readability of the meta-searching, and the cost of meta-searching in mobile devices are decreased by minimizing the amount of data to be downloaded.

The major contribution of this paper is the abstraction of the dynamic service composition process using the WebPADS architecture. The integration of service composition is demonstrated using a meta-search engine application as an example. The proposed framework supports a self-organizing approach that allows a user to specify the desired adaptation and quality-of-service (QoS) requirements through adaptation rules. These QoS characteristics are broken down into requirements for individual services in the rule base using a novel approach for active service composition [START_REF] Binder | Towards Self-Organizing Service-Oriented Architectures[END_REF].

2

The WebPADS Platform

To provide and facilitate an effective Web meta-searching experience for mobile environments, the WebPADS system (Web Proxy for Actively Deployable Service) has been employed as the underlying Web proxy framework for development.

WebPADS is a object-oriented system based on the active service deployment architecture, dynamic service composition framework. Active service deployment and dynamic reconfiguration of mobile computing services accomplish the robust and efficient adaptation to mobile environment. To regulate the service configuration policies, WebPADS maintains a configuration description file within both of client and server sides. The configuration description files are in XML [START_REF] Bradley | The XML Companion[END_REF][START_REF]Extensible Markup Language[END_REF] format and its acts as a declarative guide for dynamic service composition to adapt the vigorous changes of wireless environments. The condition of environment is reported by the client program and stored in an XML file in server side and its corresponding chain of service actions are defined in the configuration file.

We have previously described the WebPADS platform -a Web Proxy for Active Deployable Service [START_REF] Chuang | Dynamic Service Reconfiguration for Wireless Web Access[END_REF][START_REF] Chuang | Actively Deployable Mobile Services for Adaptive Web Access[END_REF]. The WebPADS platform is an object-oriented system that is based on active service deployment architecture, comprising components of dynamic service objects called mobilets, which executes under the WebPADS execution environment. Among the system's components, the event register allows objects to locate and register for event sources. When an event occurs, the objects that have registered for that event source are notified. Event sources include various changes in the status of a network, machine resources and connectivity. Furthermore, the composition of the services of the WebPADS server can be dynamically reconfigured to adapt to the vigorous changes in the characteristics of a wireless environment. The unit of service is implemented as a mobilet that provides value-added services to a wireless environment. The system's components also provide generic facilities that serve the mobilets, which in turn provide services that enhance a user's Webbrowsing experience. A series of mobilets can be linked together to form a processing-service composition, allowing WebPADS to benefit from the aggregated functionality of a group of services (as shown in figure 1). Services provided by the WebPADS system can be migrated from one WebPADS server to another to track the mobility of a mobile node and serve the mobile node continuously. Services can also be added, removed and updated dynamically without interrupting the service provision to other mobile nodes. Furthermore, the composition of the services of the WebPADS server can be dynamically reconfigured to adapt to the vigorous changes in the characteristics of a wireless environment.

Systems Architecture

With the advent of mobile computing, it is common for users to access the Web through various mobile devices such as mobile phones, hand-held PCs and PDAs etc.

Each mobile device has different characteristics. For example, a user using a personal digital assistant may have less than 480 x 640 resolution and Web access through the mobile device is normally performed through a few proxy servers, either through a home wireless network or a wireless gateway installed in a mobile user's office. To provide adaptation to suit the requirements of mobile users, we have employed the WebPADS client-proxy mobile architecture to improve web searching experience. Figure 2 shows the system's architecture of the mobile meta-searching engine. Users can interact with the system using the client application in the mobile node. The Environment Monitor on the WebPADS client reports the contextual information of the mobile node, and the dynamic information of the mobile environment is updated to the server at regular intervals. The idea is to implement the WebPADS services both in the mobile node and in the server, where all HTTP requests or responses are intercepted, transformed and optimized for transformation over a wireless network. When a meta-search query is sent to the proxy server, a chain of service is created according to the dynamic configuration of the mobile clients, to facilitate measearching in a mobile environment.

Active Service Composition

Based on the user requirements of the dynamic mobile environment, the WebPADS system introduces an active service model that extends the client-proxy model to support active service composition. In this active service model, the proxy is composed of a service object called mobilets. This model offers flexibility because the chain of mobilets can be dynamically reconfigured to adapt to the vigorous changes in the characteristics of a wireless environment, without interrupting the service provision for other mobile nodes. Figure 3 shows the chain of mobilet services for providing adaptive meta-search services and Figure 4 shows the services for formatting search results.

Base

Meta-Searching Engine

As shown in figure 3, for each service, the corresponding mobilets are implemented in pairs. For example: The HttpRelaySlave mobilet receives the http response from the Internet and the HttpRelayMaster mobilet displays the results in suitable format for the mobile station. The MetaSearchSlave mobilet searches the desired search result from the http response and the MetaSearchMaster mobilet converts the results from the meta-search engine for display. Finally the CompressionSlave mobilet compresses the retrieved results using the ZLIB library, and the CompressionMaster mobilet decompresses the retrieved result using the ZLIB for decompression. Each pair of mobilets in the service chains are dedicated for a specific function for dynamic service composition. Table 1 lists the functions of the corresponding mobilets within the service chains (as shown in Figure 4) for formatting the results of the meta-search engine. Fig. 3 The Service Chain for Meta-search Fig. 4 Service Chain for Formatting Web Content Table 1. Details of the services in the service chain for formatting the meta-search results

HttpRelaySlave

Receives the http response from the internet.

GrabResponseSlave

Retrieves all available image links from the html document, reformats the links with the domain and arrange the html and image link objects.

HTMLTransformatSlave

Reformats the html documents so that useless contents are removed. E.g. reformat the link of CSS, remove the javascript, applet and comments.

ImageTranscodingSlave

According to the conditions specified in the system configuration file, ImageTranscoding Slave can be used to transcode the image into a suitable format for the mobile client.

CompressionSlave

Compresses the retrieved result using the popular ZLIB compression library.

CompressionMaster

Decompress the retrieved result using the popular ZLIB compression library.

ImageTranscodingMaster

Stores the retrieved image in the client machine.

HTMLTransformatMaster

Stores the retrieved html documents in the client machine.

GrabResponseMaster

Commits the result storage and backup the old versions of the search result (if the same page is requested more than once).

HttpRelayMaster

Displays the results in a suitable format.

Adaptation Rules

The WebPADS platform has been used to implement mobile applications to provide efficient Web browsing experience for mobile users [START_REF] Cheung | An Adaptation Control Model to Support Mobile Web Access[END_REF][START_REF] Cheung | A Context-Aware Adaptation Model for Efficient Web Browsing on Mobile Devices[END_REF][START_REF] Cheung | An Adaptation Model for Accessing Document Clusters in a Mobile Environment[END_REF]. Table 2 lists the contextual information that is identified for the mobile devices. The information collected is used to configure the service provision dynamically to meet the processing and presentation requirements of the mobile clients. To regulate the dynamic service composition policies, the WebPADS system maintains a configuration description file utilizing XML. To dynamically adapt to the changes in the environment, WebPADS employs the environment monitor and event system to monitor and communicate the changes. An environment element consists of one or more conditions, where each condition specifies an event and a relational value that will fulfill that condition. When a WebPADS client starts, a default service composition is created that is based on the description of the XML configuration file. At the same time, a number of alternative reconfiguration service chain maps are also created. Each map is attached to an environment monitor, which regulates the time and conditions for the service reconfiguration to take place. When all the conditions monitored by a specific environment monitor are fulfilled, the current service composition will be reconfigured to the service chain map attached to that environment monitor. The configuration file is used for constructing the user adaptation model. Figure 5 shows examples of adaptations rules that are used to compose the services for metasearch dynamically. It is implemented in an XML format file. For example, the rule segments corresponding to the adaptation rules for CPU usage can be interpreted as follows: If cpu_usage < 50 then perform Best_Compression; If cpu_usage > = 50 and cpu_usage < 65 then perform Default_Compression; If cpu_usage >=65 and cpu_usage < 75 then perform Low_Compression; If cpu_usage > = 75 then perform No_Compression.

Example -Dynamic Activation of Transcoding Service

The meta-searching system is implemented with a graphic user interface on the mobile client station. The current version supports meta-searching through Yahoo, Google, AltaVista and Lycos (as shown in Figure 6). Corresponding to the selected search engines and the selected configuration options (e.g. auto option for compression and image color level defined in the configuration file), the system communicates with the meta-search engine through the WebPADS server. The following example shows the results of adaptive service composition after the dynamic activation of the image transcoding service in a low bandwidth wireless network environment (as shown in figure 6 and figure 7). In the meta-searching system, the size of images within the resulting pages directly affects the amount of data that is transported in the mobile environment. For example, if the bandwidth of the mobile connection is less than a threshold value (e.g. 64 K), it is desirable to transcode the graphic files (e.g. the GIF files) with a lower bit depth to reduce the image file size [START_REF] Bharadvaj | An Active Transcoding Proxy to Support Mobile Web Access[END_REF][START_REF] Han | Dynamic Adaptation in an Image Transcoding Proxy for Mobile Web Browsing[END_REF]. The rules for adaptations can be configured in the configuration file in WebPADS. According to the bandwidth and contextual parameters, a scaling parameter can be defined to determine how much an image is downsampled. According to the dynamic adaptation requirements, the number of colors in a color-mapped image can be reduced (e.g. a 24-bit color image may be converted to 8-bit grayscale or even monochrome representation). Figure 7 shows the examples of the original graphic image and the retrieved image (down-sampled) after dynamic activation of the transcoding service in the system.

Conclusion

A meta-search application is developed for mobile devices with limited hardware capabilities. By running in the auto-configuration mode, the system detects the dynamic contextual information, and presents the results of meta-searching in a suitable format to cope with the limitations of the mobile stations. This is achieved by an adaptive service composition that is defined according to the adaptation model defined in a system configuration files. The configuration file can be stored at the mobile device and edited by the users at any time. The parameters for the adaption model can be adjusted to suit the information requirements of the mobile users. By implementing the system in the WebPADS platform, it is possible to maintain ongoing service provision as the mobile node moves across different domains (e.g. from a home network to an office network in a wireless environment). A major concern about our implementation is that it is not easy to maintain the adaptation rules stored in the system confirmation file in XML format. Future directions of research include using artificial intelligence techniques to improve the flexibility in adaptation, and to provide user-friendly interfaces for the users to maintain the adaptation rules in the rule base.

Fig 1 .

 1 Fig 1. The WebPADS system architecture

Fig. 2 .

 2 Fig. 2. System Architecture

Fig 5 .

 5 Fig 5. The XML Configuration File

Fig 6 .

 6 Fig 6. The graphical user interface in the mobile station

Fig 7 .

 7 Fig 7. The original graphic image (left) and the down-sampled image (right) in the mobile station

Table 2 .

 2 Contextual information reported by the WebPADS client

	Unit Type	Contextual Information
	System	CPU type, clock rate, utilization, OS name, version
	Storage	RAM size, free space, Secondary Storage size, free space
	Network	Network type, capacity, data rate, delay, error rate
	Power	Battery maximum lifetime, remaining lifetime
	Display	Color type, depth, Screen resolution
	Audio	Type of sound supported
	Browser	Browser name, version
	<RECONFIGURATION>
	…
	<ENVIRONMENT config_option="COMPRESSION">
	<CONDITION_ATTRIBUTE value="CPU_USAGE">
	<CONDITION> <RELATION operator="LESS_THAN">50</RELATION>
		<CONFIG_VALUE>BEST_COMPRESSION</CONFIG_VALUE>
	</CONDITION>
	<CONDITION> <RELATION operator="MORE_OR_EQUAL">50</RELATION>
		<RELATION operator="LESS_THAN">65</RELATION>
		<CONFIG_VALUE>DEFAULT_COMPRESSION</CONFIG_VALUE>
	</CONDITION>
	<CONDITION> <RELATION operator="MORE_OR_EQUAL">65</RELATION>
		<RELATION operator="LESS_THAN">75</RELATION>
	<CONFIG_VALUE>LOW_COMPRESSION</CONFIG_VALUE>
	</CONDITION>
	<CONDITION> <RELATION operator="MORE_OR_EQUAL">75</RELATION>
		<CONFIG_VALUE>NO_COMPRESSION</CONFIG_VALUE>
	</CONDITION>
	</CONDITION_ATTRIBUTE>
	</ENVIRONMENT>
	…
	<ENVIRONMENT config_option="IMAGE_SIZE">
	<CONDITION_ATTRIBUTE value="WIDTH_PIXELS">
	<CONDITION> <RELATION operator="LESS_OR_EQUAL">320</RELATION>
		<CONFIG_VALUE>1/2</CONFIG_VALUE>
	</CONDITION>
	<CONDITION> <RELATION operator="LESS_OR_EQUAL">480</RELATION>
		<RELATION operator="MORE_THAN">320</RELATION>
		<CONFIG_VALUE>2/3</CONFIG_VALUE>
	</CONDITION>
	<CONDITION> <RELATION operator="LESS_OR_EQUAL">640</RELATION>
		<RELATION operator="MORE_THAN">480</RELATION>
		<CONFIG_VALUE>3/4</CONFIG_VALUE>
	</CONDITION>
	<CONDITION>
		<RELATION operator="MORE_THAN">640</RELATION>
		<CONFIG_VALUE>1</CONFIG_VALUE>
	</CONDITION>
	</CONDITION_ATTRIBUTE>
	</ENVIRONMENT>
	…
	</RECONFIGURATION>


Francisco J García

Ignacio Díaz

Ignacio Álvarez
email: ialvarez@isa.uniovi.es

Daniel Pérez
email: dperez@isa.uniovi.es

Daniel G Ordonez

Manuel Domínguez

Time-Frequency Analysis of Hot Rolling using Manifold Learning

Keywords: Hot rolling, dimensionality reduction, ISOMAP, spectrogram analysis

In this paper, we propose a method to compare and visualize spectrograms in a low dimensional space using manifold learning. This approach is divided in two steps: a data processing and dimensionality reduction stage and a feature extraction and a visualization stage. The procedure is applied on different types of data from a hot rolling process, with the aim to detect chatter. Results obtained suggest future developments and applications in hot rolling and other industrial processes.

Introduction

Ever since its inception in the end of sixteenth-century, metal rolling has become one of the most important industrial process in the world. Huge amounts of material and money are driven by the rolling industry, so it is so important to have a method not only for describing the observed behaviour of the process, but also for identifying the nature of a problem. Due to the high amount of variables involved, trying to find relationships among them appears to be a good aproach for dimensionality reduction (DR).

The selection of a set of variables that describes operating modes in industrial processes is closely related to DR. One of the most important DR technique is Principal Component Analysis (PCA) [START_REF] Jollife | Principal component analysis[END_REF], described by Pearson in 1901. After PCA, other DR techniques have been proposed, such as Multidimensional Scaling (MDS) methods, Independent Component Analysis (ICA) [START_REF] Hyvarinen | Survey on independent component analysis[END_REF] or Self-Organizing Maps (SOM) [START_REF] Kohonen | Self-Organizing Maps[END_REF]. However, in the last [START_REF] Specht | A general regression neural network[END_REF] in order to obtain the global coordinates of each model, usually implying a singular value decomposition (SVD). Some of the most known of these techniques are isometric feature mapping or ISOMAP [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF], local linear embedding (LLE) [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF], laplacian eigenmaps (LE) [START_REF] Belkin | Laplacian eigenmaps for dimensionality reduction and data representation[END_REF] and local tangent subspace alignment (LTSA) [START_REF] Zhang | Principal manifolds and nonlinear dimension reduction via local tangent space alignment[END_REF].

Faults appeared in rolling process provoke important economic losses to the final product, so it is necessary to detect them in an early state, which is usually performed by analizing the frequency content of signals. A common source of problems in rolling is chatter [START_REF] Drevermann | Prozess-und zustandsberwachung an einem fertiggerst[END_REF], which is an unexpected powerful vibration that affects the quality of rolled material by causing an unacceptable variation of thickness. The frequency band related to chatter appears at 100-300 Hz, so monitoring this band is a possibility to detect it. A good way to visualize that information is the spectrogram, which provides a time-varying spectral representation that shows how the spectral density of the signal varies with time [START_REF] Boashash | Time-Frequency Signal Analysis and Processing A Comprehensive Reference[END_REF], making it possible to visually detect defects. Spectrograms can be understood as vectors of high dimensionality, making it possible to use them as inputs for DR techniques in order to divide them into different groups of data. In this paper we propose a method based on the use of embedding methods for the visulization of differences in spectrograms, applying it to vibration, speed and torque data of a hot rolling mill, showing not only the data structure, but also features of the different spectrograms. This paper is organized as follows: section 2 describes the method applied, section 3 shows a description of the experiment, section 4 submits the results and finally section 5 includes the conclusions obtained.

Spectrogram Analysis using Manifold Learning

As proposed in [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF][5] [START_REF] Zhang | Principal manifolds and nonlinear dimension reduction via local tangent space alignment[END_REF], DR techniques are a good approach for image classification. From an industrial point of view, spectrograms can be understood as images of the process, because they provide time-frequency information about the state of the involved variables. The proposed method takes advantage of the analogy between spectrogram and image applying DR techniques. The procedure is divided into two parts: firstly spectrograms and ISOMAP projections of different coils are computed and secondly information about main features of process is visualized in a similar way to component planes [START_REF] Kohonen | Self-Organizing Maps[END_REF] (See Fig. 1).

Computation of ISOMAP Projections

Due to the nature of the rolling process, it is common to do a spatial sampling of signals, where harmonics are independent from speed, therefore this procedure is performed at first. Considering a measured variable y(t) at a regular time interval T m , the sequence obtained is

y k = y(t k ), where t k = k • T m . Spatial resampling needs a speed measurement v = [v 0 , v 1 , . . . , v k ],
either linear or rotatory, to know the spatial points where the original data was sampled x = [x 0 , x 1 , . . .]. Afterwards, selecting a spatial sampling rate (e m ) allows to obtain a signal regularly sampled at fixed space intervals -each e m -y = [y 0 , y 1 , . . .] T where y k = y(t k ), with t k = 0 for k = 0 and Because of this type of visualization, it is possible to stablish a logical analogy between spectrogram and image. After spectrogram computation, the obtained matrix is converted into a vector with the aim to apply a DR technique. Being S the spectrogram matrix of dimension ( R 2 +1)×M , each spectrogram can be represented as a vector s = [s 0 , . . . , s p ] T , where s r+(m-1)( R 2 +1) = S r,m . The ISOMAP algorithm [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF] was applied to s. The ISOMAP algorithm is a DR technique where geodesic distance on a weighted graph is incorporated with the classical scaling, obtaining low-dimensional embedding of a set of high-dimensional data points.

t k = t k-1 + em v k for k = 1, 2, . . .. Since actual data Coil Data Spatial Sampling Spectrogram Computation ISOMAP Feature Extraction GRNN i = 1,2,...,Q Q = # of coils Vectorization s i ∈ R 32784 g i m i S i ∈ R 2049,16

Feature Extraction and Visualization

The first step of this stage is the extraction of relevant features from the signals being analysed. Considering a variable y k of length N , a windowed Fast Fourier Transform (FFT) -as an efficient algorithm for Discrete Fourier Transform (DFT), avoiding Gibbs effect-is applied in order to obtain its spectral information, as Y i = N -1 k=0 w(k)y k e -j2πk/N , for i = 0, . . . , N -1, where Y i is a complex sequence describing the amplitudes and phases of the signal harmonics and w(k) is a Hanning window. In this case, a N -length window is used, so there is only one value of energy for each harmonic. The energy in bands around p specified center frequencies

f 1 , f 2 ,• • •, f p with predefined bandwidths B 1 , B 2 , • • •, B p
can be computed by summing up the squares of the harmonics inside this bands, in order to obtain a p-dimensional feature vector m = [m 1 , m 2 , . . . , m p ] T , where

m i = k N T ∈[fi- B i 2 ,fi+ B i 2 ] ||Y k || 2 .
Finally, features extracted for each analysed signal can be arrange in a data matrix M = (m n ) = [m 1 , m 2 , . . .], where m n represents the column feature vector of coil n. In addition to the frequency features, specific feature extraction derived from process domain knowledge can be added (see Section 3). The visualization of component planes requires the application of a interpolation algorithm to estimate the value of each feature at every point in the 2D visualization space. In this paper, the Specht's [START_REF] Specht | A general regression neural network[END_REF] algorithm, general regression neural network (GRNN) is applied to match the extracted features and ISOMAP projections.

Experiment

The method described here was applied to data from a hot rolling finishing facility. The analysed signals were acceleration at driver-side (Acc DS, 6250 Hz), as a measure of vibration, the root mean square of velocity, both at operator side and at driver side (VRMS OS and VRMS DS, 10 Hz), upper roll torque (Torque OS, 500 Hz) and, finally, rotation speed of rolls (Rot Sp, 500 Hz). Only data during rolling stage was analysed. Two states of rolling -non-chatter and chatter, which leads to low quality coils-were taken into account in order to understand the results obtained with this method. The total size of the sample is 111 coils, comprising both states of rolling. Due to the original difference in the sampling frequency between Acc DS and Rot Sp signals, Acc DS signal was decimated in order to have a unique sample rate. A spatial sample rate of 212.16 rev -1 was selected using the minimum spatial distance between two samples in the data.

Spectrogram computation was applied to Acc DS signal of every coil, with a window size of 4096 and an overlapping of 90%. To have equal sized spatial spectrograms, only the first 30 revolutions of rolling were considered, resulting in a total size of 32784 elements for each spectrogram to be projected with the ISOMAP algorithm. The dimensionality reduction stage of spectrograms involved the application of the ISOMAP algorithm with K = 30 and output dimensionality of 2. Apart from frequency features, the mean of the difference between each element of VRMS OS and VRMS DS was added, as

µ v = 1 N N -1 i=0 (v di -v oi ).
Finally, component planes generation was computed with value of σ = 0.003 in GRNN with the aim to obtain a smooth degradation of the color of the planes for the difference of chatter and non-chatter group.

Results

The application of the method obtains the ISOMAP projections shown in Fig. 3 (top). ISOMAP is able to make a clusterization of the high-dimensional input data, obtaining two clusters (chatter and non-chatter), being remarkable that coils number 14 and 15 which appear isolated. It can be observed that these two coils happen to appear just before a long series of chattered coils. Component planes of ISOMAP are visualized in Fig. 3 (bottom). In this representation, two different color zones dependent from the value of the feature analysed are distinguished . The effect of the σ value stablished for the GRNN algorithm, smoothing the color in each plane, can also be observed. This representation provides information about the value of the feature analysed in each plane. In addition, component planes characterize two zones, related to chatter and non-chatter coils. Such representations combine the visualization of the cluster structure of the data with the visual display of the value of different features associated to each coil. Also, it is noteworthy the explanatory power in the definition of chatter of VRMS DS-VRMS OS, which is an unusual feature for detecting chatter.

Conclusions

In this paper we have proposed a method to explore the visualization of spectrograms in a low dimensionality as an use of ISOMAP, similar to image classification in [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF]. This method was applied to data from a hot rolling process in order to detect different states of rolling. The resulting projections show that different spectrograms produce low dimensional structures that can be efficiently unfolded with ISOMAP, distinguishing chatter, non-chatter and transition coils before chatter appears, which suggests that there is a difference in the frequency content of rolling that could be potentially used as to estimate when chatter could appear. Another contribution are component planes of ISOMAP, which provides information about analyzed features of the process, differentiating chatter and non chatter coils. These results suggest the potential use of the proposed method not only in hot rolling, but also in other kinds batch process monitoring or in fault detection where time-frequency behavior of one or more variables bear information on process quality or fault conditions.

  years, a new trend in DR, based on nonlinear models, appeared and a new collection of algorithms have been proposed. These algorithms -called local embeddings-involve a local optimization by defining local models of the k nearest neighbours and an alignement This work has been financed by a grant from Research Fund for Coal and Steel of the European Community and by the spanish Ministry of Science and Education and FEDER funds under grants DPI2009-13398-C02-01/02

Fig. 1 .

 1 Fig. 1. Flowchart describing the method applied.

  is regular time sampled, the values of the spatial sampled data are obtained through linear interpolation.The next step in our method is to compute the spectrogram of variables. Given a discrete signal y k = [y 0 , y 1 , . . . , y n-1 ] T , the Short-Time Fourier Transform (STFT) at a time n is defined asY (ω, m) = ∞ n=-∞ y n-m ω n e -jωn = R-1 n=0 y n-m ω n e -jωn, where ω n is a window function of length R. The spectrogram is a graphical display of the magnitude of ST F T , |Y (ω, m)|. This representation provides simplicity, robustness and ease of interpretation of the information contained in the frequency content. In Fig.2, appearance of work roll (a), vibration (b), time (c) and spatial (d) spectrograms for a chattered coil are shown. Note that the strong 30 rev -1 harmonic in the spatial spectrogram matches the periodicity of the marks in the work rolls for a whole turn, regardless the rolling speed. This makes such kind of representation a proper invariant descriptor of spatial phenomena typically involved in chatter effect.

Fig. 2 .

 2 Fig. 2. Typical case of chattered coil

Fig. 3 .

 3 Fig. 3. ISOMAP projections and component planes of coils analysed.


Marc Sauget
email: marc.sauget@univ-fcomte.fr

Julien Henriet

Michel Salomon

Sylvain Contassot-Vivier

Large datasets: a mixed method to adapt and improve their learning by neural networks used in regression contexts

Keywords: Pre-clinical studies, Doses Distributions, Neural Networks, Learning algorithms, External radiotherapy, Data extraction

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

Introduction

The work presented in this paper takes place in a multi-disciplinary project called Neurad [1], involving medical physicists and computer scientists whose goal is to enhance the treatment planning of cancerous tumors by external radiotherapy [START_REF] Makovicka | Avenir des nouveaux concepts des calculs dosimétriques basés sur les méthodes de Monte Carlo[END_REF]. The final objective of our work is to propose a new tool to evaluate the result of an external radiotherapy treatment. In our previous works [START_REF] Bahi | Neural network based algorithm for radiation dose evaluation in heterogeneous environments[END_REF][START_REF] Bahi | A parallel incremental learning algorithm for neural networks with fault tolerance[END_REF], we have proposed an original approach to solve scientific problems whose accurate modeling and/or analytical description are/is difficult. A short review of this problem is described in [START_REF] Haas | Intelligent and Adaptive Systems in Medicine, chap[END_REF]. One of the major originality of that work is to use a Monte-Carlo simulator to build a very accurate dataset instead of measured data [START_REF] Blake | Artificial neural network modelling of megavoltage photon dose distributions[END_REF] (less accurate and sparser).

More precisely, the Neurad project proposes a new mechanism to simulate the dose deposit during a clinical irradiation. Our method consists in using a set of neural networks (one per processor), which act as universal approximators, in combination with a specific computational code. Each neural network predicts the dose delivered in a homogeneous environment on a subdomain of the domain to be treated, whereas a specific algorithm expresses the rules to manage any heterogeneous environment. The feasibility of this original project has been clearly established in [START_REF] Makovicka | Avenir des nouveaux concepts des calculs dosimétriques basés sur les méthodes de Monte Carlo[END_REF]. It was shown that our approach results in an accuracy similar to the Monte-Carlo one and fulfills the time constraints of the external radiotherapy evaluation. The accuracy of a neural network is a crucial issue; therefore it is the subject of many research works on neural network learning algorithms.

The main idea of our work is to improve the performance of our incremental learning algorithm [START_REF] Bahi | An incremental learning algorithm for functional approximation[END_REF][START_REF] Bahi | A parallel incremental learning algorithm for neural networks with fault tolerance[END_REF] by an efficient decomposition of the learning set. We have already proposed an optimized decomposition method based on an evaluation of the signal complexities of each data subset [START_REF] Sauget | Efficient domain decomposition for a neural network learning algorithm, used for the dose evaluation in external radiotherapy[END_REF]. This approach provides subsets of similar signal complexities, however these subsets may have different sizes. So, although that decomposition offers a better homogeneity in the learning times of the subsets than classical decompositions, it can still be enhanced. A way to further improve the learning step is to work on the subsets sizes. More precisely, the work presented thereafter is motivated by the following question: "If two data sets have the same complexity, why do they not have the same number of data samples?".

Extraction of a representative set from massive data

Our study deals with the construction of a representative dataset from a larger database, in order to train a neural network. The data samples have the following characteristic: they are usually regularly spaced and often they contain statistical noise. These samples could not be used directly to obtain an efficient data learning. Indeed, the larger is the dataset, the longer is the learning time. When the dataset is too large, the neural network behaves more like a database with a low generalization (interpolation) capacity. In our first studies we have removed the statistical noise, but the limits of this approach were rapidly reached. Therefore, we are now looking for a method that limits the size of the dataset and captures the salient characteristics of the original dataset to be approximated.

There are many solutions in the literature to limit the size of a dataset. In particular, Jankowski and Grochowski present in [START_REF] Grochowski | Comparison of instance selection algorithms ii. results and comments[END_REF][START_REF] Jankowski | Comparison of instances seletion algorithms i. algorithms survey[END_REF] a state of the art of these methods in the context of neural networks used for classification. On the one hand they describe solutions that filter data to remove noise and on the other hand, they present ones doing data selection based on a good value repartition or using a mask. Another solution is to keep only the most homogeneous data to build the dataset [START_REF] Chu | An interpolation method for adapting to sparse design in multivariate nonparametric regression[END_REF][START_REF] Guo | A method to sparsify the solution of support vector regression[END_REF]. However, those solutions are not fully adapted to neural networks used as universal approximators where the data must reflect the signal on the entire domain while preserving the sharp variations. In the classifier Fig. 1. A mixed selection method for optimized dataset decomposition context, the most important data are at the frontiers between the different data classes and their accuracy must be preserved whereas other parts can be sparser and less accurate.

Monte

In this paper, we present an innovative method to select data samples based on the combination of two existing solutions together with a selection based on the complexities (see Fig. 1). As shown in the following, the proposed method is designed for neural networks used as approximators. The interest of this method is to improve the learning time thanks to a suitable selection of the data samples, leading to an optimized dataset decomposition. That approach prevents overfitting due to the presence of useless noising data and reduces the computational cost of the learning step [START_REF] Wu | Neural network forecasts of the tropical pacific sea surface temperatures[END_REF].

Conservation of the global aspect of the signal

The general aspect of the signal could be easily guaranteed by the use of a uniform grid applied to the ranges of the dataset. The first tool used to build our dataset is very simple: the position of the new uniform grid is evaluated and we select the corresponding samples to build the subset R u . The resolution of that grid could be quite low because its only interest is to constrain the learning on the global aspect of the signal. Its particularities will be taken into account by another group of data samples selected according to their complexities.

Conservation of the particularities of the signal

The most difficult point during the learning phase of a neural network used as a universal approximator is to keep its general aspect without forgetting the quality of interpolation in local areas having an important gradient value. The equilibrium between these two parts is always difficult to preserve. The solution presented here consists in only selecting the most important values taking into account their local complexity. Our notion of data complexity has already been presented in [START_REF] Sauget | Efficient domain decomposition for a neural network learning algorithm, used for the dose evaluation in external radiotherapy[END_REF]. We recall here that, in order to evaluate the local complexity lC i,j at spatial point (i, j), we use the variations between that point and a given set of its neighbors (x, y), each of them being distance weighted. So, the local complexity at point (i, j) has the following form:

lC i,j = i+r x=i-r j+r y=j-r,(x,y) =(i,j) |f (x, y) -f (i, j)| || ---→ (x, y) - --→ (i, j)|| (1)
where parameter r defines the size of the neighborhood taken into account.

The algorithm used to select n points is described in Algorithm 1. This algorithm evaluates the complexities of every point according to (1) and produces a decreasing order sorted list. Once the list is built, the algorithm returns a subset of the initial dataset composed of the n most characteristic points. The resulting subset corresponds to the R c data subset. decreasingOrderInsertion(ei, c, Rp) 5: end for 6: append(Rc, Rp{1, n}) 7: return Rc

Algorithm 1 Most particular points selection

Homogeneous density of the complexity classes

The combination of the two previous methods does not ensure that the obtained dataset provides an optimal learning. In [START_REF] Pan | Finding representative set from massive data[END_REF], the authors have shown for a neural network used as a classifier that a dataset is composed of a few sets of data samples with the same complexity. They called such a set a class and also showed that the different classes should have the same density (number of samples).

In our case, the neural network is used as an approximator, so the data samples values are just discretized to define the complexity classes induced by a dataset. Hence, we firstly compute the complexity classes considering the data samples that compose subsets R u and R c . Secondly, once the classes are identified, new data samples are selected from the initial dataset to complete the classes that are not sufficiently represented. The objective is to obtain classes with similar densities, in order to respect the quality constraint. The new data samples selected to complete R u and R c are chosen with a classical random method, they define the data subset R a .

Global building of the dataset

To obtain each dataset affected to a single processor, more precisely a subset of the global dataset, the process is as follows.

Firstly, the initial global dataset is decomposed in p subsets, where p is the number of available processors, using our URB based decomposition described in [START_REF] Sauget | Efficient domain decomposition for a neural network learning algorithm, used for the dose evaluation in external radiotherapy[END_REF]. Since the resulting decomposition is irregular, the subsets have different sizes. In order to have similar sizes, we impose that all the subsets (R sd ) have N data samples: the size of the smaller subset in the decomposition. Obviously, this last subset keeps all its data samples, while in the remaining p -1 subsets, some data samples must be discarded.

The second step, which reduces the size of the larger R sd subsets, uses the three methods previously described to select for each of them the N data samples that will be retained. In fact, R u , R c , and R a are computed for each subset R sd such that these data subsets have each N data samples. Then, the reduced subset R sd is built by picking elements from its corresponding sets R u , R c , and R a , according to the respective proportions α, β and γ, such that:

α = ||R sd ∩Ru|| N , β = ||R sd ∩Rc|| N , γ = ||R sd ∩Ra|| N (2)
where α + γ + β = 1. In a first approach, similar ratios might be used (α = γ = β = 1/3), but this choice could not be retained because R a is not a real data subset. Indeed, its main interest is to guarantee the equilibrium between the complexity classes. 20% of the data subset R a (γ) are sufficient and necessary to balance the complexities. The most important data are provided by R u , thus 50% of the data samples from R sd are selected in it. Finally, the remaining samples correspond to the 30% (β) most characteristic ones in R c .

Once the p data subsets of N samples have been built, they are learned using our fault-tolerant parallel algorithm [START_REF] Bahi | A parallel incremental learning algorithm for neural networks with fault tolerance[END_REF].

Experimental results

In this section, both quality and performance of our approach are experimentally assessed. Our algorithm has been implemented in standard C++ with Open-MPI [START_REF]Open Source High Performance Computing[END_REF] for the parallel part. All the experiments have been performed using the computing resources from the Mesocenter of Franche-Comté [START_REF]Computing Mesocenter of Franche-Comté[END_REF]: a cluster consisting of 8-core nodes (two Intel Xeon Nehalem quad-core processors) with 12GB RAM.

Generic function

The objective of our method is to provide an accurate learning using only a selection of samples from a large dataset. To perform a first evaluation, we have built a synthetic dataset using a generic 2D function given in Fig. 2. The dataset is composed of 10000 points uniformly distributed over the two dimensions.

We have evaluated the training times to obtain the desired accuracy of learning in two cases. In the former case, the domain decomposition method presented in [START_REF] Bahi | A parallel incremental learning algorithm for neural networks with fault tolerance[END_REF] has been used with the entire dataset. In the latter case, a filtered version of the dataset has been used. The decomposition method allows us to obtain different subdomains with a relative similarity of complexities. We have also chosen to limit the size of each data subset using as reference the size of the smaller subset obtained with the decomposition mechanism. Several dataset decompositions have been tested and for each one we give the average size of the data subsets.

The results are presented in Table 1. They show the average learning time of the subdomains for each decomposition, as well as the standard deviation. This last information allows us to check the good balancing of the training times between the subdomains. Finally, the last column indicates the speedup between the average learning time obtained with the full dataset and the one obtained with the filtered one. We show with this first test the good performance of our data subset reduction method: an average speedup value of 3 can be observed. Furthermore, the speedup remains almost constant, whatever the decomposition degree used. This observation can be explained by the structure of the function, since it presents only a few parts with important gradient values which are also regularly distributed on the studied domain. Let us notice that the cumulative size of all the subdomains resulting from a decomposition is greater than the size of the initial global dataset (10000 samples in this case). Indeed, to ensure a homogeneous quality of the results of our parallel algorithm [START_REF] Bahi | A parallel incremental learning algorithm for neural networks with fault tolerance[END_REF] throughout the global domain, each subdomain must have a small overlapping area with all its neighbors, thus some data samples belong to several subdomains.

Radiotherapy context

In the radiotherapy context, we use data resulting from a Monte-Carlo simulation that represents an irradiation in a homogeneous environment. The first part is the evaluation of the initial dataset obtained with a Monte-Carlo simulator [START_REF]BEAM-nrc[END_REF]. These data are very dense and quite noisy. To enhance the learning process, a first treatment is used to limit the negative impact of the noise, as shown in Fig. 3. We use a simple filter to reduce the noise. Figure 4 presents a comparative view of the original data and the final data obtained from our selection process. These curves correspond to the dose deposit for a single material. The next step is the learning process. The neural networks obtained after the learning phase are then used in conjunction with a specific algorithm to compute the result of an irradiation in any kind of environment, potentially heterogeneous [START_REF] Vasseur | Dose calculations using artificial neural networks: a feasibility study for photon beams[END_REF].

To evaluate the behavior of our algorithm, we have chosen a restricted learning set. This configuration allows us to verify the interest of our algorithm without requiring a very long learning time. In fact, we have chosen to use only two materials (tissue and bones) and one configuration of irradiation. Since we use a grid of 120×100 points, the dataset is obviously composed of 120×100×2 samples. Each sample is characterized by seven components: the position in the three spatial dimensions; the material density; its distance from the irradiation source and the beam width (minimum and maximum values).

The tests have be performed with different decomposition degrees to evaluate the accuracy of the learning and to determine the limits of our solution. The objective of this work is to reduce the time of the learning step without affecting the final quality. So, the learning time is the essential parameter to take into account to validate our dataset construction. In all cases, the given times are only the learning times, they do not include any other data manipulation. The training stops when the specified accuracy is reached.

Table 2 shows the average learning time for each training case, as well as the standard deviation. As for the generic function in the previous subsection, this last information allows us to check the good balancing of the subdomains training times. Note that the load balancing is a very important parameter because it indicates the degree of use of all the computing resources during the training step. These results, together with the speedup information, show that the use of a selected dataset efficiently improves the learning time without inducing any significant accuracy loss (controlled during the learning process). So, we obtain in all cases a good speedup (values ranging from 3 to 5) with a very good improvement (reduction) of the standard deviation. We can also notice that with real data, like the radiotherapy case, the speedup is not as regular as in the previous case, with the generic function. We explain this difference by the fact that the parts of the dose deposit curves that exhibit an important gradient are less regularly distributed (as it was the case for the generic function). Thus, as one could expect, the size of the data subsets is not the only parameter having an impact on the learning time. In this paper, we have presented a simple and efficient method to build an optimized learning dataset from data produced by a physical simulation. Thanks to this method, both data size and noise can be reduced without loosing any information. Hence, this approach significantly reduces the learning times without impacting the final quality.

Qualitative and quantitative evaluations of the algorithm have been performed experimentally on artificial and real datasets. The use of an artificial dataset points out that this method is not restricted to the specific radiotherapy context. The tests with real datasets confirm the good behavior of our algorithm, whether in terms of quality or performance, for complex datasets. The low standard deviation values show that the method gives well-balanced decompositions, and consequently smaller learning times.

In the following of the Neurad project, it will be necessary to test our different algorithms in real conditions, which means with complete datasets required in the medical operational context. A training using a full dataset, as well as a dose deposit calculation in real 3D images will allow us to fully validate our project.

Require: 1 :

 1 Dataset viewed as elements set E = {e1, e2, . . . }, |E| = m, and n < m is the number of points to select. Rc = {}, Rp = {} 2: for i = 1 to m do 3: c = evaluateComplexity(ei) 4:

Fig. 2 .

 2 Fig. 2. Synthetic dataset generated from the function: f (x, y) = sin(0.1 * x * y)

Fig. 3 .

 3 Fig. 3. The impact of the filtering step.

Fig. 4 .

 4 Fig. 4. General aspect of the dose deposit curves (left: original set, right: selected points).

Table 1 .

 1 Performances of the learning phase for the generic function.

	Subdomains	Original dataset Size Average times (s) SD Size Average times (s) SD Selective dataset	Speedup
	4	2962	393	92 1155	131	14	3.0
	8	1591	173	61 519	59	5	2.9
	16	846	92	37 221	29	3	3.1

Table 2 .

 2 Performances of the learning phase for the dose deposit curves.

Acknowledgements

The authors thank the LCC (Ligue Contre le Cancer) for the financial support, the Franche-Comté county and the APM (Agglomération du Pays de Montbéliard).


Vladimír Olej
email: vladimir.olej@upce.cz

Petr Hájek
email: petr.hajek@upce.cz

Comparison of Fuzzy Operators for IF-Inference Systems of Takagi-Sugeno Type in Ozone Prediction

Keywords: Fuzzy inference systems, IF-sets, IF-inference system of Takagi-Sugeno type, t-norm, t-conorm, intuitionistic fuzzy t-norm and t-conorm, time series, ozone prediction

The paper presents IF-inference systems of Takagi-Sugeno type. It is based on intuitionistic fuzzy sets (IF-sets), introduced by K.T. Atanassov, fuzzy t-norm and t-conorm, intuitionistic fuzzy t-norm and t-conorm. Thus, an IFinference system is developed for ozone time series prediction. Finally, we compare the results of the IF-inference systems across various operators.

Introduction

The IF-sets theory [START_REF] Dubois | Terminological Difficulties in Fuzzy Set Theory-The case of Intuitionistic Fuzzy Sets[END_REF] represents one of the generalizations, the notion introduced by K.T. Atanassov [START_REF] Atanassov | Intuitionistic Fuzzy Sets[END_REF]. The concept of IF-sets can be viewed as an alternative approach to define a fuzzy set in cases where available information is not sufficient for the definition of an imprecise concept by means of a conventional fuzzy set. In this paper IF-sets will be presented as a tool for reasoning in the presence of imperfect facts and imprecise knowledge. The IF-sets have been for example applied for ozone prediction [START_REF] Olej | IF-Inference Systems Design for Prediction of Ozone Time Series: The Case of Pardubice Micro-Region[END_REF] and air quality modelling as they provide a good description of object attributes by means of membership functions μ and non-membership functions ν. They also present a strong potential to express uncertainty. In our previous paper [START_REF] Olej | IF-Inference Systems Design for Prediction of Ozone Time Series: The Case of Pardubice Micro-Region[END_REF] a novel IFinference system of Takagi-Sugeno type was presented for time series prediction. In this paper, the outputs of the IF-inference system are compared across various operators in if-then rules.

This paper presents basic notions of Takagi-Sugeno type fuzzy inference systems (FIS) for time series prediction. Based on the FIS defined in this way and IF-sets, tnorms and t-conorms, intuitionistic fuzzy t-norms and t-conorms are defined. Next, IF-inference systems of Takagi-Sugeno type are introduced. Further, the paper includes a comparison of the prediction results obtained by the FIS characterized by membership functions μ, by the FIS characterized by non-membership functions ν, and by the IF-inference system. The comparison is realized for the example of ozone prediction in the Pardubice micro region, the Czech Republic.

General structure of FIS is defined in [START_REF] Pedrycz | Fuzzy Control and Fuzzy Systems[END_REF]. It contains a fuzzification process of input variables by membership functions μ, the design of the base of if-then rules or automatic extraction of if-then rules from input data, application of operators (AND,OR,NOT) in if-then rules, implication and aggregation within these rules, and the process of defuzzification of gained values to crisp values.

In [START_REF] Pedrycz | Fuzzy Control and Fuzzy Systems[END_REF] there are mentioned optimization methods of the number of if-then rules. Operator AND between elements of two fuzzy sets can be generalized by t-norm and operator OR between elements of two fuzzy sets can be generalized by t-conorm [START_REF] Zadeh | Fuzzy Sets[END_REF]. The concept of IF-sets is the generalization of the concept of fuzzy sets, the notion introduced by L.A. Zadeh [START_REF] Zadeh | Fuzzy Sets[END_REF]. The theory of IF-sets is well suited to deal with vagueness. Recently, in this context, IF-sets have been used for intuitionistic classification and prediction models which can accommodate imprecise information.

Based on [START_REF] Atanassov | Intuitionistic Fuzzy Sets[END_REF], using membership function μ Α (x), non-membership function ν Α (x) and intuitionistic fuzzy index (IF-index) π Α (x) it is possible to define an IF-system. The value π Α (x) denotes a measure of non-determinancy, it may cater to either membership value or non-membership value, or both.

Let there exist a general IF-system defined in [START_REF] Montiel | Mediative Fuzzy Logic: A new Approach for Contradictory Knowledge Management[END_REF]. Then it is possible to define its output y η as y η = (1-π Α (x)) × y μ + π Α (x) × y ν , where y μ is the output of the FIS μ using the membership function μ Α (x), y ν is the output of the FIS ν using the non-membership function ν Α (x). For the IF-inference system designed in this way, the following facts hold. If IF-index [START_REF] Olej | IF-Inference Systems Design for Prediction of Ozone Time Series: The Case of Pardubice Micro-Region[END_REF]:

• π Α (x)=0, then the output of IF-inference system y η =(1-π Α (x)) × y μ (Takagi-Sugeno type FIS is characterized by membership function μ). • π Α (x)=1, then the output of IF-inference system y η =π Α (x) × y ν (Takagi-Sugeno type FIS is characterized by non-membership function ν). • 0< π Α (x) <1, then the output of IF-inference system y η = (1-π Α (x)) × y μ + π Α (x) × y ν (Takagi-Sugeno type FIS is characterized by membership function μ and non-membership function ν).

Let x 1 ,x 2 , ... ,x j , ... ,x m be input variables FIS η defined on reference sets X 1 ,X 2 , ... ,X j , ... ,X m and let y η be an output variable defined on reference set Y. Then FIS η has m input variables x 1 ,x 2 , ... ,x j , ... ,x m and one output variable y η , where η=μ are membership functions (η=ν are non-membership functions).

Further, each set X j , j=1,2, ... ,m, can be divided into i=1,2, ... ,n fuzzy sets which are represented by following way η j,1 (x),η j,2 (x), ... ,η j,i (x), ... ,η j,n (x). Individual fuzzy sets, where η=μ are membership functions (η=ν are non-membership functions) represent a mapping of linguistic variables values which are related to sets X j . Then the k-th if-then rule R k in FIS η can be defined as follows

R k : if x 1 is A 1,i(1,k) η AND x 2 is A 2,i(2,k) η AND ... AND x j is A j,i(j,k) η AND ... AND x m is A m,i(m,k) η then y η =h, or y η =f(x 1 ,x 2 , ... ,x m ), j=1,2, ... ,m; i=1,2, ... ,n, (1)
where

A 1,i(1,k) η ,A 2,i(2,k) η , ... ,A j,i(j,k) η , ... ,A m,i(m,k)
η represent the values of linguistic variable for FIS μ and FIS ν , h is constant, f(x 1 ,x 2 , ... ,x m ) is a linear or polynomial function.

Intuitionistic Fuzzy t-norms and t-conorms

Let there be given two fuzzy sets which are defined in the same universe. Then it is possible to realize operations between them, i.e. such forms of projections (relations) where the result projects to the same universe. Within the fuzzy sets theory it is possible to define classes of operations where intersection is corresponded by t-norms and union by t-conorms. Therefore, definitions of the most important fuzzy sets operations are listed further [START_REF] Pedrycz | Fuzzy Control and Fuzzy Systems[END_REF][START_REF] Klement | Triangular Norms. Position Paper I: basic Analytical and Algebraic Properties[END_REF]. As well as union and intersection are dual operations, also t-norms and t-conorms are dual. Their relation can be defined as

T(x,y)=1-S((1-x), (1-y)), S(x,y)=1-T((1-x), (1-y)). ( 2
)
Based on the introduced facts, it is possible to define stated t-norms and t-conorms which always create pairs (one t-norm and one t-conorm). Examples of t-norms and tconorms are listed in Table 1. The analysis in [START_REF] Klement | Triangular Norms. Position Paper I: basic Analytical and Algebraic Properties[END_REF] implies that t-norms and t-conorms are characterized by different rate of strictness, or tolerance, where T D is the strictest tnorms and S D the most tolerant t-conorm. They can be ordered in the following way

T D ≤ T L ≤ T E ≤ T A ≤ T H ≤ T M and S M ≤ S H ≤ S A ≤ S E ≤ S L ≤ S D . (3)
Fuzzy sets have associated a non-membership function ν A (x) degree Let be given an automorphism [START_REF] Barrenechea | Generalized Atanassov's Intuitionistic Fuzzy Index. Construction Method[END_REF] of the unit interval, i.e. every function ψ : [0,1] →[0,1], that is continuous and strictly increasing such that ψ(0)=0 and ψ(1)=1. Further, let be given a function n: [0,1] → [0,1] in such a way that it holds n(0) =1 and n(1) =0. It is called a strong negation and it is always strictly decreasing, continuous and involutive. Then, as proved by [START_REF] Barrenechea | Generalized Atanassov's Intuitionistic Fuzzy Index. Construction Method[END_REF], n: [0,1] → [0,1] is a strong negation if and only if there exists an automorphism ψ of the unit interval such that n(x) = ψ -1 (1ψ(x)). Let L * be a set for which L * ={(x,y)|(x,y)∈[0,1] × [0,1] and x+y≤1} [START_REF] Zadeh | Fuzzy Sets[END_REF] and the elements 0 L* =(0,1) and 1 L* =(1,0). Then ∀((x,y),(z,t))∈L * it holds:

A={〈x, μ A (x),ν A (x)〉| x∈X}={〈x, μ A (x),1-μ A (x)〉| x∈X}. ( 4
)
-(x,y) ≤ L* (z,t) iff x≤z and y≥t. This relation is transitive, reflexive and antisymmetric.

-(x,y) = (z,t) iff (x,y) ≤ L* (z,t) and (z,t) ≤ L* (x,y), (x,y)≼ (z,t) iff x≤z and y≤t.

The designed IF-inference system of Takagi-Sugeno type works with the inference mechanism, based on intuitionistic fuzzy t-norm and t-conorm, by means of t-norm and t-conorm [START_REF] Deschrijver | On the Representation of Intuitionistic Fuzzy tnorm and t-conorm[END_REF] on interval [0,1]. A function T: (L * ) 2 → L * is called intuitionistic fuzzy t-norm if it is commutative, associative, and increasing in both arguments with respect to the order ≤ L* and with neutral element 1 L* . Similarly, a function S: (L * ) 2 → L * is called intuitionistic fuzzy t-conorm if it is commutative, associative, and increasing with neutral element 0 L* . Intuitionistic fuzzy t-norm T is called trepresentable if and only if there exists a t-norm T and t-conorm S on interval [0,1] such that ∀(x,y),(z,t)∈L * it holds T((x,y),(z,t)) =(T(x,z),S(y,t)) ∈L * .

Intuitionistic fuzzy t-norm and t-conorm can be constructed using t-norms and tconorms on [0,1] in the following way.

Let T be a t-norm and S a t-conorm. Then the dual t-norm S* of S is defined by S*(x,y)=1-S(1-x,1-y), ∀x,y∈[0,1]. If T≤ S*, i.e. if ∀x,y∈[0,1], T(x,y) ≤ S*(x,y), then the mapping T defined by T(x,y)=(T(x 1 ,y 1 ),S(x 2 ,y 2 )), ∀x,y∈L * , is an intuitionistic fuzzy t-norm and the mapping S defined by S(x,y)=(S(x 1 ,y 1 ),T(x 2 ,y 2 )), ∀x,y∈L * , is an intuitionistic fuzzy t-conorm. Note that condition T≤ S* is necessary and sufficient for T(x,y) and S(x,y) to be elements of L * ∀x,y∈L * . It can be written that T=(T,S) and S=(S,T).

Modelling and Analysis of the Results

Verification of behaviour of various t-norms and t-conorms in designed IF-inference system of Takagi-Sugeno type is shown in ozone modelling. The data for our investigations was obtained from the Czech Hydro-meteorological Institute. This data contains the average daily ozone measurements and the average daily meteorological variables (such as temperature, wind speed, wind direction, humidity, air pressure and solar radiation), vehicle emission variables (NO 2 , CO, NO, NO x , SO 2 , PM 10 and PM 2.5 ), and other dummy variables (working day, month). All the measured variables used in this study are actual same day values. Then the formulation of the basic model is following:

y = f(x 1 t ,x 2 t , … ,x m t
), m=22, where y is daily average ozone level at time t+1. For further modelling it is necessary to minimize the number of parameters x m t , m=22, and to maximize function f.

Based on the minimization of the number of parameters x m t , m=22 using Pearson's correlation coefficient, it was shown that NO x , NO, NO 2 , month of measurement, humidity, solar radiation, and the ozone level at day ahead were important to predict daily average ozone levels. The general formulation of the model is as follows y , m=7 in time t are represented by two bell-shaped membership functions μ for FIS μ and two non-membership functions ν for FIS ν . Membership function μ and non-membership function ν, and if-then rules were designed using subtractive clustering algorithm. After projecting the clusters onto the input space, the antecedent parts of the fuzzy if-then rules can be found. The consequent parts of the if-then rules are represented by polynomial functions y=f(x 1 ,x 2 , ... ,x r ). In this way, one cluster corresponds to one if-then rule. To be specific, two if-then rules are designed for FIS μ and FIS ν respectively. The output level y k of each of the k-th if-then rule R k is weighted. The final outputs y μ and y ν of the FIS μ and FIS ν are the weighted averages of all the if-then rule R k outputs y k , k=1,2, … ,N. The output of IF-inference system is represented by the predicted value y η in time t+1. Table 2 shows the quality of ozone prediction represented by Root Mean Squared Error (RMSE η ) for different values of μ max [START_REF] Olej | IF-Inference Systems Design for Prediction of Ozone Time Series: The Case of Pardubice Micro-Region[END_REF], different values of IF-index π and for various t-norms. The resulting errors are comparable to those presented in other studies, for example [START_REF] Comrie | Comparing Neural Networks and Regression Models for Ozone Forecasting[END_REF]. Extreme situations of the IF-inference system are to be found when IF-index π Α (x) = 0 (Table 3), then μ A (x) + ν A (x) = 1 (fuzzy sets are considered as a particular case IFsets) and if IF-index π Α (x) = 1, then μ A (x) = 0 and ν A (x) = 0 (complete ignorance of the problem). For π Α (x) = 0, RMSE μ =RMSE η . Thus, only RMSE μ are reported.

= f(x 1 t ,x 2 t , … ,x m t ),
Drastic T D and bounded T L t-norms are not suitable for this IF-inference system design. The problem with drastic T D and bounded T L t-norms is that it can happen that no rule is activated. When no rule is activated, the output of the system is constant, which can be interpreted as some kind of neutral output. Strictness of these t-norms is crucial for this type of data. Based on designed IF-inference systems with t-norms T D and T L , it is implied that RMSE η for FIS η is constant. For other designed IF-inference systems with t-norms T E ,T A ,T H ,T M , RMSE η for FIS η are given by Table 2.

Conclusion

The development of effective prediction models of ozone concentrations in urban areas is important. However, it is difficult because the meteorological parameters and photochemical reactions involved in ozone formation are complex. The article compares IF-inference systems of Takagi-Sugeno type [START_REF] Olej | IF-Inference Systems Design for Prediction of Ozone Time Series: The Case of Pardubice Micro-Region[END_REF] for various fuzzy operators in if-then rules with the help of RMSE η for FIS η on testing data O test . RMSE η represents the error of IF-inference system, which consists of RMSE μ for FIS μ , which is represented by membership function μ, and error RMSE ν for FIS ν , which is represented by non-membership function ν. Further, extreme situations in the designed IF-inference systems from the viewpoint of IF-index are shown.

Table 1 .

 1 Examples of t-norms and t-conorms

	Name		t-norm, t-conorm	Notes
	Drastic	product	T D (x,y)= min(x,y) if max(x,y)=1
			0 otherwise
		sum	S D (x,y)= max(x,y) if min(x,y)=0
			1 otherwise
	Bounded	difference T L (x,y)=max(0, x+y-1)	Łukasiewicz t-norm
		sum	S L (x,y)=min(1, x+y)	Łukasiewicz t-conorm
	Einstein	product	T E (x,y)=(x.y)/((2-(x+y-x.y))
		sum	S E (x,y)=(x+y)/(1+x.y)
	Algebraic	product	T A (x,y)=x.y	Algebraic product
	Probabilistic sum	S A (x,y)=x+y-x.y	Probabilistic sum
	Hamacher	product	T H (x,y)=(x.y)/(x+y-x.y)
		sum	S H (x,y)=(x+y-2.x.y)/(1-x.y)
	MIN, MAX	min	T M (x,y)=min(x,y)	Gödel t-norm
		max	S M (x,y)=max(x,y)	Gödel t-conorm

  m=7, where y is daily average ozone level at time t+1, x 1 Based on the given facts, such FIS μ is designed which is characterized by means of membership function μ, and FIS ν characterized by non-membership function ν. Input

	nitrogen, x 2 t is nitric oxide, x 3 t is nitrogen dioxide, x 4 t is dummy variable (month), x 5 t is humidity, x 6 t is solar radiation, x 7 t is daily average ozone level at time t.
	variables x 1 t ,x 2 t , … ,x m	t
		t is oxide of

Table 2 .

 2 RMSE η on testing data O test for different values of μ max , IF-index π, and T E ,T A ,T H ,T M

	π=0.1 μ max	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
	T E	23.23	24.00	25.30	26.96	28.64	30.78	34.60	42.24	21.43
	T A	23.08	23.55	24.17	25.01	26.19	27.85	30.46	35.07	19.81
	T H	16.99	18.02	18.85	19.33	19.35	18.83	17.74	15.95	13.31
	T M π=0.2	-	11.01	11.06	11.06	11.06	11.06	11.05	11.04	10.94
	T E	22.09	24.05	27.27	31.29	36.04	43.92	60.82	30.27
	T A	21.65	22.70	24.30	26.69	30.25	35.78	46.63	25.14
	T H	16.33	17.37	18.30	18.98	19.21	18.78	17.12	13.41
	T M	-	10.90	10.93	10.93	10.92	10.92	10.91	11.63
	...
	π=0.8
	T E	42.26	112.1
	T A	37.99	108.1
	T H	15.64	25.08
	T M	12.22	26.78

Table 3 .

 3 RMSE on testing data O test for different values of μ max , IF-index π=0, and T E ,T A ,T H ,T M

	μ max	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
	T E RMSE μ 24.72	24.69	24.65	24.57	24.47	24.34	24.19	24.03	23.92
	RMSE ν 15.94 T A RMSE μ 24.72	15.07 24.72	30.33 24.72	56.82 24.72	81.50 24.72	106.00 139.60 196.30 24.72 24.72 24.72	292.60 24.71
	RMSE ν 16.65 T H RMSE μ 17.70	16.02 18.59	19.93 19.20	29.51 19.44	42.78 19.22	59.53 18.54	81.41 17.42	115.70 16.05	169.90 14.76
	RMSE ν 15.76 T M RMSE μ -	16.75 11.29	20.53 11.29	24.35 11.29	27.18 11.29	28.84 11.29	29.08 11.29	27.06 11.29	19.59 11.29
	RMSE ν	-	13.92	13.25	13.36	13.33	13.30	13.31	13.40	13.70

Acknowledgments. This work was supported by the scientific research project of the Ministry of Environment, the Czech Republic under Grant No: SP/4i2/60/07.


Hosein Alizadeh
email: halizadeh@iust.ac.ir

Behrouz Minaei
email: b_minaei@iust.ac.ir

Hamid Parvin
email: parvin@iust.ac.ir

A New Criterion for Clusters Validation

Keywords: Clustering Ensemble, Stability Measure, Cluster Evaluation

In this paper a new criterion for clusters validation is proposed. This new cluster validation criterion is used to approximate the goodness of a cluster. The clusters which satisfy a threshold of this measure are selected to participate in clustering ensemble. For combining the chosen clusters, a coassociation based consensus function is applied. Since the Evidence Accumulation Clustering method cannot derive the co-association matrix from a subset of clusters, a new EAC based method which is called Extended EAC, EEAC, is applied for constructing the co-association matrix from the subset of clusters. Employing this new cluster validation criterion, the obtained ensemble is evaluated on some well-known and standard data sets. The empirical studies show promising results for the ensemble obtained using the proposed criterion comparing with the ensemble obtained using the standard clusters validation criterion.

Introduction

Data clustering or unsupervised learning is an important and very difficult problem. The objective of clustering is to partition a set of unlabeled objects into homogeneous groups or clusters [START_REF] Faceli | Multi-objective Clustering Ensemble[END_REF]. Clustering techniques require the definition of a similarity measure between patterns. Since there is no prior knowledge about cluster shapes, choosing a specific clustering method is not easy [START_REF] Roth | A Resampling Approach to Cluster Validation[END_REF]. Studies in the last few years have tended to combinational methods. Cluster ensemble methods attempt to find better and more robust clustering solutions by fusing information from several primary data partitionings [START_REF] Lourenco | Cluster Ensemble Methods: from Single Clusterings to Combined Solutions[END_REF].

Fern and Lin [START_REF] Fern | Cluster Ensemble Selection[END_REF] have suggested a clustering ensemble approach which selects a subset of solutions to form a smaller but better-performing cluster ensemble than using all primary solutions. The ensemble selection method is designed based on quality and diversity, the two factors that have been shown to influence cluster ensemble performance. This method attempts to select a subset of primary partitions which simultaneously has both the highest quality and diversity. The Sum of Normalized Mutual Information, SNMI [START_REF] Jain | Data Clustering Using Evidence Accumulation[END_REF]- [START_REF] Jain | Learning Pairwise Similarity for Data Clustering[END_REF] and [START_REF] Strehl | Cluster ensembles -a knowledge reuse framework for combining multiple partitions[END_REF] is used to measure the quality of an individual partition with respect to other partitions. Also, the Normalized Mutual Information, NMI, is employed for measuring the diversity among partitions. Although the ensemble size in this method is relatively small, this method achieves significant performance improvement over full ensembles. Law et al. proposed a multi objective data clustering method based on the selection of individual clusters produced by several clustering algorithms through an optimization procedure [START_REF] Law | Multiobjective data clustering[END_REF]. This technique chooses the best set of objective functions for different parts of the feature space from the results of base clustering algorithms. Fred and Jain [START_REF] Jain | Learning Pairwise Similarity for Data Clustering[END_REF] have offered a new clustering ensemble method which learns the pairwise similarity between points in order to facilitate a proper partitioning of the data without the a priori knowledge of the number of clusters and of the shape of these clusters. This method which is based on cluster stability evaluates the primary clustering results instead of final clustering.

Alizadeh et al. have discussed the drawbacks of the common approaches and then have proposed a new asymmetric criterion to assess the association between a cluster and a partition which is called Alizadeh-Parvin-Moshki-Minaei criterion, APMM. The APMM criterion compensates the drawbacks of the common method. Also, a clustering ensemble method is proposed which is based on aggregating a subset of primary clusters. This method uses the Average APMM as fitness measure to select a number of clusters. The clusters which satisfy a predefined threshold of the mentioned measure are selected to participate in the clustering ensemble. To combine the chosen clusters, a co-association based consensus function is employed [START_REF] Alizadeh | An Asymmetric Criterion for Cluster Validation[END_REF].

Proposed Method

The main idea of our proposed clustering ensemble framework is utilizing a subset of best performing primary clusters in the ensemble, rather than using all of clusters. Only the clusters which satisfy a stability criterion can participate in the combination. The cluster stability is defined according to Normalized Mutual Information, NMI.

The manner of computing stability is described in the following sections in detail. After, a subset of the most stable clusters is selected for combination. This is simply done by applying a stability-threshold to each cluster. In the next step, the selected clusters are used to construct the co-association matrix. Several methods have been proposed for combination of the primary results [START_REF] Ayad | Cumulative Voting Consensus Method for Partitions with a Variable Number of Clusters[END_REF] and [START_REF] Strehl | Cluster ensembles -a knowledge reuse framework for combining multiple partitions[END_REF]. In our work, some clusters in the primary partitions may be absent (having been eliminated by the stability criterion). Since the original EAC method [START_REF] Jain | Data Clustering Using Evidence Accumulation[END_REF] cannot truly identify the pairwise similarity while there is only a subset of clusters, we present a new method for constructing the co-association matrix. We call this method: Extended Evidence Accumulation Clustering method, EEAC. Finally, we use the hierarchical single-link clustering to extract the final clusters from this matrix.

Since goodness of a cluster is determined by all the data points, the goodness function g j (C i ,D) depends on both the cluster C i and the entire dataset D, instead of C i alone. The stability as measure of cluster goodness is used in [START_REF] Lange | Stability-based model selection[END_REF]. Cluster stability reflects the variation in the clustering results under perturbation of the data by resampling. A stable cluster is one that has a high likelihood of recurrence across multiple applications of the clustering method. Stable clusters are usually preferable, since they are robust with respect to minor changes in the dataset [START_REF] Law | Multiobjective data clustering[END_REF].

Now assume that we want to compute the stability of cluster C i . In this method first a set of partitionings over resampled datasets is provided which is called the reference set. In this notation D is resampled data and P(D) is a partitioning over D. Now, the problem is: "How many times is the cluster C i repeated in the reference partitions?" Denote by NMI(C i ,P(D)), the Normalized Mutual Information between the cluster C i and a reference partition P(D). Most previous works only compare a partition with another partition [START_REF] Strehl | Cluster ensembles -a knowledge reuse framework for combining multiple partitions[END_REF]. However, the stability used in [START_REF] Law | Multiobjective data clustering[END_REF] evaluates the similarity between a cluster and a partition by transforming the cluster C i to a partition and employing common partition to partition methods. To illustrate this method let P 1 = P a ={C i ,D/C i } be a partition with two clusters, where D/C i denotes the set of data points in D that are not in C i . Then we may compute a second partition P 2 =P b ={C * ,D/C * }, where C * denotes the union of all "positive" clusters in P(D) and others are in D/C * . A cluster C j in P(D) is positive if more than half of its data points are in C i . Now, define NMI(C i ,P(D)) by NMI(P a ,P b ) which is defined in [START_REF] Jain | Combining Multiple Clusterings Using Evidence Accumulation[END_REF]. This computation is done between the cluster C i and all partitions available in the reference set. NMI i stands for the stability of cluster C i with respect to the i-th partition in reference set. The total stability of cluster C i is defined as:

∑ = = M i i i NMI M C Stability 1 1 ) ( 1
where M is the number of partitions available in reference set. This procedure is applied for each cluster of every primary partition. Here a drawback of computing stability is introduced and an alternative approach is suggested which is named Max method. Fig. 1 shows two primary partitions for which the stability of each cluster is evaluated. In this example K-means is applied as the base clustering algorithm with K=3. For this example the number of all partitions in the reference set is 40. In 36 partitions the result is relatively similar to Here the drawback of the stability measure is apparent rarely. Although it is obvious that this partition and the corresponding large cluster on the right reference set (10% repetition), the stability of this cluster is evaluated equal to 1. Since the NMI is a symmetric equation, the stability of the top left cluster in Fig 1 .a is exactly equal to the large right cluster in Fig 1 .b; however they are repeated 90% and 10%, respectively. In other words, when two clusters are complements of each other, their stabilities are always equal. This drawback is seen when the number of positive clusters in the considered partition of reference set is greater than 1. It means when the cluster C* is obtained by merging two or more clusters, undesirable stability effects occur.

To solve this problem we allow only one cluster in reference set to be considered as the C* (i.e. only the most similar cluster) and all others are considered as D/C*. In this method the problem is solved by eliminating the merged clusters.

In the following step, the selected clusters are used to construct the co-association matrix. In the EAC method the m primary results from resampled data are accumulated in an n×n co-association matrix. Each entry in this matrix is computed from this equation:

j i j i m n j i C , , ) , ( = 2
where n ij counts the number of clusters shared by objects with indices i and j in the partitions over the primary B clusterings. Also m ij is the number of partitions where this pair of objects is simultaneously present. There are only a fraction of all primary clusters available, after thresholding. So, the common EAC method cannot truly recognize the pairwise similarity for computing the co-association matrix. In our novel method (Extended Evidence Accumulation Clustering, or EEAC) each entry of the co-association matrix is computed by: ) , max( ) , ( ,

j i j i n n n j i C = 3
where n i and n j are the number present in remaining (after stability thresholding) clusters for the i-th and j-th data points, respectively. Also, n ij counts the number of remaining clusters which are shared by both data points indexed by i and j, respectively.

Experimental Results

This section reports and discusses the empirical studies. The proposed method is examined over 5 different standard datasets. Brief information about the used datasets is available in [START_REF] Newman | UCI repository of machine learning databases[END_REF]. All experiments are done over the normalized features. It means each feature is normalized with mean of 0 and variance of 1, N(0, 1). All of them are reported over means of 10 independent runs of algorithm. The final performance of the clustering algorithms is evaluated by re-labeling between obtained clusters and the ground truth labels and then counting the percentage of the true classified samples. Table 1 shows the performance of the proposed method comparing with most common base and ensemble methods. The first four columns of Table 1 are the results of some base clustering algorithms. The results show that although each of these algorithms can obtain a good result over a specific dataset, it does not perform well over other datasets. The four last columns show the performance of some ensemble methods in comparison with the proposed one. Taking a glance at the last four columns in comparison with the first four columns shows that the ensemble methods do better than the simple based algorithms in the case of performance and robustness along with different datasets. The first column of the ensemble methods is the results of an ensemble of 100 Kmeans which is fused by EAC method. The 90% sampling from dataset is used for creating diversity in primary results. The sub-sampling (without replacement) is used as the sampling method. Also the random initialization of the seed points of K-means algorithm helps them to be more diverse. The single linkage algorithm is applied as consensus function for deriving the final clusters from co-association matrix. The second column from ensemble methods is the full ensemble which uses several clustering algorithms for generating the primary results. Here, 70 K-means with the above mentioned parameters in addition to 30 linkage methods provide the primary results. The third column of Ensemble Methods is consensus partitioning using EEAC algorithm of top 33% stable clusters, employing NMI method as measure of stability. The fourth column of the ensemble methods is also consensus partitioning using EEAC algorithm of top 33% stable clusters, employing max method as measure of stability.

Conclusion and Future Works

In this paper a new clustering ensemble framework is proposed which is based on a subset of total primary spurious clusters. Also a new alternative method for common NMI is suggested. Since the quality of the primary clusters are not equal and presence of some of them can even yield to lower performance, here a method to select a subset of more effective clusters is proposed. A common cluster validity criterion which is needed to derive this subset is based on normalized mutual information. In this paper some drawbacks of this criterion is discussed and a method is suggested which is called max mehod. The experiments show that the proposed framework commonly outperforms in comparison with the full ensemble; however it uses just 33% of primary clusters. Also the proposed max criterion does slightly better than NMI criterion generally. Because of the symmetry which is concealed in NMI criterion and also in NMI based stability, it yields to lower performance whenever symmetry is also appeared in the dataset. Another innovation of this chapter is a method for constructing the co-association matrix where some of clusters and respectively some of samples do not exist in partitions. This new method is called Extended Evidence Accumulation Clustering, EEAC.

Fig. 1

 1 Fig.1 Two primary partitions with k=3. (a) True clustering. (b) Spurious clustering.

  Fig 1a, but there are four partitions in which the top left cluster is divided into two clusters, as shown in Fig 1b. Fig 1a shows a true clustering. Since the well separated cluster in the top left corner is repeated several times (90% repetition) in partitionings of the reference set, it has to acquire a great stability value (but not equal to 1), however it acquires the stability value of 1. Because the two clusters in right hand of Fig 1a are relatively joined and sometimes they are not recognized in the reference set as well, they have less stability value. Fig. 1.b shows a spurious clustering which the two right clusters are incorrectly merged. Since a fixed number of clusters are forced in the base algorithm, the top left cluster is divided into two clusters.

Table 1 .

 1 Experimental results.

			Simple Methods (%)			Ensemble Methods (%)
	Dataset	Single Linkage	Average Linkage	Complete Linkage	Kmeans	Kmeans Ensemble	Full Ensemble	Cluster Selection by NMI Method	Cluster Selection by max Method
	Wine	37.64	38.76	83.71	96.63	96.63	97.08	97.75	97.44
	Breast-C	65.15	70.13	94.73	95.37	95.46	95.10	95.75	96.49
	Yeast	34.38	35.11	38.91	40.20	45.46	47.17	47.17	51.27
	Glass	36.45	37.85	40.65	45.28	47.01	47.83	48.13	47.35
	Bupa	57.68	57.10	55.94	54.64	54.49	55.83	58.09	58.40