Marcin Lewandowski
email: marcin.lewandowski@us.edu.pl

Bartłomiej Płaczek
email: placzek.bartlomiej@gmail.com

Marcin Bernas
email: marcin.bernas@gmail.com

Self-organizing traffic signal control with prioritization strategy aided by vehicular sensor network

Keywords: vehicular sensor networks, self-organizing systems, traffic signal control, priority vehicles

Preemption strategies are necessary for traffic signal control at intersections in a road network to ensure minimum delay of priority vehicles, such as ambulances or police cars. This paper introduces a decentralized algorithm, which extends the self-organizing signal control to provide preemption for the priority vehicles. The introduced algorithm enables effective utilisation of real-time data collected in vehicular sensor network (VSN). Results of simulation experiments show that the proposed approach ensures a quick passage of the priority vehicles and minimizes the negative effect of signal preemption on delays of non-priority vehicles. The new VSN-aided preemption strategy improves performance of the state-of-the-art methods that are based on road-side vehicle detectors and simple vehicle-to-infrastructure communication systems.

Introduction

Effective traffic signal control is a key element of intelligent transport systems, which improves utilization of the existing road infrastructure and increases its capacity [START_REF] Celiński | Traffic signal control system with extended logic in the context of the modal split[END_REF]. State-of-the-art traffic control approaches are based on centralized techniques that require global information about traffic conditions in the considered road network. The centralized traffic control methods are computationally complex and inherently non-scalable. Low scalability of the centralized control algorithms has motivated the current interest in decentralized self-organizing traffic control [START_REF] Kano | Autonomous Decentralized Control of Traffic Signals that can Adapt to Changes in Traffic[END_REF][START_REF] Płaczek | A Cellular Automata Approach for Simulation-Based Evolutionary Optimization of Self-Organizing Traffic Signal Control[END_REF]. The self-organizing traffic signals are controlled independently for each intersection in the network on the basis of real-time traffic information obtained from local measurements. The information required by self-organizing traffic control describes current traffic conditions at road segments connected to a particular intersection.

Recent advances in vehicular sensor networks (VSNs) facilitate wireless data transfer between vehicles and infrastructure [START_REF] Younes | Intelligent Traffic Light Controlling Algorithms Using Vehicular Networks[END_REF][START_REF] Płaczek | Selective data collection in vehicular networks for traffic control applications[END_REF][START_REF] Płaczek | Optimizing Data Collection for Object Tracking in Wireless Sensor Networks[END_REF]. The vehicles in VSN can collect detailed and useful information regarding their current positions and velocities. The collected data can be then transmitted via wireless communication to a control unit at the nearest intersection. This technology enables cost-effective collection of the local traffic information in real-time. The increased availability of detailed real-time traffic information results in high application potential of the VSN-aided self-organizing traffic control.

This paper focuses on performance analysis of the self-organizing traffic control with a preemption strategy. The aim of signal preemption strategies is to efficiently clear the paths for priority vehicles, such as ambulances, police cars, fire engines, transit buses, light rail vehicles, snow ploughs, etc [START_REF] Nellore | Traffic Management for Emergency Vehicle Priority Based on Visual Sensing[END_REF][START_REF] Zhanga | Performance Measure for Reliable Travel Time of Emergency Vehicles[END_REF][START_REF] Yang | Performance of the Priority Control Strategies for Bus Rapid Transit: Comparative Study from Scenario Microsimulation Using VISSIM[END_REF]. Preemption interrupts normal signal operations to serve the priority vehicle as soon as possible with little or no delay [START_REF] Zamanipour | Efficient Priority Control Model for Multimodal Traffic Signals[END_REF]. An algorithm is proposed in this paper, which extends the self-organizing signal control to provide preemption for priority vehicles. The objective of the proposed algorithm is to ensure a quick passage of the priority vehicles and minimize the negative effect of signal preemption on delays of non-priority vehicles.

Performance of the proposed algorithm was examined in a simulation environment with application of different self-organizing control strategies from the literature. Two scenarios for the preemption strategy were considered during the simulation experiments. In the first scenario a priority vehicle sends preemption request to the traffic control unit as it approaches the intersection and the control unit responds immediately by switching traffic lights. This scenario corresponds to the current solutions that utilize the vehicle-to-infrastructure (V2I) communication [START_REF] Noori | Impact of VANET-Based Traffic Signal Control on the Response Time of Emergency Vehicles in Realistic Large Scale Urban Area[END_REF][START_REF] Bernas | VANETs as a Part of Weather Warning Systems[END_REF]. The new approach with VSN-aided preemption is considered in the second scenario. In this case, the traffic lights are not switched immediately, when the request from priority vehicle is received. Instead, the traffic control unit evaluates time of preemption operation, which allows the priority vehicle to pass the intersection without stopping. This evaluation is based on real-time information about vehicles position delivered from VSN.

The paper is organized as follows. Related works are discussed in Section 2. Section 3 introduces the proposed method. Results of simulation experiments are presented in Section 4. Finally, conclusions are given in Section 5.

Related works

Several decentralized control approaches for the self-organizing traffic signals have been proposed in the related literature. An advantage of the self-organizing methods discussed in this section is high scalability, which is ensured as these methods do not require any central controller and do not involve communication between local control units at intersections.

A simple algorithm for self-organizing traffic lights (SOTL) was presented in [START_REF] Cools | Self-organizing traffic lights: A realistic simulation in: Advances in Applied Self-Organizing Systems[END_REF]. According to this algorithm, a preference is given to vehicles that have been waiting longer, and to larger groups of vehicles (platoons). The experimental results reported in [START_REF] Zhang | A comparative study of Macroscopic Fundamental Diagrams of arterial road networks governed by adaptive traffic signal systems[END_REF] show that SOTL can achieve higher performance and increase the network capacity in comparison to the conventional Sydney Coordinated Adaptive Traffic System.

A more sophisticated self-organizing traffic control method was introduced by Lämmer and Helbing [START_REF] Lämmer | Self-control of traffic lights and vehicle flows in urban road networks[END_REF]. This method takes into account priorities that correspond to expected number of vehicles entering the intersection during a given time horizon. The expected numbers of vehicles are determined in this method by short-term traffic flow prediction based on a macroscopic fluid-dynamic model. Experimental comparison of this method with conventional adaptive control in a real-world road network revealed higher effectiveness of the self-organizing approach. Another work along these lines [START_REF] Płaczek | A self-organizing system for urban traffic control based on predictive interval microscopic model[END_REF] introduces a self-organizing traffic signal system, where an interval microscopic traffic model is used to predict effects of possible control actions in a short time horizon. Back-pressure [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF] is a control strategy for the self-organizing traffic signals, which takes into account differences in traffic load on the road leading into the intersection and those leading out. The back-pressure method was originally proposed for routing algorithms in wireless networks as a decentralized scheme, which can provide maximum network throughput under the assumptions that all links in the network have infinite capacities. This concept was then adapted to urban road networks for signal control.

In [START_REF] Placzek | A Cellular Automata Approach for Simulation-Based Evolutionary Optimization of Self-Organizing Traffic Signal Control[END_REF] a cellular automata model of self-organizing traffic signal system was proposed, which enables evolutionary optimization of control rules that rely on adaptation to local variations in traffic state and enable effective coordination of the vehicular traffic at a network level. Fitness function, which guides the evolution of control rules, is evaluated in this approach via traffic simulation by using a microscopic cellular automata model.

A physic-based self-organizing control scheme for traffic signals was proposed in [START_REF] Kano | Autonomous Decentralized Control of Traffic Signals that can Adapt to Changes in Traffic[END_REF]. This method uses "virtual impulses" given by red signals or preceding cars, which are defined in a similar manner as the impulses used in physics. The virtual impulses are calculated at each traffic signal by using an optimal velocity model. They characterize to what extent vehicles will slow down owing to the existence of the preceding cars or red signals. The traffic signals are switched to reduce these virtual impulses.

A considerable research has also been devoted to signal preemption strategies that utilize V2I communication. Such strategies allow priority vehicles to send green light requests to traffic control units when approaching signalized intersections. The ZigBee communication was used in [START_REF] Sundar | Implementing Intelligent Traffic Control System for Congestion Control, Ambulance Clearance, and Stolen Vehicle Detection[END_REF] for emergency vehicle clearance. According to that simple solution, the control unit at an intersection switches the traffic signals immediately, when it receives a preemption request from the emergency vehicle. The traffic lights are switched back to the normal operation once the priority vehicle passes through, and the control unit no longer receives the ZigBee signal.

Another simple preemption strategy was studied in [START_REF] Noori | Impact of VANET-Based Traffic Signal Control on the Response Time of Emergency Vehicles in Realistic Large Scale Urban Area[END_REF] with application of the WAVE standard (IEEE 802.11p). According to this method the distance between the emergency car and the traffic lights is calculated in discrete time steps. If the distance is less than the specified value (which is defined in advance), the traffic light status changes to green for the emergency vehicle and red for the other cars. After the emergency vehicle passes the traffic light (with a distance of 20 meters) the traffic light status returns to its original state.

In [START_REF] Noori | A Connected Vehicle Based Traffic Signal Control Strategy for Emergency Vehicle Preemption[END_REF] a signal control strategy was proposed, which decreases response time of emergency vehicles by employing V2I communication and a beaconing concept based on the WAVE standard as well as the prediction of queue length. According to that strategy, the traffic signals are adjusted adaptively to provide an early green at the right time so that the queue at the downstream intersections can be served just in time for the arrival of an emergency vehicle.

When using the V2I communication, it is possible that multiple priority vehicles will send requests such that there may be multiple active requests at the same time. An optimisation problem was formulated in [START_REF] He | Multi-modal traffic signal control with priority, signal actuation and coordination[END_REF] to explicitly accommodate the multiple priority requests from different modes of vehicles while simultaneously considering signal coordination and vehicle actuation.

