Imed El

Gerard Wawrzyniak
email: gwawrzyniak@ebstream.com

Imed El Fray
email: ielfray@zut.edu.pl

An Electronic Document for Distributed Electronic Services

Keywords: traditional document, electronic document, electronic transaction, XML, electronic services

The paper presents the role of documents in the implementation of various types of transactions. The main features of the document determining its usefulness in the effective exchange of legal information, ensuring the authenticity, integrity and non-repudiation of origin are presented. Considering the general background of the document, the concept of an electronic document having significant (in terms of legal effectiveness) features of traditional document as well as those features that allow its operation and processing in the virtual space has been presented. An example of the use of an electronic document in the implementation of typical transactions, which are reflecting traditional electronic transaction will be discussed as well.

Introduction

Every business, regardless of the area in which it is conducted (business, administration, etc.) apart from the flow of material goods or performance of services, is associated with transfer of capital and information. From the nature of things, the production and delivery of products and service delivery are a tangible -real. The flow of capital used to be implemented in the real world as the physical transfer of money in the past, now is almost completely dominated by the flow of information in virtual reality (electronic). The exchange and processing of information accompanying the economic processes, administrative processes etc., at all stages of their execution is carried out in many ways: talking, letters, faxes, e-mail -can be enumerated, but the importance of information is relevant to from the point of view of legal effectiveness [START_REF] Veseláa | The development of electronic document exchange[END_REF][START_REF]Guidelines on best practices for using electronic information. How to deal with machinereadable data and electronic documents[END_REF][START_REF] Petermann | Electronic document[END_REF]. At some stage of the business process execution there is a need to ensure the legal effectiveness of information being exchanged at least for purposes of legal proceedings, in case of differences in the interpretation of events and commitments undertaken by parties. Such possibility is provided by document that regardless of its form (technical implementation) must ensure authenticity, non-repudiation of origin, integrity and privacy [START_REF] Chen | Privacy protection in on-line shopping for electronic documents[END_REF][START_REF] Sion | On the computational practicality of private information retrieval[END_REF][START_REF] Sakurai | Blind decoding, blind undeniable signatures, and their applications to privacy protection[END_REF]. Furthermore, the document as an electronic document must ensure the possibility of electronic transport, storage, and first of all the processing using electronic means. The existing formats of electronic documents actually files, do not meet requirements discussed above. For example, the format of Microsoft Office "* .doc, .docx" or Libre Office (Open Office) does not provide legal efectiveness (no electronic signatures applyed), it also do not give the possibility of electronic data processing. Adobe format *.pdf in its basic form provides the ability to sign a document (whole content) using number of signatures -but it can not generate the signatures of various parts of a document by different people. These forms do not reflect the real (paper) forms in which it is possible to perform such signatures. It is also possible to use XFDF format, based on XML and representing data and annotations, which are included in PDF form file. Automatic processing of data from a PDF document requires a conversion (data mining) document into an XML data file (XFDF). Electronic document, especially the one that is used by human is composed of presentation layer and data layer. It should reflect the traditional documents and forms in which these two layers are contained in a single object -a piece of paper (or multiple pages) -this is the immanent feature of a document. Mentioned above formats of documents meet this requirement. However, as already mentioned, do not meet critical requirements (legal effectiveness, ease of electronic processing). Such requirements would meet the electronic document based on XML (ease and interoperability of processing, eith legal efficiency provided by electronic signatures (many signatures covering different parts of the document, done by many people) with the use of PKI, including in its structure both description of visualization and introduced by human data. A similar solution is presented in the XFDL form (Extensible Forms Description Language) proposed by Canadian company Pure Edge [START_REF]Extensible Form Description Language[END_REF]. In XFDL forms both data and presentation of data is stored in one XML file which syntax described using the DTD. This solution does not provide the possibility to define and then implement such features: as default values of each form field, validation rules of the data, help messages and hints. In the XFDL forms it is not possible to define a method to build XML messages based on data stored in the form, and support protocols to exchange information with network services (eg. SOAP), which would allow to build messages, sending them to the server, receiving a response in real time as synchronous mode and present (update) data in a form for presentation.

The aim of the article is to present, with regard to described above drawbacks, the format of an electronic form with syntax formally described usig XML Schema XSD. The form contains description of the form visualisation, data types of form fields, and electronic signatures with indication of elements sign by each signature, calculation rules and also the following new features (relating to the XFDL ), such as definitions of default values, validation rules, mechanisms for building XML messages, descriptons how to send XML (or the entire form) using SOAP or SMTP (the list of recipients, encryption) protocols, a mechanism for interpreting XML messages received in SOAP response. These features enable to implement electronic services of transactions in real time.. Other aim of the paper is to show possibility an benefits of such document in distributed services definition and execution.

Document in electronic service delivery

On behalf of the European Commission, the company Cap Gemini Ernst & Young, has developed a 4-point scale assessment of the progress of the e-Europe initiative for evaluating the availability of online services for citizens and businesses [START_REF]Digitizing Public Services in Europe: Putting ambition into action 9th Benchmark Measurement[END_REF]: no publicly accessible website/s, or those websites does not meet the criteria for levels 1-4; 1 -Information:

publication of electronic information on the service provided; 2 -One-way interaction:

the possibility to download forms; 3 -Two-way interaction the possibility to fill out forms or electronic submission of the application or requests;

-Transaction

full electronic execution of the case, taking into account the decision, informing the recipient, delivery and payment if applicable; Levels of electronic services maturity are shown in the figure (Fig. 1)

Achieving the highest level does not always mean executing the service at the transaction level, for example, some services are one-sided information reported to the authority and do not require a decision. Therefore, also among the criteria's for assessing the progress of e-Europe, used by the Commission of the European Union a key place takes accessibility for citizens and businesses to public services and the quality of these services. However, you can see that the achievement of 3rd and especially 4th maturity level requires:

ensure the authenticity, integrity and non-repudiation of origin of exchanged information it means the legal effectiveness of that information, and the need for automation of the service and hence the need to automate the processing of information associated with the service execution.

Public services should therefore be considered in these two dimensions: in terms of legal regulations and technical implementation.

Document and its features

The document is any tangible or symbolic indication, fixed or saved in order to prove the phenomenon of physical or mental [START_REF] Briet | Qu'est-ce que la documentation? Paris: Documentaires Industrielles et Techniques 10[END_REF], it means that document is a resource used as evidence. However, the concept of the document in the language of computer makes some problems, it is commonly equated -the concept of electronic document and the concept of the file.

The file is a collection of data stored in permanent memory (hard disk or other media), which can be seen by the user of the operating system as a unitary, indivisible, closed as a whole, having a distinct name and a specific structure. It is the result of working with a computer program, writable and then readable.

It seems that the most preferred would be to combine the two approaches, and without changing the concept of the primary document concept, state that:

-An electronic document is a document in the form of a file, which has all the features of the document and all the features of the file. -Data are stored on a medium. In the case of electronic information the data can be processed, communicated and interpreted by computer. A set of data may sometimes constitute a record [10]. -The international Council on Archives [10] Committee on electronic records defines a record as 'a specific piece of recorded information generated, collected or received in the initiation, conduct or completion of an activity and that comprises sufficient content, context and structure to provide proof or evidence of that activity'.

Legal effectiveness of the document is ensured by document features:

integrity -the immutability of content (document content), authenticity -by knowledge of the origin of the document, non-repudiation -no possibility to denial of the document authorship.

These definitions and referenced to the concept of the document. These features are implemented using a handwritten signature or electronic signature. Moreover, as already stated above, documents have features such as:

-Durability -the possibility to store on a durable medium (in relation to traditional documents, such as paper, parchment, papyrus, stone tables, images etc., in relation to an electronic document can be a disk, tape, memory, etc.) -Autonomy -it constitutes a single, closed as whole, standalone entity (independent, autonomous -data and visualization is one object).

-Interoperability -readable / interpretation by any of the entities involved in the transaction

If the document is to be used in the execution of electronic services for the exchange of legally binding information, it must be possible to.

its transmission in electronic form,, automatic reading and writing of data in file, automatic processing across different systems, automatic verification of features for its legal effectiveness, recording and storing in electronic warehouses (databases, file systems). General features of document and specific features of electronic document are depicted on the following figure (Fig 2 ):

Fig.2 Each electronic document is a document and has all of its features

The European Union Directive [11] and its national implementations in the form of national acts [12], equates in terms of legal effectiveness, the handwritten signature and the electronic signature. Thus electronic signature plays a key role in ensuring the legal effectiveness of an electronic document. In addition, it is possible and even desirable to implement other features of the handwritten signature in electronic signatures, such as:

the possibility of signing one or more parts of the document by one signature, ability to place in the document number of signatures (signing -including the indicated part of the document) possibility of countersigning. Such possibilities are given by XML Signature format -XMLdSig [START_REF]XML Signature Syntax and Processing[END_REF] and its development -XAdES [START_REF]XML Advanced Electronic Signatures[END_REF]. Below, see figures Fig. 3 and Fig. 4, the example of model-ling the contents of signature in electronic ebForm document is presented (ebForm is xml format of electronic document in the shape of electronic form defined by author:

Syntax and semantics of data in electronic document

Each file, holds in its content some information is built according to specific rules. These rules define the file format and are composed of the syntax, which is the definition of relationships between elements (data) stored in the file, and the semantics (meaning), a description of the interpretation of the data placed in certain syntactic constructions.

To ensure unambiguous and clear interpretation (by peoples and systems) of information contained in the file, the file format must be used in accordance with principles set out in the specification of the file format.

The problem of determining the format of the data containing information necessary for the implementation of electronic services, is crucial from the point of view of interoperability and universality. It is not a major problem, through the widespread use for this purpose XML. XML has become the informal but extremely popular and the applicable standard [START_REF]Extensible Markup Language (XML[END_REF][START_REF]Blake Dournaee XML Security[END_REF][START_REF] Hassler | Security Fundamentals for E-Commerce[END_REF].

In addition to many features of XML, such as:

platform independence and software being applied using, support for a universal set of national characters UNICODE clarity and ease of processing.

Special attention should be payed to:

the ability to define the syntax and automatic verification of information structure with the syntax, the ability to import syntactic structures defined in another place that is possibility to use data structures already defined, the ability to identify both the document and components imported using namespace (namespace) [18].

At present the centralized model of electronic services implementation and execution is used in Poland. This is such approach to the construction of electronic public services, in which the document formats, data dictionaries and ways of delivering services are defined, implemented and executed by a designated central organization and other organizations have to subordinate to this central organization. This approach causes the separation of the responsibility for the implementation of services in its real terms from implementing the same services in the electronic (virtual) dimension. The model is complicated by the possibility of existing a few centers (tax authorities, local authorities and government) responsible for different areas of activity This is shown in the Fig. 5.

Fig.5. The centralized model of electronic services -the existence of several

different centers is possible Considerations in the area of syntax and semantics of the data in an electronic document and the features and capabilities of XML are of particular importance in light of the concept of decentralization of public services and posting obligation to implement them to the places (institutions, organizations), where those services are actually carried outsee figure Fig. 6.

The decentralized model of defining the specifications and publishing electronic documents, is presented in this article assumes that:

document formats (syntax and meaning) are defined and published by these organizations, which are responsible for the implementation of electronic service using defined document, data structures and data are defined in organizations using namespace that has the form of a URL, as in the domain name owned by the organization responsible for implementing the service. This provides a unique and unambiguous terms used in the exchange of documents.

-Appearance (visualization of the document), taking into account specific regulations as well as freedom of visualization within a certain range (tax form, invoice)

Using the possibility of identifying formats (syntax and semantics) of specific documents and data using namespace makes it possible to avoid the need for a use the central repository of model (specifications) of documents (or electronic forms). Namespace has the form of a URL, which part is the domain name owned entity responsible for the specification of certain documents. It is therefore possible "exit" the responsibility for defining these specifications and definitions of the central office to the organization responsible for implementing the service, ensuring the uniqueness of identifiers and compliance concepts contained in an electronic document with the terms defined in the act regulating the implementation of the service.

Practical use of the principles presented above, would be the universal application of the rule of expansion of legal acts which describe the public service, by the entity implementing this service by the syntax definition of electronic documents (in the form of a DTD or XML Schema) with a description of its meaning. A description of the syntax and semantics would be a complement to this part of the act, where documents and forms in its traditional form are described Such an approach would at the same time the specification of requirements for software vendors in regards not only to data formats and visualization, but also the acceptable range of visualization freedom (eg. strictly defined tax form, or the appearance of freeform invoice).

The decentralization of the electronic services execution is:

reflection of the actual geographical and functional decentralization of services delivery; linking responsibility for the electronic dimension of the service with the real service (one entity responsible for the execution of services in real and electronic dimension); -The implementation of electronic services, complementary/extension services in a manner consistent with local customs and requirements.

Easier and unambiguous definition of the concepts related to the particular servicethese definitions, as a part of the act regulating the implementation of services are created in the same place and in the same act.

A special, very important role in the exchange of information associated with the delivery of services regardless of method of realization: whether it is e-service, or provided traditionally, regardless of the model -the central or decentralized, regardless of the area (industry), plays the form. Natural need to enter data in the appropriate space limits the possibilities of interpreting the meaning of these data so that the form is a convenient means to collect the data necessary for the service, as well as the processing of these data, which is important especially for automatic execution of these processes. Taking into account the fact that the currently performed service may be fully or partially carried out automatically and partially, by human it would be relevant to make use of such an electronic document (form), with the use of suitable software, which could be used by a man and simultaneously processed in computer systems.

Fig.6. Decentralized (distributed) model of electronic services -organization delivers services in real and electronic form 5 Electronic form

Electronic document containing the information necessary to execute the service is processed automatically. Identification of the document type and the particular data using namespace allows unambiguous interpretation of these data (interpretation is published in the type specification document and published in the act of describing the realization of the service as described in the discussion on the implementation of services in the decentralized model) by all entities taking part in the service. The use of a document in XML format syntax as XML schema, makes possible to automatic verification of document syntax and automatic document processing.

If documents are exchanged between systems that implement the services (or services that form part of other service), then visualization of the data is not necessary, because the machine executing the service has been implemented in accordance with publicly available specifications described above.

However, if the party taking part in the execution of the service is the human, the document must be presented to the user. Human must understand the document, type the information to it and consciously sign this document.

Similar to the traditional paper document, the most convenient form of the document for this purpose is the form. The electronic form it is a document containing free places for data representing desired information, and to ensure the characteristics of the document -signature. The data are entered in the form in which the appearance of the form and arrangement of fields for entered data determine the semantics of these data. In terms of the form it is a document in which visualization and data are one inseparable entity, in which the semantics of data is determined by the graphical environment of the data. Thus, if an electronic document will contain both the data and its presentation it will be electronic implementation -a metaphor of the traditional paper form readable / understandable by man and at the same time possible to automatic processing using commonly available tools.

It should be noted that the concept of an electronic form presented above, in accordance with its traditional understanding deviates from the currently existing electronic forms, in which an separation of presentation layer and the data layer is implemented (eg. An HTML in which "forms" are used to collect data to be sent to the server, or separating data from presentation of XML documents with reference to the transformation file XSLT). Visualization layer is responsible for presenting the form view, the user enters the required data, which are sent to the service provider (after separating them from the presentation layer -the graphical environment determining the semantics of these data). This approach prevents a uniform semantic interpretation of the transmitted (stored) data.

In the proposed solution the form is an electronic document based on XML, with syntax defined using XSD [XML Schema Definition], applying electronic signatures based on XMLDSig/XAdES [XML Advanced Electronic Signatures], containing both the data and the description of the presentation (visualization) of the form in one single filesee Fig. 7. In addition to its "traditional functionality" electronic form can and should be enhanced with the features offered by the Information Technique such as:

possibility to verify the formal validity of data, possibility to define default values, possibility to define of help and tips, providing a dynamic (or lock) input fields.

calculating the value of each field based on the data entered into other fields.

ability to define the mechanisms of communication and ways of exchanging data between the form and the environment through a well known protocols as email or web services protocols.

All these features are part of the form and are part of the document together with the data and presentation. This is due to the need to ensure that the description of the method of processing and presentation of data is accessible and known to all users in order to avoid doubts in interpretation. In the following figure (Fig, 8) the example of definition of text field ("textField" element) with its properties is presented (ebForm format).

<textField X="0" Y="2" height="20" horizontalAlignment="Right" id="Pismo.MiastoPowstania. Komponent Form features defined in this way, make it possible to use the form as an information medium that is synonymous with the traditional document (form) and to use the form as a intelligent interface to services, where form is a generator of messages sent out, or processor of message received from service, and involving human.

Very wide range applications of electronic forms could be enumerated. Such forms is a generic solution with can be used in different areas regardless of business areaform small companies for ordering and invoicing, thru activities associated with internal company management up to support for Client -Business, Client -Administration and Business -Administration operations. It can be applied wherever legally effective information is required or forms are being used (exchanged) both by human and machines, or by human only.

7

The use of electronic formsapplications/implementations Electronic forms based on the concept presented in the article can be used wherever legal effectiveness is required, regardless of the area of activity and the size of the business.

Electronic form looks exactly like its traditional counterpart. The logic of usage is also identical.

It can be transferred/delivered to recipient using widely known mechanisms like: simple mail as attachment to mail message or SOAP as Soap envelope content. It also can be transferred as ordinary file.

It can be simply processed by information systems using standard XML parsers and then integrated with internal organization's systems including data retrieval and transferring data to internal databases. For example:

-Exchange documents (agreements, orders, others) using SMTP, as attachment, -Implementation of simple document flow even composed of few steps of document exchange within company or between companies (holiday arranging, internal reports etc…) and integration with internal systems and databases using SMTP or services implemented using SOAP protocol. -Legally effective delivery of a document to the public authority with the official synchronous (immediately) confirmation of delivery / reception. The confirmation is digitally signed part of the document, and document is automatically integrated with internal authority system, -Legally effective delivery of a document to resipient (human) using SMTP with confirmation signature of recipient (client) returned to sender. -Implementation of fiscal charges undeniably linked with the document. This shows, that presented concept of the form, in contrast to formats presented in the introduction (.doc, odt, pdf/xfdf, xfdl), allows:

-exact implementation of traditional documents.

-automatic document processing.

-automatic signatures verification (authorization, authentication).

-document integration with existing systems.

-ensuring the legal effectiveness of the document.

Summary

Electronic services are typically implemented using dedicated, closed -demanding and accounts of users. Legal effectiveness of documents used for the transaction is provided only in the space of the system. The autonomy and interoperability of document is violated -it can not exist out of dedicated system. Another way to implement such transactions is the use of signed PDF documents and PDF forms. The use of such documents is a source of serious problems and costs associated with processing its.

In turn, the use of e-mail (SMTP) does not provide legal effectiveness and also creates serious problems with messages processing.

The proposed concept of electronic documents in the shape of forms using the XML format, containing both a description of visualization and data input, signed with electronic signatures and containing other elements (calculations, verification rules, defaults, etc.).

The concept of electronic form presented in this paper is a subject of work in progress at the stage of wide testing. Results of work will be presented in future papers.

Fig 1 .

 1 Fig 1. Maturity levels of electronic services 0 -The service is not (in any form) provided electronically:

Fig. 3 .Fig. 4 .

 34 Fig.3. Example of definition of signature content (XML element XPath) signing the client signature (one of the many users) in the ebForm form) <ds:XPath>(ancestor::*/parent::value or ancestor-or-self::ds:Signature/ancestor::formSignature or ancestor-or-self::ds:Signature/ancestor::signature//parent::ebForm or ancestor::content/ancestor::attachment or ancestor::*/ancestor::*/ancestor::mailStatus or ancestor::*/ancestor::value/ancestor::soap-RPC or ancestor::body/ancestor::request or ancestor::header/ancestor::request or ancestor::body/ancestor::response) </ds:XPath> Fig.4. Example of definition of signature content (XML element XPath) signing the form template in the ebForm form

Fig. 7 .

 7 Fig.7. Electronic form (syntax -XSD, data XML, presentation XML) -example of Polish tax declaration form

Fig. 8 .

 8 Fig.8. Example of defining the features in the form (value, default value, background, help text, text, hints, validation rules)


Michal Czolombitko
email: m.czolombitko@pb.edu.pl

Jaroslaw Stepaniuk
email: j.stepaniuk@pb.edu.pl

Attribute reduction based on MapReduce model and discernibility measure

Keywords: Rough Sets, MapReduce, reducts, attribute reduction, core

This paper discusses two important problems of data reduction. The problems are related to computing reducts and core in rough sets. The authors use the fact that the necessary information about discernibility matrices can be computed directly from data tables, in the case of this paper so called counting tables are used. The discussed problems are of high computational complexity. Hence the authors propose to use the relevant heuristics, MRCR (MapReduce Core and Reduct Generation) implemented using the MapReduce model.

Introduction

Since the massive data could be stored in cloud platforms, data mining for the large datasets is hot topic. Parallel methods of computing are alternative for large datasets processing and knowledge discovery for large data. MapReduce is a distributed programming model, proposed by Google for processing large datasets, so called Big Data. Users specify the required functions Map and Reduce and optional function Combine. Every step of computation takes as input pairs < key, values > and produces another output pairs < key ′ , values ′ >. In the first step, the Map function reads the input as a set < key, values > pairs and applies user defined function to each pair. The result is a second set of the intermediate pairs < key ′ , values ′ >, sent to Combine or Reduce function. Combine function is a local Reduce, which can help to reduce final computation. It applies second user defined function to each intermediate key with all its associated values to merge and group data. Results are sorted, shuffled and sent to the Reduce function. Reduce function merges and groups all values to each key and produces zero or more outputs.

Rough set theory is mathematical tool for dealing with incomplete and uncertain information [START_REF] Pawlak | Rudiments of rough sets[END_REF]. In the decision systems, not all of the attributes are needed in decision making process. Some of them can be removed without affecting the classification quality, in this sense they are superfluous. One of the advantage of rough set theory is an ability to compute the reductions of the set of conditional attributes, so called reducts.

In recent years, there has been some research works combining MapReduce and rough set theory. In [START_REF] Zhang | A parallel method for computing rough set approximations[END_REF] parallel method for computing rough set approximations was proposed. The authors continued their work and proposed in [START_REF] Zhang | A parallel matrix-based method for computing approximations in incomplete information systems, systems[END_REF] three strategies based on MapReduce to compute approximations in incomplete information systems. In [START_REF] Yang | Parallelized Computing of Attribute Core Based on Rough Set Theory and MapReduce[END_REF] method for computing core based on finding positive region was proposed. They also presented parallel algorithm of attribute reduction in [START_REF] Yang | Attribute Reduction for Massive Data Based on Rough Set Theory and MapReduce[END_REF]. However authors used model MapReduce only for splitting data set and parallelization computation using one of traditional reduction algorithm. In [START_REF] Lee | A Design of a Patient-customized Healthcare System based on the Hadoop with Text Mining (PHSHT) for an efficient Disease Management and Prediction[END_REF] is proposed a design of a Patient-customized Healthcare System based on the Hadoop with Text Mining for an efficient Disease Management and Prediction.

In this paper we propose a parallel method MRCR (MapReduce Core and Reduct Generation) for generating core and one reduct or superreduct based on distributed programming model MapReduce and rough set theory. In order to reduce the memory complexity, instead of discernibility matrix were used counting tables to compute discernibility measure of the datasets. The results of the experiments on real datasets show that the proposed method is effective for big data.

This paper is organized as follows. Section 1 includes background introduction to rough sets. Problem of attribute reduction and algorithm of generating core using counting tables are presented in Section 2. Parallel algorithm MRCR based on discernibility measure and MapReduce is proposed in Section 3. Results of experiments and analysis is presented in Section 4. Conclusions and future work are drawn in the last Section.

Reducing number of attributes

Reduct and Core Computation

Let DT = (U, A ∪ {d}) be a decision table, where U is a set of objects, A is a set of conditional attributes and d is a decision attribute. Reduct is subset of conditional attributes R ⊆ A, sufficient to get information which we need from the decision table. Superreduct is not necessarily minimal set of those attributes. The core is a set of conditional attributes, which are cannot be removed from original data set without affecting the quality of the classification.

In order to compute the core and reduct we can use discernibility matrix introduced by Prof. Andrzej Skowron (see e.g. [START_REF] Pawlak | Rudiments of rough sets[END_REF][START_REF] Stepaniuk | Rough-Granular Computing in Knowledge Discovery and Data Mining[END_REF]). Discernibility Matrix is two dimensional table indexed by the objects. Cells of the discernibility matrix contains set with all of conditional attributes on which corresponding objects have different values. Number of not empty cells is discernibility measure of set A. The core is the set of all single element entries of the discernibility matrix. In some cases core can be an empty set.

However, memory complexity of creating discernibility matrix is equal to (cardinality(U )) 2 * cardinality(A). This makes impractical using this structure for large data sets, so called Big Data. Solution could be using counting tables to compute discernibility measure. In next subsection we present method for computing the core, which is base to finding one of the reducts.

Pseudocode for Generating Core Based on Discernibility

Measure of a Set of Attributes

Generating core based on discernibility measure was discussed in [START_REF] Nguyen | Approximate Boolean Reasoning: Foundations and Applications in Data Mining[END_REF]. Counting table CT is a two-dimensional array indexed by values of information vectors (vector of all values of an attribute set B ⊆ A) and decision values, where

CT (i, j) = cardinality({x ∈ U : x B = i and d(x) = j})
Pessimistic memory complexity of creating this type of matrix is equal to cardinality(U ) * cardinality(V d ), where V d is a set of all decisions.

The discernibility measure disc(B) of set of attributes B ⊆ A can be calculated from the counting table as follows:

disc(B) = 1 2 i,j k,l CT (i, j) • CT (k, l), if i = k and j = l
The discernibility measure is the number of non empty cells in discernibility matrix.

Below is the pseudocode for this algorithm:

Input: decision table DT = (U, A ∪ {d}) Output: Core ⊆ A 1: Core ← ∅
CT ( x A , d(x)) ← CT ( x A , d(x)) + 1 5: end for 6: disc(A) ← 0 7: for [x] A ∈ U/IN D(A) {U/IN D(A) is partition of U defined by A} do 8: for [y] A ∈ U/IN D(A) do 9: if x A = y A and d(x) = d(y) then 10: disc(A) ← disc(A) + CT ( x A , d(x)) • CT ( y A , d(y)) 11: end if 12:
end for 13: end for 14: CT ← 0 15: for a ∈ A do 16: end if 31: end for Input to the algorithm is a decision table DT , and output is the core C of DT . In the beginning core C is initialized as empty set and all values in the counting table are set to zero. First loop in line 3 generate counting table for set of all conditional attributes. For each object in decision table, value in array is increased by one. Indexes of value are information vector of object and its value of decision. In the line 6 value of discernibility measure of set of all conditional attributes, disc(A), is initialized as zero. Next two loops in lines 7 and 8 take subsequent equivalence classes to comparison. If information vectors of these classes are not equal, disc(A) is increased by product of two values from the counting tables where indexes are values information vectors and different decisions. Next step is computing the discernibility measure of set of attributes after removing one of them. In line 14 all values in the counting table are set to zero. Loop in line 15 takes attribute a from set of all conditional attributes A. Set B is initialized as set of all conditional attributes after removing this attribute. Similarly as above, in lines 15-27 is calculated disc(B). Finally, values of the discernibility measure of set of all attributes and after removing attribute a are compared in the line 28. In case of difference, this attribute is added to the core.

B ← A -{a} 17: disc(B) ← 0 18: for x ∈ U do 19: CT ( x B , d(x)) ← CT ( x B , d(x)) + 1 20: end for 21: for [x] B ∈ U/IN D(A) do 22: for [y] B ∈ U/IN D(A) do 23: if x B = y B and d(x) = d(y) then 24: disc(B) ← disc(B) + CT ( x B , d(x)) • CT ( y B , d(y))

MapReduce Implementation -proposed method

The main concept of the proposed algorithm MRCR is parallel computation of counting tables and discernibility measure for each of conditional attributes and potential reducts. We extended the method proposed by us in [START_REF] Czo Lombitko | Generating core based on discernibility measure and MapReduce, Pattern recognition and machine intelligence: 6th International conference[END_REF] on parallel computing discernibility measure and adopt to computing the reduct.

Algorithm MRCR Input: decision table DT = (U, A ∪ {d}) Output: reduct R 1: Core ← ComputeCoreM R(DT ) {See Step 1a & Step 1b } 2: B ← A -Core 3: R ← Core 4: while disc(A) > disc(R) do 5:
for a ∈ B do

6: P R a ← R ∪ {a} 7:
end for 8:

ComputeDiscM easureM R(P R, DT ) {See Step 2}

9:
R ← max disc(P R a )) {function returns the set with the largest value of discernibility measure} 10:

B ← B -R 11: end while

The proposed algorithm consists of two main steps: compute core and one reduct. Both stages are composed of two operations Map and Reduce. After computing core, set B is initialized as a set of attributes that not in the core and reduct as a set attributes that are in core.

Table P R (potential reducts) is initialized in the line 6 as a collection containing sets that are unions of the reduct and the every attribute from set B. For each of these sets is parallel calculated the discernibility measure in the line 9. As a new reduct is chosen a set with the maximal discernibility measure and from set B is removed the attribute added to the reduct. Operations in lines 5-10 are repeated until the discernibility measures of the reduct and the set containing all conditional attributes aren't equal.

Step 1a. ComputeCoreMR -Counting Tables Map Input: key : subtable id, value: decision subtable DT i = (U i , A ∪ {d}) Output: < key ′ , value ′ > pair where key ′ : ( x B , d(x)) and value ′ is id of the object x 1: for x ∈ U i do 2:

key ′ ← ( x A , d(x)) 3:
value ′ ← id of the object x end for 11: end for Input to function Map are: key is a subtable id stored in HDFS, and value is decision subtable DT i = (U i , A ∪ {d}). First loop in line 1 takes an object from decision subtable DT i and emits pair < key ′ , value ′ >, where key ′ is information vector with respect to set of all conditional attributes and decision of the object x, and value is id of the this object. Loop in line 5 takes attribute a from set of all conditional attributes A. Set B is initialized as set A after removing this attribute. Next step is emitting pair < key ′ , value ′ >, where key ′ is information vector with respect to set B and decision of the object x, and value ′ is id of this object. value ′ ← value ′ + value 5: end for 6: emit(< key ′ , value ′ >) Input to function Reduce are < key, value > pairs where key : ( x B , d(x)) and value is the number of objects belonging to equivalence class [x] B with the same decision from decision subtable DT i . Function emits pairs < key ′ , value ′ >, where key ′ is ( x B , d(x)) and value ′ is a number of the objects associated with this key from decision table DT . Each of these pair is emitting (See fig. 1). key ′ ← removed attribute 3:

Reduce

value ′ ← x B , d(x), count( x B , d(x)) 4:
emit(< key ′ , value ′ >) 5: end for Input to the Map operation is directory contains files with pairs < key, value > where key : ( x B , d(x)) and value is number of the objects belong to [x] B with the same decision value. Loop in the first line takes every pair < key, value > and emits < key ′ , value ′ > pair where key ′ is the removed attribute from the set of the conditional attributes and value ′ contains x B , d(x) and the number of objects belonging to equivalence class [x] B with equal decision valuescount( x B , d(x)).

Reduce

Input: the pairs < key, value > where key is the removed attribute a from the set of the conditional attributes A and value : ( x B , d(x), count( x B , d(x))) Output: < key ′ , value ′ > pair where key ′ is the removed attribute a from the set of the conditional attributes and value ′ is the discernibility measure of set A after removing attribute a 1: disc(A -{a}) ← 0 2: for all ( x B , d(x), count( x B , d(x))) do

disc(A -{a}) ← disc(A -{a}) + count( x B , d(x))) • count( y B , d(y)) 6: end if 7:
end for 8: end for 9: key ′ ← a 10: value ′ ← disc(A -{a}) 11: emit(< key ′ , value ′ >)

Input to the Reduce operation are pairs < key, value > where key is the removed attribute a from the set A of conditional attributes and value : ( x B , d(x), count( x B , d(x))). Two loops in lines 2 and 3 take subsequent lines from input to comparison. If these two pairs contains information about two different information vectors and decisions, disc(A -{a}) is increased by product of count( x B , d(x)) and count( y B , d(y)).

Computing the core consists of finding in the output files all attributes that cannot be removed from set A without decrease of the discernibility measure.

Step 2. ComputeDiscMeasureMR Counting Tables -Map Input: key : subtable id, value: decision subtable DT i = (U i , A ∪ {d}) , table P R -potential reducts Output: < key ′ , value ′ > pair where key ′ : ( x B , d(x)) and value ′ is id of the object x

1: for x ∈ U i do 2:

for P R i ∈ P R do 3:

key ′ ← ( x P Ri , d (x)) 4:
value ′ ← id of the object x 5:

emit(< key ′ , value ′ >)

6:
end for 7: end for Input to function Map are: key is a subtable id stored in HDFS and value is decision subtable DT i = (U i , A ∪ {d}) and potential reducts.

Reduce operation is the same like in operation Reduce in the Step 1a. The discernibility measure is computing similarly like in the Step 1b so its description will be skipped.

The output of the second step are files containing subsets of the conditional attributes with their discernibility measure.

Experimental Results

The algorithm MRCR was running on the Hadoop MapReduce platform [START_REF]Hadoop MapReduce[END_REF], where Hadoop MapReduce is a YARN-based system for parallel processing of big datasets. In the experiments, Hadoop 2.5.1 version was used. All the computation nodes have four 3.4 GHz cores processors and 16 GB of memory. All files were stored in HDFS. Each file was merged on blocks and each of those blocks was replicated tree times. A bound of the proposed method is available free disc space in distributed file system for files and temporary data.

In this paper, we present the results of the conducted experiments using data about children with insulin-dependent diabetes mellitus (type 1) and dataset KDDCup-99 from the machine learning data repository, University of California at Irvine [2].

Diabetes mellitus is a chronic disease of the body's metabolism characterized by an inability to produce enough insulin to process carbohydrates, fat, and protein efficiently. Treatment requires injections of insulin. Twelve conditional attributes, which include the results of physical and laboratory examinations and one decision attribute (microalbuminuria) describe the database used in our experiments. The data collection so far consists of 107 cases. The database is shown at the end of the paper [START_REF] Stepaniuk | Knowledge discovery by application of rough set models, Rough Set Methods and Applications[END_REF]. A detailed analysis of the above data is in chapter 6 of the book [START_REF] Stepaniuk | Rough-Granular Computing in Knowledge Discovery and Data Mining[END_REF]. This database was used for generating bigger datasets consisting of 1 • 10 6 to 20 • 10 6 of objects. New datasets were created by randomly multiplying the rows of original dataset.

The data set KDDCup-99 consists of almost five million objects. Each object is described by forty one conditional attributes and one decision attribute. Informations gather in this dataset can be used to build a network intrusion detector. This database was used for generating smaller datasets consisting approximately of 0.25 •10 6 to 5 •10 6 of objects. New datasets were created by randomly splitting the rows of original dataset.

Numerical values in both datasets were discretized.

Speedup

In speedup tests, the dataset size is constant and the number of nodes grows in each step of experiment. To measure speedup, we used dataset diabetes contains 20•10 6 objects and whole KDDCup-99 dataset. The speedup given by the n-times larger system is measured as [START_REF] Xu | A fast parallel clustering algorithm for large spatial databases[END_REF]:

Speedup(n) = t n t 1
where n is number of the nodes in cluster, t 1 is the computation time on one node, and t n is the computation time on n nodes.

The ideal parallel system with n nodes provides n times speedup. The linear speedup is difficult to achieve because of the I/O operations data from HDFS and the communication cost between nodes of Hadoop cluster. Fig. 3 shows that with the growth of the number of nodes, the speed performs better.

Scaleup

Scaleup analysis measures stability system when system and dataset size grow in each step of experiment. The scaleup coefficient is defined as follows [START_REF] Xu | A fast parallel clustering algorithm for large spatial databases[END_REF]:

Scaleup(DT, n) = t DT1,1 t DTn,n
where t DT1,1 is the computational time for dataset DT on one node, and t DTn,n is the computational time for n times larger dataset DT on n nodes. Table shows number of attributes in computed the core and the reduct for KDDCup-99 dataset.

Fig. 3 shows the scalability of algorithm for KDDCup-99 dataset strictly depends on the size of the core and the reduct. For the diabetes dataset scalability of the proposed parallel algorithm stabilize when the number of the nodes is equal 15.

Table 1. Size of the core and the reduct in scaleup experiment for KDDCup-99 dataset

Sizeup

In sizeup tests, the number of nodes is constant, and the dataset size grows in each step of experiment. Sizeup measures how much time is needed for calculations when the size of dataset is n times larger than the original dataset. Sizeup is defined as follows [START_REF] Xu | A fast parallel clustering algorithm for large spatial databases[END_REF]:

Sizeup(DT ) = t DTn t DT1
where t DT1 is execution time for a given dataset DT , and t DTn is execution time n times larger dataset than DT . Fig. 4 shows the sizeup experiments results on twenty nodes. Results shows that the proposed algorithm copes well with the growing amount of data.

Conclusions and Future Research

In this paper, attribute reduction for large datasets based on rough set theory is studied. A parallel attribute reduction algorithm MRCR is proposed, which is based on the distributed programming model of MapReduce and the reduct computation algorithm using discernibility measure of a set of attributes. It is worth noting that a very interesting element of the paper is an usage of a counting table instead of a discernibility matrix. The results of the experiments show that the proposed method is efficient for large data, and it is a useful

4 : 7 :

 47 emit(< key ′ , value ′ >)key ′ ← ( x B , d(x)) 8:value ′ ← id of the object x 9:emit(< key ′ , value ′ >) 10:

Fig. 1 . 1 :

 11 Fig. 1. The Reduce operation in the Step 1a

3 :

 3 for all ( y B , d(y), count( y B , d(y))) do 4: if x B = y B and d(x) = d(y) then 5:

Fig. 2 .

 2 Fig. 2. Speedup

Number 1 2Fig. 3 .

 13 Fig. 3. Scaleup

Fig. 4 .

 4 Fig. 4. Sizeup

  Input: < key, value > where key : ( x B , d(x)) and value is the number of objects belonging to equivalence class [x] B with equal decision values from decision subtable DT i . Output: the files containing pairs < key ′ , value ′ > where key : ( x B , d(x)) and value ′ is the number of objects belonging to equivalence class [x] B with equal decision values from decision table DT . 1: key ′ ← key 2: value ′ ← 0 3: for all value do

	4:

Acknowledgements

This research was partially supported by the grant S/WI/3/2013 of the Polish Ministry of Science and Higher Education. The experiments were performed using resources co-financed with the European Union funds as a part of the "Centre for Modern Education of the Bialystok University of Technology" project (Operational Programme Development of Eastern Poland).


Maciej Kopczynski
email: m.kopczynski@pb.edu.pl

Tomasz Grzes
email: t.grzes@pb.edu.pl

Jaroslaw Stepaniuk
email: j.stepaniuk@pb.edu.pl

Hardware Supported Rough Sets Based Rules Generation for Big Datasets

Keywords: Rough sets, FPGA, hardware, rules

In this paper we propose a combination of capabilities of the Field Programmable Gate Arrays based device and PC computer for rough sets based data processing resulting in generation of decision rules. Solution is focused on big datasets. Presented architecture has been tested in programmable unit on real datasets. Obtained results confirm the significant acceleration of the computation time using hardware supporting rough set operations in comparison to software implementation.

Introduction

The rough sets' theory was developed in the eighties of the twentieth century by Prof. Z. Pawlak and is an useful tool for data analysis. A lot of rough sets algorithms were implemented in scientific and commercial tools for data processing. Data processing efficiency problem is arising with increase of the amount of data. Software limitations leads to the search for new possibilities.

Field Programmable Gate Arrays (FPGAs) are the digital integrated circuits which function is not determined during the manufacturing process, but can be programmed by engineer any time. One of the main features of FPGAs is the possibility of evaluating any boolean function. That's why they can be used for supporting rough sets calculations.

At the moment there are some hardware implementation of specific rough set methods. The idea of sample processor generating decision rules from decision tables was described in [START_REF] Pawlak | Elementary rough set granules: Toward a rough set processor[END_REF]. In [START_REF] Lewis | Learning in Hardware: Architecture and Implementation of an FPGA-Based Rough Set Machine[END_REF] authors presented architecture of rough set processor based on cellular networks described in [START_REF] Muraszkiewicz | Towards a Parallel Rough Sets Computer In: Rough Sets, Fuzzy Sets and Knowledge Discovery[END_REF]. In [START_REF] Kanasugi | A basic design for rough set processor[END_REF] a concept of hardware device capable of minimizing the large logic functions created on the basis of discernibility matrix was developed. More detailed summary of the existing ideas and hardware implementations of rough set methods can be found in [START_REF] Kopczyński | Hardware Implementations of Rough Set Methods in Programmable Logic Devices, Rough Sets and Intelligent Systems -Professor Zdzis law Pawlak in Memoriam[END_REF].

None of the above solutions is complete, i.e. creates a system making it possible to solve each problem from wider class of basic problems related to rough sets. Our aim is to create such a system. Authors are working on fully operational System-on-Chip (SoC) including central processing unit based on Altera NIOS II core implemented in Stratix III FPGA and co-processor for rough sets calculations. More details on previous authors' work can be found in [START_REF] Grześ | FPGA in rough set based core and reduct computation[END_REF][START_REF] Kopczyński | FPGA in Rough-Granular Computing : Reduct Generation[END_REF][START_REF] Kopczyński | Generating core in rough set theory : Design and implementation on FPGA[END_REF][START_REF] Kopczyński | Core for Large Datasets : Rough Sets on FPGA[END_REF][START_REF] Stepaniuk | The First Step Toward Processor for Rough Set Methods[END_REF]].

Introductory Information

Notions

Let DT = (U, A ∪ {d}) be a decision table, where U is a set of objects, A is a set of condition attributes and d is a decision attribute.

Notions and definitions used in pseudocode shown in next section are presented below for the clarity of understanding:

t -pair (a, v), where a is a condition attribute and v is a value for this attribute,

-[t] -set of objects fulfilling single condition t = (a, v), i.e. [(a, v)] = {x ∈ U : a(x) = v} -[T ] -set of objects fulfilling every condition t ∈ T , i.e. [T ] = t∈T [t]

Algorithm for Hardware Supported Rule Generation

This section describes pseudocode for an algorithm of rule generation based on LEM2 (Learning from Examples Module -version 2) solution presented by J. W. Grzymala-Busse in [START_REF] Grzymala-Busse | Rule induction, Data Mining and Knowledge Discovery Handbook[END_REF]. We called this algorithm HRG2-LEM2 (Hardware Rules Generation version 2 -LEM2). There are two main differences between HRG2-LEM2 algorithm and one described by J. W. Grzymala Busse. First is that HRG2-LEM2 is using hardware supported units for operations related to counting the elements as well as creating and checking sets of objects fulfilling a given condition. Second important difference is introduction of input dataset decomposition that allows for processing data by fixed size hardware modules. Further details on hardware part are presented in Section 3. Algorithm parts supported by hardware are prefixed with [H1] or [H2] in pseudocode. [H1] is module for calulating objects classes (unit dtComparator ), while [H2] is module for calculating number of objects fulfilling condition t = (a, v) (unit avCounter ). Further details are included in Section 3.2. For clarity of understanding, algorithm pseudocode is kept as close as possible to the original one. Authors avoided diving into hardware details, becuase pseudocode would become hardly understandable. Results generated by hardware blocks and their design is presented in Section 3.2. while G = ∅ do 7:

HRG2-LEM2 Algorithm (Hardware Rules

T ← ∅ GR ← GR ∪ LR 29: end for Input of the algorithm is decision table DT and precomputed lower approximations set LA for every decision class related to value of decision attribute d. Output is global rule set GR. Main algorithm loop in line 2 runs for every value vd of attribute d because lower approximations were precomputed for every decision class related to values of d attribute. Given lower approximation is loaded into set lowerApprox in line 3. Then lowerApprox is copied to the temporary set G in line 4. This set is recomputed during rule creation process performed by loop in lines 9 to 14. Local rules set LR (initialized as empty in line 5) stores rules generated for the given lower approximation (loop in lines 6 to 22). Set T that can be interpreted as single created consists of conditional parts (pairs (a, v)). All possible combinations of conditional parts based on objects in set G, are created in line 8 and are stored in set T G . This is introductory step that leads to definition of all available condition parts of rule created by loop in lines 9 to 14. Every iteration of loop leads to adding new conditional part to the rule. In line 10 best part t of the rule is chosen according to presented constraint. Line 11 adds part t to the constructed rule T . Sets G and T G are recalculated respectively in lines 12 and 13. Purpose of recalculation is removing objects covered by current rule and limit amount of possible conditional parts for future iterations of loop. Loop in lines 15 to 19 is for cutting the created rule. Cutting means removing redundant condition parts of created rule. Loop iterates over every part of temporary rule T . If rule T without its one part t is still subset of lower approximation lowerApprox (line 16), then part t is removed from rule T (line 17). New rule T is added to the local rules set LR in line 20. Set G is recalculated in line 21 by using all rules from LR set. Loop in lines 23 to 27 is used for cutting local rule set LR. Purpose of this operation is removing redundant rules covering objects that are covered by other rules. Loop iterates over every rule T stored in LR. If local rule set LR without its one part T is still subset of lower approximation lowerApprox (line 24), then part T is removed from rule set LR (line 25). Finally, local rule set LR is added to the global rule set GR.

Example of the execution of LEM2 algorithm can be found in [START_REF] Grzymala-Busse | Rule induction, Data Mining and Knowledge Discovery Handbook[END_REF]. Description of subsequent dataset processing performed by hardware units is shown in Section 2.3.

Hardware Dataset Processing in Proposed Algorithm

As it was mentioned, every line in pseudocode shown in Section 2.2 prefixed by [H1] or [H2] is processed by respective hardware unit. Input dataset is divided by control software into fixed-size parts which are subsequently processed by responsible for given operation hardware unit. General pseudocode for such processing is shown below:

HRG2-LEM2 Algorithm dataset processing INPUT: decision table DT = (U, A ∪ {d}),
RAM set ← {x ∈ U : x cnt•n to x (cnt+1)•n-1 } 4:
O part ← result of calculations performed on RAM set objects set Brief descriptions of two hardware units as well as operation result structures O and O part are given below:

-[H1] -hardware block for calulating objects classes (unit dtComparator ).

Result structure is set represented by binary values, where 1 means that given object is in output set, while 0 means that given object is not in output set. Objects and attributes are processed in parallel by checking given attribute-value pairs. One or more pairs are passed to the module, which then performs comparisions using parts of decomposed input dataset and creates binary sets as a result. -[H2] -hardware block for calculating number of objects fulfilling conditions t = (a, v) (unit avCounter ). Result structure is one-dimensional array containing number of objects equal and not equal for defined conditions t. Size of array corresponds to number of condition attributes. Similar to previous module, operations on objects and attributes are performed in parallel. Multiple pairs t = (a, v) are passed to the module and returned results are number of objects that are equal and not equal to given pair.

Data to Conduct Experimental Research

In this paper, we present the results of the conducted experiments using two datasets: Poker Hand Dataset (created by Robert Cattral and Franz Oppacher) and data about children with insulin-dependent diabetes mellitus type 1 (created by Jaros law Stepaniuk). First dataset was obtained from UCI Machine Learning Repository [START_REF] Lichman | UCI Machine Learning Repository[END_REF]. Each of 1 000 000 records is an example of a hand consisting of five playing cards drawn from a standard deck of 52. Each card is described using two attributes (suit and rank), for a total of 10 predictive attributes. There is one decision attribute that describes the "Poker Hand". Decision attribute describes 10 possible combinations of cards in descending probability in the dataset: nothing in hand, one pair, two pairs, three of a kind, straight, flush, full house, four of a kind, straight flush, royal flush.

Diabetes mellitus is a chronic disease of the body's metabolism characterized by an inability to produce enough insulin to process carbohydrates, fat, and protein efficiently. Twelve conditional (physical examination results) and one decision attribute (microalbuminuria) describe the database. The database consisting of 107 objects is shown at the end of the paper [START_REF] Stepaniuk | Knowledge discovery by application of rough set models, Rough Set Methods and Applications[END_REF]. An analysis can be found in chapter 6 of the book [START_REF] Stepaniuk | Rough-Granular Computing in Knowledge Discovery and Data Mining[END_REF].

The Poker Hand database was used for creating smaller datasets consisting of 1 000 to 1 000 000 of objects by selecting given number of first rows of original dataset. Diabetes database was used for generating bigger datasets consisting of 1 000 to 1 000 000 of objects. New datasets were created by multiplying the rows of original dataset. Numerical values were discretized and each attributes value was encoded using four bits for both datasets. Every single object was described on 44 bits for Poker Hand and 52 bits for Diabetes. To fit to memory boundaries in both cases, objects descriptions had to be extended to 64 bits words by filling unused attributes with 0's. Thus prepared hardware units doesn't have to be reconfigured for different datasets until these datasets fit into configured and compiled unit.

System Architecture and Hardware Realization

Startix III FPGA contains processor control unit implemented as NIOS II embedded core. Softcore processor supports hardware block responsible for rules generation. Hardware calculation blocks are synthesized together with NIOS II inside the FPGA chip. Development board provides other necessary for SoC elements like memories for storing data and programs or communication interfaces to exchange data and transmit calculation results.

Softcore Control Unit

Hardware modules are controlled by software execeuted in softcore processor. Main goal of this implementation is:

read and write data to hardware modules, -prepare input dataset, -perform operations on sets, -control overall operation.

Initially preprocessed on PC dataset is stored on Secure Digital card in binary version. Preprocessing includes discretization and calculation of lower approximations. In the first step of operation, dataset is copied from SD card to external DDR2 RAM module. Results of subsequent operations are stored in FPGA built-in RAM memories (MLAB, M9k and M144k).

MLAB blocks are synchronous, dual-port memories with configurable organization 32 x 20 or 64 x 10. Dual-port memories can be read and written simultaneously what makes operations faster. M9k and M144k are also synchronous, dual-port memory blocks with many possible configurable organizations. These blocks give a wide possibility of preparing memories capable of storing almost every type of the objects (words) -from small ones to big ones.

Hardware Implementation

Hardware implementation, created after analysis of the algorithm HRG2-LEM2 described in Section 2.2, was focused on accelerating the operations of calculating number of objects fulfilling attribute-value pairs (a, v) stored in decision table. Another primary important operation was generating sets of objects fulfilling conditions given as (a, v) pairs. Hardware blocks were implemented as combinational units, what means that all calculations are performed in one clock cycle. Nature of performed operation gives possibility of using them for parallel computing systems.

Two hardware modules were prepared. First of them is avCounter used for parallel counting number of objects occurrences. Second one is dtComparator, which in parallel generates sets of objects fulfilling given conditions. Below are the descriptions of prepared modules.

Diagram of avCounter module is shown on Fig. 1. Inputs of this module are:

-DATR -decision table containing data for processing, -CAV -set of conditional attributes' values represented by (a, v), -AMR -attributes mask register for disabling attributes which are not taken into consideration, -OMR -object mask register for choosing objects which are processed.

Outputs of the module return the number of objects' occurrences fulfilling each of (a, v) pair. Returned result represents both values (EOC and NOC) which are calculated in line 10 in algorithm HRG2-LEM2 described in Section 2.2.

... Comparator block (CB) shown on Fig. 2 is used to compare the values from CAV register and values of given objects' attributes.

= = = ... V a 0 a 1 a M-1 d ... a 0 (x) a 1 (x) a M-1 (x) d(x)
CMP Fig. 2. avCounter primary building block, where M is a number of condition attributes

Diagram of dtComparator module is shown on Fig. 3. Inputs of this module are:

-DATR -decision table containing data for processing, -CPDR -defines if conditional part of the rule (or pair (a, v)) is defined on input, -CPVR -contains conditional parts of the rule, -OMR -object mask register for choosing objects which are processed.

Output of the module (OER) returns the set of objects which fulfills each conditional part of the rule.

... avCounter and dtComparator are designed as a combinational circuits and thus do not need a clock signal for proper work. Amount of time needed to obtain correct results depends only on propagation time of logic blocks inside the FPGA. This property allows to significantly increase the speed of calculations because the time of propagation in contemporary FPGAs usually do not exceed 10ns. However, for the proper cooperation with external control blocks, as well as to perform other parts of the HRG2-LEM2 algorithm, both hardware modules must be controlled by the clock.

Main design principle of presented solution assumes, that each of described modules process fixed in size part of dataset. Results of calculations are stored using software implemented inside NIOSII softcore processor. Biggest impact on time of calculation is due to the parallel processing of many objects and all attributes in single clock cycle. Both modules are configured to process 64 objects described by maximum 16 attributes (condition and decision). Extending possibilities of these modules needs simple reconfiguration in VHDL source code and recompilation of hardware units. The same applies to control software.

Experimental Results

Software implementation on PC was prepared in C language and the source code was compiled using the GNU GCC 4.8.1 compiler. Results were obtained using a PC equipped with an 8 GB RAM and 4-core Intel Core i7 3632QM with maximum 3.2 GHz in Turbo mode clock speed running Windows 7 Professional operational system. Software for NIOS II softcore processor was implemented in C language using NIOS II Software Build Tools for Eclipse IDE.

Quartus II 13.1 was used design and implementation of the hardware using VHDL language. Synthesized hardware blocks were tested on TeraSIC DE-3 development board equipped with Stratix III EP3SL150F1152C2N FPGA chip. FPGA clock running at 50 MHz for the sequential parts of the project was derived from development board oscillator.

Timing results were obtained using LeCroy waveSurfer 104MXs-B (1 GHz bandwidth, 10 GS/s) oscilloscope for small datasets. Hardware time counter was introduced for bigger datasets.

It should be noticed, that PCs clock is clkP C clkF P GA = 64 times faster than development boards clock source.

Algorithm HRG2-LEM2 described in Section 2.2 was used for hardware implementation. Software implementation used HRG-LEM2 algorithm (described in paper that is reviewed), which differs from above in lack of dividing data into parts -all data is stored in PC memory. In current version of hardware implementation, authors used data which was preprocessed on PC in terms of discretization and calculation of lower approximations. Time needed for these operations was not taken into consideration in tests related to both types of implementation. Presented results show the times for generating global rule set using pure software implementation (t S ) and hardware supported rule generation (t H ). Results are shown in Table 1 for Diabetes and Poker Hand datasets. Last two columns in table describe the speed-up factor without (C) and with (C clk ) taking clock speed difference between PC and FPGA into consideration. k denotes thousands and M stands for millions.

In this case, one size of hardware execution unit was used, which consumed 15 679 of 113 600 Logical Elements (LEs) total available. This number includes also resources used by NIOS II softcore processor.

Fig. 4 presents a graph showing the relationship between the number of objects and execution time for hardware and software solution for both datasets. Both axes use logarithmic scale.

Presented results show big increase in the speed of data processing. Hardware module execution time compared to the software implementation is 5 to more than 7 500 times faster. If we take clock speed difference between PC and FPGA under consideration, these results are much better -speed-up factor is up to 485 000 for Poker Hand and Diabetes datasets.

Hardware modules speed-up factors for both datasets are similar. It is worth to notice, that it doesn't matter what is the width in bits of single object from dataset, unless it fits in assumed memory boundary. Hardware processing unit takes the same time to finish the calculation for every object size, because it always performs the same type of operation. Differences between hardware solutions comes from the nature of data and number of loops iterations. For software execution time comparison of Poker Hand and Diabetes datasets shows, that number of attributes and characteristic of the dataset have big impact on computation time. For hardware implementation characteristic of the dataset has biggest impact.

Let comparison of attributes' values between two objects or iterating over dynamic list of elements be an elementary operation. k denotes number of conditional attributes and n is the number of objects in decision table. Computational complexity of software implementation of the rules generation is Θ(kn 4 ) according to algorithm HRG2-LEM2 shown in Section 2.2. Using hardware implementation, complexity of rules generation is Θ(n 4 ). The k is missing, because our solution performs comparison between all attributes in Θ(1) -all attributes' values between two objects are compared in single clock cycle. Additionally, rule generation module performs comparisons between many objects at time.

Many real datasets are built of tens or hundreds of attributes, so it is impossible to create a single hardware structure capacious enough to process all at-Fig. 4. Relation between number of objects and calculation time for hardware and software implementation using HRG2-LEM2 algorithm for both datasets tributes at once. In such case decomposition must be done in terms of attributes, thus the computational complexity of software and hardware implementation will be almost the same, but in terms of time needed for data processing, hardware implementation will be still much faster than software implementation. The reason for this is that most comparison and counting operations are performed by the hardware block in parallel in terms of objects and attributes.

Conclusions

The hardware implementation is the main direction of using scalable rough sets methods in real time solutions. As it was presented, performing rule generation using hardware implementations gives us a big acceleration in comparison to software solution, especially in case of bigger datasets. It can be noticed, that speed-up factor is increasing with growing datasets.

Hardware supported rule generation calculation unit was not optimized for performance in this paper. Processing time can be substantially reduced by increasing FPGA clock frequency, modifying control unit and introducing triggering on both edges of clock signal.

Future research will be focused on optimization of presented solution: different sizes of hardware rule generation unit will be checked, as well as results related to performing the calculations in parallel by multiplying hardware modules. Using FPGA-based solutions it is relatively easy, because multiplication of execution modules needs only few changes in VHDL source code. Most timeconsuming part will be design and implementation of parallel execution control unit.

  additional data dependant on type of operation OUTPUT: operation result structure O 1: initialize O structure 2: for cnt ← 0 to m -1 do 3:

Fig. 1 .

 1 Fig. 1. avCounter module, where N is a number of objects in part of decision table

Fig. 3 .

 3 Fig. 3. dtComparator module

  Loop in lines 2 to 6 is responsible for choosing parts of input decision table DT . Decision table is divided into m parts, where each of them have the fixed size of n objects. Selected part denoted as RAM set , is loaded into internal FPGA's RAM memory (more details in Section 3.1) in line 3. Line 4 is responsible for storing partial results of given operation in general result structure O part . Obtained results are combined together with previous ones using general structure O.

5: O ← combine O and O part structures 6: end for Input of the hardware control algorithm is decision table DT and, required by type of performed operation, additional data. Output is general operation result structure O.

Table 1 .

 1 Comparison of execution time between hardware and software implementation for Diabetes and Poker Hand datasets using HRG2-LEM2 algorithm Objects Software -tS Hardware -tH C = t S t H C clk = 64 t S

	t H

Acknowledgements

The research is supported by the Polish National Science Centre under the grant 2012/07/B/ST6/01504.


Puja Mukherjee
email: pujamukherjee2014@gmail.com1

Rituparna Chaki
email: rituchaki@gmail.com2

A K Choudhury

Towards Generating a Unique Signature for Remote User by Keystrokes Dynamics

Keywords: keystrokes, remote user, free-text, key hold time & key dwell time, signature vector, authentication

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

Introduction

In this era enormous use of automated system together with the cloud based means gives a broader perspective to end user for storing as well as accessing data in an efficient manner. However it throws a big challenge to security and authentication domain. Prior to access the secured data, it is essential to verify the authenticity of the user. Determining the relevancy of the user with respect to the data is foremost agenda of authentication. Most of the advanced systems in different application working with distributed workstations (servers) deployed over different geographic region. The security of user and his/her data becomes more vulnerable in the wireless medium as there is no dedicated link or metod specified over there. We need a foolproof measure against unauthorized access to computer resources and data. The traditional authentication techniques were mostly depended on password based methods. The traditional techniques fail to provide enough protection to the user data. This has prompted the researchers to identify a new area of authentication known as Biometrics, which include finger prints, palm veins; face recognition, DNA, palm print, hand geometry, iris recognition, pattern of human behavior, like-key typing rhythm, ETC. Keystroke dynamics [START_REF] Umpires | Identity Verification through Keyboard Characteristics[END_REF][START_REF] Karnana | Biometric personal authentication using keystroke dynamics: A review[END_REF] or typing dynamics is a behavioral biometric, refers to the automated method of identifying or confirming the identity of an individual based on the manner and the rhythm of typing on a keyboard. The keystroke techniques are of two type -Keystroke Static authentication (KSA) and Keystroke dynamic authentication (KDA). In Static keystroke based technique, user authentication is done at a particular time instance. The continuous/ dynamic keystroke method is more effective than KSA and it requires the verification process to be continued during the entire session of user interaction. The raw measurements used for keystroke dynamics are dwell time and flight time.

The rest of the paper is organized as follows. In section 2, we review various approaches in keystroke biometrics briefly and analyze their error rates. In Section 3, our proposed approach is described. We give a full detail of the implementations of the approaches in Section 4 and provide experimental results in Section 5. Finally, Section 6 concludes the paper with suggestions for future work.

Literature Review

Most of the existing approaches focus on static verification, where a user types specific pre-enrolled string, e.g., a password during a login process, and then their keystroke features are analyzed for authentication purposes [START_REF] Umpires | Identity Verification through Keyboard Characteristics[END_REF]. Pin et al. [START_REF] Pin Sheen The | Keystroke dynamics in password authentication enhancement[END_REF] proposed a solution with EER of 1.401% for strengthening existing password based authentication system by using two layer fusion approach. Using classification techniques based on template matching and Bayesian likelihood models Fabian Monrose [START_REF] Monroe | Keystroke dynamics as a biometric for authentication[END_REF] achieved accuracy level of 83.22-92.14%. Yu et al. [START_REF] Hong | Keystroke Dynamics for User Authentication[END_REF] recommended nearest neighbor classifier with the new distance metric in order to identify a legitimate user with respect to a threshold value; this system achieved EER of 8.7%. Kenneth Revett et al. [START_REF] Revert | Data Mining a Keystroke Dynamics Based Biometrics Database Using Rough Sets[END_REF] achieved 95% of accuracy in user authentication by inventing software based module where combination of the typing speed and the first and last few characters of the login ID is enough to identify an authenticate user. Wang et al [START_REF] Babaeizadeh | Authentication Method through Keystrokes Measurement of Mobile users in Cloud Environment[END_REF] introduced a new user authentication approach by using keystroke dynamic method. This method includes training and authentication. It showed better performance in term of FAR and FRR. Babaeizadeh [START_REF] Kotani | Evaluation on a keystroke authentication system by keying force incorporated with temporal characteristics of keystroke dynamics[END_REF] suggested a KDA based system for verifying a user while requesting for services via CSP in Mobile cloud computing (MCC) environment. The proposed ECC cryptographic algorithm along with keystroke duration attribute was proved to defend 97.33% of efforts for an imposter attack. The data quality, uniqueness and consistency of typing pattern can be improved by using artificial rhythms and tempo cues [START_REF] Hwang | Keystroke dynamics-based authentication for mobile devices[END_REF].

3

The Proposed System

Biometric authentication systems usually have two phases for verification purpose-Enrolment Phase and Authentication Phase. In enrolment phase user data is gathered, processed and stored in a database. This becomes a template for future authentication phase. In authentication phase, the user data is acquired and processed. A matching process is there to check the authenticity of the user based on his pre-stored reference templates.

Our fundamental objective is to generate a unique signature for each individual way by analyzing his/her typing behavior. The proposed system will capture user data on a continuous basis and it use the concept of free-text (i.e. no dedicated text to be provided by the user in order to create individual's profile). In brief, the characteristics of the proposed model are:

1. Keystrokes based continuous authentication. 2. Dynamic (all text editor based data collection.

. Unique signature vector for each user

The proposed logic has three sub-phases for identifying a user's unique behavior, these are: data collection, Preprocessing of stored data and signature vector generation.

Our proposed system depicted in Figure2 focused on generating a unique typing behavior of each individual. Here is a brief description of each sub-phase:

 Data Acquisition: Here raw keystroke data of individuals are collected via various input devices. These may consist of normal computer keyboard, customized pressure sensitive keyboard, virtual keyboard etc. The output of this phase is a text file of an individual's typing behavior with key dwell time and key hold time.  Data Preparation: Pre-processing procedures such as feature selection, dimension reduction, and outlier detection [] are to be applied to the collected samples prior to feature extraction to ensure or to increase the quality of feature data. A substantial number of data samples are collected for each individual.  Signature Vector Generator: The output of phase II is used as input in this phase.

This file is used to generate a unique signature for each individual by applying some rules on the identified features and store them in database for future classification.

Data Acquisition

For the purpose of the work we have designed a routine to collect user data (key typing behavior). This routine aims to collect events generated by individuals (operators of computer systems) while using a keyboard. At present, the system works on the MS-Windows platform and does not require any additional libraries. The proposed logic works continuously in background and records a user's activity associated with a keyboard. The events are captured on the fly and saved in text files user character [user_id, vi] in a database. A sample of collected input data is presented below.

Input data collection is carried out for each user user_id separately. We can represent each key event as a vector with 5 tuples. On ith Session the key pressed event represented with vector vi is as follows, vi = {Session_ID, key_namei, hold_timei, dwell_timei, sys_timei} where, key_namei is the name of the ith key pressed event, naming convention is according to standard QWERTY keyboard interface on the session with Session_ID; hold_timei is the timestamp difference between key pressed and key released; dwell_timei is the timestamp difference between (i-1) th key release and ith key pressed; sys_timei is the system generated time in hour and minute when the event occur.

V is the composite vector {v1, v2 ... vn}; n depends on the overall key press occur on each session on a single day. In practice we restrict the number of sample data collected from the user hence our database is a collection of SV = {V1, V2 …, Vm} where m is number of sample data collected for each uid.

Additionally we store the total number of BACKSPACE key-press during each session the user interact with his/her machine. The sample collected for each session for the BACKSPACE key can be described with a vector TB = {TB1, TB2 … TBl};

where L= number of sessions on a single day, andTBj = {sessionj, backspace_countj};

where backspace_countj is the total number of times BACKSPACE key is pressed in sessionj. Then we compute the average number of BACKSPACE key-press on a single day and store them into the database with day_id . The average number of the BACKSPACE key-press (AB) on k th day is calculated as follows;

ABk = 1 𝐿 ∑ 𝑇𝐵𝑗 𝐿 𝑗=1
, where L is the total number of sessions on k th day.

All ABk will consititute a vector Ai = {uid, dayi, ABi} describe the average number of BACKSPACE key-press on ith day by the user uid.

Table 1. Key_event_recoder

Data Preparation

In this phase we select unique features for generating individual signature. For this, key_hold_time and key_dwell_time are selected for analysis. We aim to generate a specific range for each key event for these two features.

Our database stored the collected sample in the form of vector SV = {V1, V2 …, Vm} where m is total number of session for each uid on a particular day. The preprocessing done on Vi, where Vi = {v1, v2 ... vn}; n=number of key pressed on ith session.

We sort the key pressed event in a session and measure the maximum and minimum holding time of the key event (k). Store the range of key holding time and check for update on next sessions. Finally we get a list for each key_event (k) for Day (d) with specified range for user u_id and store them into database in the form of vector K_H {day_id, key_eventk, max_hold_timek, min_hold_timek}. max_hold_timek and min_hold_timek defines the range for key holding time for kth key_event on day day_id.

For key_dwell_time feature, we make a pairing between adjacent keys (k, k+1) and store the pair-wise dwell time. In each session, we select the same pairs and list all the dwell_time values. This way, a range for all possible key-pairs is obtained for a day,

Input:

The key pressed (K) from any text editor, like: Word Pad, Note pad, Facebook, etc.

Output: a) A text file key_detail{Session_ID, key pressed, system time of key press, k_hold, k_dwell} b) N=Total number of session on a particular day.

1. Initialize count = 0, k_hold = 0, k_dwell = 0, session_counter = 0; 2. Assume a threshold THD in milliseconds for dwell time.

Signature Vector Generator

In order to generate a template for individual uid we constructed a unique signature vector for each individual. Our feature space has 3 attributes (features); key_hold_time (kh), key_dwell_time (kd) and Backspace_key_count (bkc). For template creation we consider first two features from the feature space.

After the preprocessing of the input data stored in the form of K_H and K_D vector in our repository we proceed to generate a signature vector S_V for each user.

Input:

The text file containing the key press event with hold time for each user U for a particular day D.

Output: The sample file containing the range for key hold time feature for all possible key on day D.

1. For each s ∈ 𝑆ession_Id a. Sort all the keys pressed and group the similar keys into Kgroup. b. For each k ∈ Kgroup, Find the k_MAXhold_time(s) and k_MINhold_time(s) for k. 2. Check for the re-occurrence of the same key(k) in all sessions of day D.

Experimental Results

We collected the data-sets from 10 participants for 10 days. The sample data-set collected for each individual shown in Table 4.1 based on session on a day. The users were asked to run our proposed application in background during the entire period of interaction with their dedicated machine. The sample data collected from different machine having different configuration.

The users were not bound to press any dedicated text string and there is no additional interface for capturing data. All the active windows accessed by the users were taken into consideration for generating sample data-set.

Input: Hold time range for all key K(Hold) and pair-wise dwell time range for all possible key pair ∈ K(Pair) day D.

Output: A signature vector U_V = {u_id, (Avg_hold_time ,key), (Avg_dwell_time, key_pair)} for each user (u_id).

1. Initialize maximum_hold = 0, minimum_hold = 0, max_dwell = 0, min_dwell = 0;

Conclusion

We have observed that the prevalent biometrics based techniques for identification of a legitimate user often suffered from high FAR and FPR rates, which had a negative effect on the respective accuracy rate. The study reveals a fact that most of the developed applications consider a dedicated text (mainly passwords of specific format) to be typed by the user. However, the fixed text examples failed to capture significant variations in individual typing due to limited characters used. In this paper, we have used free-text concept to solve this issue. The software for collecting user data is designed to be machine independent, and samples are collected from a varying set of computers. Our proposed signature vectors deal with all possible key events so that the aggregated behavior of the end user is stored in to the repository. Our future work will concentrate on the classification verification part of the individual based on these store templates.

Fig

  Fig. 1.Classification of Biometric Authentication

Fig

  Fig. 2. Block Diagram of the proposed system.

3 .

 3 For ∀𝑘 ∈K a. K_pressed =Time duration (in millisecond) of key pressed. b. K_released = Time duration (in millisecond) of key released c. Compute k_hold = K_pressed-K_released. d. count=count+1; //count total number of key pressed e. Compute k_dwell = K_released[i] -K_pressed[i+1];i. If k_dwell> THD then Session_counter=Ses-sion_counter+1; f. Continue till closing of all editors. 4. Compute the total number of sessions on each day (N) of interaction with the dedicated machine for each individual. 5. Stop. and stored as vector K_D {day_id, key_pair j, max_dwell_timej, min_dwell_timej, } per user.

3 .

 3 If k_MAXhold_time(s) >= k_MAXhold_time(s+1) replace k_MAXhold_time(s) with k_MAXhold_time(s+1). If the k_MINhold_time(s) <= k_MINhold_time(s+1) replace the k_MINhold_time(s) with k_MINhold_time(s+1).4. Stop.Input:The text file containing the key press event (K) with dwell time (kD) for each user (u_id) for a particular day D.Output: The sample file containing the time range of key dwelling period for all possible pairs of keys on D day.1. Initialize an array K_D [],where K_D[i] = dwell time for a pair of keys. 2. For ∀ s ∈ 𝑆ession_Id a. For each k ∈ K i. Group k th & (k+1) th into a pair P (k, k+1) and store the respective dwell time (kD) into K_D. ii. Search for the re-occurrence of P (k, k+1). Store all the kD values in K_D. 3. Combine all the sessions on day D and check for the re-occurrence of the similar key pair. 4. Find the maximum and minimum kD value in the K_D array and define it as the range for all pairs of keys. 5. Stop. U_V = {u_id, Avg_hold_time, Avg_dwell_time} Avg_hold_time derived from max_hold_time, min_hold_timek ∈ K_H vector for∀𝑘 ∈ 𝐾𝑒𝑦, Key comprises of all key event possessed by the user for the entire sample collection period. Similarly, max_dwell_timej, min_dwell_timej ∈ K_D used for obtaining Avg_dwell_time for ∀ kp ∈ 𝐾𝑒𝑦_𝑃𝑎𝑖𝑟.

2 .

 2 For ∀d∈D, (D= No. of days of collection) a. For ∀ k ∈ K(Hold), i. Set maximum = k_MAXhold_time (d) and minimum= k_MINhold_time (d). ii. Update maximum and minimum if k_MAXhold_time (d+1) > maximum and k_MINhold_time (d) < minimum respectively. b. For ∀ (𝑙, 𝑙 + 1) ∈ K(Pair), i. Set max_dwell = l_MAXdwell_time (d) and min_dwell= l_MINdwell_time (d). ii. Update max_dwell and min_dwell if l_MAXdwell_time (d+1) > max_dwell and l_MINdwell_time (d+1) < min_dwell respectively. 3. Compute the Avg_hold_time from max_dwell and min_dwell value and store in U_V with corresponding key set pairs (KPair). 4. Stop.

Fig. 3 .

 3 Fig. 3. Average key holding time for all possible keys

Fig. 4 .

 4 Fig. 4. Average Dwell time for a key pair

Table 2 .

 2 Table 3. Key_Hold_Time

Table 4 .

 4 Key_dwell_Time

Table 5 .

 5 Signature_vector_generator

We differentiate the user behavior based on the two unique feature discussed so far, i.e., hold time and dwell time. [Figure 4.2, 4.3] illustrate the comparative analysis of two user USER1 and USER2 depending on key Hold time and key dwell time feature.

The collected samples for each user on a particular day then sorted in alphabetic order of key events. The processed samples depicted in Table 4.2 and Table 4.3 for hold time and dwell time features respectively.