In this paper a decentralized algorithm is proposed, which combines the selforganizing signal control with a preemption strategy. The introduced algorithm enables effective utilisation of real-time position and speed data collected from particular vehicles in VSN.

Proposed approach

This section introduces an algorithm, which allows the self-organizing signal control to provide preemption for priority vehicles. The objective of the preemption procedure is to serve the priority vehicles as soon as possible with minimum negative impact on the delay of non-priority vehicles. To this end, the proposed procedure utilizes data collected in VSN. The considered VSN is composed of vehicle nodes and control units that take control decisions and manage traffic signals at intersections by using the self-organizing strategy. Vehicles are equipped with sensors that collect speed and position data. The collected information is periodically transmitted from vehicles to control units.

Pseudocode of the self-organizing traffic signal control algorithm with preemption is presented in Algorithm 1. The input data of this algorithm consists of parameters that describe the traffic streams passing through an intersection. Output of the algorithm is a control decision that determines which traffic lane (or lanes) should get a green signal for a subsequent time interval. The consecutive control decisions are taken in constant time steps. In order to take control decision, priorities are assigned to the traffic lanes approaching the intersection. The priorities for traffic lanes are calculated dynamically based on current traffic data delivered from VSN.

According to the proposed algorithm, a preemption_condition function is used to verify if a priority vehicle for which the preemption has to be executed immediately is present in given traffic lane (line 5 of the pseudocode). The preemption condition takes into account expected time in which the priority vehicle will reach the traffic signal (t R ) and the predicted time, which is necessary to clear the queue of vehicles in the considered lane (t C ). This condition is defined as follows:

t R t G + t C , (1)
where t G is required intergreen time between the green period terminating for traffic lanes that are losing right of way and the start of the green period for the lane where priority vehicle is detected. The intergreen time has to be introduced to ensure traffic safety. Signal reaching time is calculated as:

t R = d/v F , (2)
where d denotes distance of the priority vehicle to traffic signal and v F is desired speed of the priority vehicle, which is observed in low traffic (free flow) conditions and in the absence of traffic signals. The vehicle node calculates the desired speed based on collected historical sensor readings and reports it to the control unit. Queue clearance time is estimated by using the formula:

t C = n/s + t 0 , (3)
where n denotes number of vehicles in a queue ahead of the priority vehicle, s is saturation flow rate, i.e. the maximum number of vehicles that can pass through the intersection during a time unit, when the traffic signal is green, t 0 is the time lost at the beginning of green light, when vehicles are accelerating.

Algorithm 1 Self-organizing traffic signal control with preemption If preemption condition is satisfied for a given lane, then a priority of the preemption is calculated using the preemption_priority function. The preemption priority is useful for taking control decision when priority vehicles are approaching in two or more conflicting traffic lanes (that cannot get the right of way in the same time). This priority is calculated as follows:

preemption_priority = m t start G + t S + t end G , (4)
where m is number of priority vehicles in the given lane, t start G is intergreen time, which has to be introduced before giving green signal for the considered lane (t start G = 0 if the considered lane already has the green signal), t S is the green time necessary for the m priority vehicles to leave the intersection, and t end G denotes intergreen time after green signal for the considered lane. The above definition of the preemption priority is based on the approach presented in [START_REF] Lämmer | Self-control of traffic lights and vehicle flows in urban road networks[END_REF].

If the preemption condition is not satisfied for all traffic lanes, then the proposed algorithm uses the regular_priority function to calculate the priority of each lane in accordance with a selected state-of-the-art traffic control method. The regular_priority function also assures that all traffic lanes at the intersection will get the green signal at least once in a predetermined time period. In this study different definitions of the regular_priority function are taken into consideration, as discussed in the next section. These definitions correspond to various self-organizing traffic control methods from the literature.

During setup time, which includes the intergreen time and a minimum green time, the priority computation and decision making procedure is skipped because the service cannot be switched to another traffic lane.

Experiments

Simulation experiments were performed to compare effectiveness of the proposed VSN-aided preemption strategy with the state-of-the-art methods. Application of various self-organizing traffic control methods was considered in this study. The experimental results presented in this section concern delay and average speed of both the priority and non-priority vehicles. Based on these results, impact of priority vehicles on the performance of different self-organizing traffic control strategies is analysed.

Simulation setup

In this study the simulation experiments were conducted in SUMO (Simulation of Urban MObility) [START_REF] Sundar | Implementing Intelligent Traffic Control System for Congestion Control, Ambulance Clearance, and Stolen Vehicle Detection[END_REF]. SUMO is a widely recognized open-source traffic simulation package including a traffic simulator as well as supporting tools. The simulator is microscopic, space-continuous and time-discrete, providing a fair approximation of real world traffic scenarios. Topology of the simulated network is a lattice of 8 bidirectional roads with 16 signalized intersections. Schema of the simulated road network and an intersection example are presented in Fig. 1. During single run of simulation, the traffic intensity was changed from 0.02 to 0.14 vehicles per second. The vehicles were generated with the same intensity at each entrance of the road network. One simulation run corresponds to one hour. Percentage of the priority vehicles was changed between 0% and 3.5%. This percentage was determined for each one-hour simulation run. Two types of the priority vehicles were considered: slow, with maximum speed of 60 km/h, and fast, with the maximum speed of 72 km/h. Maximum speed of the non-priority vehicles was equal to 60 km/h. Results of the simulation include stop delays and average speeds of vehicles. The results were collected for four intersections in centre of the simulated road network. Traffic signals at the simulated intersections were controlled by using decentralized self-organizing algorithms. Six different signal control algorithms were implemented in the simulation environment (Tab. 1). These algorithms use three control strategies (SOTL, LH, and BP) to calculate the regular priorities for traffic lanes, when priority vehicles are absent.

The SOTL (Self-Organizing Traffic Lights) strategy [START_REF] Lämmer | Self-control of traffic lights and vehicle flows in urban road networks[END_REF] takes into account current counts of vehicles approaching an intersection. Each traffic signal has a counter, which is set to zero when the signal turns red and then it is incremented at each time step by the number of vehicles approaching this red signal. When the counter reaches a predetermined threshold, the traffic lane gets the highest priority. In order to prevent the traffic signals from switching too frequently, the minimum green time constraint is used. Another constraint in the SOTL strategy keeps the small groups of vehicles (platoons) together and allows for dividing the large platoons that would excessively block the traffic flow of intersecting streets. Pseudo-code of the SOTL strategy can be found in [START_REF] Cools | Self-organizing traffic lights: A realistic simulation in: Advances in Applied Self-Organizing Systems[END_REF]. In case of LH strategy [START_REF] Płaczek | A self-organizing system for urban traffic control based on predictive interval microscopic model[END_REF], which is based on the method introduced by Lämmer and Helbing, two control rules are used: optimization rule, and stabilisation rule. According to the optimization rule, a cost associated with providing green signal for a particular lane is predicted as a total increase of vehicle delay. The prediction is performed by using a microscopic traffic model, which is based on cellular automata. The traffic lane with minimum cost gets the highest priority. The objective of the stabilisation is to assure that all traffic lanes will get a green signal at least once in a maximum time period. More detailed information about the optimization and stabilisation rules can be found in [START_REF] Lämmer | Self-control of traffic lights and vehicle flows in urban road networks[END_REF].

The idea of BackPressure (BP) strategy [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF] is to compute pressures at every intersection of the network based on queue lengths and to give priority for traffic lanes with a high upstream pressure and a low downstream pressure. This strategy uses priorities that are proportional to the difference of queue lengths in traffic lanes leading into the intersection and those leading out. Pseudo-code of the BP strategy can be found in [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF].

The LH strategy uses a microscopic cellular automata model to map current positions and velocities of particular vehicles. Thus, this strategy can fully utilize the detailed data from VSN. In contrast, the SOTL and BP strategies are designed for cooperation with state-of-the-art road-side detectors that deliver information about vehicle counts and queue lengths in traffic lanes.

The signal control algorithms in Tab. 1 are categorized into two groups with regard to the preemption method. For the first group (SOTL1, LH1, and BP1) the state-of-the-art preemption method is used, which means that the preemption request is registered when the distance of priority vehicle to intersection is below a predetermined threshold. In case of many requests, the highest priority is assigned to the first registered request. This scenario corresponds to the current solutions that utilize the V2I communication or the road-side detectors. Utilization of the detailed VSN data (i.e., current position and speed of the priority vehicles) for preemption purposes is possible for the second group of algorithms (SOTL2, LH2, and BP2). These algorithms include the preemption condition and the preemption priority functions that were proposed in Sect. 3.

Experimental results

A signal preemption strategy should enable a quick passage of the priority vehicles with a minimum negative effect for the non-priority vehicles. The traffic simulations were conducted to evaluate average speed and stop delay of vehicles for the compared algorithms. In this section the simulation results are analysed to determine the impact of signal preemption on speed and delay of the non-priority vehicles.

Average delay and speed of non-priority vehicles for the considered algorithms are compared in Fig. 2. The lowest delay and the highest speed were observed for the LH algorithm, which utilizes the detailed data delivered from VSN. The algorithms designed for the state-of-the-art road-side detectors (SOTL and BP) have achieved a lower performance. When comparing the algorithms that employ the state-of -the-art preemption strategy (denoted by the suffix 1) with those implementing the proposed VSN-aided signal preemption (denoted by the suffix 2), it can be observed that the proposed approach ensures lower delay and increased speed of the vehicles. The introduced preemption strategy has decreased the average delay by 11% for algorithm LH, 6% for algorithm SOTL, and 2% for algorithm BP (Fig. 2 a). Moreover, the average speed was increased by 2% for LH and 1% for SOTL. In case of algorithm BP, the average speed remains at the same level (Fig. 2 b). The chart in Fig. 3 compares average speed of priority vehicles for the considered algorithms. These results show that the proposed VSN-aided preemption strategy does not decrease the average speed of priority vehicles for the LH algorithm. It means that the LH2 algorithm, which utilizes the data collected from VSN to the largest extent, allows the delay of non-priority cars to be reduced and at the same time ensures high speed of the priority vehicles. In case of SOTL and BP algorithms the reduced delay of non-priority cars is obtained at the cost of lower speed of the priority vehicles.

Detailed results of the simulation for LH and SOTL algorithms are presented in Figs. 4 and5. Each data point in these charts corresponds to results of onehour traffic simulation. For particular runs of the simulation, the model settings were adjusted in order to obtain different percentages of the priority vehicles. The results show that average delay of non-priority vehicles increases with the percentage of the priority vehicles. In contrary, average speed of non-priority cars decreases as the percentage of priority vehicles increases. Such dependencies have been observed for all analysed algorithms. Comparison of the results obtained for algorithm LH1 with those of algorithm LH2 (Fig. 4) confirms that the VSN-aided preemption strategy decreases the negative impact of priority vehicles on delay and speed of the non-priority vehicles. This effect can be observed for a wide range of percentages of priority vehicles. Similar observations are made when comparing the results of algorithms SOTL1 and SOTL2 (Fig. 5). The better results for the proposed preemption strategy (LH2 and SOTL2) are related to the fact that the required time of preemption operation, which allows the priority vehicle to pass the intersection without stopping, can be accurately evaluated by using the detailed data from VSN. Thus, the normal signal operations are interrupted for a shorter time than in case of the state-of-the-art preemption method, which takes into account only the distance of priority vehicle to the traffic signal.

Conclusion

The introduced traffic control algorithm with preemption strategy enables effective utilisation of the data collected from VSN, which describe positions and velocities of particular vehicles. These data allow the control unit to accurately decide when a signal preemption operation has to be executed in order to clear the path through intersection for a priority vehicle. As a consequence, the negative impact of signal preemption on the flow of non-priority vehicles can be minimized. Results of simulations show that the proposed VSN-aided preemption strategy improves performance of the state-of-the-art methods that were designed for cooperation with road-side vehicle detectors or simple V2I communication solutions. The proposed preemption strategy was combined with the self-organizing signal control method. Thus, the proposed algorithm is scalable and can be implemented in decentralized systems, where the traffic signals are controlled independently for a large number of intersections. Moreover, the input data for this algorithm have to be collected locally from vehicles at road segments connected directly to a particular intersection. It means that the cost of data collection in VSN can be kept at a low level. Further research is necessary to test the proposed approach in different scenarios with multimodal priority.

Fig. 1 .

 1 Fig. 1. Simulated road network.

Fig. 2 .

 2 Fig. 2. Average delay and average speed of non-priority vehicles for the compared algorithms.

Fig. 3 .

 3 Fig. 3. Average speed of priority vehicles for the compared algorithms.

Fig. 4 .

 4 Fig. 4. Average delay and average speed of non-priority vehicles for the LH algorithms.

Fig. 5 .

 5 Fig. 5. Average delay and average speed of non-priority vehicles for the SOTL algorithms.

Table 1 .

 1 Compared algorithms

	Algorithm	SOTL1 LH1	BP1	SOTL2 LH2 BP2
	Source of information
	about non-priority	RSD VSN Road-side detectors (RSD) VSN RSD
	vehicles
	Source of information about priority vehicles	RSD or V2I communication	VSN
	Preemption condition	Distance to signal	Time to reach signal
	Preemption priority	Order of requests	Minimum delay


Emanuel Tomasz

Rafal Wesolowski
email: tomasz.wesolowski@us.edu.pl

Krzysztof Doroz

Hossein Wrobel

Safaverdi

Tomasz Emanuel

Weso Lowski

Rafal Doroz
email: rafal.doroz@us.edu.pl

Krzysztof Wrobel
email: krzysztof.wrobel@us.edu.pl

Hossein Safaverdi
email: hossein.safaverdi@us.edu.pl

Keystroke Dynamics and Finger Knuckle Imaging Fusion for Continuous User Verification

Keywords: biometrics, keystroke dynamics, finger knuckle, user verification

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

Introduction

Increasing computer systems security is a crucial task in the world dominated by electronically stored personal data and sensitive information. The number of attacks is increasing year by year. Only within the years 2014 and 2015 the amount of individuals affected by security breaches, where sensitive personal data such as electronic health records were stolen, increased hundred times [START_REF] Wesolowski | Electronic Health Record Security Based on Ensemble Classification of Keystroke Dynamics[END_REF]. The attacks themselves are becoming more and more sophisticated. There is various kinds of cyber attacks therefore different cyber attack detection strategies have to be developed [START_REF] Raiyn | A survey of cyber attack detection strategies[END_REF]. Attacks can come from outside of the computer system but a big part of intrusions consists of insider attacks [START_REF] Salem | A survey of insider attack detection research[END_REF]. Hence the requirement for novel security measures is very high. As the main goal of biometrics is the automatic recognition of individuals based on the knowledge of their physical or behavioral characteristics, biometric methods are commonly used in IT security systems because of their high effectiveness.

Behavioral biometric methods use, among other things, an analysis of the movements of various manipulators (eg. a computer mouse [START_REF] Wesolowski | Computer User Verification Based on Mouse Activity Analysis[END_REF]) or the dynamics of typing on a computer keyboard (keystroke dynamics) [START_REF] Alsultan | Keystroke Dynamics Authentication: A Survey of Freetext Methods[END_REF][START_REF] Banerjee | Biometric Authentication and Identification Using Keystroke Dynamics: A survey[END_REF][START_REF] Rybnik | An Exploration of Keystroke Dynamics Authentication using Non-fixed Text of Various Length[END_REF][START_REF] Teh | A Survey of Keystroke Dynamics Biometrics[END_REF]]. An analysis of keystroke dynamics involves detection of a rhythm and habits of a computer user while typing on a keyboard [START_REF] Zhong | Keystroke Dynamics for User Authentication[END_REF]. As the result of such an analysis, a user profile is obtained that can then be used in the access authorization systems. In our approach the registration of the user activity while working with a keyboard is performed automatically and continuously in the background, without additionally involving a user. The data are captured on the fly and saved in text files on the ongoing basis. Based on these text logs keystroke dynamics analysis is performed in order to verify an active user's access permissions. The big advantage of the proposed method is that user verification can be performed continuously on the fly. To increase a protection level the proposed in this paper approach combines the keystroke dynamics with another biometric method based on finger knuckle pattern recognition. Image acquisition is performed using a dedicated device especially designed for this purpose [START_REF] Doroz | A New Personal Verification Technique Using Finger-Knuckle Imaging[END_REF].

An intrusion detection can be performed in various ways. Literature sources indicate among others methods based on a fuzzy approach [START_REF] Kudlacik | Fuzzy approach for intrusion detection based on user's commands[END_REF]. However more frequently proposed solutions are based on classifiers. The in this paper proposed approach is based on classification. Ensembles of classifiers are used to classify features derived from keystroke dynamics analysis and a single classifier approach is used with knuckle patterns.

The goal of the described research is to develop a real time user verification system based on fusion of keystroke dynamics and finger knuckle images analysis. However a method of analyzing the finger knuckle on the fly has not been developed yet as it needs a lot of resources to analyze the images in a real time. Before the decision was made it was necessary to verify, if it is worth investing time and resources in developing such a method and, if the fusion of keystroke dynamics and finger knuckle analysis is potentially interesting. Therefore the preliminary research was conducted to assess the potential of the above mentioned biometric methods fusion. This paper presents the preliminary results of an intruder detection system based on the introduced novel approach.

Proposed biometric user verification system

The proposed computer security approach involves two phases: legitimate user profiling and active user verification. In the first stage user profiling is performed that consists of recording a legitimate user activity while working with a keyboard and acquiring this user's finger knuckle images. Based on the acquired data user's profile is being established according to the procedures described in the following sections of this paper.

After establishing user's profile in the first stage the profile can be used for verification of an active user in the second stage. The proposed user verification model shown in Fig. 1 connects two methods of user verification. The introduced approach is based on the fusion of keystroke dynamics and knuckle analysis. For the purpose of the fusion the biometric user verification methods were chosen that according to the [START_REF] Wesolowski | Electronic Health Record Security Based on Ensemble Classification of Keystroke Dynamics[END_REF] for keystroke based approach and [START_REF] Doroz | A New Personal Verification Technique Using Finger-Knuckle Imaging[END_REF] for finger knuckle pattern analysis perform better than other methods described in literature. User activity should be verified continuously, in the background, while a user is performing his everyday tasks. To allow this, all keyboard events generated by the user are recorded and time dependencies between them are analyzed. The keystroke verification unit basing on the profiles of legitimate users and recorded activity of an at the moment active user establishes a decision if the activity belongs to a legitimate user. If the user has been successfully verified an access is granted and the verification procedure continues. In case the verification was not successful there is a suspicion that an active user is an intruder. Therefore an additional verification is made by means of knuckle pattern recognition unit after taking a picture of the user's finger knuckles. If the user has been successfully verified an access is granted and the verification procedure continues with the keystroke based verification. If, again, the verification has not been successful an access to resources is denied and the security breach alert is generated.

Keystroke based subsystem

Keystroke dynamics refers to a typing pattern of an individual which in practice constitutes a so called profile. In the proposed method a profile of a user contains information on a sequence of key events and time dependencies that occur between the key events. The advantage of the proposed profiling method is that activity data collecting and analyzing is performed continuously in the background which makes it practically transparent for a user. For this reason the profiling method can be used in Host-based Intrusion Detection Systems (HIDS) that analyze the logs with registered user activity in real time to detect an unauthorized access. For the purpose of the research the dedicated software for data acquisition was implemented. The software was designed to collect events generated by individuals (operators of computer systems) while working with a protected system. Proposed software works continuously in a background and records the user activity. The events are captured on the fly and saved in text files. The consecutive lines of the data file contain a sequence of events related to a user activity. Each line starts with the prefix describing a type of an event, followed by the timestamp of this event and an identifier of a key that generated the event. Possible values of prefix are: keyDown representing pressing of a key and keyUp for key release event. An example of a raw input data is presented in Fig. 2. Such a recorded raw data can be presented in a data vector form (1). Fig. 2: A fragment of an input dataset with recorded keyboard events Data of a single j-th keyboard event for a given user constitute a vector e j :

e j = [type j , t j , ω j ], (1)
where type ∈ {keyDown, keyU p} describes a type of a j-th event; t j is a timestamp of a given event; ω j is an identifier of a used key. Activity data analysis is carried out separately for each user identified in the system by user identifier uid. All vectors e j of the same user constitute this user activity dataset E uid . In practice a number of vectors e j is limited by period of time when the user activity was recorded. Data in this form are difficult to interpret because they do not provide directly in-formation on how a user interacts with a computer system. Therefore it is necessary to process the data to obtain characteristics of a user by extracting time dependencies between keyboard events generated while the user was working. It should be noted that during the user activity analysis not only single characters are taken into account but pairs of keys are analyzed as well (for example when writing capital letters). In the proposed method there are 113 separate keys and key pairs considered. Time dependencies were depicted as a difference of time between two keyboard events and were calculated according to the following rules. Time dependencies for single keys are represented by dwell times (time when a key stays pressed) and for pairs of keys by a delay time between two consecutive key down events of the overlapping keys (as shown in Fig. 3). In the next step time dependencies representing a use of the same key or key pair are grouped together. As, in total, there are 113 different keys and key pairs, there are also 113 separate time dependency groups G k , k = 1, ..., 113 considered. The allowed number of time dependencies stored in a single group is limited by the parameter g. Each time a number of time dependencies in any of the groups G k reaches g a feature vector F is created and this group that reached the limit is cleared. The value of parameter g = 15 has been determined experimentally.

Based on time dependencies stored in all previously formed groups G k a feature vector F = [f 1 , ..., f 113 ] is constructed as follows. The k-th element f k of the Fig. 3: Time dependencies between keyboard events vector F is calculated as the standard deviation of time dependencies stored in a k-th group G k . For a given user identified by uid (based on this user's input data set) more feature vectors F are created and a profile Φ uid = F uid 1 , F uid 2 , ..., F uid z describing the activity of a user in a computer system is constituted. The value of the parameter z = 100 has been determined experimentally. User's profile Φ uid is stored in the database to be used by a classification based intrusion detection module. User profiling method based on keystroke analysis used in this proposed approach is described in details in [START_REF] Wesolowski | Electronic Health Record Security Based on Ensemble Classification of Keystroke Dynamics[END_REF]. The keystroke verification system is based on three ensembles of classifiers EC a , a = 1, ..., 3. Each of them consists of four heterogeneous classifiers: Ψ (1) , Ψ (2) , Ψ (3) and Ψ (4) . The ensembles of classifiers EC a work simultaneously and each one of them is trained using a separate training set T S a (see Fig. 4) established by means of the Algorithm 1. The general structure of the proposed classification module is presented in Fig. 4.

Classifier Ψ

(1)

Ψ (3) Ψ (2)
Ψ

Classifier Ψ

Classifier Ψ

Classifier Ψ

Classifier Ψ

Classifier Ψ

Classifier Ψ

Classifier Ψ User verification consists in assigning a user to one of two possible classes: legitimate user or an intruder. A classifier Ψ maps the vector F of a given user to a class label c j , where j ∈ {1, 2}:

Ψ(F) → c j ∈ C. (2)
In the proposed approach, the classifiers Ψ (i) return a probability pi (c j |F), j ∈ {1, 2} that a given object F belongs to a class c j . At the input of the node Ψ

(Fig. 4) the following data matrix is introduced:

I (a) (F) =     p1 (c 1 |F) p1 (c 2 |F) p2 (c 1 |F) p2 (c 2 |F) p3 (c 1 |F) p3 (c 2 |F) p4 (c 1 |F) p4 (c 2 |F)     . (3)
Following the classification, each ensemble of classifiers EC a , a = 1, .., 3 generates a local decision Ψ

The class labels returned as a result of (4) are converted to numerical values according to the formula:

Ψ (a) (F) =    -1 if Ψ (a) (F) = c 1 +1 if Ψ (a) (F) = c 2 (5)
The results of each ensemble of classifiers EC a are stored in the set

L = { Ψ (1) (F), Ψ (2)
(F), Ψ

(F)}. On the basis of the set L the value of LS is determined [START_REF] Krawczyk | Cost-sensitive decision tree ensembles for effective imbalanced classification[END_REF].

LS(F) = 3 a=1 Ψ (a) (F) ∈ L, a = 1, .., 3. (6)
If the value of LS(F) is greater than a threshold τ than the user is allowed to keep working, and the process of keystroke verification is repeated continuously. Otherwise the user must proceed to knuckle verification stage. The influence of the threshold τ value on the keystroke verification accuracy is presented in the section concerning experiments.

Knuckle analysis subsystem

The aim of knuckle image analysis is to compare and find the similarity between the knuckle image of a person being verified and the reference knuckle images. The reference knuckle images are the images that have been acquired from a user and stored in the database during the profiling phase. In our method a special device was used for knuckle image acquisition. This device consists of a box that has a camera and three built in, white LED-lights. The purpose of the LED-lights is to illuminate the fingers equally from different directions. When taking a picture the camera is focused on the index finger. The example of finger knuckle image acquisition is shown in Fig 5. After a knuckle image acquisition an analysis is carried out which consists in extracting finger ridges. At first, the Hessian filtering was applied. The reason to choose this filtering method is, that it can detect the local strength of lines, ridges and direction of edges [START_REF] Iwahori | Automatic detection of polyp using Hessian Filter and HOG features[END_REF][START_REF] Jin | Vascular tree segmentation in medical images using Hessian-based multiscale filtering and level set method[END_REF][START_REF] Nitsch | Automatic Segmentation of the Cerebral Falx and Adjacent Gyri in 2D Ultrasound Images[END_REF]. In the next step to the analyzed image a binarization is applied using the Otsu method -a well known binarization technique. This method assumes that there are two different classes in the image, foreground (object) and background. Classes are separated from each other by an intensity factor. The Otsu method automatically seeks for the optimum threshold that can maximize the distance between these two classes [START_REF] Otsu | A Threshold Selection Method from Gray-Level Histograms[END_REF]. On the binarized image a skeletonization is performed which allows to reduce the thickness of lines in the image to one pixel. In the presented method the Pavlidis thinning algorithm was applied. In Fig. 6 all stages of line extraction are shown. The detailed description of the acquisition procedure is presented in [START_REF] Doroz | A New Personal Verification Technique Using Finger-Knuckle Imaging[END_REF].

Fig. 6: Stages of finger knuckle image analysis

Upon completion of image analysis, for a verified person (let it be denoted as A), two sets X and Y are formed. The set X contains values of similarity coefficients calculated between all possible pairs of images taken from the person A. All elements of the set X are assigned to the class c 1 . The construction of the set X is shown below:

X = {sim(ImR A i , ImR A j )}, i, j = 1, ..., r, i = j, (7)
where ImR A i is an i-th reference knuckle image of the person A being verified, r is a number of all reference knuckle images of the person A.

The set Y contains values of similarity coefficients calculated between knuckle images of person A and the knuckle images of another user B, where B = A, randomly selected from a database. The elements of the set Y are assigned to the class c 2 . The construction of the set Y is shown below:

Y = {sim(ImR A i , ImR B j )}, i = 1, , r, j = 1, , s, (8)
where ImR A i is the i-th reference knuckle image belonging to the person A being verified, r is the number of all reference knuckle images of person A, ImR B j is the j-th reference knuckle image of the person B, s is the number of analyzed reference knuckle images of person B.

To avoid imbalanced data [START_REF] Krawczyk | Cost-sensitive decision tree ensembles for effective imbalanced classification[END_REF] the number of elements in the set X should be close to the number of elements in set Y . This assumption is fulfilled if the number of knuckle images used for creating the set Y is equal to s = r -1.

In the presented method, the similarity between any two knuckle images is estimated based on the shape and localization of the knuckle ridges. The comparison of images is carried out by means of the Normal Cross Correlation (NCC) technique. The NCC has been widely used as a metric to evaluate the degree of a similarity (or dissimilarity) between two compared images [START_REF] Nakhmani | A new distance measure based on generalized Image Normalized Cross-Correlation for robust video tracking and image recognition[END_REF]. In our method all images must have the same size and the shape of a square.

To find the similarity sim(Im1, Im2) between two images denoted as Im1 and Im2 the image Im1 is divided into the square shaped sub-images. A length of a side of these sub-images is a parameter of the method. Each k-th sub-image in Im1 is treated as a template and is noted as T k . The task is to find a fragment in the tested image Im2 which has the most similarity to the template T k . An example of searching for the sub-image T 1 in the image Im2 is shown in Fig. 7. By means of the following formula the similarity between a template T k and tested image Im2 is calculated:

Im1 Im2

ncc(T k , Im2) = max    (i,j)∈T k Im2(x + i, y + j) • T k (i, j) (i,j)∈T k Im2 2 (x + i, y + j) • (i,j)∈T k T 2 k (i, j)    . (9)
The final similarity between the images Im1 and Im2 is calculated using [START_REF] Otsu | A Threshold Selection Method from Gray-Level Histograms[END_REF]. sim(Im1, Im2) = mean{ncc(T 1 , Im2), ncc(T 2 , Im2), ..., ncc(T b , Im2)}, (10) where b is the number of all sub-images T k created in the image Im1.

After the creation the sets X and Y the tested knuckle image Im * is compared with a random image in the database taken from the person who claimed the identity (let it be A). The result of comparison is an object d * :

d * = sim(Im * , Im A i ), (11)
where, Im * is the knuckle image to be verified and Im A i is a randomly selected original knuckle image of the person A.

Next, the verified knuckle image Im * is used in the classification stage, where the k-NN classifier is applied [START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF]. In this approach for k-NN classifier the commonly used Euclidean distance metric is used. In the classification stage first, the distances between classified object d * and objects from X and Y sets are determined. The selection of the value of parameter k for the k-NN classifier is presented in section concerning experiments. Based on majority, the k-NN gives a decision to which class (c 1 or c 2 ) the classified object d * belongs to.

Ψ knu (d * ) → c j , j ∈ {1, 2}. ( 12
)
If the object d * belongs to the class c 1 it means that the verified knuckle image Im * comes from the legitimate user.

Fusion of the methods

The proposed system is based on fusion of two verification methods. The ultimate decision of the user verification depends on both: keystroke and knuckle image verification results. This task is done by analyzing the value of τ , which is the result of the keystroke verification, and the parameter k value in k-NN method. The rules of fusion system are presented below: decision = access granted if (LS > τ ) or (LS > τ and k > k * ) access denied otherwise .

(13) Values of parameters τ , τ and k * have been described in experiments section.

Experimental results

The efficiency of the proposed method has been investigated experimentally. The researches have been conducted on a database which consists of 4000 vectors F and 150 knuckle images acquired from 30 persons. All experiments were repeated 10 times to provide better statistical accuracy and then the average values of evaluation metrics for all trials were calculated.

The proposed architecture of the classification module for keystroke dynamics based verification assumes the use of four single classifiers in an ensemble: C4.5, Bayesian Network, Support Vector Machine, Random Forest. Those classifiers were chosen because of their high accuracy confirmed in [START_REF] Wesolowski | Electronic Health Record Security Based on Ensemble Classification of Keystroke Dynamics[END_REF]. The aim of the first stage of this research was to determine an optimal values of parameters τ , τ and k * . The values of mentioned parameters were determined by use of grid search procedure from the following sets τ , τ ∈ {1, 2, 3}, k * ∈ {1, 3, 5, 7}.

The experiments were conducted several times. Each time we used different numbers of knuckle images n and r to determine the sets X and Y . Table 1 shows the best obtained results and the values of the parameters τ , τ and k * for which these results were obtained. Based on the obtained results we can state that the optimal values of the parameters for the proposed method are τ = 3, τ = 2 and k * = 5. When we analyze the influence of a number of knuckle images on the results of an investigation, we can observe that the efficiency of the classification is the best when we analyze only 8 knuckle images from each person.

In order to fully assess the effectiveness of the proposed fusion-based approach, its efficiency has been compared with the efficiencies obtained by each of the biometrical verification methods separately. For this purpose the optimal values of parameters τ and k have been selected once again but this time the efficiency of each verification method (keystroke verification and knuckle verification) has been assessed independently. The comparison of efficiency obtained by the fusion-based method and each individual verification method is presented in Table 2. By analyzing Table 2, we can notice that the fusion of two methods allows to obtain better efficiency in classification than using only one of these methods separately.

Conclusions

This paper presents the preliminary results for the biometric user verification system based on the fusion of keystroke and knuckle analysis. The experiments were conducted to assess the potential of the mentioned biometric methods fusion. The obtained results show that the fusion of the two methods performs better than the keystroke and knuckle analysis separate. Therefore, there is a motivation to continue this research and to develop a real time knuckle analysis method allowing o verify finger knuckles of a computer user while typing on the keyboard. This seems to be a complex task due to the constant movement of fingers over the keyboard. Preliminary research and experiments show that basing on images of the user's knuckles taken in various hand positions it is difficult to verify an identity of a user.

What more, all the image processing has to be performed in the background of the computer system while users are performing everyday tasks. Depending on the frequency of taking a picture this can cause some computer system efficiency issues. Solving the issues mentioned above is the next step of our research on developing fusion-based computer user continuous verification method.

Fig. 1 :

 1 Fig. 1: The proposed biometric user verification algorithm

FFig. 4 : 1 : 3 O 4 T

 4134 Fig. 4: The general scheme of the proposed classification module

  j |F), a = 1, .., 3.

Fig. 5 :

 5 Fig. 5: Finger knuckle image acquisition

1 T 2 T 3 T 4 T 5 T 6 T 7 T 9 T 8 T 1 (Fig. 7 :

 12345679817 Fig. 7: Searching for the template T 1 within the image Im2.

Table 1 :

 1 The best results and the values of parameters used in experiments.

	Number of
	elements in	FAR [%]	FRR [%]	AER [%]	ACC [%] τ τ	k *
	sets X & Y
	4 and 4	7.72 ± 1.36 19.38 ± 2.32 13.55 ± 1.73 93.36 ± 1.89 3 2 5
	6 and 6	6.38 ± 0.51 12.56 ± 1.45 9.47 ± 2.12 95.17 ± 2.54 3 2 5
	8 and 8	1.07 ± 1.47 3.35 ± 2.04 2.21 ± 1.76 98.50 ± 1.33 3 2 5
	10 and 10 1.11 ± 1.13 3.33 ± 2.26 2.22 ± 1.64 98.49 ± 1.22 3 2 7
	12 and 12 1.09 ± 1.45 3.36 ± 2.35 2.22 ± 1.32 98.51 ± 1.53 3 2 5

Table 2 :

 2 The comparison of the performance of various verification methods. Keystroke 5.59 ± 1.16 7.94 ± 1.46 5.41 ± 1.72 97.83 ± 3.28 Knuckle 4.30 ± 0.23 8.19 ± 1.05 6.24 ± 1.09 95.96 ± 7.53 Keystroke + Knuckle 1.07 ± 1.47 3.35 ± 2.04 2.21 ± 1.76 98.50 ± 1.33

	Method	FAR [%]	FRR [%]	AER [%]	ACC [%]


Krzysztof Hajto
email: krzysztof.hajto@ii.uj.edu.pl

Konrad Kamieniecki
email: konrad.kamieniecki@alumni.uj.edu.pl

Krzysztof Misztal
email: krzysztof.misztal@ii.uj.edu.pl

Przemyslaw Spurek
email: przemyslaw.spurek@ii.uj.edu.pl

Przemys Law Spurek

Split-and-merge Tweak in Cross Entropy Clustering

Keywords: cross entropy clustering, clusters splitting, clusters merging

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

Clustering plays a basic role in many parts of data engineering, pattern recognition, data mining, data quantization and image analysis [START_REF] Anil K Jain | Data clustering: a review[END_REF][START_REF] Anil | Data clustering: 50 years beyond k-means[END_REF][START_REF] Xu | Clustering[END_REF]. Some of the most important clustering algorithms are based on density estimation.

In the probabilistic model construction for univariate and multivariate data, finite mixture models have been widely used. The capability of representing arbitrary complex probability density functions (pdfs) enables it to have many applications not only in unsupervised learning [START_REF] Maulik | Genetic algorithm-based clustering technique[END_REF], but also in (Bayesian) supervised learning or in parameter estimation of class-conditional pdfs [START_REF] Hinton | Modeling the manifolds of images of handwritten digits[END_REF].

One of the most important clustering method is based on GMM (Gaussian Mixture Models), which uses the Expectation maximization (EM) algorithm. Unfortunately, GMM has strong limitations related to its optimization procedure, which has to be applied in each iteration of the EM algorithm. While the expectation step is relatively simple, the maximization step usually needs complicated numerical optimization [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF][START_REF] Mclachlan | The EM algorithm and extensions[END_REF]. Because of its greedy nature, the EM algorithm is sensitive to the initial configuration and usually gets stuck at local maxima. Moreover, there is a problem with choosing the correct number of clusters.

A feasible way for solving this problem is to choose several sets of initial values, then proceed respectively with the EM algorithms, and finally choose the best outcome set as the estimation. In most cases, the Bayesian information criterion (BIC) is used to establish the best result and final number of clusters. However, this will certainly increase computational complexity, since we have to apply a method many times with different initial parameters.

In order to solve this problem, many various methods were introduced. In [14] the authors proposed a split-and-merge EM (SMEM) algorithm in which they applied a split-and-merge operation to the EM algorithm. The basic idea of the SMEM algorithm is: after the convergence of the usual EM algorithm, we first use the split-and-merge operation to update the values of some parameters among all the parameters, then we perform the next round of the usual EM algorithm, and alternatively iterate the split-and-merge operation and the EM algorithm until some criterion is met. However, the split or merge method is a linear heuristic procedure without theoretical support. Moreover, the split or merge of the mean vector is independent of the covariance matrix, and vice versa.

In [START_REF] Zhang | Em algorithms for gaussian mixtures with split-and-merge operation[END_REF] authors propose two split methods based on SVD and the Cholesky decomposition of the covariance matrices. Shoham presented a robust clustering algorithm by creating a deterministic agglomeration EM (DAGEM) with multivariate t-distributions [START_REF] Shoham | Robust clustering by deterministic agglomeration em of mixtures of multivariate t-distributions[END_REF]. It was derived from the DAEM algorithm and achieved encouraging performance. Because the initial component number is much larger than the true number, the computation load is one to two orders of magnitude heavier than EM [START_REF] Shoham | Robust clustering by deterministic agglomeration em of mixtures of multivariate t-distributions[END_REF]. In [START_REF] Zhang | Competitive EM algorithm for finite mixture models[END_REF] authors present Competitive EM (CEM) which uses an information theory based criterion for split and merge operations. The initial component number and model parameters can be set arbitrarily and the split and merge operation can be selected efficiently. In [START_REF] Lughofer | A dynamic split-and-merge approach for evolving cluster models[END_REF] the authors present a method that uses two different split and merge criteria. Homogeneity criterion decides whether two clusters should be merged or not (clusters which touch each other or slightly overlap can be merged, if they fulfill the homogeneity criterion). The split criterion is based on a penalized Bayesian information criterion (BIC), evaluated for the actual clusters and hypothetically split clusters, updated in the previous incremental learning step.

In all of the methods the basic idea is to construct a split merge strategy by analyzing cluster shapes. The idea is to avoid a local minima by applying some unconventional operation. The main problem is that such an operation does not depend on the cost function, that is minimized by the EM algorithms. Moreover, after the split or merge operation it is non trivial how to update the parameters of the components, since each point belongs to all cluster with different probability.

In this paper we present a split and merge strategy which solves these two basic problems. First of all, a simpler optimization procedure Cross Entropy Clustering (CEC) [START_REF] Tabor | Cross-entropy clustering[END_REF] is used instead of EM. The goal of CEC is to optimally approximate the scatter of a data set X ⊂ R d by a function which is a small modification of EM (for more information see Section 2). It occurs that at the small cost of having a minimally worse density approximation [START_REF] Tabor | Cross-entropy clustering[END_REF], we gain an efficient method which can be easily adapted for more complicated density models. Moreover, we can treat clusters separately which allows us to update the parameters of clusters more easily(each point belongs to only one group). Furthermore, we can treat each cluster as a new dataset, that is separated from other data, and apply the CEC algorithm in that single cluster. The new division of the cluster is accepted if the global value of the cost function is lower. Similarly, we can verify if the merge of two clusters decreases the cost function.

Let us discuss the contents of the paper. In the first part of our work we briefly describe the CEC algorithm together with the basic structures which we can use in model construction. Then we describe the split-and-merge tweak in detail. At the end of this paper we present results of numerical experiments and conclusions.

Split-and-merge Cross Entropy Clustering

In this section the Split-and-merge Cross Entropy Clustering method will be presented. Our method is based on the CEC approach. Therefore, we start with a short introduction to the method. Since CEC is similar to EM in many aspects, let us first recall that, in general, EM aims to find p 1 , . . . , p k ≥ 0 ( k i=1 p i = 1) and f 1 , . . . , f k Gaussian densities (where k is given beforehand and denotes the number of densities for which the convex combination builds the desired density model) such that the convex combination f = p 1 f 1 +. . .+p k f k optimally approximates the scatter of our data X with respect to the MLE cost function

MLE(f, X) = - x∈X ln(p 1 f 1 (x) + . . . + p k f k (x)).
(

A goal of CEC is to minimize the cost function, which is a minor modification of the one given in (1) by substituting the sum with the maximum:

CEC(f, X) = - x∈X ln(max(p 1 f 1 (x), . . . , p k f k (x))). (2)
Instead of focusing on the density estimation as its main task, CEC aims at solving the clustering problem directly. As it turns out, at the small cost of having a minimally worse density approximation [START_REF] Tabor | Cross-entropy clustering[END_REF], we gain speed in implementation1 and the ease of using less complicated density models. This is an advantage, roughly speaking, because the models do not mix with each other since we take the maximum instead of the sum.

To explain cross entropy clustering (CEC), we need to first introduce an energy function for the purpose of minimizing, which uses cross entropy. But let's start with the definition of cross entropy itself.

By the cross-entropy of the dataset X ⊂ R d with respect to density f we understand

H × X f = - 1 |X| x∈X ln f (x).
Cross entropy corresponds to the theoretical code-length of compression. Let us consider the case of partitioning X ⊂ R N into pairwise disjoint sets X 1 , . . . , X k , such that elements of X i are encoded by the optimal density from family F. In this case, the cross-entropy with respect to a family of coding densities F is given by H × X F = inf f ∈F H × X f . Thus, the mean code-length of a randomly chosen element x equals

E(X 1 , . . . ; X k , F) := k i=1 p i • (-ln(p i ) + H × X i F i ), (3)
where

p i = |Xi| |X| .
The aim of CEC is to find a partitioning of X ⊂ R N into pairwise disjoint sets X i , i = 1, . . . , k which minimizes the function given by (3). The minimization of (3) is equivalent to optimization of (2). In our case we consider as a F a family of all Gaussian distributions2 G. According to [START_REF] Tabor | Cross-entropy clustering[END_REF], for single piece

X i ⊂ R N considered with respect to N (µ, Σ) ∈ G we can get that H × X i N (µ, Σ) = N 2 ln(2π) + 1 2 tr(Σ -1 Σ Xi ) + 1 2 ln det(Σ), (4)
where Σ Xi is a covariance matrix of X i , which allows as to easily calculate the cost function [START_REF] Fraley | MCLUST: Software for model-based cluster analysis[END_REF].

Let us now briefly introduce the algorithm step by step. The CEC clustering method starts from an initial clustering, which can be obtained randomly or by the use of the k-means++ [1] approach. Then the following two simple steps are applied simultaneously. First, we estimate the parameters of the optimal Gaussian function in each cluster. In the second step, we construct a new division of X by adding points to the closest cluster, or rather, to the closest Gaussian density. Specifically, we assign a point x ∈ X to the cluster i ∈ {1, . . . , k} such that -ln(p i ) -ln N (x; µ i , Σ i ) is minimal. We apply the above steps simultaneously until the change of the cost function is smaller than a predefined threshold or if the clusters did not change at all. This approach causes a problem with local minima. Therefore, we aply a two point strategy for increasing the performance of the algorithm. More precisely, we apply a split and merge strategy.

Merge strategies

Let us consider Gaussian densities G. For two disjoint sets X and Y (X, Y ⊂ R N ), we want to develop a condition under which we should combine them into one cluster, rather then consider them separately -namely, energy/cost of X ∪ Y is less then sum of energy of X and Y . This condition is given by

E(X ∪ Y, G) ≤ E(X, G) + E(Y, G). (5)
For the general case, it is very difficult to solve the above inequality and give an analytical solution. Thus, for simplicity of the problem, it is necessary to put some restrictions on the sets X and Y . In this section we solve this in a one dimensional real space under same constraint about sets X and Y . But before that, let us now recall the following important remark which simplifies our situation.

Remark 1. Let X, Y be given as finite subsets of R N . Assume additionally that

X ∩ Y = ∅. Then m X∪Y = p X m X + p Y m Y Σ X∪Y = p X Σ X + p Y Σ Y + p X p Y (m X -m Y )(m X -m Y ) T where p X = |X| |X|+|Y | , p Y = |Y | |X|+|Y | .
Theorem 1. Let X, Y be given as finite subsets of R. Assume additionally that

-X ∩ Y = ∅, -|X| = |Y |, -Σ X = Σ Y = Σ = (σ 2
) for an arbitrary σ > 0.

Then the distributions N (m X , Σ) and N (m Y , Σ) should be combined into one Gaussian distribution

N ( 1 2 (m X + m Y ), (σ 2 + 1 4 (m X -m Y ) 2 )) with respect to condition (5) iff |m X -m Y | < 2 √ 3σ,
where m X , m Y denote the mean values of sets X, Y .

Proof. Let us consider equation ( 5) under the terms of our theorem. This leds us to

-ln(1) + H × X ∪ Y G ≤ 1 2 • (-ln( 1 2 ) + H × X G ) + 1 2 • (-ln( 1 2 ) + H × Y G ).
By equation ( 4

where

Σ X∪Y = Σ + 1 4 (m X -m Y )(m X -m Y ) T .
In the case of one dimensional space the equation ( 6) simplifies to

σ 2 + 1 4 (m X -m Y ) 2 ≤ 4σ 2
which ends the proof.

Figure 1 presents a simple illustration of the above theorem in the case of σ = 1. It needs to be highlighted that even in one dimensional space our considerations were limited to strong constraints, which shows how it is a very hard task in the general case.

In the approach proposed by the authors for the merge problem we will always check the condition (5) directly. However, we will use Remark 1, according to which we do not need to recalculate the covariance matrix for a cluster combination, which simplifies and speeds up the calculations.

Split strategies

The decision about splitting a given cluster X ⊂ R N into two parts X 1 , X 2 (X 1 ∪ X 2 = X, X 1 ∩ X 2 = ∅) for CEC clustering in our case is given by the following run CEC clustering with two clusters for set X, for obtained clusters X 1 and X 2 , if E(X, G) ≥ E(X 1 , G) + E(X 2 , G) then replace cluster X by X 1 and X 2 .

The approach, in this case, is similar to the merge strategy, since we also want to decrease energy. Figure 2 presents division steps for a sample set from CEC clustering.

Proposed strategies and experiments

We develop a few strategies to check when split and merge steps should be applied during CEC clustering. We denote them as follows:

-CEC-FAF -the merge and split are performed when a CEC iteration did not reduce energy, the merge step is performed as many times as possible; -CEC-FSF -the merge and split are performed when a CEC iteration did not reduce energy, the merge is performed only once at a time; -CEC-P3AF -the merge is performed every third iteration as many times as possible, the split is perfmormed if a CEC iteration(including the merge) did not reduce energy, -CEC-P1SP1 -the merge and split are performed in every iteration, the merge is performed once at most in each iteration.

We compare them with -CEC-Grid -we apply CEC clustering with a starting number of clusters from 2 to 70 and then we choose the best result according to the lowest Bayesian information criterion (BIC); -GMM-Grid -we used the Project R package mclust [START_REF] Fraley | MCLUST: Software for model-based cluster analysis[END_REF] which performs a grid search for finding the optimal numbers of mixture components (clusters) according to the BIC criterion. The considered range of the number of clusters was the same as in CEC-Grid.

Split-and-merge strategies effectiveness

Illustrations: Table 1 presents the results of clustering of the sample sets with the strategies listed above. The results of all strategies are pretty similar except for GMM-Grid. Accuracy: Table 2 presents the comparision of the results obtained by investigating different strategies. We show the calculated MLE (maximum likelihood estimation -the higher the better), BIC (Bayesian information criterion -the lower the better), AIC (Akaike information criterion -the lower the better) and also give the values of the enegry function obrained by CEC clusterings (the lower the better). In this case results seem to favor the strategies CEC-Grid and CEC-P1SP1 as the best ones, although the results are usually very close (except for GMM-Grid).

Table 3 presents an adjusted rank index for different strategies. In this case all strategies gave the same result on their best runs. Speed: While the above could suggest the CEC-P1SP1 strategy was the fastest, take note that because it performs both split and merge operations at each iteration, the iterations themself are more expensive computational-wise. A direct time measurement of the strategies revealed CEC-FSF to be the fastest, followed closely by CEC-P3AF.

Split-and-merge CEC in higher dimensions

Table 4 presents the results obtained with the same strategies and algorithms on higher dimensional data. In this experiment there was much more variation both between the strategies and between different runs of the same strategy. It appears that the algorithm suffers from the curse of dimensionality and has trouble finding the right number of clusters in higher dimensional data. This is most evident in the iris dataset, where it overshots that number tenfold.

Conclusions and future work

We have proposed an approach for the split and merge problem in CEC clustering. It was shown that even in a one dimensional space the condition is not so easy to assess. Thus, in the proposed approach, we implicitly use the formula to decide if two clusters should be combined. Our experiments present that the strategy when the merge and split are performed in every iteration and the merge is performed once at most in each iteration can be competitive to classical CEC or even CEC-Grid.

Our future work will focus on developing new measures which will allow us to solve the split problem using information theory.

Fig. 1 :

 1 Fig. 1: Comparision of density descriptions of two sets. First, the sum of two densities N (0, 1) (the blue one) and N (2 √ 3, 1) (the green one) describe separated clusters, while the density N ( √ 3, 4) (the red one) presents the best description of their set combination.

Fig. 2 :

 2 Fig. 2: Split strategy. An initial clustering (with one cluster) is divided into as many clusters as needed using the split strategy. The numbers below the images present the numbers of waves of divisions. Those do not correspond to the number of clusters since multiple divisions can happen simultainiously.

Fig. 3 :

 3 Fig. 3: Energy during clustering iterations under different strategies. The split and merge strategies were all started with a single cluster.

Table 1 :

 1 Comparision of different CEC split and merge strategies with GMM clustering.

Table 2 :

 2 Effectiveness of clustering for datasets from Figure1. Table presents a comparison of results for various criteria with the best strategies selected (the marked ones).

	Set Method	MLE	AIC	BIC	cost No. clust
	1 CEC-Grid	-5028.89 10135.77 10317.88 6.387748	7
	CEC-FAF	-4971.75 10090.16 10274.28 6.372357	8
	CEC-FSF	-4972.59 10092.01 10274.28 6.368866	8
	CEC-P3AF -4985.80 10088.99 10274.28 6.375692	8
	CEC-P1SP1 -4973.65 10092.16 10274.27 6.369666	8
	GMM-Grid -5052.78 10171.55 10325.65		8
	2 CEC-Grid	-4772.61 9828.48 10164.06 4.820493	12
	CEC-FAF	-4910.83 9840.92 10190.31 5.086688	18
	CEC-FSF	-4826.43 9840.41 10181.07 5.086773	18
	CEC-P3AF -4831.82 9841.64 10183.92 5.086012	17
	CEC-P1SP1 -4827.30 9840.52 10181.90 5.088752	18
	GMM-Grid -4844.54 9923.09 10497.30		29
	3 CEC-Grid	-5302.07 10933.03 11523.40 5.337437	24
	CEC-FAF	-5296.87 10949.07 11511.24 5.545499	35
	CEC-FSF	-5297.57 10954.84 11516.37 5.544520	38
	CEC-P3AF -5295.65 10953.27 11503.95 5.546854	36
	CEC-P1SP1 -5293.99 10943.12 11494.34 5.546223	38
	GMM-Grid -5476.76 11275.40 12065.55		40
	4 CEC-Grid -17345.28 35275.38 36420.90 5.626151	28
	CEC-FAF -17469.87 35247.75 36177.78 5.791727	31
	CEC-FSF -17469.87 35247.75 36177.78 5.791727	31
	CEC-P3AF -17469.87 35247.75 36177.78 5.791727	31
	CEC-P1SP1 -17469.87 35247.75 36177.78 5.791727	31
	GMM-Grid -17857.81 35933.63 36591.90		27
	5 CEC-Grid	1169.98 -2142.05 -1908.32 -1.55705	7
	CEC-FAF	1260.44 -2259.60 -1780.56 -2.23154	20
	CEC-FSF	1261.10 -2252.04 -1765.01 -2.39991	20
	CEC-P3AF	1259.68 -2260.20 -1781.17 -2.47543	19
	CEC-P1SP1 1279.09 -2227.21 -1613.51 -1.76784	29
	GMM-Grid	1048.00 -1854.02 -1312.30		30
	6 CEC-Grid	1585.14 -2822.28 -2088.01 -1.00290	25
	CEC-FAF	1762.23 -2876.52 -1554.79 -1.09039	46
	CEC-FSF	1738.68 -2876.18 -1566.58 -0.96549	54
	CEC-P3AF	1758.68 -2893.73 -1658.30 -1.19903	42
	CEC-P1SP1 1790.03 -2855.14 -1260.18 -0.85854	63
	GMM-Grid	815.81 -1413.62 -834.12		27

Table 4 :

 4 The results of algorithms in the case of data from UCI repository.

	Set	Method	MLE	AIC	BIC	cost No. clust
	cancer CEC-Grid -5397.75 12541.50 14248.87 12.6645

We can often use the Hartigan approach to clustering, which is faster and typically finds better minimas.

We can also consider same Gaussians subfamilies[START_REF] Tabor | Cross-entropy clustering[END_REF][START_REF] Misztal | Cross entropy clustering approach to iris segmentation for biometrics purpose[END_REF][START_REF] Tabor | Detection of elliptical shapes via cross-entropy clustering[END_REF].


Malik Khurram Awan

Agostino Cortesi

Blockchain Transaction Analysis Using Dominant Sets

Keywords: Transaction behavior analysis, Blockchain technology, Clustering

Blockchain is an emerging backbone technology behind different crypto-currencies. It can also be used for other purposes and areas. There are different scalability issues associated with blockchain. It is important to know the in depth structure of blockchain by identifying common behaviors of the transactions and the effect of these behaviors on the nodes of the network. Dominant set approach can categorize the blockchain transactions into different clusters without mentioning number of clusters in advance. The experimental evaluation of blockchain transactions shows better clustering accuracy of dominant set approach than existing method of central clustering approach.

Introduction

Blockchain is a technology that is working behind bitcoin. The rising adoption and promising security of blockchain technology has the potential to reshape the current infrastructure of different business areas. In bitcoin, blockchain is a decentralized ledger containing the complete transaction history which is public at each node. All transactions are locked with the information of time, date, nodes and the amount. Nodes generate transactions and broadcast them to the network. Miners generate new blocks by solving proof-of-work and broadcast them to the network.

Blockchain analysis under different clustering heuristics can help to study its in-depth structure and to know the behavior of nodes and associated transactions. The clustering results obtained from these heuristics can also be useful for backend designers of the blockchain technology. These days achieving scalability in blockchain is a heated topic. Many researchers have presented different approaches and ideas for the scalability of blockchain to get better throughput in minimum latency. The recent research work [START_REF] Croman | On Scaling Decentralized Blockchains[END_REF][START_REF] Beck | Blockchain-The Gateway to Trust-Free Cryptographic Transactions[END_REF][START_REF] Decker | A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels[END_REF][START_REF] Eyal | Bitcoin-NG: A Scalable Blockchain Protocol[END_REF][START_REF] Kosba | Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts[END_REF][START_REF] Miller | Shadow-Bitcoin: Scalable Simulation via Direct Execution of Multi-threaded Applications[END_REF][START_REF] Bonneau | SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurriencies[END_REF][START_REF] Pazmino | Simply Dividing a Bitcoin Network Node may Reduce Transaction Verification Time[END_REF] of past two years about scalability issues of blockchain model it is shown that blockchain incur storage, latency, security, processing and bandwidth problems [START_REF] Eyal | Bitcoin-NG: A Scalable Blockchain Protocol[END_REF][START_REF] Kosba | Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts[END_REF][START_REF] Miller | Shadow-Bitcoin: Scalable Simulation via Direct Execution of Multi-threaded Applications[END_REF][START_REF] Bonneau | SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurriencies[END_REF][START_REF] Pazmino | Simply Dividing a Bitcoin Network Node may Reduce Transaction Verification Time[END_REF]. Different researchers have carried out research activities by introducing some new proposals and improving the existing mechanism of blockchain in different crypto-curriencies [START_REF] Back | Enabling Blockchain Innovations with Pegged Sidechains[END_REF][START_REF] King | PPCoin: Peer-to-peer Crypto-Currency with Proof-of-Stake[END_REF][START_REF] Kroll | The Economics of Bitcoin Minning or, Bitcoin in the Presence of Adversaries[END_REF][START_REF] Decker | Information Propagation in the Bitcoin Networks[END_REF][START_REF] Bamert | Have a Snack, Pay with Bitcoins[END_REF][START_REF] Ried | An Analysis of Anonymity in the Bitcoin System[END_REF][START_REF] Miers | Zerocoin: Anonymous Distributed e-Cash from Bitcoin[END_REF][START_REF] Decker | Bitcoin Transaction Malleability and MTGox[END_REF][START_REF] Eyal | Majority is not Enough: Bitcoin Mining is Vulnerable[END_REF][START_REF] Doll | Btctrackr: Finding and Displaying Clusters in Bitcoin[END_REF]. In [START_REF] Meiklejohn | A Fistful of Bitcoins: Characterizing Payments among Men with no Names[END_REF] the authors discovered that by making the clustering of non-real account names of users according to their shared ownership and associated real names can give the clearer picture of the cryptocurrency. In [START_REF] Lischke | Analyzing the Bitcoin Network:The First Four Years[END_REF] transaction volume per node is presented with clustering coefficients per node in the bitcoin network.

Inside blockchain network, there are thousands of transactions which are increasing over time. To manage and organize this increasing number of transactions it is important to study their common behavior. Clustering these increasing number of transactions can help to find out the transactions with common behavior and to identify and trace anomalous transactions.

This paper is a step towards it by using the dominant set approach for blockchain transactions that automatically categorize the blockchain transactions into different clusters without specifying number of clusters in advance. The percentage accuracy of experimental results show better performance of dominant set approach than existing method of central clustering approach.

In next Section 2 we highlight the basic terminologies and algorithmic structure of dominant set approach. Section 3 shows experimental results, evaluation measures and the results summary. Conclusion is discussed in Section 4.

Background

Generally clustering can be categorized into two types: central and pairwise. Central clustering is a feature based clustering. K-means algorithm is a type of feature based clustering. Pairwise clustering is a graph based clustering and a more general approach and adaptable in the sense that the algorithm works fine with wider range of input forms. Dominant set clustering framework has been defined and introduced in [22,[START_REF] Pavan | Dominant Sets and Pairwise Clustering[END_REF]. The clustering method of choice is dominant sets, a pairwise clustering method that generalizes the idea of maximal clique to weighted graphs. It works with pairwise similarities i.e metric embedding is not needed. For an undirected unweighted graph G =(V, E), clique can be defined as a subset of mutually adjacent nodes where V = {1, 2 . . . , n} denotes vertex set and E ⊆ V × V represents the edge set. The key notions and definitions of the dominant set approach are discussed below: For a non-empty set of vertices S ⊆ V and i ∈ V . The average weighted degree of node i w.r.t set S is defined as:

AW Deg S (i) = 1 |S| j∈S w i,j (1)
In case of relative similarity φ S (i, j), when node j does not belong to set S as shown in Fig. 1. We can measure the similarity between nodes i and j w.r.t the average similarity between node i and its neighbors in S which is expressed as: For set S ⊆ V and i ∈ S we can compute the weight of node i w.r.t S:

φ S (i, j) = w i,j -AW Deg S (i) (2)
W S (i) = 1 if |S| = 1 j∈S\{i} φ S\{i} (j, i)W S\{i} (j) otherwise (3)
Total weight of the set S can be calculated by adding up all weights of W S (i) of the above mentioned recursive function.

W (S) = i∈S W S (i) (4)
Further in [22,[START_REF] Pavan | Dominant Sets and Pairwise Clustering[END_REF] set S is specified as dominant set by defining the internal and external criteria of clustering as:

I. W S (i) > 0 for all i ∈ S II. W S∪{i} (i) < 0 for all i / ∈ S
The authors in [22,[START_REF] Pavan | Dominant Sets and Pairwise Clustering[END_REF] transformed the combinatorial problem of identifying dominant set in graph into quadratic optimization problem and the use of dynamic system of evolutionary game theory to solve it. Which is a general-form of a problem in graph theory known as Motzkin-Straus problem [START_REF] Motzkin | A New Graph-theoretic Approach to Clustering and Segmentation[END_REF]. The findings in [22,[START_REF] Pavan | Dominant Sets and Pairwise Clustering[END_REF] reveal that there is a one-to-one correspondence between dominant sets and the strict local maximizer of the problem.

max x T W x subject.to x ∈ ∆ (5)
where

∆ n = {x ∈ R n + : x ≥ 0, ēT x = 1}
is the standard simplex. The weighted characteristic vector of a dominant set S, which is a strict local solution of the problem ( 5) is defined as:

x S = W S (i) W (S) if i ∈ S; 0 otherwise.
The Motzkin-Straus problem is generalized by creating 1-to-1 correspondence between dominant set and strict local solution of the problem (5) in a conversely way by explaining that if x * is a strict local solution of the problem (5) then its support σ(x * ) = {i ∈ V : x * i = 0} is a dominant set provided that w σ∪{i} = 0 ∀i = σ. For finding the local solution of the above mentioned quadratic problem [START_REF] Bonneau | SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurriencies[END_REF] we use replicator dynamics that originates from evolutionary game theory. The following evolutionary step is adopted.

x i (t + 1) = x i (t) (AX) i X(t) T AX(t) (6)
For i = 1 . . . n, all trajectories that start within standard simplex will remain in the simplex for any number or iterations of (6). Let A be a non-negative symmetric matrix so the objective function will strictly increase along any nonconstant trajectory of [START_REF] Cortesi | Datacentric Semantics for Verification of Privacy Policy Compliance by Mobile Applications[END_REF]. The asymptotically stable points correspond to dominant set for the similarity matrix A. With an affinity matrix A of graph G the abstract algorithmic structure of dominant set clustering approach is:

P a r t i t i o n _ i n t o _ d o m i n a n t

Results and Evaluation

This section highlights the detail decription about performed experiments mentioned in section 3.2 and the results comparison with different evaluation measures in section 3.3. The experimental evaluation summary is mentioned in section 3.4.

Experimental settings

We have selected a sample of 2,048 vectors of blockchain transaction data. The pairwise distance between two set of observations has been computed by using standardized euclidean distance similarity function. The transaction data has been experimented in matlab with different parameters and settings. Some graph structures have been studied with gephi graph visualization tool. The machine used to perform experiments and compute the clustering results is a standard computer with 2.3 GHz Intel Dual-core with 3GB RAM.

Experimental results

Dominant set approach and central clustering approach has been applied on standard blockchain transactions data. With K as number of clusters, the sample output of first 2,048 vectors of transaction edges are shown in Fig. 2. With dominant set approach, only 2 required clusters of transaction edges are extracted out of the whole graph. Transactions edges that show 'similar behavior' are in one cluster(blue) and the transaction edges that show 'different behavior' are in another cluster(green) as shown in Fig. 3. With K-means approach, we have extracted 2 clusters(red and blue) from the whole transaction graph which is actually a partitioning of the whole graph as shown in Fig. 4.

Evaluation measures and comparison

There are different measures for comparing clustering results. Clustering results of blockchain transactions are evaluated by computing silhouette value and rand index value. Silhouette values of results are computed to know about wellseparatedness of clusters and their average is calculated to get better quantitative analysis view. Silhouette value plots are shown in Fig. 5 and Fig. 6. Table 1 shows average silhouette value computed for range of values of K for both approaches as shown in Fig. 7 Rand index is usually used to see the accuracy or measure of similarity between two clusterings. Mathematically rand index is defined as: R = 2(a+b) n(n+1) For analysis and evaluation 6 clusters have been selected for the calculation of percentage accuracy and rand index for both appraoches as shown in Table 2 and Table 3. The plotted results are shown in Fig. 8 and Fig. 9. From Fig. 8 rand index plot shows that at around cluster 3 the slope is getting lower in dominant set approach. The result accuracy plot as shown in Fig. 9 shows that the percentage result accuracy of clustering results of dominant set is better than K-means appraoch that shows less spike at around cluster 4.

Summary of the results

The experimental evaluation explains that: (1) dominant set method performs well for 2,048 vectors of blockchain transaction data (2) transactions with 'similar behavior' are clustered without specifying number of clusters in advance (3) with dominant set approach transactions subgraph with 'similar behavior' is extracted out of the main graph, and (4) percentage result accuracy shows better clustering results in dominant set method than feature based approach when number of clusters increases.

Constraints and complexity

Some constraints related to experimental results are: (1) smooth running of experiments mainly depend on size of the blockchain transactions selected, and

(2) hardware specification. The standard approach used here to find dominant set is replicator dynamics. From theoretical point of view, replicator dynamics has quadratic O(n 2 ) computational complexity in every step of the dynamics for a dataset with n points.

Conclusion

We analyzed blockchain transaction data with pairwise dominant set and central clustering approaches by testing and evaluating it with different measures and settings. The experimental and evaluation results show better clustering accuracy of dominant set approach than existing method of central clustering approach. The in-depth information coming out of the dominant set clustering analysis can be useful for blockchain maintainers and to accurately identify anomalous transactions in the blockchain.

From scalability point of view, further study is needed for the concept of centralized blockchain with distributed chain of dominant set labels of the transactions.

Finally, in would be interesting to investigate the impact of alternative approaches to the analysis of blockchain systems, like for instance semantics-based static analysis techniques, that already provided interesting results in security analysis of software systems [START_REF] Barbon | Privacy Analysis of Android Apps: Implicit Flows and Quantitative Analysis[END_REF][START_REF] Cortesi | Datacentric Semantics for Verification of Privacy Policy Compliance by Mobile Applications[END_REF][START_REF] Zanioli | SAILS: static analysis of information leakage with sample[END_REF].

Fig. 1 :

 1 Fig. 1: (a) Average weighted degree of node i (b) Relative similarity between two nodes

Fig. 2 :Fig. 3 :Fig. 4 :

 234 Fig. 2: Sample output of blockchain transaction edges

Fig. 5 :

 5 Fig. 5: Dominant Set silhouette value plot of sample with K=2

Fig. 7 :

 7 Fig. 7: Average silhouette value plot for dominant set and feature based approach(Kmeans)

Fig. 8 :Fig. 9 :

 89 Fig. 8: Rand Index Plot of Dominant Set and Feature based Approach(K-means)

Table 2 :

 2 Rand index and accuracy for dominant set clustering from 1 to 6

	Clusters	1	2	3	4	5	6
	%Rand Index 17.96 64.00 70.78 82.08 86.60 99.53
	%Accuracy 20.31 38.37 44.62 61.86 71.38 99.36
	Rand Index 0.17 0.64 0.70 0.82 0.86 0.99
	Accuracy	0.20 0.38 0.44 0.61 0.71 0.99

Table 3 :

 3 Rand index and accuracy for K-means clustering from 1 to 6