This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
| . Therefore, we should construct location information independent of absolute path, which involves seeking the anchor including the extraction information. Generally, anchors, based on the information content, have nothing to do with HTML paths. For example, if we want to extract the information about books recently-published, as soon as finding the word "book_name", we have make an anchor independent of the path, codes are as follows: <xsl:template match="td[contains(.,'Last Tade')]"> 476 A new file will come into being if it is the first time to extract data. If there is another file, we can use the Merge function to merge the two files, and we can check the correctness of data extraction. 5. Defects of The Model and an Improved Model The model is designed for HTML document or XML document. But data on the web are not limited in HTML format or XML document; there are other forms, such as databases, logs, and files. How to extract data from these sources is a great challenge. Adopting XML grammar, RDF can easily realize automatic search without manual tagging interference, improving the rate of search coverage and veracity. Logically, the data extraction system base on XML and RDF has three layers: Information layer; Middle layer (RDF and XML) and Application layer. Considering its logical structure, the previous model can be modified and an improved model is Figure 2. 6. Conclusion A web data extraction model based on XML and its framework implementation are introduced. Based on the discussion about its limitations and defects, an improved semantic web data extraction model is provided by the authors. Data mining is composed of repetitive data extraction processes. We should consider the specialty of data mining, extract data from the web time and again, merge the products, and construct a practical data mining system. References 1. Jiawei Han, Micheline Kamber, DATA MINING Concepts and Techniques. 1st ed., Springfield: High Education Press and Morgan Kaufmann Press, pp.6-12 (2001). 2. MyllymakiJussi.Effective, Web Data Extraction with Standard XML Technologies. International Journal of Computer and Telecommunication Networking In: 10th intl. World Wide Web Conf. Hong Kong, (2001). 3. V. Baran, M. Colonna, M. Di Toro and A. B. Larionov, Intelligent Web Mining System Based on MLDB. Computer Engineering, vol.30, no.5, pp93-94, 101 (2003). 4. Chamberiin D D.Robie J, Florescu D. Quilt, An XML Query Language for Heterogeneous Data Sources. In: Proc. Of the Third Intl. Workshop on the Web and Database, Dallas, Texas, U.S.A., May 2000,pp53-62 (2001). 5. Zhang Chenghong, Gu Xiaohong, Bai Yanhong, The Progress of Web Data Extraction Technology. Computer Science, vol.31, no.2, pp 129-131, 151, (2004). EVALUATION OF E-SERVICE PROVIDERS USING A FUZZY MULTI-ATTRIBUTE GROUP DECISION- MAKING METHOD CENGIZ KAHRAMAN Istanbul Technical University, Department of Industrial Engineering, 34367 Macka Istanbul, Turkey GULgiN BUYUKOZKAN Galatasaray University, Department of Industrial Engineering, 34357 Ortakoy Istanbul Turkey Since most of the companies prefer outsourcing for e-activities, the selection of e-service provider becomes a crucial issue for those companies. E-service evaluation is a complex problem in which many qualitative attributes must be considered. These kinds of attributes make the evaluation process hard and vague. Cost-benefit analyses applied to various areas are usually based on the data under certainty or risk. In case of uncertain, vague, and/or linguistic data, the fuzzy set theory can be used to handle the analysis. This paper presents the evaluation and selection process for e-service provider alternatives. Many main and sub-attributes are considered in the evaluation. The e-service providers are evaluated and prioritized using a fuzzy multi-attribute group decision-making method. This method first defines group consistency and inconsistency indices based on preferences to alternatives given by decision makers and construct a linear programming decision model based on the distance of each alternative to a fuzzy positive ideal solution which is unknown. Then the fuzzy positive ideal solution and the weights of attributes are estimated using the new decision model based on the group consistency and inconsistency indices. Finally, the distance of each alternative to the fuzzy positive ideal solution is calculated to determine the ranking order of all alternatives. 1. Introduction As it is open seven days a weeks, 24 hours a day, in fact, according to industry observers, Web-based customer service that is also known as "E-Service", is one of the biggest business opportunities on the Net. Internet's influence in creating e-services has been revolutionary for providers and their customers. Unfortunately, there has been a wide gap between inspiring applications of the Internet that help increase service customization while maintaining or even improving delivery efficiency. The firms are not able to determine the scale of the e-service they will provide [1] and select the best Internet service provider, which meets their needs for e-service applications. For firms concerned with e477 service, one central issue is to determine the decision criteria for proper selection of an e-service provider. The lack of accurate decision criteria reveals benefit/cost imbalance such as high investment and inadequate return. This article aims at developing a model for evaluation of different e-service providers for a particular company. Multiple attribute decision-making (MADM) problems find a best compromise solution from all feasible alternatives assessed on multiple attributes, both quantitative and qualitative. Suppose the decision makers have to choose one of or rank n alternatives, A A ••• A , based on m attributes, C ,C •••Cm. An alternative set is denoted by A = \A A •••,Anj and an attribute set is denoted by c = jc , C , • • •, C }• Let Xy be the score of alternative A, (i = 1,2,•••,«) on attribute Cj(j = 1,2, • • •,m), and suppose CO is the relative weight of attribute Cj, where a > o (j = 1,2, —,m) and g a = j . A weight vector H j is denoted by a> = (a>, ,co2,--,co J • A MADM problem can then be expressed as the following decision matrix: c, A D = (x) = 4 X u c ca X n '" ** *n - X \m *~ (1) Crisp data are often inadequate or insufficient to model real-life decision problems. Human judgments are vague or fuzzy in nature and as such it may not be appropriate to represent them by accurate numerical values. A more realistic approach is to use linguistic variables to model human judgments. In this paper we evaluate e-services using Li and Yang's approach [2]. In their approach, linguistic variables are used to capture fuzziness in decision information and group decision-making processes by means of a fuzzy decision matrix. They propose a new vertex method to calculate the distance between triangular fuzzy scores. Group consistency and inconsistency indices are defined on the basis of preferences between alternatives given by decision makers. Each alternative is assessed on the basis of its distance to a fuzzy positive ideal solution (FPIS), which is unknown. The fuzzy positive ideal solution and the weights of attributes are then estimated using a new linear programming model based upon the group consistency and inconsistency indices defined. Finally, the distance of each alternative to FPIS is calculated to determine the ranking order of all alternatives. The lower value of the distance for an alternative indicates that the alternative is closer to FPIS. The paper is organized as follows. In next section, the basic definitions and notations of fuzzy numbers and linguistic variables are defined as well as the fuzzy distance formula and the normalization method. Section 3 defines fuzzy group decision-making model. Fuzzy multi-attribute e-service provider selection is explained in Section 4 and illustrated with a numerical example in Section 5. The paper is concluded in Section 6. 2. Related Terms 2.1. Triangular Fuzzy numbers Let ? = {l,m,u) be a triangular fuzzy number (TFN). Its membership function /*.(*) is given by I \ x- -l l<x<m m -/' \m-i u— u-x x u- -m m<x (2) 2.2. Linguistic variables A linguistic variable is a variable whose values are linguistic terms. The concept of linguistic variable is very useful in situations where decision problems are too complex or too ill defined to be described properly using conventional quantitative expressions. 2.3. Distance between two TFNs Let S^ and S2 be two TFNs. The vertex method is used to calculate the distance between them as follows: 4tth$t-hJ+fa-mJ + (»,-uj] (3) 2.4. Normalization method Suppose there exist n possible alternatives A ,A ,---,A from which P decision makers Pp{p = 1,2, •••,/•) have to choose on the basis of m attributes^ ,c , — ,c • Suppose the rating of alternative A. (/ = 1,2, •••,«) on attribute c .{j = 1,2, -,m) gi v e n by decision maker p ( p = 1,2,•••,/•) is x; =(a'J,b*,c*). A multi attribute group decision-making problem can be expressed in matrix format as follows: C, C, - C DF-{x,± P= \X-,P A x (4) Now let minja'|< « ; = («;, 6;, c; )}, i = 1,2, - , « ; / > = 1,2, • • •, P = max{i;\a', ex; ={a'„b;,c;)}, i = 1,2,-,n;p = 1,2,-,P (5) (6) = min^'|6; ex; =(a;,b;,c;)}, ; = 1,2,-,K;/? = 1 , 2 , - , P (7) = mvJp;\b;ex;=(a>,b>,c>% i = \,2,-,n;p = \,2,-,P (8) = 1,2,-, P (9) , = m i n ^ c ; e x,' = {a'„b'„c',% i = \,2,-,n;p C- = min{c;|c; ex;= {a'„b;,c',)}, i = l,2,-,/i;/> = 1,2,-,P (10) Then the following normalization formulas are used: Al forjeC (11) -Al forjeC 1 (12) and Now, the fuzzy decision matrices D" {p- \,2,---,P) are transformed into the normalized fuzzy decision matrix Rp as follows: c, 4 '=(r') c2 • •• r» c = 4 K' K: • - r;m P= • •• K: 4, r; ?: • •• rtl' \2,-,P (13) r± 3. Fuzzy Group Decision-Making Model Li linear programming based multiple VA and ana Yang iang [3] \p\ propose propose the me following ionowing un -"••''• • - *• ' ' 'on-makine model: attribute fuzzy group decision-making model: 481 Max £ £ 4 (14) s.t. J l-i 3tr r'1 (i,/).n'' 2X Ek-<) •J y=i ft>. =e,j j y=i = l,2,---,m £ (15) ^ ' W - and v.„(y = 1,2, •••,/«) can be obtained by solving Eq. (14). Then a)L,dm,and a'm (j = 1,2,• • •,m)are computed using Eq. (15) 4. Fuzzy Multi-attribute e-Service Provider Selection Fuzzy sets were introduced by Zadeh in 1965 [3] to represent/manipulate data and information possessing non-statistical uncertainties. Fuzzy logic provides an inference methodology that enables approximate human reasoning capabilities to be applied to knowledge-based systems. The theory of fuzzy logic provides a mathematical strength to capture the uncertainties associated with human cognitive processes, such as thinking and reasoning. Fuzzy multi-criteria decision-making has been widely used to deal with decision making problems involving multiple criteria evaluation/selection of alternatives [4, 5, 6]. These studies show the advantages in handling unquantifiable/qualitative criteria, and obtained quite reliable results. E-service provider selection is a complex problem in which many qualitative attributes must be considered. These kinds of attributes make the evaluation process hard and vague. Since most of the companies prefer outsourcing for e-activities, the selection of e-service provider becomes a crucial issue for those companies. In this paper, taking into consideration the literature on e-services [7, 8, 9], the following cost-benefit attributes are preferred in the evaluation of the best e-service provider. • Cost Attributes: 1. Setup costs (SC): These costs include installation costs of the required system such as operating system, database system, e-payment systems etc., 2. Hosting Costs (HC): Periodic cost of hiring the service and/or system, 3. Design & Programming Costs (DPC): Costs for designing the Web, programming procedures and preparing necessary scripts, 4. Backup & Maintenance Costs (BMC): The cost of backing up the important data on the system and maintenance and upgrading costs to provide better service, 5. Advertising & Promotion Costs (APM), 6. Personnel (Staff) Cost (PC): The cost of the staff that will primarily work for this system. • Benefit Attributes: 1. Service Guarantee, References & Familiarity (SGRF), 2. Stability, reliability, and uptime (SRU): The e-service should be available online 24 h a day. That is, the operation system of e-services should not present failures at anytime, 3. Ease of control and use (ECU): The system provided should have control panel easy to use, 4. Security & Privacy (SP): Because e-commerce is operated on an open network, encryption technologies must be developed to deter hacker attacks. The system has maximum security for credit card applications. It is very important that stored data should also be kept private, 5. Speed (S), 6. Physical Location (PL), 7. Customer Service Level (CSL): E-service provider should have good customer relations, respond to the matters quickly. 5. A Numerical Application Suppose a firm plans to select a e-service provider among four candidates A\, A2, A-i and A4. There are four experts Pp (p=l, 2, 3, 4) who agree to take into consideration the following six attributes in evaluating the e-service providers: Setup costs (SC), Hosting Costs (HC), Backup & Maintenance Costs (BMC), Security & Privacy (SP), Speed (S), and Customer Service Level (CSL). Assume that the experts provide their preferences between alternatives as a 1 ={(2,l),(l,3),(2,4),(3,4)}, « 2 ={(2)l),(l,3),(l,4),(3,4)}, n 3 = {(2,1),(2,3)>(3,l),(3,4)}) and n ={(l,3), (2,4), (3,4), (3,2)}. The corresponding relations between linguistic variables and positive triangular fuzzy numbers are given in Table 1. The data and ratings of all alternatives on every attribute are given by the four experts Ph P2, P3, and P4 as in Tables 2 respectively. Table 1. Linguistic variables and their representation with fuzzy numbers Triangular fuzzy numbers (0.8,0.9,1.0) (0.7, 0.8, 0.9) (0.6, 0.7, 0.8) (0.3, 0.5, 0.7) (0.2, 0.3, 0.4) (0.1,0.2,0.3) (0,0.1,0.2) Linguistic variables Excellent (E) Very good (VG) Good (G) Fair (F) Poor (P) Very poor (VP) Too poor (TP) Table 2. Evaluations of experts Attributes e-service providers A, A2 A3 A, HC SC E2 E3 E4 El E2 E3 E4 El E2 E3 E4 33 38 78 64 43 32 78 62 41 39 76 74 42 45 68 55 44 33 45 52 40 33 41 59 45 33 35 52 37 36 37 42 30 34 39 30 25 36 29 30 32 34 35 30 45 28 45 34 El E2 E3 E4 El E2 E3 E4 El E2 CSL E3 E4 30 21 21 24 32 24 18 22 32 21 20 24 28 34 22 25 F VG G VG G P F VG G G P E G VG P VG G P G P G G VG F P G VG F G P VG G S SP A, A2 A, A4 BMC El Now, using Eqs. (11), (12), and (13), we obtain the normalized decision matrices and then the transpose of these for each expert. Accepting e = 0.01 and A = 1.0 and substituting the normalized decision matrices and Q' [p = 1,2,3,4) into Eqs. (14) and (15), the linear programming problem is solved. The final ranking for evaluating and selecting among e-service providers is obtained as A, >- A, y A, > A,. 6. Conclusions In this paper the model developed by Li and Yang [2] has been used for evaluating and selecting among e-service providers. The selection among eservice providers is a complex problem in which many qualitative attributes must be considered. These kinds of attributes make the evaluation process hard and vague. The judgments from experts are always in vague rather than in crisp numbers. It is suitable and flexible to express the judgments of experts in fuzzy number instead of in crisp number. For further research, the results of this study may be compared with other fuzzy multi-attribute methods like fuzzy outranking methods, fuzzy utility theory and fuzzy AHP. Acknowledgments The authors acknowledge the financial support of the Galatasaray University Research Fund. References 1. K.B. Kenneth, H. Roger and V.R. Aleda, E-services: operating strategy—a case study and a method for analyzing operational benefits, Journal of Operations Management, 20, 175-188 (2002). 2. D-F. Li and J-B. Yang, Fuzzy linear programming technique for multi attribute group decision making in fuzzy environments, Information Sciences, 158, 263-275 (2004). 3. L. Zadeh, Fuzzy sets, Information Control, 8, 338-353, (1965). 4. C. Kahraman, D. Ruan and I. Dogan, Fuzzy group decision-making for facility location selection, International Journal of Production Economics, 87(2), 171-184(2004). 5. G. Buyukozkan, C. Kahraman and D. Ruan, A fuzzy multi-criteria decision approach for software development strategy selection, International Journal of General Systems, 33 (2-3), 259-280 (2004). 6. O. Kulak and C. Kahraman, Multi-attribute comparison of advanced manufacturing systems using fuzzy vs. crisp axiomatic design approach, International Journal ofProduction Economics, 95 (3), 415-424 (2005). 7. P.A. Dabholkar, D.I. Thorpe and J.O. Rentz, A measure of service quality for retail stores: scale development and validation, Journal of the Academy of Marketing Science, 24 (1), 3-16 (1996). 8. C. Liu and K.P. Arnett, Exploring the factors associated with Web site success in the context of electronic commerce, Information and Management, 38 (1), 23-33 (2000). 9. M. Wolfinbarger and M.C. Gilly, eTailQ: Dimensionalizing, Measuring and Predicting eTail Quality, Journal of Retailing, 79, 183-198 (2002). A CASE BASED RESEARCH ON THE DIRECTIVE FUNCTION OF WEBSITE INTELLIGENCE TO HUMAN FLOW ZILU, ZHUOPENG DENG, YANG WANG Faculty ofResource and Environment Science, Hebei Normal University, Shijiazhuang, 050016, P. R.China Email: luzi@mail. hebtu. edu. en Abstract: More and more websites have started to apply intelligent techniques to conduct effective and flexible operations and provide high-quality and personalized online services. One of the explicit manifestations of website intelligence is that web-based information flow directs and guides a related human flow. This paper chooses Sino-Australian as a case to explore how information flow directs a study-abroad human flow through providing intelligent e-services. An evaluation system with the case is conducted to prove the rationality of the directing function and process. Keywords: website intelligence; e-services; study-abroad; directive functions; human flow; China 1. Introduction Online services (e-services) have been growing rapidly, keeping pace with the web. More and more websites are applying intelligent techniques to provide high-quality online services. These intelligent e-services have conducted an impact on the user decision-making for their activities in the real life. Therefore, some important website information may promote the movement of human flow in a real space. Taking websites as a front-office, some education agents/companies apply intelligent approaches and system to provide Chinese students full-stop services to study abroad from information search to visa application online. The rest of the paper is organized as follows. Literature review and background in related areas are shown in Section 2. The directing process and mechanism of information flow to related human flow are deeply revealed in Section 3. Section 4 focuses on an empirical analysis of how information flow directing human flow by taking www.ozstudynet.com as a case. An evaluation result is displayed and discussed to the directing effect of information flow to human flow. Conclusions are drawn in Section 5. 485 2. Literature Review and Background E-service intelligence (ESI) is an integration of intelligent technologies and e-services [1]. E-service intelligence has been right now identified as a new direction and next stage of e-services. Intelligent online services can provide with much higher quality information, personalized recommendations and more integrated seamless link services. Brazier and Cookson [2] discuss how real-time intelligent technique is applied to the business world. In the context of providing solutions for real-time communications services, their paper puts forward the following design patterns: service node, intelligent network and service delivery platform. Valerie et al [3] points out that enabling the intelligent e-services means that consumers will be provided with universal and immediate access to available content and services, together with the ways of effectively exploiting them. Intelligent online techniques and approaches have been received more and more attention. In the meantime, some researchers have shown their interests in how invisible information flow directing visible material flow. Graham and Marvin [4] identify four effects of information technology to a city, which include cooperation effect, substitution effect, derivation effect and enhancement effect. Moss [5] analyses the information and spatial distribution according to the Internet infrastructure of American. Adams and Ghose [6] have a qualitative analysis to the real effect of Internet in promoting migrations from India to American from the view of new ICTs. Some Chinese researchers have particularly conducted research in this area with China's cases. For example, Yao et al [7] give an explanation and empirical analysis to the four effects mentioned by Graham and Marvin. Zhen et al [8] develops related theories between information flow and transportation. Lu and Zhang [9] analyses the positive effect of implementation of intelligent Traffic Guiding System (TGS). Lu and Sun [10] put forward their perspectives to the nature of flow space. However, review results show that the research on the directive functions of invisible information flow to visible material flow is limited in simple qualitative analysis and lack of deep analysis to its mechanism generation. With the full-scale exchanges and cooperations of politics, economy, trade, culture, science and technology between China and Australia in last decade, education exchange and cooperation have been developed and extended gradually. As shown in Table 1, the number of Chinese students in Australia is rapidly increasing. Besides the various attractions from Australian education systems and policy impetus from Chinese government, one of the important reasons is the extensive establishment of study-abroad websites. Table 1 The increased human flow of Sino-Australia student abroad during 1997-2002 China to Australia 1997 1700 1998 3100 1999 4100 2000 8909 2001 13452 2002 14215 Data source: Chinese Ministry of Education, Australian statistic bureau and federal immigrant agency The study-abroad websites of Sino-Australian is a kind of virtual platform constructed in a network space for Chinese students study abroad. This platform contributes to the construction of a "study-abroad bridge" between China and Australia. With the websites, a virtual community for study abroad is formed, in which various information exchanges can be freely conducted between website users and owners or among users. This approach is efficient in ultimate result, it thus stands for the future development trends. Therefore, websites can produce an effect to human flow through online information flow provided. 3. Directing Process of Web Intelligence to Human Flow 3.1 The directing process of web intelligence to human flow Stage 1 Stage 2 The destination confirmation of study abroad The selection and interview of agent for study abroad 4 1 Stage 3 Stage 4 The application and transaction for study abroad The completion and derivation of study abroad • * t Online information exchange community Figure 1 Intelligent services provided by study-abroad websites at different stages The process of information flow directing human flow under website intelligence includes four stages as shown in Figure 1. We will discuss it in detail below. 3.1.1 Stage 1: The destination confirmation of study abroad Previous research [11] indicates that to enhance the website usability is a key issue. The enhancement of website intelligence can help handling this issue. In this stage, the most significant application of intelligent technology to websites is intelligent information retrieval function. (l)Web Intelligence enhances the proportion of useful information. Some advanced intelligent techniques, such as cooperative filtering, multi-keywords search, are employed to enhance the understanding of "natural language" of users. (2)Website intelligence enhances the pertinence of users' search. In www.ozstudynet.com, it provides an intelligent engine for searching information of study abroad destination. Users can choose countries, cities, even universities and majors through using it. Users therefore can have a quick and full understanding to everything they may concern the process of study abroad. (3)Website intelligence also enhances the utility and pertinence of website links. Many previous links in www.ozstudynet.com are constructed in the absence of analysing their users. 3.1.2 Stage 2: The selection and interview of agentfor study abroad At this stage website intelligence is mainly embodied in their services provided. The improvement of service quality mainly depends on that of website intelligence, including: (1) An intelligent online feedback function. It is a function that can periodically send the related information pertaining to the study abroad destination automatically by e-mails according to different demands of users. (2) An intelligent online consultation function. They can consult the further detailed information about study abroad through intelligent means such as e-mails or on-line chat tools (QQ, MSN) etc. The www.ozstudynet.com online consultation function is available anytime to its users. (3) An intelligent online evaluation function. The student abroad can send their specific circumstance to the websites by e-forms. The intelligent evaluation system and experienced staff give the most accurate and authoritative results within a short time and offer suggestions suitable for different users. 3.1.3 Stage 3: The application and transaction of study abroad In this stage the website intelligence is reflected in three aspects. (1) An intelligent application function for study abroad. This means that users can log in websites to submit a set of their application forms. The service staff of websites will help accomplish necessary procedures for study abroad. Meanwhile, users can log in websites at any time to know their current application state. If some problems happen, they can be solved online without any delay. (2) An intelligent visa transaction function. A typical one is e-visa application. All visa application materials can be transmitted and transacted between Overseas Procedure Centre (OPC) of Australian government and their agents for study abroad in the form of e-files. This way makes the visa procedure become simpler and ensures the objectivity and impartiality to the largest degree. Table 2 lists the differences between traditional and intelligent visa transaction. (3) A follow-up service for directing human flow. Namely, websites make the use of their perfect service Table 2 Differences between traditional and intelligent visa transactions Transaction procedure of traditional visa Applicants or agents post the whole application materials to OPC; After OPC receives the applications materials and fees, the file number and other forms are sent back to your agents, (to wait more than one month); Then you should wait another three months. If pass, the pre-evaluation results will post to your agents; After agents receive the results, it will be posted to your school with tuition fee. When the school gives a confirmation and the enrolment notice will be back; Agents send the confirmation to OPC again; OPC will post the letter of visa approval to general consulate of Australian in Shanghai; Agents will post the passport of applicants to Shanghai to transact visa; General consulate in Shanghai will post the visa to your agents. Notes: the whole process needs about four months. Your related materials should be posted at least six times. Transaction procedure of e-visa Application materials of applicants will be scanned by agents authorized e-visa transaction. Then input certain passwords. It will be sent to OPC by e-files; E-Visa is a smart system. Every application will be generated a TRN (Transaction Reference Number) automatically. Applicants also can use their TRN to acknowledge their application state. Meanwhile, the body-checking form can be printed and have a check in appointed hospital; OPC will send the results and letter of visa approval to agents by e-files, too; Agents wilt post the passport of applicants to Shanghai to transact visa. When finished, general consulate in Shanghai will post the visa to your agents. Notes: most process is done online. Save more time using in pre-evaluation and material posting. 489 network and continue providing intelligent services to users who plan to study in Australian. The directing effect to human flow is ultimately realized. 3.1.4 Stage 4: The completion and derivation of study abroad The fourth stage is completion and derivative stage. Its significance is that through continuous online exchanges, new information flow and human flow may be derived, which further enlarges the circulative size of directive functions. (1) A custom-made service function. One of the important aspects of website intelligence here is to support personalization. The online services also include study accompany and bridging course transferring to provide personalized student-abroad services. (2) An online exchange community function. It is a virtual space in which website owners and online members or members exchange their thoughts, emotions and experiences. In this virtual space, members can have discussions for the interested topics according to their own characters, interest and taste etc. The website www.ozstudynet.com provides such a free exchange community, which includes the four different forums as shown in Table 3. It needs to indicate that intelligent interactive online exchanges in the virtual community are not limited in the fourth stage. As a means of service or personalization, it functions in the whole process. Table 3 The topic of exchange forum in www.ozstudynet.com Different forum Special area for study abroad Ally of study abroad to Australian Living information Website affairs administration hot topics __ __„—__ Study abroad to Australian; school transfer IELTS ally; major ally; school ally; homemate forum; meeting friends from same city; middle school ally; scholar ally Accommodation; living in Australian; back ticket; Second-hand market; migration to Australian; employment information; matchmaking; recreation Latest activities: Website affairs administration 3.2 Mechanisms The directing mechanism of intelligent information flow to human flow is shown in Figure 2. The human brain is affected by intelligent information directly and they will have an indirect impact on human's decision-making. In turn, e-services will be provided to direct and guide related human flow. On the condition that human cognition is fixed, the availability, precision and abundance of information and intelligent e-services will directly determine the human behaviour. We will prove the process and mechanism in next section by conducting an empirical analysis. 4. The Empirical Analysis — Taking www.ozstudynet.com as a Case 4.1 Research objective, method and result The website www.ozstudynet.com was established in May 2000, Melbourne, Australia. It develops its own intelligent e-study system and provides intelligent e-services that cover all steps of a study-broad application, based on a new operation model. Therefore, this study selects it as an example for exploring how website with e-service intelligence directing the study-Australia human flow. According to continuous investigation to www.ozstudynet.com for three weeks in December 2005, the evaluation system was created as shown in Table 4. The selection of those factors is based on literature review result and data collection availability. Synthesizing these factors orderly formed the evaluation system. The evaluation system is divided into four levels. Three factors are considered in level 1, eight factors in level 2, 17 factors in level 3 and 33 factors in level 4. The reason to divide factors into four levels is to facilitate scoring and have a deep and systematic view to website intelligence. The Likert Style Scale was employed to quantitative analysis. The score of each factor was divided into five levels (2, 4, 6, 8, and 10) according to the data we observed and collected. First, the scores of factor on level 4 were obtained. Second, the scores of factors on level 3 indexes were also obtained according to their corresponding factors in level 4. In turn, the level 1 and level 2 factors were calculated finally. Different humai man! flowtoAustrali fv^ Front NO Transaction process Information flow _ZTI | Transaction If application-notary-body check fee paying-visa application I Service Instntction-ticketaccommodation-study instruction -school transfer Figure 2 The directing mechanism of information flow to related human flow 4.2 Evaluation result analysis (1) The score of factor "website content" in level 1 is 7.9, the score of factor "website service" in level 1 is 8.4 and the score of factor "personalization" in level 1 is 6.2. According to the scoring criterion, the factor "website service" gets the best evaluation and the score of its four factors in level 2 are all beyond 8; the factor "website content" gets a better evaluation and the score of its one factor in level 2 is more than 7; the factor "personalization" gets a worse evaluation and only one factor in level 2 gets a score 7. (2) On the base of website intelligent e-services, the directive functions of information flow to a related human flow become more effective and orderly. (3) This research also offers some valuable references to website owners in website improvement. First, the results suggest that the multi-keywords, Table 4 The evaluation index system of website intelligence Level 1 Score Intelligent information retrieval function Level of website content 7.9 Level 2 Intelligent online consultation function Intelligent evaluation function Level 3 Score Information serviceability 6 Personalized Retrieval 8.7 Related links 9 Level 4 Score Rate of useful information Number of useful information Destination retrieval College retrieval Major retrieval Number of links 6 6 Relevance abroad E-mail Multi-means 8.4 8.7 8 8.5 Intelligent online feedback function 5.3 study 10 8 oo MSN 10 8 8 Response time Consultation satisfaction 8 8 Non-profit S Charge fee or not Extra fee 10 6 9 Number of Professional Related working experience 10 Professional Evaluation Dynamic query 6 Fast and convenient 6 Diverse ways 10 Especially interview Make whole process simplified 7 Time-saving Procedure simplified 6 8 Success rate 10 Regularly automatic send e-mail to users 5.3 Other custom-ma de services function Perfectibility 5 Completeness 7.3 6.2 Online exchang e function 7 with 8 10 8 8 Real-time response 8.5 Intellige nt visa applicati on function Level of personalization 6.2 7.9 Intellig ent applica tion fiinctio Level of website service 8.4 Score Gathering effect 7 Topic abundance 7 video 8 10 Increased success rate 10 Time interval E-mail content 2 6 Junk-mail or not 8 Accompany visa service Transfer service 4 6 Buying plane tickets Meeting at airport Accommodation Number of members Online number at peak time Number of topics Coverage degree 8 6 8 8 6 6 8 cooperative filtering and associated rule techniques are comprehensively used together in the future information retrieval. Second, the personalization of website is still weak. More emphasis should be laid on its real application effect. (4) The website intelligence is a relative new concept and the directive function is not same effective in all-human groups. The effective exertion of its intelligence must aim at specific sub-groups. (5) The significance of intelligent online exchange is not only forming the favourable cycle between web-based information flow and related human flow, but also enlarging the circulative size of its directive functions. Therefore, the intelligent online exchanges can play an important role in the whole process of directing human flow of studying in Australia. 5. Conclusions Intelligent online services in study abroad industry can break down the regionality, enhance realtimeness and create high efficiency. Web based information flow is effecting related human flow. Especially, with the development of intelligent e-visa, online services for study abroad become very effective and efficient. The study-abroad websites offer an approach to let applicants enter a virtual world, and this virtual world can direct and guide the movement of student flow from China to Australian. The research has also found that: (1) As a front-office of study abroad companies, study-abroad websites perfectly meet the users' demand through intelligent e-services; (2) The Sino-Australian study-abroad website direct and guides the human flow effectively; (3) The development of Sino-Australian study-abroad website has been transmitted from information provision and services to full-stop intelligent e-services. Acknowledgement This research is supported by National Science Foundation of China. (40571042) References 1. Lu, J. (2005), "Recent developments on E-service intelligence", www.fuzzy.ugent.be Noordrach Jie Lu .pdf 2005. 2. Brazier, R., Cookson, M. (2005), "Intelligence design patterns", BT technology Journal, Vol.23, No.l, pp 69-81. 3. Valerie, I., Daniele, S, Ferda, T, Francoise, S. (2005), "Developing ambient intelligence systems: a solution based on web services", Automated Software Engineering, No.12, ppl01-137. 4. Graham, S., Marvin, S. (1996), "Telecommunications and the city", Electronics, Urban places, Routledge, London, 234. 5. Moss, L. (1998), 'Townsend AM, Spatial analysis of the Internet in U.S. cities and states." http:// urban.nyu.edu/research/newcastle/Newcastle.html. 6. Adams, R, Ghose, R. (2003), "India.com: the construction of a space between", Progress in Human Geography, Vol.27, No.4, pp414-437. 7. Yao, S., Chen, S., Zhu, Z. (2001), "From the development of information network to the construction of digital-city in urban agglomeration", Human Geography (in Chinese), Vol.16, No.5, pp20-23. 8. Zhen, H., Liu, H., Zhang, J. (2001), "Related theory of information flow and transportation" (in Chinese), China Communications Press, 2001. 9. Lu, Z., Zhang, H. (2003), "The active impact of traffic guiding system to urban space distribution in Shijiazhuang", Economic Geography (in Chinese). Vol.23, No.2, pp242-246. 10. Lu, Z., Sun, Z. (2005), "A geographical perspective to the elementary nature of space of flows", Geography and Geo-Information Science (in Chinese). Vol.21, No.l, ppl09-112. 11. Nielsen, J. (2001). "Did poor usability kill e-Commerce?" Jacob Nielsen's Alertbox, http://www.useit.com/alertbox/20010819.html, 2001. GENETIC ALGORITHM FOR INTERVAL OPTIMIZATION AND ITS APPLICATION IN THE WEB-ADVERTISING INCOME CONTROL QIN LIAO 1 , XIWEN LI1 'School of Mathematical Sciences, South China University of Technology, Guangzhou, Guangdong 510640, P. R. China Abstract: The control problem of the web-advertising income is discussed in this paper. Firstly, the evaluation index system of the web advertisement and the evaluation model of the neural network are built. Secondly, in order to effectively control the factors influencing the income of the web advertisement, the genetic algorithm for interval optimization is proposed to find the corresponding intervals of those factors according to the anticipant income in a certain interval. Finally, an appropriate allocation of the advertising cost is made by using the clustering algorithm to classify the keywords. Numerical experiments are given and the results show that the novel method is effective. Keywords: Interval optimization, Genetic algorithm, Web advertisement, Advertising income 1. Overview Following by the prompt development of Internet, the evaluation problem about the web-advertising effect, income and factors attain more and more concern. By building the evaluation indexes and evaluation model of the web advertisement, the genetic algorithm for interval optimization is proposed to study the control of the intervals of the web-advertising influencing factors. Furthermore, by using the clustering algorithm to class the keywords, the keywords having maximum advertising income are found and an appropriate allocation of the web-advertising cost is made. 2. Evaluation indexes and evaluation model of the web advertisement CTR (Click Through Rate), CPC (Cost Per Click), and CVR (Conversion Rate) are chosen to be the evaluation indexes of the web-advertising effect. ROI (Return on investment) is chosen to be the evaluation index of the web-advertising income. CTR is the number of clicks divided by the number of impressions—the number of times the advertisements have been displayed. CPC is how much the 493 advertisers should be charged for a click on their ads. CVR is the number of conversions, which occurs when someone clicks on the ads and performs a behavior on the websites published on the ads, divided by the number of ad clicks. ROI can be calculated as revenue from sales, minus advertising costs, all divided by the cost. Suppose ROI is evaluated by the three evaluation indexes, the B-P model is built by choosing CTR, CVR and CPC as 3 input neurons and ROI as the output neuron. The B-P model is showed as follow: ROI = F(xl,x2,xi) = f(fjVj(£wijxJ-0i)-r) 1=1 (1) 7=1 where/=l / (1 + e"*) ,x\= CPC,x2 = CTR,x3 = CVR, V-, and w,, are connection weights, di and r are thresholds. By the network study of the samples, the total error, which is between the output of the model and the practical result of the sample, can satisfy the demand and the weights and thresholds of Eq. (1) are obtained. Furthermore, the evaluation model is built. By using the evaluation model, the ROI can be forecasted by inputting the values of the three indexes. But to an appointed ROI, it is too burdensome to try many combinations of the values of the indexes in order to satisfy the ROI. Thus, the genetic algorithm for interval optimization is proposed to find the corresponding intervals of those factors according to the anticipant income in a certain interval. 3. Genetic algorithm for interval optimization and the web-advertising income control model Traditional genetic algorithm is to find out the best individual^ K-AfV• ^ V , <XJ0) individualsX{ ' - {x\ ', x\ ', • • •, x[ '} , and then the population presented as S = {^]\ tf2\.. .X^} comprises N individuals. The output of the individual is: Y = {y^ yi2\...Y(N)}, ^ e [Ymax, Ymin] i = 1, 2...N. The midpoint is presented as Ymtd= (Ymwl+ Ymln) 12 and the fitness function is defined as By using the genetic algorithm first time, when the fitness achieves the maximum value, the corresponding individual X = {xx, x2...xn} is obtained. It means to find the best combination X = {x\, x2...x„} of the independent variable that makes the output close to the midpoint Ymid of the practical output. Basing on the process of finding the best individual X = {x\, x2...xa}, it generates random intervals (x, - e„ x, + e,), ei>0 of each independent variable (gene) xt, where e, is a positive number chosen randomly. Randomly generate M genes x) k = 1, 2...M, i = 1, 2...«, respectively from n intervals, so consequently M individualsX -{x[ ,---,xn )k = 1, 2...M are obtained, where x; e (x,- eh x,+ e,). The fitness function is defined as Eq. (2). The genetic algorithm is carried out again with the M individuals. After computing several times through the defined crossover operator and mutation, all the individuals that satisfy 1^*' - Yml^ < (Ymax - Ymi„) I 2 are chosen. Suppose P individuals are chosen and the i* genes of the P individuals are ranked from small to big as xfl, xf2, • • •, xfp, so the corresponding interval of the i"1 gene is [ xf ,xf ], j=l, 2...n. In order to determine the possibility that the corresponding output Y, which is calculated by the combination of the random values chosen from n intervals [xf ,xfp], is bounded in [Ymax, Ymi„], we can randomly test H times by choosing JC, from their corresponding intervals [jcf1, xf ] which constitute individuals X(k) = {JC,W, x[k), • • •, X(„k}} , k=\, 2...H. And then determine how many outputs Y= {Y"l\ y ^ , . . . ! ^ } are bounded in[Ymax, Ymin] thereby calculating the frequency that the outputs of the H individuals are bounded in the interval of Y. The frequency presents the approximate possibility describing the outputs, which is calculated by the combination of xt bounded in [xf ,xfp ] and other genes, bounded in an appointed interval. Overall, the interval [xf ,xfp ] of each independent variable xt is obtained, which makes the corresponding output Y e [Ymax, Ymi„], and the possibility of this relationship is also obtained. Suppose CTR and CVR are bounded in [0, 1], CPC\ is depended on the lowest cost demanded by the website, and CPC2 is determined by the maximum cost the advertisers willing to pay. Based on Eq. (1), there is ROI = F (CPC, CTR, CVR). In order to control the factors CTR, CVR and CPC influencing the ROI, an interval [ROI,, ROI2] is defined for ROI and ROImid= (ROI,+ROI2y2. The individual constituted by CTR, CVR and CPC is defined as tfk)=(CPClk\CTR(k\CVRik)) and the fitness function is defined as: G(Xik)) = ] -j—\ROI^-ROImid\ 1 + ,a>0 (3) a The best combination X=(CPC, CTR, CVR) of the independent variable is obtained, which makes the output of Eq. (1) achieves or close to the midpoint ROImid of the practical output. By using the genetic algorithm for interval optimization, the corresponding optimal intervals of CTR, CVR and CPC are respectively determined, which make ROI&[ROI,,ROI2]: CPCe[CPC,,CPC2], CVR&[CVR,,CVR2], CTR<E[CTR,,CTR2]. According to these three intervals the ROI can be controlled effectively. 4. Test of the web-advertising income control model Table 1 is the web-advertising sample data of a campaign in 7 weeks. By using the sample data in table 1, the B-P model for the ROI can be built and the parameters of the model are shown in table 2. When the ROI is demanded from 90% to 100%, by combining the evaluation model and the genetic algorithm for interval optimization, three control intervals of the advertising evaluation indexes are obtained, as table 3 shows. In table 3, in order to make the ROI bounded in [90%, 100%], CTR, CVR, CPC should be respectively bounded in [0.030, 0.049], [0.63, 0.99], [1.61, 2.41]. 100 samples bounded in these three intervals are randomly chosen and the ROI of these 100 samples are found out all bounded in [90%, 100%]. It means when the values of the three indexes are respectively bounded in corresponding intervals, the possibility that the outputs, which are calculated by the combinations of the values, are confined in the appointed interval is 100%. Table 1 Web-advertising sample data of a campaign in 7 weeks Week CTR CVR CPC ROI Week CTR CVR CPC ROI 1 0.029 0.718 2.39 0.79 5 0.029 0.546 2.1 0.59 2 0.027 0.396 2.08 0. 16 6 0.030 0.525 1.98 0.62 3 0.033 0.472 1.78 0.61 7 0.035 0.311 2. 17 0. 12 4 0.031 0.651 2.03 0.87 Table 2 The parameters of the B-P model Input neurons 3 Hidden neurons 3 Output neurons 1 Learning times 7566 Total error 0.0009 Smoothness factor 0.15 Adjusting factor 1 Table 3 The result of the genetic algorithm for interval optimization Control interval CTR [0.030, 0.049] CVR TO.63,0.991 CPC [1.61,2.41] ROI [0.9,11 5. Effective allocation of web-advertising cost In order to raise the advertising income, besides applying the method proposed above to control the values of the factors influencing the advertising ROI, the quality of the influencing factors have to be controlled. Hence, the relation between the keyword of the website and the evaluation indexes of the advertising income has to be studied in order to control the advertising ROI. To raise the CTR and CVR the advertiser should make the keywords of the campaign more pertinence. If a keyword is too general, the advertiser run the risk of getting clicks to his site that aren't really relevant, and have a lower conversion rate. Advertiser can increase the keyword's profitability by adjusting its CPC. For keywords that show a profit, increase the CPC to increase exposure and generate more traffic. For keywords that aren't profitable, decrease the CPC to lower the costs. So clustering is done to the keywords and find out which keywords are profitable and which are not. Two indexes are used: CTR and CVR to determine the quality of the keywords. Table 4. Sample data of the advertising keyword CTR CVR Keyword CTR CVR 29% 42.4% data mining technologies 5% 2.8% 45% 61.5% data mining technology 87% 21.3% data mining analysis 3% 0.0% intelligent data mining 3% 3.9% data mining solutions 6% 0.0% multimedia data mining 5% 0.0% Keyword business intelligence data mining data mining The 8 sample data in table 4 are clustered by using the specimen system clustering method and the distance of the cluster is defined as the minimum distance based on the Euclidean Distance. If the keywords are clustered into two groups, then the result is represented as Ul and U2: Ul={business intelligence data mining, data mining, data mining technology} U2={data mining analysis, data mining solutions, data mining technologies, intelligent data mining, multimedia data mining} Ul shows the keywords, which contribute a lot to the CTR and CVR, having higher quality, while U2 shows the keywords that have lower quality. So, the CPC of the first cluster can be increased, and the CPC of the second cluster should be decreased to allocate the costs of the web advertisement and it's helpful to increase the advertisers' web-advertising income. 6. Conclusion The genetic algorithm for interval optimization not only can be applied in controlling the influencing factors interval of the web-advertising income but also be validated on controlling multiple factors of general multiple objectives problems. Combining the evaluation indexes of web-advertising income and evaluation neural network model, not only the ROI is forecasted by changing the values of CPC, CTR, CVR but also the optimal control is processed reversibly according to the anticipate advertising income. In optimal control interval, the advertising income of any group, which constituted by "CPC, CTR, CVR", are bounded in the anticipate income interval. The clustering for the advertising keywords in the website can assistant the optimal allocation of advertising cost and effectively controls both the influencing factors and cost of the web advertisement. The result of the application indicates that the models are feasible and can be extended. References 1. Huang Z. W., Liao Q., "A celerity association Rules Method Based on Data Sort Search", Lecture Notes in Computer Science, No. 3613, August 2005, Springer, 1063-1066. 2. Liao Q., Gu H. M., Hao Z. F., "Fuzzy Comprehensive Evaluation of E-Commerce and Process Improvement", Lecture Notes in Computer Science, No. 3828, December, 2005, Springer, 366-374. 3. Liao Q., Li J., Hao Z. F., Li X. W., "Optimized Fuzzy Evaluation Model on Security Risk of Underground network", Asia Pacific Symposium on Safety, 2005,129-135. 4. Li Y. Q. & Liao Q., "Influence Factors and Mathematical Modeling of the Security of Underground Gas Conduit Network". Journal of South China of University of Technology (Natural Science Edition), 2004, 32: 89-93. 5. Syswerda G., Uniform Crossover in Genetic Algorithms. Proc of the 3rd Int. Conf. on Genetic Algorithms, Morgan Kaufmann, Los, 1989, 2-9. 6. Syswerda G., A Study of Reproduction in Generational and Steady-State Genetic Algorithms, Foundation of Genetic Algorithms, Morgan Kaufmann, CA, 332-349. DESIGN AND IMPLEMENTATION OF AN E-COMMERCE ONLINE GAME FOR EDUCATION AND TRAINING PEILI ZHANG 1 , MEIQI FANG 1 , YI ZENG 1 , JIA YU 2 I. Economy & Science Lab, Renrnin University of China, 1000872, P.R. China 2. School of Electrical Engineering and Telecommunications University of New South Wales UNSW, Sydney, NSW2052, Australia In this paper, we describe our design and implementation of a flexible, efficient way for ECommerce education by utilizing online game mode. We are building a multi-player ECommerce simulating online game - ECGAME, which everyone can login in via Internet all over the world. The platform provides participants with a virtual integrated business world to experience and helps them to learn business rules more effectively. It also motivates participants to learn E-Commerce and sparks competitiveness. 1. Introduction As the online game business growing, we realize that massive multiplayer online game can inspire people's interests greatly. We find that it is a new way to help students experience real business world. Therefore, during this year, we are building a multi-player E-Commerce online game -ECGAME. There are four basic roles in the game: consumers, manufacturers, retailers and transporters. The participants can run their own companies with various strategies and compete with the other companies in the virtual world. In ECGAME, each player will act different roles: consumer, manufacturer, retailer or transporter. The tasks of each role are different. We will calculate the scores based on their performance, for example, the money they earn. It is helpful for students, business planners and e-commerce product designers to train their skills via the game platform. It is also an inexpensive, safe way to evaluate the potential consequences of business strategies and market models. In addition, we cooperate with an art school to ornament our system with embellishment scenes in order to attract participants' interests (Fig. 1.). Fig. 1. Consumer's Home in ECGAME 499 500 2. Roles Assignment 2.1. Consumer Buy Product Earn Money Work IS Auction > Consumer ^ if I ^4 i Stu.dy Buy Stock Fig. 2. Consumer Description: Participants who act consumers have various attributes. They need to consume products to enhance their abilities, such as eating food to get strength. There are several ways to earn money. They can auction products with other consumers, work for companies, buy stock and study in the school to get better jobs. 2.2. Manufacturer Research & Development Buy Materials J Manufacture ] Products - with » Contact Transporters Bargain with Retailers k Accomplish the Contract Employment Fig. 3. Manufacturer Description: Participants who act manufacturer need to research and develop new product at first. They can manufacture products as long as they buy enough materials and employ enough workers. They also bargain with retailers to sell their products. After signing the contracts, they need contact with transporters to transfer their products to retailers. 2.3. Retailer Investigation Bargain with Manufacturers Buy the Goods Fig. 4. Retailer S Manage Storage ^ " y J S e l l Goods to Consumers 501 Description: Participants who act retailers should investigate consumers' interests at the beginning. Then, they bargain with manufacturers to buy the goods they want based on the investigation reports. Finally, they need to manage the warehouse and sell the products to consumers. 2.4. Transporter Develop new Lane Receive order Transporter Buy Vehicles Employment V 1 K* Transfer goods Fig. 5. Transporter Description: Participants who act transporter should develop new lanes firstly. Then they need to buy vehicles and employ workers. Each vehicle has different capacity. At the same time, they will receive orders from manufacturers to transfer goods to retailers. They decide the optimal way to transfer goods to save time. 2.5. Auto Roles It is far less enough to assign only four basic roles (consumers, manufacturers, retailers and transports) to simulate the business market. Hence, we add in several auto roles, such as Supplier, Bank, College, Supermarket, Job Center, Stock Center, Custom Center, Insurance Center, Auction Center, and Arbitration Center etc. Each auto role has its own rules to assist participants to accomplish their tasks. The primary events in ECGAME are listed in Figure 6. Baigain Sjviiij- mantv Partkinants Auto rules Fig. 6. The events among basic roles and auto roles 502 3. Game Scenarios 3.1. Overview ECGAME offers an integral market simulation platform for participants to experience the real business world. As we can see in Figure 7, there are three general game scenarios in our system: "^N £**"»! S(»* M&**(S|S^ i s-omng 1 tee& Accumuia/ufig the stock SHr-fcci Fig. 7. Overview of Game scenarios in ECGAME Stage 1: Initializing and Accumulating In ECGAME, participants will act consumers with little money and low abilities at the beginning. They will participate in various activities to earn money and enhance their abilities. Stage 2: Running a new company After their skills and personal savings reach the level scenario II requires, participants can enter the scenario II to run a new company. They can act as manufacturer, retailer or transporter. The tasks of each role are different for participants to experience distinct business modes. In this scenario, each participant can manage his company with own strategies and trade with other participants to earn money. Stage 3: Coming into the stock market When participants run their companies well enough, they can apply to act as super enterprisers. The super enterprise can come into the stock market to accumulate more money from the public. In ECGAME, we establish a simplified stock market for participants to experience. 503 3.2. Enterprise resource planning (ERP) We add ERP (Enterprise Resource Planning) components into our online game platform for business management catering the complex task requirements in ECGAME. Participants who act as enterprisers (manufacturers, retailers or transporters) can easily use ERP technology to manage their virtual company during playing the game. In our ERP software, there are five crucial modules: Finance Management, Human Resource Management, Manufacturing Management, Strategy Decision and Materials Management. Participants can learn how to plan enterprise resources efficiently using this platform. 3.3. Enterprise Alliance Although the game provides participants with opportunities to compete with the others, the experienced participants tend to cooperate with potential partners. We find that participants' behavioral patterns keep changing and the relationships among people are dynamic. When they benefit from integrating enterprises' resource, they will become partners. ECGAME provides a platform for those participants to form alliances. The members in the Enterprise Alliance can share information with each other, and come to an agreement with discounts. It is more challenging that participants need to change their strategies and find their partners in order to survive in the game. 3.4. How to win the game In the ECGAME, there are a lot of activities and targets for participants to achieve including various decision factors. In order to win, there are four primary factors that participants should take into account: 1. 2. 3. 4. Money: How to use the money to invest the company? Time: When to manufacture? When to transfer? Human Resource: How to schedule the workers for manufacturing? Information: What are consumer needs now? How about the opponents? Therefore, when participants make decisions on the business strategies, they must consider all the factors above. If some one ignores any factor, it will lead to failure. As a whole, only when the student plans everything carefully, could he or she get a high score. 504 4. Conclusion In conclusion, ECGAME is an original and efficient approach to learn and experience E-Commerce. It is an excellent review of many business strategies, management methods, and marketing principles. It provides an approachable way to gain hands-on management experiences. Currently, we have accomplished the prototype of ECGAME with most functions and here we described some main innovations of our system in this paper. As for an online-game, efficiency is a significant factor to attract participants. The participants are inpatient if they play the game in a low speed. Thus, to evaluate the efficiency of our system is a crucial task in the next step. Furthermore, we will add more components in the game for participants to experience other latest technologies: such as Supply Chain Management (SCM), Client Resource Management (CRM) and Supply Resource Management (SRM). References 1. Martin Griss, Reed Letsinger(2000). Games at Work - Agent-Mediated Ecommerce Simulation, Workshop on Autonomous Agents 2000, Barcelona, Spain, June 2000. 2. Hua Cheng, Meiqi Fang and lin Guan, Zuqiang Hong, "Design and implementation of an E-Commerce platform," Journal of Electronic Commerce in Organizations, 2 (2), pp. 44-54, 2004. 3. John Mitchell (2000). The Implications of E-commerce for Online Learning Systems, Proceedings of Moving Online Conference II, 2 - 4 September, Gold Coast, Australia, 110-123. 4. Martin Fowler. Patterns of Enterprise Application Architecture, AddisonWesley, Hardcover, Published November 2002, 533 pages, ISBN 0321127420 5. A. Chaves and P. Maes. "Kasbah: An Agent Marketplace for Buying and Selling Goods". Proceedings of the First International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology (PAAM'96). London, UK, April 1996. 6. T. Kindberg, et.al., "People, Places, Things: Web Presence for the Real World", HP Laboratories, Technical Report, HPL-2000-16, Feb 2000. 7. A. Durante, et. Al., "A Model for the E-Service Marketplace," HP Laboratories, Technical Report, HPL-2000-17,Feb 2000. 8. R.Guttman, A. Moukas, and P. Maes. "Agent-mediated Electronic commerce: A Survey." Knowledge Engineering Review, June 1998. SELECTION MODEL OF SEMANTIC WEB SERVICES X. WANG, Y. ZHAO, A N D W. A. HALANG Faculty of Electrical and Computer Engineering FernUniversitat, 58084 Hagen, Germany E-mail: {xia.wang, yi.zhao, Wolfgang.halang}@fernuni-hagen.de Widely supported by industry and research developments, Semantic Web Services appear to be the next generation of the service-oriented paradigm. Their discovery constitutes a great challenge. Although much work has been done on selecting semantic services, an exact selection model is still not defined, which could describe services and service selection in a powerful way. Moreover, little consideration was given to quantify the selection of services basing on both the capabilities and quality of service (QoS). Here, a QoS-based selection model of semantic services is proposed, and a service matching algorithm working under this model is presented. Also, two real-life examples are discussed to validate its implementation. 1. Introduction With the development of the Semantic Web11, the future web could provide not only static information understood by human beings, but also semantic services which implement a series of tasks and can automatically be accomplished by machines. More and more semantic web services will be developed and published in the fields of business, such as travel agencies, on-line trade, e-commerce, or manufacturing. Thus, the automatic discovery or selection of desired services is becoming critical. The achievements in the area of Semantic Web Services (SWS) so far can be summarised as follows. Currently, OWL-S12 is one important web ontology language for services, providing strong semantic support for web services. There is also some work on service matching algorithms. Sycara et al. 6 , for instance, proposed a dynamic matchmaking algorithm based on the agent capability description language LARKS. Similar work1,7 adopts these ideas to different degrees. Most current work, however, deals with the selection problem only with respect to similarity of non-functionality and functionality. The quality attributes of services10 are considered to a lesser extent. Moreover, the similarity of services is considered to match the whole description of ser505 vices published in OWL-S or WSDL documents , which may render the selection process to be erroneous 5 as the documents contain too much redundant information. Therefore, as a remedy, this paper proposes a concise and practical QoS-based service model inherently supporting selection. In the context of this model, two real-life examples of implementing the matching process are presented, which consider both the qualities and the capabilities of services. 2. M o d e l of S e m a n t i c W e b Services To describe a service, its non-functionality and functionality should be defined. Based on 2 , 1 2 , a service is stated as a tuple s = (NF, F, Q, C), where NF is a set defining its non-functionalities, F as a set describing the functionalities, Q defines the quality of the service, and Cis the overall cost of its invocation. The details of this service model presented in OWL Description Language (DL) 3 are as follows: - NF, an array of String, is denoted as NF = {serviceName, serviceCategory,textDescription}. According to the OWL-S specification, they are: (1) serviceName a String as the name of a service; (2) serviceCategory a String array as the categories of a service, which is classified according to the application fields, kinds of services, or some industry taxonomy, e.g., NACIS a or UN-SPSC b ; (3) textDescription a short text readable for humans briefly describing the service. - F is a set of service functionalities defined as F = {/j, ji, •••, fi}, i € N, with the ith function fa = (cypi,Hji,T1oi,Consi,Pi,Ei) described by: (1) (2) (3) (4) (5) (6) (7) a b opi: String naming the operation i; S / ; : array of String consisting of input parameters; HoV array of String consisting of output parameters; Consi: set of assertions expressed in DL syntax as constraints; Pi: set of assertions in DL syntax as pre-conditions; Ei\ set of assertions in DL syntax as effects; Relation 5: (op, x T,0. x Consi x Pj) — • ( £ 0 . x .E*) being the logic implication of service execution. North American Cartographic Information Society (NACIS), www.nacis.org United Nations Standard Products and Services Code (UNSPSC), www.unspsc.org The relation 5 follows the logic statement "If (opi x So, x ConSi x Pj) is true, then (Eoi x Ei) is true". That means, if the inputs, constraints and pre-conditions required by operation i are fulfilled, its relevant outputs and effects are yielded. - Q denotes the quality attributes of a service. In 8 , all possible quality requirements of services were identified. For the purpose of efficiency of service selection and from the point of view of clients, our model only categories QoS metrics into two parts, a necessary set (Qn) and an optional one (Qo)- We explicitly define Q in our model as Q = Qn = {QI,Q2, •••jQj}, j € N, which is formalised as a set of attribute assertions expressed in DL syntax, see Fig. 1. - C is the overall cost of invoking a service, generally an assertion formulated in DL syntax. Fig 1 takes as examples two real flight-booking systems0, which have been re-described using the above service model. T»F-{CheapFtightBearch, Flight, "Search far a cheap flight tickel.UK citizens"); OP={CheapFlightSearch); Sf={LondonUK,OrlandoVSAJu!yl405Myi 705,lAdu!ts.OCkildren.01n/antsJieturnTrip); Z^=(TicketDeparl, TicketReturn); Cons=(n(=M5.70cosLTicket)r(=morningti me.DepartTicket)ri(=eveningtime.Return7ick et) r\(=economyc!ass. Ticket)); P={(=\valid.PaymentCard)); .&={ {money.InsurenceCard-cosL Ticket)); Q=(rX<8time.quaIityResponseTime)r\£8tim e.qualityExecuteTime)ri^8rank.Reliabihty) nQ>7rank.quahtyExceptionHandling)n(i'9 rankqualityAccuracy) n&2rank.quahtySecu rip)); C={(= \55.70cosLCostService)); NF={Flights,Flight, "travel expertise, unrivalled knowledge, excellent value... "); OF=(FindFlight). Sj={LondonCit//Airport,OrlandolISAJulyl 405Julyl70JAduIts,OChildren,OInfants,Retu rnTrip); S0={TicketDepart, TicketReturn); Cons={rX=22S0.35cost.Ticket)ri(=morningti me.DepartTicket)n(=eveni/igtime.RelurnTick et) n (=2class.Ticket) ) , P={{=\valid.PaymentCard)); E=((money.InsurenceCard-cost.Ticket)), Q={rX^2time.qualityResponseTime)n(<8ti me.qua!ityExecuteTime)r\(^8rank.Re!iabilil y)r\(^7rankqualityExceptionHandling)n(8 rank.qualityAccuracy)n(^8rank.qualitySec "rip)); C={(< \M35cosLCostService)), (a) Advertisement; (b) Advertisement Figure 1. c Two real-world examples of the service model Advertisement}, at www.squareroutetravel.com/Flights/cheap-fiight-ticket.htm; Advertisement2, at www.travelbag.co.uk/fiights/index.html and 3. S e l e c t i o n A l g o r i t h m Usually, there is always a service requester {sR), and a number of service providers {sA). A selection algorithm matches the published services potentially meeting the requirements of the service requester. Denoted as sR = (NFR, FR, QR, CR) and sA = {NFA, FA,QA, CA), the service requirement and the service advertisement form the inputs to the matching engine. Then, pairs of sA and sR are interpreted and processed conforming to the matching algorithm. The output of the matching engine is a sorted set of candidate services returned to the requester as result. The matching process can flexibly be organised by various kinds of filters. Here, we sequentially combine three filters to illustrate this. I. NF - This filter is based on service name, service category, and service description to select the available services, and obtain a collection of relative candidates, named resultSetn. The process is to run a program implementing the pseudo-code in Fig. 2 twice, using serviceName and serviceCategory as input parameters, respectively. The distance of two different concepts is computed according to 6 . The outputs are the similarity of serviceName and serviceCategory, with a value between 0 and 1. matchConcept (ConceptR, ConceptA){ double simConcept; simConcept = distance (ConceptR, ConceptA) return eimConcept; } / / BimConcept G [0,1]; Figure 2. Matching and serviceCategory serviceName matchDescript ion (DescriptionR, DescriptionA){ Double simDes; for each term in DescriptionR and DescriptionA { DesR[tj] = number of term t j in DescriptionR; DesA[ti]= number of term t j in DescriptionA;} a i m D e s = (DesR * DesA)/(\DesR\ * |Des<4|); returnsimDea; } / /simDes e [0, 1]; Figure 3. Matching serviceDescription To measure the similarity of short text information, like serviceDescription, the cosine coefficient is a simple and effective approach. In Fig. 3, serviceDescription is the input, and the similarity of descriptions is the output, which ranges between 0 and 1. II. op, £/, Eo - This filter works on the functionalities of service, and obtains a result set resultSetf. First, the operation op is compared by using matchConcept, as defined in Fig. 2: matchConcept{OperationR, Operation A); //returnsimOP G [0,1] Second, if the service requester's input information subsumes the parameters required by the service advertisement, request and advertisement are considered to be similar. Then, the value of simPara is assigned to 1. Otherwise, it is thought that the requester's input parameters are not sufficient to fulfill the implementation of advertised service, and simPara is set to 0. The function matchOutput, however, does the opposite. If the service requester's output cannot be subsumed in the service advertisement, then the results of the advertisement's execution meet the service requester's requirement only partly. In this case the match fails, noted as 0. III. Cons, P, E, Q and C - This filter processes resultSet/ to refine the selection and similarly to obtain resultSet. In this step, the matchmaking is processed on a set of expressions in DL format. Here, one could not simply consider the subsumption, because the similarity degree is more important than their subsumption relationship. Considering cost. Ticket in Fig. 1, the requester R is assumed to state that the ticket must cost less than $800; Advertisement\ asks for $645.70 and A2 for $2280.35. In this case, an approach should be used to scale the close-degree rather than the values' difference. This is addressed by the algorithm as: closeExpCost(R, Ax) = 8^(800 - 645.70) = 0.192875; closeExpCost{R, A2) = ^(800 - 2280.35) = -1.8504375; Obviously, the bigger the numerical value is, the better is the result. Advertisementi is a better choice than AdvertisementiIf extended to a set of expressions (in this context, Cons, P, E, Q, and C), the multi-attribute utility theory 2 , 5 should be applied. T h a t is, after computing the close-degree based on fuzzy computing 4 , to the expressions are assigned utility scores 2 between 1 and 5 based on the attribute definitions. In the above example, the values of closeness are utilityScore(R, A\) = 5 and utilityScore{R, A2) = 1. A set of expressions is E = {E\, E2, •••,En} is assumed, whose related utility score are u = {ui,U2, . . . , u „ } , n € N. If a weight (v) between 0 and 1 is assigned to each attribute, then . . svmExpression = Vi • Ml + V2 • U2 + ... + Vn • Un . vi+v2 + ... + vn Cons, P, E, Q, and C are all sets of expressions, whose corresponding similarities could be calculated as simCons, simP, simE, simQoS and simC. Similarly, to quantify the similarity between service requirements and advertisements, to each attribute involved in the matchmaking a weight between 0 and 1 is assigned. Then, 11 sumSimilarity = (S, w i)~l ' (wi • simName + w2 • simCategory -f W3 x !=1 x simDes x simCons 4- W4 • simOP + W5 • simlnput + WQ • simOutput + ws • simP + uig • simE + W\Q • simQoS + 107 x + u>n • simC) 510 4. C o n c l u s i o n Semantic Web Services appear to be the next generation of the serviceoriented paradigm. The discovery of semantic services constitutes a great challenge. All problems encountered currently lead to the conclusion that an effective semantic service model for selection is missing, which provides powerful expressiveness with respect to capabilities and qualities of service, and that a quantified matching algorithm is needed, too. For these problems, this paper proposed a selection model, which effectively implements QoS-based matchmaking of semantic web services. The matching process is discussed with two real examples. Future work is to optimise the method of accessing each quality attribute of service, and to consider how to combine various QoS attributes. References 1. C. Zhou, L. Chia and B. Lee, DAML-QoS Ontology for Web Services, Proc. ICWS04, pp. 472-479 (2004). 2. D. Menasce, Composing Web Services: A QoS View, IEEE Internet Computing, 8(6) (2004). 3. D. Nardi, F. Baader, D. Calvanese, D.L. McGuinness and P.F. PatelSchneider, The Description Logic Handbook, Cambridge (2003). 4. E. Herrera-Viedma et al., Evaluating the Informative Quality of Web Sites by Fuzzy Computing with Words. Proc. Atlantic Web Intelligence Conference, LNAI 2663 (2003). 5. E.M. Maximilien and M.P. Singh, A Framework and Ontology for Dynamic Web Services Selection, IEEE Internet Computing, 8(5), 84-93 (2004). 6. K. Sycara, S. Widoff, M. Klusch and J. Lu, LARKS: Dynamic Matchmaking Among Heterogeneous Software Agents in Cyberspace, Autonomous Agents and Multi-Agent Systems, 5(2), 172-203 (2002). 7. M. Paolucci, T. Kawmura, T. Payne and K. Sycara, Semantic Matching of Web Services Capabilities, Proc. ISWC02, pp. 333-347 (2002). 8. QoS for Web Services: Requirements and Possible Approaches. W3C Working Group Note (2003). 9. R. Akkiraju et al., Web Service Semantics - WSDL-S, A joint UGA-IBM Technical Note, Version 1.0 (2005). 10. S. Ran, A Model for Web Services Discovery With QoS, ACM SIGecom (2003). 11. T. Berners-Lee, J. Hendler and O. Lassila, The Semantic Web. Scientific American, 284(5), 34-43 (2001). 12. The OWL Services Coalition, OWL-S Semantic Markup for Web Services, W3C Member Submission (2004). 13. Web Services Description Language (WSDL) Version 2.0, Part 0: Primer. W3C Working Draft (2004). A T R U S T ASSERTION M A K E R TOOL P A O L O CERAVOLO, E R N E S T O DAMIANI, M A R C O VIVIANI E-mail: University of Milan via Bramante 65, 26013 Crema (CR), Italy {ceravolo, damiani, viviani}@dti.unimi.it ALESSIO C U R C I O , MICOL PINELLI E-mail: University of Milan via Bramante 65, 26013 Crema (CR), Haly {acurcio, mpinelli}@crema.unimi.it In this paper we outline the architecture of a distributed Trust Layer that can be superimposed to metadata generators, like our Trust Assertion Maker. TAM is a tool allowing to produce metadata from multiple sources in an authoritybased environment, where user's role is certified and associated to a trust value. These metadata can complement metadata automatically generated by document classifiers. Our ongoing experimentation is aimed at validating the role of a Trust Layer as a technique for automatically screening high quality metadata in a set of assertions coming from sources with different level of trustworthiness. 1. I n t r o d u c t i o n Nowadays, communication technologies have created a space of flows that substitutes the space of places: geographical proximity is giving way to relational proximity. These phenomena greatly impact on the architecture of a community of practice, giving to it a distributed extension of the internal processes and dynamics. CoPs exist within businesses and across business units and company boundaries; even though they are informally constituted, these self-organizing systems share the capability of creating and using organizational knowledge through informal learning and mutual engagement 5 , putting users at the center of the space of interactions. Moreover, in current business contexts that require multidisciplinary approaches and competencies, this stress the relevance of user's role, reputation, and trust. For these reasons, generic knowledge management techniques in CoPs have 511 512 to be evolved towards a source oriented evaluation of the acquired knowledge. The knowledge extracted during the analysis of the information flow produced by the community must be filtered by the relevance of the node producing it. Also the composition of nodes can evolve and the knowledge is continuously under the evolution pressure. Typically, knowledge management techniques used metadata in order to specifying content, quality, type, creation, and spatial information of a data item. A number of specialized formats for the creation of metadata exist. A typical example is the Resource Description Framework (RDF). But metadata can be stored in any format such as free text, Extensible Markup Language (XML), or database entries. All of these format must relay on a vocabulary that can have different degree of formality. If this vocabulary is compliant to a set of logical axioms it is called an ontology. There are a number of well-known advantages in using information extracted from data instead of data themselves. On one hand, because of their small size compared to the data they describe, metadata are more easily shareable than data. Thanks to metadata sharing, information about data becomes readily available to anyone seeking it. Thus, metadata make data discovery easier and reduces data duplication. On the other hand, metadata can be created by a number of sources (the data owner, other users, automatic tools) and may or may not be digitally signed by their author. The present paper briefly outlines our current research work (for a more detailed description, see 2 ) on how to validate such assertions by means of a Trust Layer, including a Trust Manager able to collect votes from the different nodes and to compute variations to trust values on metadata. Then we focus our discussion on the description of Trust Assertion Maker (TAM), a tool especially designed for allowing the manual production of trust assertions, in distributed environments. Trust assertions are metadata assertions associated to a trust value. The trust level of an assertion is based on user roles. The adoption of a manual tool allows a detailed level of description and represents an important complement to assertion produced by automatic classifier that simply associate resources to domain concepts. This paper is organized as follows: in Section 2 we outline the architecture of our Trust Layer, while Section 3.1 we focus our attention on TAM; finally in section 3.2 we define in detail the type of asserttns supported by TAM. 2. T h e Trust Layer architecture Before describing our proposed Trust Layer, let us make some short remarks on related work. Current approaches distinguish between two main types of trust management systems *, namely Centralized Reputation Systems and Distributed Reputation Systems. In centralized reputation systems, trust information is collected from members in the community in the form of ratings on resources. The central authority collects all the ratings and derives a score for each resource. In a distributed reputation system there is no central location for submitting ratings and obtaining resources reputation scores; instead, there are distributed stores where ratings can be submitted. In our approach trust is attached to metadata in the form of assertions rather than to generic resources. While trust values are expressed by clients, our Trust Layer includes a centralized Metadata Publication Center that acts as an index, collecting and displaying metadata assertions, possibly in different formats and coming from different sources. It is possible to assign different trust values to assertions depending on their origin: assertions manually provided by a domain expert are more reliable than automatically generated ones. Metadata in the Publication Center are indexed and clientss interact with them by navigating them and providing implicitly (with their behavior) or explicitly (by means of an explicit vote) an evaluation about metadata trustworthiness. This trust-related information is provided by the Publication Center to the Trust Manager in the form of new assertions. Trust assertions, which we call Trust Metadata, are built using the well-known technique of reification. This choice allows our system to interact with heterogeneous sources of metadata: our Trust Metadata are not dependent on the format of the original assertions. Also, all software modules in our architecture can evolve separately; taken together, they compose a complete Trust Layer, whose components communicate by means of web services interfaces. This makes it possible to test the whole system despite the fact that single models can evolve with different speeds. Summarizing our architecture, the Trust Manager is composed of two functional modules: Trust Evaluator: examines metadata and evaluates their reliability; Trust Aggregator: aggregates all the inputs coming from the trust evaluators by means of a suitable aggregation function. This system allows to integrate large amount of assertions produced from different sources. Trust aggregation algorithms provides a self-running mechanism allowing high quality assertion to emerge in the whole set of produced assertions. Fig. 1 describes the architecture of our Trust Layer. More details 514 on Trust Manger can be found in 3 . Figure 1. The Trust Layer Architecture. 3. Trust Assertion Maker 3.1. Architecture and requirements The functional requirements of TAM are to manage role-based creation of metadata assertions. This means that each user must be associated to a role. Roles are obtained by an authority tasked to certify user's expertise. For these reasons TAM is organized according to a client-server architecture. The client provides the structure for editing assertions. The server manages user's access, and maintains the metadata base synchronizing updating. User's expertise is represented associating to a role the portions of ontology describing a domain where his expertise can be considered reliable. Portions of ontologies can be computed simply listing a concept list containing concepts where the expertise of a role is maximal. These concepts are associated to a trust value. And trust values of other concepts of the ontology are deviated decreasing progressively the trust value according to the distance from the closer concept among those in the concept list. In a knowledge management system the role of a manual metadata editor such 515 as TAM, is to complement automatic classifiers. Tools implementing automatic or semi-automatic algorithms for indexing resources are essential in order to support a satisfactory number of resources. But these tools are able to provide only simple assertions connecting a resource to a concept. For this reason they can be used only for producing a first base of metadata. In order to enrich the metadata base users must be provided with easy instruments for the production of semantically complex assertions. As shown in Fig. 2 TAM guides the user in a step-by-step dialogs allowing to produce an assertion without any expertise on the format used in the system for storing and sharing metadata assertions. According to Stojanovic, Staab, and Studer 4 it is possible to distinguish two type of ontologies: a domain ontology, or content ontology, that provides the vocabulary valid for a particular domain, or a structure ontology, or context ontology, that provides general concepts, cross functional to specific domains, describing the type/structure of the resource. Our tool supports both these type of ontologies. We call Direct the assertions made on structural concepts, because we directly assert on the resources. We call Indirect the assertions made on the content of a resource. Also the tool allows to produce simple or complex assertions. In summary we have four type of metadata assertions, as shown in Table 1. In section 3.2 we describe in more detail these assertions. Direct Indirect 3.2. Editing Simple DS IS Complex DC IC assertions Metadata produced by TAM are editable by means of an user friendly interface. The interface proposed in TAM leads the user to the creation of an assertion, using step-by-step dialogs. In the first step the user has to select the role he want to hold, the resource he want to relate to the metadata assertion, and the ontology he want to use for creating metadata. Fig. 2 shows a screenshot from the TAM interface. In the second step the user has to choose the type of assertion he want to create. As previously mentioned four type of assertions are supported by TAM. Figure 2. The TAM interface. IS: Indirect Simple assertion. An Indirect Simple assertion consists in associating single concepts of the domain ontology to a resource. To obtain this, it is necessary to select the resource and, then, to choose from the contextual menu, the option related to indirect simple assertion. Then, it is necessary to individuate the concept of the ontology to be related to the resource. For example, a indirect simple assertion can be represented by the following: "Document-X speaks about Enterprise", where E n t e r p r i s e is a concept belonging to the domain ontology. DC: Indirect Complex assertion. An Indirect Complex assertion consists in associating not only single concepts of the ontology to a document, but whole logic assertions, structured according to the model subject-predicate-object. To obtain this, it is necessary to select the resource and, then, to choose from the contextual menu, the option related to direct complex assertion. Then, it is necessary to individuate the subject of the assertion, selecting a concept from the ontology. After that, it is necessary to specify the predicate, choosing it among all the possible predicates, suitable with the subject (considering also the inheritance among the concepts). Finally, it is necessary to select the object of the assertion. The following statement illustrates an example: "Document-X speaks about enterprise that invests in technology". Where, E n t e r p r i s e 517 and t e c h n o l o g y are concepts belonging to the domain ontology. DS: Direct Simple assertion. Direct Simple assertion is different from the previous ones, because it is built relying on a structure ontology. This assertion specifies the type of the current resource the user is indexing. This is an example of a simple no-semantic assertion: "Document-X is an image". IC: Direct Complex assertion. Direct Complex assertion is well explained by the following example: "Document_X is an image that has a white background". The structure is similar to the indirect complex assertion; the only difference is in the typology of utilized ontology, that is a structural ontology, instead of a domain ontology. 4. Conclusions In this paper, we have presented an approach for developing a Trust Layer service, aimed at improving the quality of automatically generated metadata. Such a system must be supported by a tool for manual creation of complex metadata assertions. A specific solution to this requirement is illustrated in the paper, introducing TAM: a tool allowing to produce different type of metadata assertions in a distributed environment. Acknowledgments This work was partly funded by the Italian Ministry of Research Fund for Basic Research (FIRB) under projects RBAU01CLNB_001 "Knowledge Management for the Web Infrastructure" (KIWI), and RBNE01JRK8_003 "Metodologie Agili per la Produzione del Software" (MAPS). References 1. J. Audun, I. Roslan, C.A. Boyd, Survey of Trust and Reputation Systems for Online Service Provision. Decision Support Systems (to appear) (2005) 2. P. Ceravolo, E. Damiani, M. Viviani, Adding a Trust Layer to Semantic Web Metadata To appear in Soft Computing for Information Retrieval on the Web, F. Crestani, E. Herrera-Viedma, G. Pasi, eds., Elsevier. 3. P. Ceravolo, E. Damiani, M. Viviani, Adding a Peer-to-Peer Trust Layer to Metadata Generators, Lecture Notes in Computer Science, vol 3762, pages 809-815, (2005). 518 4. L. Stojanovic, S. Staab, R. Studer, E-Learning based on the Semantic Web. Proceedings of the World Conference on the WWW and Internet, Orlando, Florida, USA, (2001). 5. E. Wenger, Communities of Practice: The Key to Knowledge Strategy, Knowledge Directions, 48-64, (1999). W E B ACCESS LOG MINING WITH SOFT SEQUENTIAL PATTERNS C. F I O T , A. L A U R E N T A N D M. T E I S S E I R E LIRMM - CNRS - UMII, Montpellier, France E-mail: {fiot, laurent, teisseire} @lirmm.fr Mining the time-stamped numerical data contained in web access logs is interesting for numerous applications (e.g. customer targeting, automatic updating of commercial websites or web server dimensioning). In this context, the algorithms for sequential patterns mining do not allow processing numerical information frequently. In previous works we defined fuzzy sequential patterns to cope with the numerical representation problem. In this paper, we apply these algorithms to web mining and assess them through experiments showing the relevancy of this work in the context of web access log mining. 1. Introduction The quantity of data from the World Wide Web is growing dramatically: requested URLs, number of requests or session duration, etc. are gathered automatically by web servers and stored in access log files. Analysing these data can provide useful information for performance enhancement or customer targeting. In this context, many works have been proposed to mine usage patterns and user profiles [1, 2, 3]. Particularly, [4] provides knowledge from database of visited page sequences. However this method, based on sequential pattern mining, cannot be used to mine numerical data contained in these log files, such as number of requests for the same page, transfer rates, number of downloaded kilobytes or duration of sessions. Few works have been carried out to process such numerical data and most of them are restricted to association rules [5, 6]. Sequential patterns are more adapted to time-stamped data. In order to cope with this problem, we propose here to apply an efficient fuzzy approach for sequential pattern mining to mine time-stamped numerical data from web access logs. This approach, defined in our previous works [7], is based on the definition of fuzzy intervals. Obtained patterns are of the type "60% of users visiting a lot the Disneyland website and a few Eiffel Tower pages visit later a lot 519 520 of traveling websites". These patterns are characterized by their support, which is the percentage of users who have followed this rule. Three approaches are proposed to mine such rules: SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY, differing by the support computation. The end-user is allowed to choose between the speed of result extraction and the accuracy of the obtained frequent patterns. Implementation of these solutions is based on a method, which extends the PSP algorithm proposed in [4]. Experiments were carried out on synthetic datasets and on real-world data. They highlight the feasibility and robustness of a fuzzy approach. This paper gives an overview of our algorithms focusing on the processing of web log data. Section 2 introduces sequential patterns and fuzzy sequential patterns. Section 3 presents the experiments on web access logs. Section 4 concludes on the perspectives associated to this work. 2. From Crisp to Fuzzy Sequential Patterns In this section, we briefly describe the basic concepts of sequential patterns and fuzzy sequential patterns. Let T be a set of object records where each record consists of three information elements: an object-id, a timestamp and a set of items. An itemset, (iii-z . • -ik), is a non-empty, unordered set of items taken from / = {ii,i2, •••,*m}- A sequence s is a non-empty ordered list of itemsets, denoted by < siS2-..sp >. The support of a sequence s is the percentage of objects having s in their records. To decide whether a sequence is frequent or not, a minimum support value (minSupp) is specified by the user. A sequence s is said to be frequent if support(s) > minSupp. The problem of sequential pattern mining is to find all maximal frequent sequences [8]. In this context, fuzzy sequential patterns were defined to handle quantitative attributes. [9] and [10] proposed methods to mine fuzzy sequential patterns without providing experimental evaluations. We thus here consider the complete approach from [7], defining three fuzzification levels through the algorithms, SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY. We consider the fuzzy extension of item, itemset and sequence. The quantity universe of each attribute is discretized into fuzzy subsets (see next paragraph). A fuzzy item is the association of one item and one fuzzy set. For instance, [/php/tutor.htm, lot] is a fuzzy item where lot is a fuzzy set defined by a membership function on the access quantity universe of the item /php/tutor.htm. A fuzzy itemset is a set of fuzzy items, e.g. ([/php/tutor.htm,lot][/php/functions.php, little]). Note that the fuzzy itemset {{/php/tutor.htm, lot]{/php/tutor.htm, little]) 521 is not a valid fuzzy itemset, since no item can be repeated within an itemset. A fuzzy sequence is a sequence of fuzzy itemsets, e.g. < ([/php/faq.htm,lot})(\/php/eg.php,lot]) >. Table 1. Access grouped by IPs, temporaly ordered (empty cells for unaccessed pages) Cust./IP CI 82.228.151.02 86.197.153.12 82.226.199.47 82.226.199.48 | Date dl d2 d3 d4 d5 dl d2 d3 d4 dl d2 d3 d4 | /php/tutor.htm 2 1 || 1 j /php/eg.htm || /php/functions.php 3 /php/faq.php 1 1 1 2 4 2 2 1 4 1 || | 3 1 5 1 dl 2 2 1 First, the quantitative database is converted into a membership degree database. These partitions are automatically built by dividing the universe of quantities into intervals. Each interval groups the same proportion of users. It is then fuzzified in order to enhance generalization. From these membership functions we get the membership degrees for each record and for each fuzzy set. An example is given for CI in Table 2. Table 2. D. dl d2 d3 d4 d5 Membership degrees for customer 1 /php/tutor.htm U. | L. || ,, j , 1 :• J". Items /php/eg.htm L. || m. li 5 V 7S /php/functions.php li. L. /php/faq.php || m | T. i j 0.5 0.3 0.5 •• fM . 0.5 II.fi 1 1 The support of a fuzzy itemset (X, A) is the proportion of objects supporting it. We propose three definitions depending on the fuzzification level: (1) SPEEDYFUZZY counts objects recording, for each item of the itemset, a membership degree not null at least once; (2) MINIFUZZY is based on a thresholded count, incrementing the number of objects supporting the fuzzy itemset when each of its item has a membership degree greater than a specified threshold in the data sequence; (3) TOTALLYFUZZY carries out a thresholded S-count. The support is computed as a weighted sum of the membership degrees greater than a relevancy threshold u>. The support of a fuzzy sequence is computed as the ratio of the number of objects supporting this fuzzy sequence compared to the total number of objects in 522 database. This support degree is computed algorithms detailed in [7]. Let us consider the membership database for customer 1 (Table 2) and the support of < ([/php/tutor.htm, lot])([/php/f unctions.php, lot]) >. With SPEEDYFUZZY, we consider the items underlined into account. With MINIFUZZY (w=0.49), we take the items boldfaced into account. With TOTALLYFUZZY (o;=0.49), customer 1 supports the sequence, the best occurrence of the sequence is kept, twice underlined. Table 3. SPEEDYFUZZY MINIFUZZY TOTALLYFUZZY Sequential patterns extracted with minsupp=55% <([/php/tutor.htm, little])([/php/functions.php, lot])> <([/php/tutor.htm, lot]}([/php/functions.php, lot])> <([/php/tutor.htm, little])([/php/functions.php, lot])> <([/php/functions.php, lot])> <([/php/tutor.htm, little])([/php/functions.php, lot])> <([/php/functions.php, Iot])> 75% 75% 75% 75% 69% 56% Table 3 shows the sequential patterns respectively extracted by SPEEDYand TOTALLYFUZZY. Note that the frequent items are the same for all counting methods. The difference is in the number and length of the sequences. For a same minSupp, the number and length of the mined patterns are indeed greater with MINIFUZZY or SPEEDYFUZZY than with TOTALLYFUZZY (due to the thresholded E-count). This reduction in the number of patterns can be used for a database containing very high amount of frequent patterns to find the most relevant ones, the user will thus be provided with a selection of patterns, and not only have to assess a selection of patterns and not a really large quantity of them. So SPEEDYFUZZY could be used to identify user profiles, whereas TOTALLYFUZZY for mining detailed downloading rate. FUZZY, MINIFUZZY 3. E x p e r i m e n t s In this section, we present performances of the algorithms SPEEDYFUZZY, MINIFUZZY and TOTALLYFUZZY compared to PSP [4] and results of web access log mining with TOTALLYFUZZY. We show that soft sequential pattern mining brings more relevant information than crisp methods. Access logs from a laboratory website were prepared and mined to find frequently visited pages - such as in crisp sequential pattern mining - but also repeatedly visited pages. The access logs were pre-processed and the dataset recorded the number of accesses to one page, the same half-day by one user. For example, record "1500 5067 10 6" means that "visitor 21500" on half-day 523 5067 visited 6 times the URL coded by 10. This dataset contained 27,209 web pages visited by 79,756 different IPs over 16 days (32 half-days). As explained previously, we fuzzify the number of access per visitors on each page 3 fuzzy sets using a tool based on the DiscretizeFilter module of Weka [11]. Note that all data modeling choices have impact on what can be extracted from the data. Next experiments should thus be carried out using a fuzzification more adapted to the dataset, based on the approach of [12]. First, we compared performances of the fuzzy algorithms to those of PSP [4]. Figure 1(a), it can be noted that SPEEDYFUZZY is almost as fast as PSP despite the fact that it scans three times more items. Figure 1(b) shows that MINIFUZZY and TOTALLYFUZZY extract less frequent sequences than SPEEDYFUZZY and PSP. MINIFUZZY and ToTALLYFuzzYonly keep the items which have a degree greater than w and so which are considered as relevant by the user. The number of frequent sequences is then necessarily reduced compared to SPEEDYFUZZY or PSP. Figure 1(c) shows the extraction time according to the number of data sequences in database for minSupp = 0.2. These preliminary experiments show that results on fuzzy logs are consistent with the one on crisp values. The same frequent URLs can indeed be found using crisp or soft sequential pattern mining. The advantages of our method concern the additional knowledge supplied by quantities. Indeed, while the crisp algorithm PSP found URL 139 was frequently accessed, TOTALLYFUZZY found that it was frequently accessed between 2 and 5 times during the same period. Runtime according to the minsup value (a) t of frequent sequences according to minSupp (b) Runtime according to the sequence number (c) Figure 1. (a)Runtime according to rninSupp for 79756 sequences; (b)Number of frequent sequences according to minSupp for 79756 sequences; (c)Runtime according to the number of sequences in the datasets, for minSupp=0.2% 524 4. C o n c l u s i o n a n d p e r s p e c t i v e s Historical analysis of web logs and more especially sequential pattern extraction from web databases is highly interesting for customer targeting, server dimensioning or transfer optimization. In this paper we propose to mine web logs using fuzzy sequential patterns handling three fuzzification levels thanks to three algorithms. This choice allows the extraction of frequent sequences by making a trade-off between relevancy and performance. Experiments on web access logs have highlighted the relevance of our proposal. This work builds many perspectives, for instance, to mine web-purchases for e-marketing. References 1. M. Spiliopoulou and L. C. Faulstich. WUM: A tool for Web utilization analysis. Lecture Notes in Computer Science, 1590, 1999. 2. O.-R. Zaiane, M. Xin and J. Han. Discovering web access patterns and trends by applying olap and data mining technology on web logs. In Proc. of the Advances in Digital Libraries Conf., pages 19-30, 1998. 3. E. Damiani, B. Oliboni, E. Quintarelli and L. Tanca. Modeling users' navigation history. In WS. on Int. Tech. for Web Personalisation, 2001. 4. F. Masseglia, P. Poncelet and R. Cicchetti. An efficient algorithm for web usage mining. Networking and Information Systems Journal, 2(5-6), 1999. 5. C. M. Kuok, A. W.-C. Fu and M. H. Wong. Mining Fuzzy Association Rules in Databases. SIGMOD Record, 27(1), pages 41-46, 1998. 6. R. Srikant and R. Agrawal. Mining Quantitative Association Rules in Large Relational Tables. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 1-12, 1996. 7. C. Fiot, A. Laurent, M. Teisseire and B. Laurent. Why Fuzzy Sequential Patterns can Help Data Summarization: An Application to the INPI Trademark Database. In Proc. of the 2006 Fuzz-IEEE Conference, to appear. 8. R. Agrawal and R. Srikant. Mining Sequential Patterns. In Proc. of the 11th Int. Conf. on Data Engineering, pages 3-14, 1995. 9. T.P. Hong, K.Y. Lin and S.L. Wang. Mining Fuzzy Sequential Patterns from Multiple-Items Transactions. In Proc. of the Joint 9th IFSA World Congress and 20th NAFIPS Int. Conf., pages 1317-1321, 2001. 10. Y.-C. Hu, R.-S. Chen, G.-H. Tzeng and J.-H. Shieh. A Fuzzy Data Mining Algorithm for Finding Sequential Patterns. Int. J. of Uncertainty Fuzziness Knowledge-Based Systems, 11(2), pages 173-193, 2003. 11. I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools with Java Implementations, 2000. 12. A. Gyenesei and J. Teuhola. Multidimensional fuzzy partitioning of attribute ranges for mining quantitative data: Research articles. Int. J. Intell. Syst., 19(11), pages 1111-1126, 2004. AN IMPROVED ECC DIGITAL SIGNATURE ALGORITHM AND APPLICATION IN E-COMMERCE XU XIAO-PING Guangdong Polytechnic Normal University Guangzhou Electron-information Department, 510633 Abstract: It is well known that Elliptic Curve Cryptograph (ECC) features the highest bit security. The author analyses the advantages of ECC by comparison, explores the mathematics base on elliptic curve and the complexity of discrete logarithm, and makes improvements on existing Elliptic Curve Digital Signature Algorithm (ECDSA) to accelerate the arithmetic speed and shorten time for data transmission. Better effects have been achieved by applying ECC into E-commerce to realize digital signature algorithm. Keyword: Elliptic Curve Cryptograph, Digital Signature, E-commerce 1 Introduction The popularity of the Internet and the sharing of the information have now reached a new level, which have made information security protruded day by day. Key technology is critical in solving network information security. The study on key has been increasing in an explosive way over the past 20 years. RSA, a popular technology, has matured and has higher requirements on bit length. The increase on key module has slowed down its speed in encryption and decryption. Its realization by hardware also becomes more and more unbearable. Therefore the application of RAS has become a heavy burden, especially its application in E-commerce, a substantive way of safe trading. ECC adopts small module and still reaches the same level of security as RAS. Thus the study on ECC has become hot for domestic and overseas scholars. The author has made some improvements on existing ECDSA. Its arithmetic speed has been accelerated and its data transmission has been shortened. The author also studies the application of its improved algorithm in E-commerce and makes E-commerce faster and safer. 2 ECC Systems and its Comparison Since the birth of public key cryptography, people have presented various public key cryptography methods. The following three types of systems have been thought to be safe and effective: Big Integer Factorization System (The representative one is RSA), ECC and Discrete Logarithm System (The representative one is DSA.) 2.1 RSA RSA was firstly put forward in 1978 by three professors from Massachusetts Institute of Technology: Rivest, shamir and Adleman. This is a 525 526 unilateral trapdoor function, an exponential function based on factorization. An exponential function is a unilateral trapdoor function based on seeking discrete logarithm. It is a matured and widely used key system nowadays. The security of RSA is based on the difficulty of factorizing big integer in number theory. Therefore if the integer is bigger, the factorizing will be more difficult. It will be more difficult to decrypt the key. The level of encryption will be much higher. The advantages of RSA methods are: it is simple in theory and easy to use. But with the advancement and perfection of big integer factorization, the raising of computer operation speed and the advancement of computer network, the integer for safeguarding RSA encryption and decryption is required to be bigger and bigger. To ensure RSA safety, the length of its key is expanding. For example, today it is thought RSA needs 1024-bit length to protect its safety'11. Therefore it brings a heavy burden to use RSA and its application range is limited. 2.2 DSA DSA has been presented by National Institute of Standards and Technology of U.S. in August 1991. It is a digital signature standard based on discrete logarithm which is used for Digital Signature Standard (DSS). This is a DSS of public key. DSA uses a public key to verify data integrity and consistency. DSA only provides digital signature. It does not provide data encryption'21. 2.3 ECC In 1985, Neil Koblitz and Victor Miller respectively put forward Elliptic Curve Cryptograph (ECC). The security of ECC not only relies on the factorization of discrete logarithm at elliptic curve, but also on the selection of the curve and system of curve. At present, 200 bits ECC already has very high security. The mathematic theory of ECC is that'31: at a binary finite field F, an elliptic curve is developed based on certain rule where addition and multiplication are defined. Suppose that two points P and Q are known at elliptic curve: Q=xP Seek x? The seeking of X is the well-known discrete logarithm on elliptic curve. At one side, it maps multiplication and exponent arithmetic on field of real numbers into addition on elliptic curve. It is faster and easier than other public key systems whether ECC is realized by hardware or software. The cost is also very low. At the other side, seeking X at elliptic curve is involved in both integer factorization and discrete logarithm, which is undoubtedly more difficult. It is quite natural that this system has higher security. 527 Table 1: Comparison among Various Public Key Systems in key length Protected key (bit) 80 E C C (bit) n 161 D S A (bit) R S A (bit) n 112 224 128 256 192 384 256 512 q 160 224 256 384 512 P 1024 2048 3072 7680 15360 1024 2048 3072 7680 15360 The security of encryption is reflected by its ability to resist attacking. Compared to other public key systems. ECC has absolute advantages in resist attacking. For example, 160-bit ECC has the same level of security as 1024-bit RSA or DSA. 210-bit ECC has the same level of security as 204-bit RSA or DSA. Decryption Time (MIPS Years) Figure 1: Comparison among ECC, RSA and DSA in Resisting Attacking ECC has the following technical advantages: 1 .Smaller computational complexity and it is quick in operation. Though RSA can raise key processing speed by selecting smaller key (can be as small as 3) to speed up processing of encryption and signature verification and make RSA compatible in encryption and signature verification speed, ECC is much more faster in processing key (decryption and signature verification) than RSA or DSA. Therefore the comprehensive speed of ECC is much faster than that of RSA or DSA. 2.Smaller storage space Key size and system parameter of ECC is much smaller than RSA or DSA. This means that its storage space is much smaller. It is very significant in applying encryption on IC card. 528 3. Lower bandwidth requirement. When long message is encrypted or decrypted, these three key systems have the same requirements on bandwidth. But ECC has much lower bandwidth requirements when short message is processed. While key encryption is mainly used for processing short message, for example, for digital signature or conversation key transmission in symmetrical system. The low requirements on bandwidth make ECC have very wide prospect in application at wireless network. These features from ECC will make it take the place of RSA and become a popular public key decryption algorithm. For example, SET framer has decided to make ECC a default public key algorithm for next SET protocol. 3 ECC Digital Signature Algorithms and its Improvement Digital signature is used to guarantee data integrity in transmission and provide identity verification and non-repudiation of sender. Using public key algorithm is the main technology to realize digital signature. The flow chart of digital signature and verification • Plaint Text Hashed Value Plaint lext ^ Hash Algorithm Signature Algorithm uigitai signature Private Key | Figure 2: Digital Signat ure Flow chart Plaint Text Plaint Text ^ Hash Algorithm Hashed Value .. Verification Algorithm ^ Digital Signature Valid or not ^ iL Public Key Figure 3: Signature Verification Process By existing elliptic curve digital signature algorithm, we have made some improvements in ECC to make its operation burden decreased and its speed accelerated. Inversion is the main operation burden in existing ECC encryption or signature process. For example, in verifying signature, the algorithm of w= s"1 (mod n), which uses extended Euclid algorithm and needs to complete 0.8431og2(n)+1.47 divisions in average, is very slow'41. We developed a totally 529 new signature equation, which does not need inversion in its algorithmic process. The signature and verifying equations are as following: Signature Equation: k=s+mrx Verifying Equation: r=sg+mry Operation: sg+mry=(k-mrx)g+mrxg=kg=r From above process, we can understand that it is same to generation of elliptic curve and distribution of private keys in existing IEEE PI363. The difference lies in its signature generation and verification process. The improved algorithm reduces the operation burden and speeds up the operation, which has been verified by experimental results. Under the premium that the same security will be provided, this solution has lower requirements on system resources and is much more suitable for using at environment that is limited by algorithm or storage capability, such as intelligent card etc'51. 4 Application of Improved ECC in E-commerce E-commerce is the inevitable result from social and technology development. The network transaction needs a lot of information, such as information on product manufacturing, supply, product demand, competition etc. Compared to traditional transaction, E-commerce has higher requirements on information security'61. The core and key of E-commerce security is the security of e-transaction. At present, the popular safe on-line payment protocols used in e-transaction are SSL and SET. SET (Safe Electronic Transaction) is one of the protocols to guarantee safe transaction on Internet. Because of its strict design and high security, it has been widely used. In SET protocol, various encryption algorithms, including symmetrical and unsymmetrical encryption, have been used to realize safety. In text, we will apply improved ecliptic curve digital signature algorithm into SET. 4.1 SHA Application SI.Add the text for abstracting; S2.Reckon abstract S3.Send your information and abstract to other (business or bank) S4.The other side (business or bank) initializes in the same way. Added text, reckon abstract and compare if abstracts are same. 4.2 Signing Process SI.Cardholder uses SHA to generate abstract H(OI), H(PI) from (OlorPI) . S2.Card holder decides elliptic curve parameters F= (P, a, b, g, n, h) or (m, f(x), a, b, g> n, h) . S3.Cardholder sends decided hash function (SHA) and parameters of elliptic parameters to business and bank. 530 S4.Cardholder chooses private key X based on decided limited field G (P) and elliptic curve. Public key Y will be got from the public point g: y=xg. The signer makes y in public. S5.Cardholder chooses random parameter K, l ^ K ^ n - 1 . S6.Reckon r=kg. If r=0, go to step S5. S7.Reckon s=mrx-k. ( m is text abstract). S8.Use (s, r) to sign m. Send (s, r) with m to verifier. 4.3 Verifying Process S9.The business reckon r'=sg+mry. SlO.If r'=r, then signature is valid. Otherwise the signature will be turned down. 4.4 Code The selection of elliptic curve adopts IEEE P2363 standard. The selection of parameters171 is as following: // Various fields: p(t) = tA163 + tA7 + tA6 + tA3 + 1 inline void use_NIST_B_163 () {F2X pt=Pentanomial (163, 7, 6, 3, 0); setModulus (pt);} // Degree 163 Binary Field from fips 186-2 // (fake random curve E) : yA2 + xy = xA3 + xA2 + b, // b = 2 0a601907 b8c953ca 1481ebl0 512f7874 4a3205fd // (Order of base point) : // r = 5846006549323611672814742442876390689256843201587 // (Base point G) : // Gx = 3 f0ebal62 86a2d57e a0991168 d4994637 e8343e36 // Gy = 0 d51fbc6c 71a0094f a2cdd545 bllc5c0c 797324A // remaining factor h = 2 #define NIST_B_163 EC_Domain_Parameters (163, 3, 7, 6, 3, Curve ("1", "20a601907b8c953cal481ebl0512f78744a3205fd"), decto_Bigint ("5846006549323611672814742442876390689256843201587"), Point ("3f0ebal6286a2d57ea0991168d4994637e8343e36", "0d51 fbc6c71 a0094fa2cdd545b 11 c5c0c797324f 1"), decto_BigInt ("2")); void ecdsa_ex () { // Degree 163 Binary Field from fips 186-2 use_NIST_B_163 (); EC_Domain_Parameters dp = NIST_B_163; ECPrivKey sk (dp);// (generate key pair from elliptic curve parameters) std::string M ("correct message"); ECDSAsigl (sk,OS2IP(SHAl(M)));// (generate signature) // (DER encode) DERder_str(sigl); 531 HexEncoder hex_str (der_str); std::cout« "DER Encoding: " « hex_str « std::endl; ECDSA sig2; try {// (analyze and check the error from DER) sig2 = der_str.toECDSA (); // (decode) } catch (borzoiException e) {// (Print error message and exit) e.debug_print (); return;} ECPubKey pk (sk); std::cout« "Checking signature against M: " « M.c_str ( ) « "\n->"; std::cout« "SHA1(M):" « OS2IP(SHAl(M)) « std::endl; if (sig2.verify(pk, OS2IP(SHAl(M))» // (verify and sign) std::cout«"valid signature\n"; else std::cout« "invalid signature\n"; M = "in" + M; // (falsify data) s t d . x o u t « "Checking signature against M: " « M.c_str ( ) « "\n->"; if (sig2.verify(pk, OS2IP(SHAl(M)))) // (verify signature) std::cout« "valid signature\n"; else std::cout« "invalid signature\n";} The improved algorithm has higher performance now and it is good for implementing key, but not good to crack key. The improved algorithm has raised key practicability as well as guaranteed key security, simplified operation complexity and accelerated operation speed. These have been verified by experiment. i^iiirK , 'P* , ' Hi 7^ J *^Kag.5iri!,~* zva,," -- •*•'-!™ .•• • - Pi xf deyfil: 3a3id53081a20btt72a8648ce3d82B130819602Biai3Blaa28288a30f>092a8648ce3dBia2U 3033O0?e2@18302010C02ei8?:i82e04i50000OB8000@0800000008008fl80BB008B0B008000104i!;B 2B«6B1907b8c953cal48iebl0512f 78V44a328SFdB42MM«3F0eljal6286a2dS7eaB9¥l.:1.68d4V9463 7i;8343e360Bd51fbc6r.7:ta0094f«2c:dd545hllc5c0i:797324ri82:lS04B8080Baa08800808800292f e77e70ci2a4234c33020102032eB8042bB48:l9bc9ba«e09S34M045224S'»92dF5dM>834b86SFfBiB e26418028aa7S9ae3376ai92c69a8014e34FS8c Aei-d?.-- 3881dS3081«.206872*8648<;B3da201388i96028:1013Bl»82028B»306092a8648ce3dai82M 3033009028103828184020J.07302ea41S0BB0800000fl0B8008fl0000000BBB8888000008BB0i041S0 28a6019a?b8c953cal481eM0S'12F?8?44a328£Fd042b0403F0ebal628Ga2dS7ea899U68d499463 7c8343e360Brt5lFhc6r.7la0B94fa2cdd51KhllcHc0i;797324Fl.02i504BBBB8fl0000B00000a00292F e7?e78cl2a4234c330201B2U32sB0842hB40:l.9bc9bd«e09!i34blM45224S492dF5db6834bS65FF01W e2«41.8B28aa7S9ae3376Bl92c69aSB14e34fSI»r: OK Pi'ess anij key to continue^ Figure 4: the experiment and its results. 532 5 Conclusions With continuous popularity of Internet, E-commerce has become social development trend. As a network payment protocol, SET is in continuous perfection. After ECC becomes a hot issue, there are a lot of studies on its application. The author has made some improvements on existing elliptic curve digital signature algorithm and has verified the theory and practical applications on improved algorithm. The improved algorithm has simplified operation complexity, accelerated operation and guaranteed key security. It is suitable for application in SET. Reference [1] Li Ke-hong, Wang Da-ling and Dong Xiao-mei. Applied Password Study and Computer Data Security. Northeast University Publishing House. Shengyang. 1997. [2] Written by Bruce Schneier; Translated by Wu Shi-zhong, Zhu Shi-xiong and Zhang Wen-zheng. Applied Password Study —Protocol, Algorithm and C Source Program. Machine Press. Beijing. 2002. [3] National Institute for Standards and Technology, "Digital signature standard', FIPS Publication 186, 1993 [4] Qing Si-han. Password Study and Computer Network Safety. Qinghua University Publishing House. Beijing. 2001. [5] Lu Sheng, Miao Quan-xing, Bian Zheng-zhong, Luo Rong-tong. Design and Realization of Elliptic Curve Intelligent Card Algorithm. 2003(9):25-2 [6] Han Bao-ming, Du Peng and Liu Hua. Safety and Payment of E-commerce. People's Post and Telecommuniations Publishing House. Beijing. 2001. [7] G Agnew, R. Mullin and S. Vanstone, "An implementation of elliptic curve cryptosystems over F2155", IEEE Journal on Selected Areas in Communications, 11 (1993), 804-813. Note: This topic is a natural science study project for universities from Education Department of Guangdong Province. The project number is 203061. Author: Xu Xiao-ping, Associate Professor of Computer Applications. Mainly involved in the study of Internet Environment and Applications. Address: Room C903, New Teachers Village, South China Normal University, Guangzhou P C : 510631 Email: cathy.xu@ 163.com AN IMMUNE SYMMETRICAL NETWORK-BASED SERVICE MODEL IN PEER-TO-PEER NETWORK ENVHIONMENT XIANGFENG ZHANG1, LIHONG REN1, AND YONGSHENG DING1'2, * I) College of Information Sciences and Technology 2) Engineering Research Center of Digitized Textile & Fashion Technology, Ministry of Education Donghua University, Shanghai 201620, P. R. China * Email: [email protected] Requirements for future Internet are implemented possibly in peer-to-peer network environments where all network nodes are equal to each other. Inspired by the similar features between immune systems and future Internet, based on the immune symmetrical network theory, a network service model in a peer-to-peer network environment is designed on our bio-network platform. To validate the feasibility of the model, we do experiments with different network service distributions and user requests towards each node. The results of the hops per request with time show that the users can acquire network services flexibly and efficiently. 1. Introduction The development of Internet technologies enables more and more man-made devices to access Internet and act as its components, which shows us a bright prospect of Internet. Obviously, future Internet must be capable of extensibility, survivability, mobility, and adaptability to network environments. It is necessary to optimize Internet architecture and its applications to address the challenges of the above key features. On the other hand, biological immune systems are adaptive systems and learning behaviors take place through evolutionary mechanisms similar to biological evolutions. They are distributed systems without central control. They can survive local failures and external attacks and maintain balance because of emergent behaviors of the interactions of many local elements, like immune cells. Inspired by the similar features between the immune systems and future Internet, a bio-network platform architecture has been designed in our former work. Bio-entities in the bio-network architecture are regarded as autonomous immune cells and they possess the characteristics of immune cells, such as interaction, no central control, diversity, mobility, and evolution. 533 534 Requirements for future Internet are implemented possibly in peer-to-peer (P2P) network environments where all network nodes are equal to each other and provide network application and services for other nodes in a distributed mode. Hoffmann [1] has proposed a symmetrical network theory for the immune system, which is a tractable first approximation. Principal lymphocytes that are involved in the response to a particular antigen are classified into just two specificity classes or sets. The interaction between these two sets maintains the balance of the immune system. So we develop a network service model in a P2P network environment based on the immune symmetrical network theory. This paper aims at the design a network service model in a P2P network environment. To this end, it is organized as follows: Section 2 will introduce some basic theories about immune symmetrical system and P2P network. Section 3 will present briefly our bio-network platform architecture. Section 4 will emphasize on the creation of the network service model. In order to validate its feasibility, some experiments are made on the bio-network platform with different network service distributions and user requests towards each node. The results show that the users can acquire network services flexibly and efficiently. Section 5 concludes the paper by discussing advantages of the service model. 2. Background 2.1. Immune Symmetrical Network The natural immune system is a very complex system with several functional components. It plays an important role in coping with dynamically changing environment through constructing self-non-self recognition networks among different species of antibodies. According to the immunologists, the components such as cells, molecules and organs in the immune system can prevent a body from being damaged by pathogens, known as antigens. The basic components of the immune system are lymphocytes that have two major types, B lymphocytes (B cells) and T lymphocytes (T cells). These two types play different roles in the immune response, but they act together and control or affect each other. The immune system is an adaptive system and learning behaviors take place through evolutionary mechanisms similar to biological evolution. It is a distributed system without central control. It can survive local failures and external attacks and maintains balance because of emergent behaviors of many local elements, like immune cells. Hoffmann [1] has proposed a symmetrical network theory for the immune system. The principal lymphocytes are classified into just two specificity classes. The first class is the antigen-binding set, denoted T+ andB+ for T 535 cells and B cells respectively. The second set is minus or anti-idiotypic set, T and B -. There are three types of interaction between the plus and minus sets as follows: stimulation, inhibition, and killing. Stimulation can occur when two lymphocytes encounter each other. The receptors of one lymphocyte ('+') can cross-link the receptors of a second lymphocyte ('-'), the converse is also true, so stimulation is assumed to be symmetrical in both directions between these two sets. Specific T cells factors could inhibit receptors. Finally, antibody molecules are assumed to kill in a symmetrical mode. According to interactions among B cells and T cells, we can receive a set of four stable steady states for the system of T+, B +, T - and B - cells. The steady states are initial, suppressive, responsive, and anti-responsive. 2.2. Peer-to-Peer Network Although the traditional client-server model first establishes Internet's backbone, more and more clients enter Internet and loads on the servers are steadily rising, resulting in long access times and server breakdowns. The user requests and communications among users are completed through application server. While P2P systems offer an alternative to such traditional systems for a number of application domains. In P2P systems, every node (peer) of the system acts as both client and server and provides part of the overall resources/information available from the system. In a pure P2P system, no central coordination or central database exists and no peer has a global view of the system. Participating peers are autonomous and self-organize the system's structure, i.e., global behavior emerges from local interactions. P2P technologies have many applications, such as file sharing and exchanging, distributed computing, collaborative system, peer-to-peer computing, and enterprise application. Like most other P2P applications, Gnutella builds, at the application level, a virtual network with its own routing mechanisms. Reference [2] extracts the topology of Gnutella's application level network. A content location solution is also proposed in which peers loosely organize themselves into an interest-based structure on top of the existing Gnutella network and this method makes Gnutella a more competitive solution [3]. Yang [4] further evaluates a non-forwarding peer-to-peer search. 3. A Bio-Network Platform Architecture In our previous work [5,6], we regarded services and applications on Internet as a number of interacting entities and applied some key principles and mechanisms of the immune systems to build network computation models. Based on these models, we have built a new bio-network platform architecture 536 (see Figure 1.) and its simulation platform which has the capability of service emergence, evolution etc. The simulation platform can be used to simulate some complex services and applications for Internet or distributed network. Bio-network Low-level Functional Modules Figure 1. The bio-network platform architecture. In the bio-network platform architecture, a basic and important entity is called bio-entity. A bio-entity is an autonomous mobile agent and analogous to a cell or an antibody in the immune system. The bio-entity consists of its attribute, behaviors, services information, and communication. Interactions among a group of bio-entities can form an emergent service or application, called a society-entity. Apart from the bio-entities, the layered infrastructure consists of bio-entities' survivable environment, bio-network core services, and bio-network low-level functional modules established in a network node. Obviously, the bio-network platform hosts in a network node. The bio-network architecture has the advantages of extensibility, survivability, mobility, and adaptability to the changes of different users and network environments over the current Internet. Bio-entity survivable environment. The Bio-entity survivable environment is a runtime environment for deploying and executing bio-entities and protects the node from attacking with some security policies. It exists on different platforms so that the bio-entities could migrate in the heterogeneous network and access resources of different systems. Bio-network core services. The bio-network core service layer provides a set of general-purpose runtime services that are frequently used by bio-entities. They include event processing service and some basic services such as lifecycle 537 service, directory service, naming service, community sensing service, bio-entities migration service, evolution state management service, interaction control service, credit-driven control service, security authentication service, and application service. All these services alleviate bio-entities from low-level operations and also allow bio-entities to be lightweight by separating them from routine work. Bio-network low-level functional modules. In the bio-network low-level functional modules, there are six main modules: local resource management, bio-entity registration, bio-entity state control, local security, message transport, and class loader. The ideal model would place a bio-network platform on every device as a network node. The modules are just a bridge to maintain access to local resources. 4. A Service Model in Peer-to-Peer Network Environment 4.1. The Creation ofP2P Network Environment We implement the P2P network model on the designed bio-network simulation platform according to the symmetrical network theory of immune systems. The network can provide services and applications to users. Because of complexity and heterogeneity of future Internet, the network structure is very changeable, from just few nodes to incalculable nodes. Users can communicate directly, share resources and collaborate with each other. Users or services, represented by bio-entities in the network nodes, can be regarded as antibodies or anti-antibodies in the immune system. The bio-entities in different nodes interact equally. They have three actions between two neighbor nodes and keep four steady states. There are several bio-entities on the nodes to provide network services. The inter-connecting nodes are called symmetrical nodes. As an example, Node 1(N1) and Node 2 (N2) are regarded as two sets and bio-entities in the bio-network are regarded as antibodies in the symmetrical immune network, thus interactions of bio-entities in these two nodes exit stimulation, inhibition, and killing. The two nodes have four stable states: initial state, suppressive state, responsive state, and anti-responsive state, as shown in Figure 2.These states are shown in details as follows. (1) Initial state. When user requests to nodes are few, the bio-entities in the node can provide enough services to the users so that the users need not send requests to other nodes. At the same time, bio-entities have not enough credits to provide services to the other nodes. 538 (2) Suppressive state. With the increment of user requests, bio-entities in the network nodes require more and more credits to reward their services and they will evolve to produce next generations. At the same time, bio-entities in the node cannot provide enough services to the request users towards the node. For instance, the bio-entities on Nl have not enough credits for some users; while the bio-entities on N2 suppress the users of Nl to access their services because they have to provide services to their own users. The two nodes suppress each other to use their own resources and services, so the bio-entities in the nodes keep suppressive state. Nl oo o o o (1) Initial state (2) Suppressive state (3) Responsive state (4) Anti-responsive state Fig. 2. Interaction of two end nodes in P2P network. (3) Responsive state. When the requests towards Nl are increasing while the requests towards N2 are decreasing, a lot of unused resources or bio-entities exist on N2, bio-entities on Nl stimulus bio-entities on N2 and the latter provides services directly or migrates to Nl to provide services. When the services are provided, the bio-entities return their nodes and establish relationship with Nl. The state of the two nodes is in responsive state. With the decrement of bio-entities on N2, the services to N2 reduce and the credit level of Nl is higher than that of N2 so that Nl and N2 cannot keep the relationship, they will look for new nodes, and return the initial state. But the relationship between these nodes still exits and the bio-entities on the nodes interact with each other to provide services. If a bio-entity, denoting user requests, needs network services on other nodes, it sends a request to all of its known neighbors. The neighbors then check to see whether they can reply to the request by matching it to the service type. If they find a match, then they will reply; otherwise, they will forward the query to their own neighbors and increase the message's hop count. For instance, there are three bio-entities A, B, and C hosting on Nl, N2, and N3 respectively. Bio-entity A sends requests to other bio-entities of its neighbors. If B can provide service, it replies to A. At the same time, B acquires credits from A and establishes a relationship with B. If B cannot provide services to A, it sends the 539 request to C, and C will migrate to Nl to provide service for A. Then C returns its node and establishes a relationship with A. At the same time, bio-entities A and C announce their relationships to odier bio-entities on Nl. Bio-entities on Nl may access services on N3 directly and save time because of the decrease of the hops next time. (4) Anti-responsive state. The state is opposite to responsive state. The bio-entities on Nl provide services to requests from N2 and receive the credits. 4.2. Simulation Experiments In the simulation platform, we implement the P2P network model with two thousand nodes and simulate the service access. Before starting the experiments, we model the following parameters: (1) service information distribution; (2) request distribution encapsulates information on users' behavior. First, we set simulation parameters and set up simulation environments. We assume two request distributions: an unbiased distribution, with all requests having the same probability of being submitted, and a biased distribution, with a small number of requests are frequently asked. Suppose ten kinds of different network services distribute randomly on different nodes. In these experiments, we assume static resource distributions and no failures. The resource distributions are balanced and unbalanced. 100 H m | 40 O - -"— -13' - Unbalanced & biased Unbalanced & unbiased Balanced & biased Balanced & unbiased I 20 10 20 30 40 Simulator Time (generations) 50 Figure 3. Average number of hops per request with the change of simulation time. Average number of hops per request with time is shown in the Figure 3. We can see that biased user request can access more easily services than biased uses request under unbalanced or balanced resource distribution. As to a type of user request, bio-entities can migrate much more efficiently resource nodes and achieve much more easily resource services under the unbalanced resource distribution. 540 5. Conclusions In this paper, a network service model in P2P network environment is designed which based on the immune symmetrical network theory. Bio-entities on two nodes can interact through stimulation, inhibition, and killing to provide some services. From the simulation experiments, the nodes are designed in four stable states as those in the immune symmetrical network. Different request distribution affects the average number of hops. The interaction among bio-entities maintains the balance of bio-network and makes the resources utilized reasonably and optimizes architectures of bio-network. The characteristics of biological immune systems can satisfy service evolution, adaptability, and security of future Internet, so it is necessary to study other bio-network computational models to improve the exiting network architecture and to make future network services become much more intelligent and individual. Acknowledgments This work was supported in part by the Key Project of the National Nature Science Foundation of China (No. 60534020), the National Nature Science Foundation of China (No. 60474037 and 60004006), and Program for New Century Excellent Talents in University (No. NCET-04-415). References 1. G. W. Hoffmann, A neural network model based on the analogy with the immune system, J. Theoretical Biology, 122, 33-67(1986). 2. M. Ripeanu, I. Foster, and A. Iamnitchi, Mapping the Gnutella network: Properties of large-scale peer-to-peer systems and implications for system design, IEEE Internet Computing Journal. 6(1),(2002). 3. K. Sripanidkulchai, B. Maggs, and H. Zhang, Efficient content location using Interest-based locality in peer-to-peer systems, Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE INFCOM2003, 30 March- 3 April, San Francisco, California, USA(2003). 4. B. Yang, P. Vinograd, H. G. Molina, Evaluating GUESS and non-Forwarding peer-to-peer search, The 24th IEEE Internet Conference on Distributed Computing Systems, Hachioji, Tokyo, Japan, 24-26, March 2004 (2004). 5. Y. S. Ding and L. H.Ren, Design of a bio-network architecture based on immune emergent computation, Control and Decision (in Chinese). 18(2), 185-189(2003). 6. L. Gao, Y. S. Ding, and L. H. Ren , A Novel Ecological Network-Based Computation Platform as Grid Middleware System, Int. J. Intelligent Systems. 19(10), 859-884 (2004). M A C H I N E L E A R N I N G A N D S O F T - C O M P U T I N G IN BIOINFORMATICS - A SHORT J O U R N E Y F.-M. SCHLEIF a AND T. VILLMANN University of Leipzig, Department of Mathematics and Computer Science, Institute of Computer Science, Leipzig, Germany T. ELSSNER AND J. DECKER AND M. KOSTRZEWA Bruker Daltonik GmbH, Fahrenheitstrafie 4, D-28359 Bremen, Germany Bioinformatics is a promising and innovative research field which gains hope to develop new approaches for e.g. medical diagnostics. Appropriate methods for pre processing as well as high level analysis are needed. In this overview we highlight some aspects in the light of machine learning and neural networks. Thereby, we indicate crucial problems like the curse of dimensionality and give possibilities for overcoming. In an examplary application we shortly demonstrate a possible scenario in the field of mass spectrometry analysis in cancer detection. Despite of a high number of techniques dedicated to bioinformatic research as well as many successful applications, we are in the beginning of a process to massively integrate the aspects and experiences in the different core subjects such as biology, medicine, computer science, chemistry, physics, and mathematics. 1. Introduction Bioinformatics is a challenging field in research on the border between computer science and biology. It brings together scientists from mathematics, physics, chemistry, medicine and biology. The applications of bioinformatic research ranging from food industry, medical analytic, drug development in pharmacy to agriculture. From computer science point of view a broad variety of methods contribute to these applications, including artificial neural networks, statistical and Bayes methods, tree-based systems, image processing, statistical pattern recognition, visualization models to name just a few 1 " 8 . In the following we will shortly outline basic directions of methods in softcomputing for bioinformatics and link the contributions from this special session therein. a Corresponding author: Frank-Michael Schleif: Bruker Daltonik GmbH, Permoserstr. 15, D-04318 Leipzig, Germany, Tel/(Fax): +49 341 24 31-408(404), [email protected] 541 542 2. Data analysis - clustering and classification Data analysis in the field of bioinformatics takes place after maybe advanced data processing 9 . Main issues of data mining and data analysis are knowledge extraction, modelling of biological processes, generating of classification and decision systems featuring the biological knowledge, which can be used for classification, regression and prediction 10 . Thereby, the data frequently are noisy, high-dimensional/complex and, in particular in medicine, sparse. These aspects cause several difficulties. Especially, many of the traditional statistical methods can not be applied in medical or bioinformatic applications due to these restrictions u . Methods of soft-computing offer alternative ways to handle these difficulties. Clustering as an unsupervised paradigm plays a central role. It can have different purposes depending on the context: data compression, identification of typical patterns, efficient data description. Standard method is the commonly used agglomerative hierarchical clustering, which can be realized in several ways. A more robust class of methods are prototype based vector quantizer as k-means or its fuzzy counterpart fuzzy-k-means 12 , 13 . A robust type of vector quantizer is the family of neural maps 14 . Thereby, the self-organizing map (SOM, 15 ) and the neural gas algorithm (NG, 16 ) are prominent examples, which are successfully used in bioinformatic clustering tasks l r . These unsupervised algorithms allow information optimum compression and clustering of data together with robust noise tolerant behavior 18 In close relation to clustering and compression is complexity reduction of data. Standard methods are principal component analysis (PCA), Fourierand Wavelet analysis for feature extraction 5 or feature extraction by optimization of mutual information 19 or other objective functions. The growing variant of the above mentioned SOM can be taken as non-linear PCA 20 . Another paradigm is classification 21 . In machine learning context, it belongs to supervised learning methods. After training the classification model by pre-classified examples, the model should decide for unknown data the (probably) respective class. Classical statistics uses Bayes inference, which usually require knowledge or assumptions about the mathematical type of distribution of the data 22 . Alternatively, decision trees are a commonly applied method in biological or clinical classification systems 23 . Again, several objectives are possible. Usually some kind of information measures is used (Gini-index or Renyi-index) 24 . In bioinformatics, decision trees are applied for phylogenetic trees, for example 25 . This can be combined with neural networks approaches 26 . A popular prototype based classification method is the family of kernel methods, and, in particular, the support vector machines (SVMs) 27 . Based on the usage of separation properties of huge-dimensional spaces, classification is obtained by mapping of data into such high-dimensional 543 spaces and subsequent separation margin maximization. SVMs are successfully applied to complex data in bioinformatics as gene expression data in micro-array analysis 2 8 , 3 . A combination of SVMs together with decision trees for classification of plant spectra is provided in 29 . Learning vector quantization as another prototype based classification method allows an intuitive interpretation of the class dependent prototypebased classification decision as well as of the adaptation process (learning), which tries to approximate the Bayes borders of classification 14 . Several methods have been established to improve the standard algorithm LVQ2.1 concerning aspects like overlapping classes (Generalized LVQ - GLVQ) or insensitivity to initial conditions by neighborhood cooperativeness using the framework of NG (Supervised NG) 3 0 , 3 1 . Recent approaches also include probabilistic (fuzzy) classification extensions 32 , which have been successfully applied in proteomics and image segmentation of barley grains 3 3 , 3 4 . A challenging issue is the use of non-standard metric for classification 3 5 . Instead of the widely used Euclidean metric, other, more task specific metric should be applied. Examples are the Tanimoto-distance 2 1 widely applied in taxonomy, LIK-kernels or correlation measures in splice site recognition and microarray-analysis 3 6 , 3 7 . Further, parametrized distance measure can be applied. They allow an optimal adaptation to the given classification or clustering tasks. Adaptive metric were applied to cluster gene expression data 38 and cancer spectral data 39 . 3. D a t a visualization Data visualization of high-dimensional data may offer new insights in data structures and, therefore, is of increasing interest for biological experts, too. Standard tools for distance preserving mapping are curvilinear mapping or multidimensional scaling (MDS) 4 0 . Other methods like (linear) principal component analysis (PCA) obtain low-dimensional models by dimensionality reduction, which easily can be visualized 21 . A non-linear PCA can be realized by the growing self-organizing map (GSOM) 20 . It was demonstrated that this method is suitable to visualize the internal data structure of large-dimensional data by faithful data representation covering both statistical and structural (topological) properties, due to the fact, that most high-dimensional data have a low-dimensional internal representation caused by high inner correlations 41 . Applications in bioinformatics comprise visualization of micro-array analysis, gene expression data 42 , and proteomics 33 . Another type of dimensionality reduction scheme is based on the search for independent components based on blind source separation 43 . Thereby, usually a linear mixing of the unknown sources is assumed. The method determines the inverse mixing matrix such that the original low-dimensional sources can be reconstructed and thereafter may be visualized. 544 Another complicate task is the visualization of decision processes or structured non-metric data. The first one can be taken as visualization of decision trees which, hence, leads to the more general problem of visualization of trees. This includes also the above mention phylogenetic trees and, therefore, the visualization of phylogenetic structures and dependen44 45 cies ^ , * ° . 4. Exemplary clinical proteomics application in the light of bioinformatics We present in the following an exemplary application. This is the classification of mass-spectrometry (MS) data for cancer prediction. It comprise several of the above addressed problems, which are typical in bioinformatics: 1.) The data are high-dimensional 2.) Only a small sample set is available. 3) The data need to be preprocessed carefully. 4.) A visualization is highly recommended to detect internal relations and to extract them for biomarker search. 5.) The ability of generalizations is demanded for prediction. The exemplary data set is the LEUK data set generated by 4 6 . It was obtained by matrix assisted laser desorption ionization time of flight (MALDI-TOF) mass spectrometry analysis of blood plasma of patients suffering from acute lymphatic leukemia. Additionally a group of control volunteers was under consideration. A mass range between 1 to lOkDa was used. The spectra were first processed using the standardized workflow as given in 47 . The particular sample preparation is described in 4 8 . After preprocessing the spectra are obtained as 145-dimensional vectors, i.e. the feature vectors to be classified are high-dimensional. The data set consists of 30 cancer samples and 30 control samples, reflecting the problem of small sample sets, see Fig.1.The data were mapped onto their first two non-linear principal components spanned by a two-dimensional SOM 14 . A re-mapping of the SOM lattice into the data subspace spanned by the first two linear principle components is depicted in Fig. 2.A more appropriate probabilistic model of SOM is obtained by incorporation of fuzzy classification learning (FL-SOM, 3 3 ) , such that the responsibilities of the lattice notes give probability values for cancer prediction , Fig. 3. Acknowledgement The processing of the proteomic data was supported by the Bruker Daltonik GmbH using the C L I N P R O T ™ system and Sachsische Aufbaubank grant 7495/1187. References 1. U. Seiffert, B. Hammer, S. Kaski, and Th. Villmann. Neural networks and machine learning in bioinformatics - theory and applications. In M. Verleysen, editor, Proc. Of European Symposium on Artificial Neural Networks (ESANN'2006), pages 521-532, Brussels, Belgium, 2006. d-side publications. 545 laaukaernie\tcil_wcxjin_pat_s\134 Raw j 1 i JXJ;JmUL *J^m l3aukaamta\lol_wcxJin_koiit^s\JT52Raw jJJMt III Ju X W L Jju.^.i . XH..JL. , .. A Figure 1. Mass spectrum samples from LEUK. The above spectrum is a sample from the cancer class, the spectrum below is taken from the healthy control group. 2. M. Amos. Theoretical and Experimental DNA Computation. Natural Computing. Springer, Berlin, 2005. 3. I. Guyon, J. Weston, S. Barnhill, and V. Vapnik. Gene selection for cancer classification using support vector machines. Mach. Learn., 46:389-422, 2002. 4. L. Li, H. Tang, Z. Wu, J. Gong, M. Gruidl, J. Zou, M. Tockman, and R.A. Clark. Data mining techniques for cancer detection using serum proteomic profiling. Artificial Intelligence in Medicine, 32:71-83, 2004. 5. Pietro Lio. Wavelets in bioinformatics and computational biology: state of art and perspectives. Bioinformatics, 19(l):2-9, 2003. 6. M. Kussmann, M. Affolter, and L.B. Fay. Proteomics in nutrition and health. Comb. Chem. High Throughput Screen., 8(8):679-696, December 2005. 7. Jeffrey S. Morris, Philip J. Brown, Richard C. Herrick, Keith A. Baggerly, and Kevin R. Coombes. Bayesian analysis of mass spectrometry proteomics data using wavelet based functional mixed models. UT MD Anderson Cancer Center Department of Biostatistics and Applied Mathematics Working Paper Series. Be press, 2006. http://www.bepress.com/mdandersonbiostat/paper22. 8. N. Benoudjit, D. Francois, M. Meurens, and M. Verleysen. Spectrophotometric variable selection by mutual information. Chemometrics and Intelligent Laboratory Systems, 74:243-251, 2004. 9. M. Strickert, T. Czauderna, S. Peterek, A. Matros, H.-P. Mock, and U. Seiffert. Full-Length HPLC signal clustering and biomarker identification in tomato plants. In Proc. of FLINS 2006, 2006. 546 OVjOCS Figure 2. Re-mapping of the 3 x 2 SOM lattice into the data subspace spanned by the first two linear principle components of the data set. Different colors and shapes ( • 0) refer to different responsibilities according to volunteers and patients. FL-SOM for leukaemia data set •9B%\ 83% $0 8 %$L J r. Figure 3. Probabilistic fuzzy label for the 3 x 2 (FL-)SOM. The prototypes representing the responsibilities for the healthy and the patient class, respectively. The first bar visualizes the probability for cancer whereas the second one refers to healthy group membership. 10. W . T i m m , S. Boecker, T . T w e l l m a n n , a n d T. W . N a t t k e m p e r . P e a k intensity prediction for pmf m a s s s p e c t r a using s u p p o r t vector regression. In Proc. of FLINS 2006, 2006. 11. T. Villmann, G. Blaser, A. K o r n e r , and C. Albani. Relevanzlernen u n d 547 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. statistische Diskriminanzverfahren zur ICD-10 Klassifizierung von SCL90Patienten-Profilen bei Therapiebeginn. In G. Plottner, editor, Aktuelle Entwicklungen in der Psychotherapieforschung, pages 99-118. Leipziger Universitatsverlag, Leipzig, Germany, 2004. Y. Linde, A. Buzo, and R.M. Gray. An algorithm for vector quantizer design. IEEE Transactions on Communications, 28:84-95, 1980. J.C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum, New York, 1981. T. Kohonen. Self-Organizing Maps, volume 30 of Springer Series in Information Sciences. Springer, Berlin, Heidelberg, 1995. (2nd Ext. Ed. 1997). Helge Ritter, Thomas Martinetz, and Klaus Schulten. Neural Computation and Self-Organizing Maps: An Introduction. Addison-Wesley, Reading, MA, 1992. Thomas M. Martinetz, Stanislav G. Berkovich, and Klaus J. Schulten. 'Neural-gas' network for vector quantization and its application to time-series prediction. IEEE Trans, on Neural Networks, 4(4):558-569, 1993. Udo Seiffert, Lakhmi C. Jain, and Patrick Schweizer. Bioinformatics using Computational Intelligence Paradigms. Springer-Verlag, 2004. T. Villmann and J.-C. Claussen. Magnification control in self-organizing maps and neural gas. Neural Computation, 18(2):446-469, February 2006. C. Krier, D. Francois, V. Wertz, and M. Verleysen. Feature scoring by mutual information for classification of mass spectra. In Proc. of FLINS 2006, 2006. Th. Villmann and H.-U. Bauer. Applications of the growing self-organizing map. Neurocomputing, 21(1-3):91-100, 1998. R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. Wiley, New York, 1973. Marina Vannucci, Naijun Sha, and Philip J. Brown. Nir and mass spectra classification: Bayesian methods for wavelet-based feature selection. Chemometrics and Int. Lab. Systems, 77:139-148, 2005. M.K. Mareky, G.D. Tourassi, and C.E. Floyd Jr. Decision tree classification of proteins identified by mass spectrometry of blood serum samples from people with and without lung cancer. Proteomics, 3:1678-1679, 2003. J.R. Quinlan. C4-5: Programs for Machine Learning. Morgan Kaufmann, 1993. J. Dopazo and J.M. Carazo. Phylogenetic reconstruction using an unsupervised growing neural network that adopts the topology of a phylogenetic tree. Journal of Molecular Evolution, 44(2):226-233, 1997. E.V. Samsonova, T. Back, M.W. Beukers, A.P. Ijzerman, and J. Kok. Combining and comparing cluster methods in a receptor database. In Proceedings of the 5th International Conference on Intelligent Data Analysis (IDA), volume 2810 of Lecture Notes in Computer Science. Springer, 2003. Vladimir N. Vapnik. The nature of statistical learning theory. Springer New York, Inc., New York, NY, USA, 1995. M.P.S. Brown, W.N. Grundy, D. Lin, N. Christianini, C.W. Sugnet, T.S. Furey, M. Ares Jr., and D. Haussler. Knowledge-based analysis of microarray gene expression data using support vector machines. PNAS, 97(l):262-267, 2000. P.M. Granitto, F. Biasioli, C. Furlanello, and F. Gasperi. Rf-rfe on ptr-ms fingerprinting of agroindustrial products. In Proc. of FLINS 2006, 2006. A. Sato and K. Yamada. Generalized learning vector quantization. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, editors, Advances in Neural Information Processing Systems 8. Proceedings of the 1995 Conference, pages 423-9. MIT Press, Cambridge, MA, USA, 1996. B. Hammer, M. Strickert, and Th. Villmann. Supervised neural gas with 548 general similarity measure. Neural Processing Letters, 21(l):21-44, 2005. 32. T. Villmann, B. Hammer, F.-M. Schleif, and T. Geweniger. Fuzzy labeled neural gas for fuzzy classification. In M. Cottrell, editor, Proc. of Workshop on Self-Organizing Maps (WSOM) 2005, pages 283-290, 2005. 33. F.-M. Schleif, T. Elssner, M. Kostrzewa, T. Villmann, and B. Hammer. Analysis and visualization of proteomic data by fuzzy labeled self-organizing maps. In Proc. of CBMS, page in press. IEEE Computer Society Press, Los Alamitos, 2006. 34. C. Brtifi, F. Bollenbeck, F.-M. Schleif, W. Weschke, Th. Villmann, and U. Seiffert. Fuzzy image segmentation with fuzzy labeled neural gas. In M. Verleysen, editor, Proc. Of European Symposium on Artificial Neural Networks (ESANN'2006), pages 563-568, Brussels, Belgium, 2006. d-side publications. 35. B. Hammer and Th. Villmann. Classification using non-standard metrics. In M. Verleysen, editor, Proc. Of European Symposium on Artificial Neural Networks (ESANN'2005), pages 303-316, Brussels, Belgium, 2005. d-side publications. 36. Barbara Hammer, Marc Strickert, and Thomas Villmann. Prototype based recognition of splice sites. In U. Seiffert, L.A. Jain, and P. Schweitzer, editors, Bioinformatic using Computational Intelligence Paradigms, pages 2 5 56. Springer-Verlag, 2005. 37. M. Strickert, U. Seiffert, N. Sreenivasulu, W. Weschke, T. Villmann, and B. Hammer. Generalized relevance LVQ (GRLVQ) with correlation measures for gene expression analysis. Neurocomputing, 69(6-7):651-659, March 2006. ISSN: 0925-2312. 38. Samuel Kaski. SOM-based exploratory analysis of gene expression data. In Nigel Allinson, Hujun Yin, Lesley Allinson, and Jon Slack, editors, Advances in Self-Organizing Maps, pages 124-131. Springer, London, 2001. 39. V. Cheng, C.-H. Li, J.T. Kwok, and C.-K. Li. Dissimilarity learning for nominal data. Pattern Recognition, 37(7):1471-1477, 2004. 40. M. Strickert, N. Sreenivasulu, and U. Seiffert. Sanger- driven MDSLocalize - a comparative study for genomic data. In M. Verleysen, editor, Proc. Of European Symposium on Artificial Neural Networks (ESANN'2006), pages 265-270, Brussels, Belgium, 2006. d-side publications. 41. Th. Villmann, E. Merenyi, and B. Hammer. Neural maps in remote sensing image analysis. Neural Networks, 16(3-4):389-403, 2003. 42. S. Kaski, J. Nikkila, M. Oja, J. Venna, P. Toronen, and E. Castren. Trustworthiness and metrics in visualizing similarity of gene expression. BMC Bioinformatics, 4:48, 2003. 43. A. Hyvarinen, J. Karhunen, and E. Oja. Independent Component Analysis. J. Wiley Sons, 2001. 44. F. Schreiber. Visual comparison of metabolic pathways. Journal of Visual Languages and Computing, 14(4):327-340, 2003. 45. A. Drummond and K. Strimmer. PAL: an object-oriented programming library for molecular evolution and phylogenetics. Bioinformatics Applications Note, 17(7):662-663, 2001. 46. IKP Stuttgart MHH Hannover and Bruker Daltonik Leipzig, internal results on leukaemia, 2004. 47. B.L. Adam et al. Serum protein finger printing coupled with a patternmatching algorithm distinguishes prostate cancer from benign prostate hyperplasia and healthy men. Cancer Research, 62(13):3609-3614, July 2002. 48. E. Schaffeler, U. Zanger, and M. Schwab. Magnetic bead based human plasma profiling discriminate acute lymphatic leukaemia from non-diseased samples. In 52st ASMS Conf. 2004, page TPV 420, 2004. FULL-LENGTH HPLC SIGNAL CLUSTERING A N D BIOMARKER IDENTIFICATION IN TOMATO PLANTS M. S T R I C K E R T 1 , T. C Z A U D E R N A 1 , S. P E T E R E K 2 , A. M A T R O S 2 , H.-R M O C K 2 , AND U. S E I F F E R T 1 1 - Pattern Recognition Group, 2 - Applied Biochemistry Leibniz Institute of Crop Plant Research, Corrensstr. 3, D-06466 Gatersleben, Germany E-mail: stricker@ipk-gatersleben. de Group High resolution HPLC data of a tomato germplasm collection are studied: Analysis of the molecular constituents of tomato peels from 55 experiments is conducted with focus on the visualization of the plant interrelationships, and on biomarker extraction for the identification of new and highly abundant substances at a wavelength of 280nm. 3000-dimensional chromatogram vectors are processed by stateof-the-art and novel methods for baseline correction, data alignment, biomarker retrieval, and data clustering. These processing methods are applied to the tomato data set and the results are presented in a comparative manner, thereby focusing on interesting clusters and retention times of nutritionally valuable tomato lines. 1. I n t r o d u c t i o n High-performance liquid chromatography (HPLC) enables detection of molecular compounds in probe material. Here, substances of tomato peel from 36 accessions from the in-house germplasm collection, providing 55 partly redundant data sets, are studied in order to identify those lines with highly abundant phenolic compounds. The available HPLC multi-channel device records absorption rates in a wavelength range between 200nm and 600nm using a diode array detector with 1.2nm resolution. Specific interest lies in the components displayed at about 280nm for a 50rran sampling at 1Hz. Thus, absorption values for 3000 retention time points are considered corresponding to substance composition in the peel of each tomato fruit. The available 55 high-dimensional chromatogram vectors are further analyzed in a processing pipeline of baseline correction, vector alignment, and clustering. Additionally, a new feature selection method is introduced for identification of distinctive retention times. The extracted time points serve as biomarkers of specific differences within the set of chromatograms. Instead of utilizing standard software tools accompanying the HPLC device, the analytic steps are realized by alternative state-of-the-art and novel methods here. Thereby, entire chromatograms, not a selection of manually determined peaks, are processed. This maintains all information and it is a particular advantage if the chemical compounds are a priori unknown. 549 550 2. C h r o m a t o g r a m d a t a processing pipeline The goal, identification of possibly interesting tomato lines and relevant retention times, is addressed after raw data export from delivered chromatogram software, such as Empower or MetaboliteTools. Data processing steps proposed here are summarized in Fig. 1. 0. 1. 2. 3. 4. Raw Data —• Baseline Correction —» Alignment —>• /Biomarker ExtractionX —* Clustering QuantileSpline DTW, PTW, COW \ FUSE / PCA,HiT-MDS Figure 1. Pipeline for chromatogram data processing. 1. Baseline correction is an essential step to remove low-frequency instationarities occurring during the measuring procedure. Here, correction is obtained by a moving window approach. Within fixed time frames the g-quantiles (q < 20%), regarded as noise-induced baseline thresholds, are calculated and interpolated by a spline (QuantileSpline); this background spline is subtracted from the original signal in order to obtain the corrected data. This approach implements a high-pass filter and is, for example, part of the MATLAB Bioinformatics Toolbox. 2. Chromatogram alignment is essential to make the measured signals intercomparable. During the HPLC recording usually slight delays or accelerations are observed because of specific processes in the probe columns. Three approaches to chromatogram alignment have been studied, (restricted) dynamic time warping (DTW), parametric time warping (PTW), and correlation optimized warping (COW). Dynamic time warping DTW1 yields optimum alignment in terms of the shortest way, corresponding to the smallest sum of distances, in the component-wise source vs. target distance matrix. Thereby, the source signal becomes stretched by constant replica of adjacent components. This undesired effect of constantinduction is attenuated by upper limit constraints, but it cannot be completely avoided. The constant sections are unnatural for subsequent chromatogram peak integrations and, moreover, the stretched signal has to be mapped back to the original time scale. For these reasons, DTW has been excluded from the following considerations. Parametric time warping PTW 2 is an alternative alignment method without unnatural constant stretching. It provides very fast source-to-target time scale mappings by fitting parameters of a quadratic transfer function via an iterative least squares approach. Different to that, correlation optimized warping COW 3 computes local timescale adaptations by interval-based correlation maximization. Within a fixed range, all possible shifts are tested around either 551 discretely sampled or manually selected retention times to find the best match. A crucial alignment choice of both PTW and COW is the alignment target: all chromatograms need a common reference signal by means of which they become intercomparable. Possible choices of such a prototypic reference signal are the average (mean) chromatogram values or the medians at each time point. The alignment quality is very important, because the subsequent steps, biomarker identification and clustering, are based solely upon the preprocessed data. 3. Biomarker extraction is an optional step after alignment for the identification of retention times that are characteristic of the data set. Unsupervised feature selection (FUSE) is proposed which, in an exhaustive manner, iteratively isolates those retention times i that do maximum dis-correlate the original chromatogram distance matrix D and the time-reduced distance matrix DsS(k) = arg min v2{D, Z? S (*-i)ui), i G ( 1 . . . T)\S{k - l ) , f c = l . . . T - l i S(k) is the growing set of index pointers to retention times which have been isolated until iteration number k; by definition 5(0) := {}, and by construction \S(k)\ = k. £>s(k-i)ui 1S the distance matrix calculated using the chromatogram vectors, thereby skipping the time indices given in set S(k — 1) U i. The total number of retention times is T = 3000 in the present study; in larger applications early stopping can be considered if the remaining squared correlation r2 drops below a critical near-zero threshold or when reaching a plateau. FUSE is analogous to sensitivity analysis of system input response. The reference inter-relationships of preprocessed source chromatograms are calculated once as distance matrix D and compared with the simplified models reflected by Ds- Thereby, matrix entries in D and Ds are not necessarily Euclidean distances. They may denote any reasonable similarity measure between input chromatograms and their time-reduced counterparts. FUSE is thus more than mere variance analysis of T independent time slots or difficult-to-interpret PCA-loading factor analysis. For example, the variance of components might be high just due to noise without contributing fruitfully to the reconstruction of original data relationships. To summarize, the indices S(k) from FUSE denote in descending manner the relevance of data components for faithful relationship reconstruction. Particularly, these biomarkers represent intuitive components responsible for systematic differences between the source vectors. 4- Visual clustering is the last step of the data processing pipeline to view inter-relationships of aligned chromatograms and their biomarker representations. This helps to find groups of tomatoes with similar chemical 552 compounds and it helps to identify outliers with specific substance combinations. Principal component analysis (PCA) is the standard visual clustering method for inspecting data proximities by projecting chromatogram vectors onto the two axes of maximum variance. PCA, however, is a linear approach with implicit assumption of a Euclidean input space. Moreover, as mentioned before, the axes of maximum variance are not necessarily the axes of maximum interest. The general multi-dimensional scaling (MDS) methodology aims at distance-preserving reconstruction of source data in a low-dimensional space. High-throughput multidimensional scaling (HiTMDS) is a highly optimized realization of MDS, specifically designed for dealing with very high-dimensional data 4 . Analogous to the biomarker detection approach, the optimization goal of HiT-MDS is to find positions of points in low-dimensional, interpretable Euclidean space in such a way that the matrix of their mutual distances is maximum correlated with the original data distance matrix. HiT-MDS iteratively improves the locations of randomly initialized points by update rules derived from an efficient dis-correlation stress minimization criterion. 3. Results Data screening of the 280nm-chromatograms is obtained by pseudo-gelplots of the raw data. The top panel of Fig. 2 displays in their recording order the 55 unprocessed experiments. Three groups are visually identified, experiments 1-19, 20-41, and 42-55. The first group 1-19, separated by the solid horizontal line, is one entire set of continuous HPLC recordings. Experiments 20-55, also continuously taken, were conducted one month later for testing and validation purposes. Runs 20-41 exhibit systematic recording artefacts between 250s and 500s, but a recalibration phase in the late stage of record 41 leads to a recovery of the measuring process for the subsequent runs, starting with the dashed horizontal line. 1. Baseline correction is obtained with the QuantileSpline method. The time frame size is fixed to 50s, providing a number of 3000/50=60 base points for the interpolating spline. A quantile value of q = 15% is chosen. The setting of the quantile value and the window width is determined by visual validation of the background curve and the source data under the constraints of average peak width and avoidance of too many negative baseline-corrected target points. A data example with its corresponding baseline is given in Fig. 3 for the focus of interest between 500s and 2750s: the baseline smoothly follows the original signal without interfering with the time scale of the retention dynamic. Thus, the summation of peak areas of baseline-corrected chromatograms provides more comparable standards. Raw Data 1 5? 10 15 20 E 2530 ' 1 • i I j 1 I I • 1 i > i " • 35 [ 40t_. 45i * i . J i __ 1 50 1 1 - • . . _ ! . -; ; 1 , ', , 1 500 1000 '. 1 i 1500 2000 retention time (s] i 2500 3000 PTW-aligned Data , ; r I I .'• j , .,...| J ' - i t i : I'I , 500 I, 1000 , I i . .; ,. , • !• : • 'i l 1500 2000 retention time [s] ' ! . _ ) 1 f* 2500 3000 2500 3000 COW-aligned Data 5 10 . 15 r 500 1000 1500 2000 retention time [s] Figure 2. Pseudo-gelplots of tomato chromatograms at 280nm. Dark bands denote high substance concentrations. Top panel: raw data; as indicated by horizontal lines, the 55 experiments fall into three temporal categories, records 1-19, 20-41, and 42-55. Two bottom panels: plots for aligned chromatograms from PTW and COW; they are already baseline corrected. 2. Chromatogram alignment is studied for PTW and COW. When all 55 experiments are processed at once, PTW produces alignments of substantially worse quality than COW. The reason for this are the three temporal groups of chromatograms identified visually: they constitute a data set too heterogeneous for the quadratic warping model. Once the three groups are independently processed, much better alignments are obtained for PTW and COW. Further considerations focus on the first group of runs 1-19, because they are supposed to contain the most trustworthy data. Alignments are shown in the two bottom panels of Fig. 2 for PTW and COW. As can be seen, the bands of the aligned chromatograms are significantly straightened in comparison to the raw data in the the upper panel above the Chromatogram Baseline Correction reference signal spline base points baseline • «»(• • • » nJ\n, 500 750 1000 1250 1500 1750 retention time [s] 2000 2250 2500 . » 2750 Figure 3. Chromatogram baseline determination as spline interpolation of 15%-quantile of 50s-time-windows. solid line. For these results, biological knowledge has been used in COW to roughly specify 39 intervals of retention times with potentially interesting substances - for these manually set focuses the correlation is maximized, whereby the search is restricted to empirically determined maximum shifts of 20s. Conveniently, PTW does not require further parameter choices. However, for both PTW and COW the alignment reference must be given. Although the differences are small, the mean chromatogram generally performs better than the median signal. This has been confirmed for all three groups. Comparing the alignment quality of PTW and COW it turns out that, for the favored mean-alignment, PTW shows higher squared deviations from the reference and lower correlation values than COW in all three cases. To conclude, COW takes more calculation time, but it yields the best overall alignment quality. Apart from one obvious COW-misalignment for experiment 17 at 1600s, this result is visually confirmed by close inspection of the two bottom panels in Fig. 2. Biomarker Identification (FUSE) 1 la...A...4iljJ.i.l'oifiLiili].k^JJi.Ul'i.>-. 0.8 0.6 8 I •£-. •{. 0.4 0.2 500 750 1000 1250 1500 1750 retention time [s] 2000 2250 2500 2750 Figure 4. Biomarker extraction. Dots are feature ranks 1-3000 scaled to [0;1]. Upper line connects 20% top most discriminative retention times. Vertical lines refer to equivalent view on corresponding correlation loss of r 2 e [0; 1] during feature exclusion. 555 3. Biomarker extraction is an optional step after alignment. The goal is to reduce the overall data complexity to only relevant retention time intervals. By focusing on the most discriminative features of the data set according to the FUSE protocol, the noise influence of unimportant components is discarded. For the chromatograms X\,.,\§ of runs 1-19 FUSE has been calculated for Pearson similarity with matrix entries D{j = 1 — r(xi,Xj), and Dij = 1 — r(ii,Xj) for the time-dropped chromatogram vectors. This yields Fig. 4, zooming on an interesting time interval. Vertical lines correspond to the correlation loss r2(D, Ds(k-i)vi) during successive time point dropping. The dashed horizontal line separates 600, i.e. 20%, top ranked, most discriminative retention times from the less important features (dots). As expected, these feature ranks and the correlation loss are highly correlated. The top-rated retention times are of high biochemical interest for the characterization of the tomato plant compounds. 4- Visual clustering is the last step of the data processing pipeline to inspect relationships between the tomato lines. Since peak areas are proportional to compound concentrations, integral differences, i.e. Manhattan Lldistances, of chromatograms provide particularly meaningful comparisons. These distances of peak-aligned data are used for 2D-embeddings by HiTMDS of the 3000-dimensional chromatograms and of the 600-dimensional biomarkers obtained by FUSE. Figure 5 displays the visualization results. Within each plot, two visual clusters can be identified, as well as the clear outliers 6, 16, 18, and 19. The elliptic cluster corresponds to tomato lines with specifically high compound concentrations at 7805 and 9605, the circular cluster comprises tomatoes with more subtle differences, but with a tendency to higher rutin concentrations. In a chromatogram overlay, outlier 16 matches pretty well the circular group, except for an exceptionally high rutin level, which is one of the desired compounds in the study. Runs 6, 18, and 19 have more complex structure and show up as outliers. The high similarity of both panels in Fig. 5 must be pointed out: although the biomarker embedding uses only 20% of the original chromatogram length, the results are essentially the same. Since FUSE and HiT-MDS are founded on the same principles, i.e. the consideration of correlation between the original data and the dimension-reduced models, such result is expected. 4. Conclusions a n d future directions HPLC signals of probes from tomato peels have been successfully analyzed by means of a d a t a processing pipeline with the stages QuantileSpline-baseline correction, chromatogram alignment to the chromatograms' mean signal, optional FUSE biomarker identification, and HiT-MDS-based HiT-MDS full chromatogram clustering HiT-MDS chromatogram subspace clustering 19 1 19 16 /Ti\ r 16 /14S ,I /7~^\ 7 0 5 "1 \_y 1 17 1 - 1 Figure 5. 0 i 6 1 2 embedding axis 1 6 16 17 18 3 - 1 0 1 2 embedding axis 1 3 Chromatogram and biomarker embedding by HiT-MDS and Ll-distance. chromatogram and biomarker embedding. The obtained results help significantly to focus on experiment outliers and groups of experiments as well as on relevant retention time intervals. The processing pipeline points out an important direction t o semi-automatic chromatogram processing, especially interesting for handling massive data sets. Future research will focus on improving the alignment procedure by reducing free parameters in COW and by enabling reiteration, i.e. by realignment of already aligned data to the recomputed mean signal. FUSE biomarker detection shows promising results, but is yet only at its starting point. Subsequent experiments are necessary to fully assess the power of this method. Finally, the visual arrangement after embedding is not only determined by the signal alignment quality, but also essentially by the underlying similarity measure for signal comparison. Therefore, meaningful measures must be reconsidered, which is a crucial topic already for most alignment procedures. Taking these issues into account, the presented pipeline can be canonically extended for dealing with mass spectra, which is subject to future investigations. References 1. V. Pravdova, B. Walczak, and D.L. Massart, "A comparison of two algorithms for warping of analytical signals", Analytica Chimica Acta 456, Issue 1, pp. 77-92, 2002 2. Paul H.C. Eilers, "Parametric time warping", Analytical Chemistry 76, Issue 2, pp. 404-411, 2004 3. N.V. Nielsen, J.M. Carstensen, J. Smedsgaard, "Aligning of single and multiple wavelength chromatographic profiles for chemometric data analysis using correlation optimised warping", J. of Chromatography A 805, pp. 17-35, 1998 4. M. Strickert, S. Teichmann, N. Sreenivasulu, and U. Seiffert, "HighThroughput Multi-Dimensional Scaling (HiT-MDS) for cDNA-Array Expression Data", in W. Duch et al. (Eds.): Artificial Neural Networks: Biological Inspirations, LNCS 3696, pp. 625-634, Springer, 2005 FEATURE SCORING BY MUTUAL INFORMATION FOR CLASSIFICATION OF MASS SPECTRA C. KRIER 1 , D. FRANCOIS 2 , V. WERTZ 2 , M. VERLEYSEN 1 Universite catholique de Louvain, Machine Learning Group DICE, Place du Levant 3, B-1348 Louvain-la-Neuve, Belgium fkrier, verleysenj @ dice. ucl. ac. be 2 CESAME Research Center, Av. G. Lemaitre 4, B-1348 Louvain-la-Neuve, (francois, wertz}@inma.ucl.ac.be 1 Belgium Selecting relevant features in mass spectra analysis is important both for classification and search for causality. In this paper, it is shown how using mutual information can help answering to both objectives, in a model-free nonlinear way. A combination of ranking and forward selection makes it possible to select several feature groups that may lead to similar classification performances, but that may lead to different results when evaluated from an interpretability perspective. 1. Introduction Mass spectrometry allows identifying chemicals in a substance by their mass and charge. It produces spectra that plot the quantity of chemicals in the substance as a function of their mass to charge ratio (m/z). Typically, several thousands m/z values are considered. Such spectra are said to be high-dimensional. For illustration purposes, the detection of cancer will be considered. The interesting question for researchers is of course which chemicals are involved in the process and which biomolecules are affected by the disease process. Two objectives are thus sought together: classification performances should be high, and the method should identify which chemicals are affected. Focusing only on features (m/z) that allow building an efficient classification model is not sufficient; indeed several sets of features could lead to similar classification performances, while one set could be of much greater interest for causality interpretability than the other ones. Another way of identifying relevant features is to examine the statistical dependency between each of them (taken individually) and the class label. While the statistical dependency concept does not make any assumption on the model that is further used for classification, it will discard features that are only relevant in a group, and not individually. 557 558 In this paper, we suggest to overcome these limitations by using the mutual information measure between features and the class label. Mutual information is a nonparametric, model-free method for scoring a set of features. It can be used to spot all features relevant to the classification, and to identify groups of features that allow building a valid classification model. It is applied to the detection of ovarian cancer through spectra of human serum. The process allows identifying feature sets that can be later assessed from a clinical perspective. The paper is organized as follows: Section 2 reviews the existing literature, Section 3 introduces the concept of the mutual information. Section 4 proposes some experiments with the Ovarian Cancer dataset and Section 5 concludes. 2. Previous work Several mass spectrometry classification algorithms have been proposed in the literature [1, 2, 3]; yet only a few studies focus on feature selection. In a comparative study, Liu [4] considers the Chi-squared test and the t-test, making the assumption that the class populations are normal-distributed. He furthermore uses an entropy-based method, considering the mutual information between pairs of features, and between each feature and the class label. Those methods will however eliminate features relevant only in conjunction with each other. Petricoin uses a Genetic algorithm [5] prior to probabilistic classification. This allows to find an (sub-)optimal feature subset, but fails at scoring each feature individually. The method may thus find a set of features adequate for classification, but not all sets that could be of interest. Furthermore, the procedure is model-dependent and prone to convergence issues. Lilien [6] proposes the use of the Linear Discriminant Analysis, and Back Projection to score the features. The LDA results in a discriminant vector that is then normalized according to the initial features variances. The score associated to each feature is the corresponding element in the normalized discriminant vector. The classification model is thus constructed on all features; therefore, a lot of poorly scored (by the LDA criterion) features may have the same weight in the classification process as a single high-scoring feature. Here again, two features that are relevant only when paired will not be identified as such. In the following section, we will see that the mutual information allows scoring groups of features, independently from a subsequent classification model, and without making any assumptions about the class sample distributions. 3. The mutual information The mutual information (MI) between two random variables or random vectors measures the "amount of information", i.e. the "loss of uncertainty" that one can bring to the knowledge of the other, and vice versa. 3.1. Definition of the mutual information The concept of uncertainty of a random variable is expressed by its entropy [7]. Although the notion of entropy has first been developed for discrete variables, it can be extended to continuous variables rather easily. The entropy H(Y) of a random variable Y with probability density function (pdf) juY is defined by H{Y) = -\nY{y)\ognY{y)dy. (1) The entropy of a random variable or vector Y when the value of some other random variable X is known is the conditional entropy: H(Y\ X)=-\Mx(x) \nY{y\X^x)\ogMY{y\X=x)dydx. (2) The mutual information is the difference between the entropy of a variable and the conditional entropy I(X, Y) = H(Y) - H(Y\X). The mutual information can be expressed as the Kullback-Leibler divergence between the joint distribution fix.y of the variables and the product of the marginal distributions fix and / ^^'^dbcdy . (3) When X and Y are independent, the mutual information is zero; the higher the dependency between variables X and Y, the higher is their mutual information. Contrarily to the correlation, the mutual information measures any relationship between variables, and not only linear relations. In the above equations, X and Y can be random vectors instead of random variables. If Y is a binary class label, definition (3) holds. Its extension to multi-class problem is not obvious though, as an adequate class labeling has to be provided. 3.2. Estimation Equations (1) to (3) are not applicable as such, as the pdf are not known in practice. The estimation of the mutual information given finite samples is thus a problem of density estimation. Density estimation can be achieved in several ways [8], for instance with histograms, kernels, B-splines, or Nearest 560 Neighbours. The latter has the major advantage to be reasonably efficient for the estimation of a multivariate density (when a random vector is involved), while the other ones suffer more dramatically from the 'curse of dimensionality' (the required number of samples needed for the estimation grows exponentially with the dimension of the random vector). There exists an extensive literature on density-based entropy estimators [9, 10]; recently, they have been extended to the Mutual Information by Kraskov et al [11]. The latter estimator is used in the experimental part of this paper. 3.3. Using the mutual information for feature scoring/selection A high mutual information between a feature X and the class label Y thus means that feature X is relevant, regardless of the classification algorithm. However, the mutual information can be used in several ways to select (sets of) features. First, the mutual information scores can be estimated between each feature individually (m/z) and the class label. The highest scores correspond to features that are most relevant in discriminating between the two classes. In contrast, the features with a mutual information near zero are statistically independent from the class label. The drawback of this method is that features that are relevant together but useless individually cannot be accurately spotted. Secondly, the mutual information can be used to search for the optimal feature subset (which may or may not be the subset of optimal features) in a forward manner: the feature with the highest mutual information with the class label is chosen first. Then, pairs of features containing the already selected one and any remaining one are built. The mutual information between each of these pairs and the class label are measured; the second chosen feature is the one contained in the pair with the highest mutual information score. The procedure is then iterated until the adequate number of features has been reached. Although this procedure, which is greedy in the sense that the choice of a feature is never questioned afterwards, can lead to a sub-optimal feature subset, it performs most often efficiently, and definitely better than the previous option. While the second procedure is good at identifying the most relevant subset, it will probably not select all features that could be relevant for the problem, as redundancy between features is avoided. Both procedures have advantages; therefore, in order to identify all features relevant as well individually as in conjunction with others, they are merged into a single one, inspired from [12]: 1. N features are selected by individual mutual information 2. M features are selected by the forward procedure 3. All 2N+M possible feature subsets are constructed and their mutual information with the class label is estimated. 561 The subset with the highest mutual information can be chosen for classification purposes; however, all other subsets associated to a high value of the mutual information with the class label can be considered as relevant for the problem too. In this way, several subsets of features can be identified, hopefully allowing spotting all features relevant to the problem, either individually or in conjunction with others. The subsets can thus be ranked and further applicationdependent investigations performed. The values of N and M should be chosen as high as possible, while keeping the 2N+M MI estimations tractable. Despite the fact that the complexity of the method is proportional to the square of the number of features in the worst case, the average number of computations is linear with the number of features. In practice, the computation of all MI values does not exceed a few tenth of minutes on a standard computer if, as an example, N+M is limited to 7. Furthermore, the whole variables selection process can be performed off-line, as it does not need to be repeated to classify a new sample. 4. Example The method is illustrated on an ovarian cancer dataset from the Clinical Proteomics Program of the U.S. National Cancer Institute [13]. The spectra result from SELDI-TOF experiments. The healthy samples come from women showing risks of cancer from a clinical perspective, while the positive cancer samples come from women with various tumors types and severity (see [5] for details.) To get a tractable number of feature subsets to assess, three features were chosen by the forward selection method; then, four other ones were chosen among the highest scored features not already selected. To assess the relevance of the selected features, a linear classification is performed on a test set, as in [6]. 4.1. Results Figure 1 shows the mutual information score for each m/z value. The vertical lines indicate which features were chosen by the forward strategy and not by the ranking procedure (in this case, the m/z ratios 2.7921 and 24.2851). Few features have really high mutual information scores. Note that negative values are obviously the result of the estimates bias (without consequence on the ranking) and variance (that gives an idea of the estimator accuracy). The final set of selected features is given in Table 1, with the corresponding m/z values. Feature 1679 has the highest mutual information with the class label. The features selected by the ranking method are obviously highly correlated; nevertheless, we will see that they are not totally equivalent for classification. 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 m/z Figure 1. Mutual information for each m/z feature. Table I. The seven selected features, along with their corresponding m/z values. An O in regard of the name of a method indicates that the feature was selected by the method. Feature 181 530 1678 1679 1680 1681 1682 m/z 2.7927 24.2851 244.6604 244.9525 245.2447 245.5370 245.8296 Forward O O O Ranking O O O O O The mutual information of each possible of the 128 feature subsets is given in Figure 2, along with the performances of a linear classifier built using that subset. The feature groups are ordered by increasing mutual information. Table 2 presents some of those feature groups. Figure 2 confirms that the classification performances are highly correlated to the mutual information (0.9041). O 20 40 60 group ID 80 100 120 Figure 2. The mutual information and classification performances for a linear classifier built on every possible subset of the selected features. 4.2. Discussion From the analysis of Table 2, it appears that: • The group of features achieving the best classification is not the group of most individually relevant features nor it is the group identified by the 2. Some values from Figure 2. Group Feature group ID 181 126 127 530 1678 118 113 530 ;1678 38 181 ; 530 ; 1678 1 181; 1678; 1679; 1680; 1682 33 181; 530; 1678; 1679; 1680; 1682;1681 1678;1679; 1680;1681;1682 59 34 181; 530; 1680 1678 ; 1679 35 • • • • Mutual information 0.3694 -0.0349 0.3694 0.5644 0.6571 0.7026 0.6585 0.6347 0.6583 0.6581 % Correct classification 74.86 58.00 75.86 90.00 100.00 98.43 98.43 95.31 98.43 95.23 forward procedure. Group 38 is the best group and contains only one of the highest-ranked features. Furthermore, the group discovered by the forward procedure achieves less good classification performances; this is because the choice of the first feature was never questioned. Using a forward or ranking procedure alone does not lead to the optimal feature subset. Some individually less relevant features help building more accurate classifiers than if using individually relevant features only. Features 530 (Group 127 - low MI) 1678 together reach 90% of correct classification (Group 113), while feature 1678 (Group 118) classifies only 76% of the samples correctly. It can thus be assumed that feature 530 is involved in the process. Only ranking features may prevent from spotting relevant ones. There are groups of different features that achieve very similar results. For example Groups 34 and 35 share no variable, although their classification performances (95 and 98 %) are rather close. Simply relying on the best feature subset according to the mutual information or to some model-based algorithm does not allow recovering all features involved in the process. The performances in classification reached by the method are similar to the results obtained by Lilen with LDA and Back Projection [6]. In this problem, it appears that only features with low m/z ratio are relevant. 5. Conclusion This paper shows that using the mutual information between features and class label in mass spectra analysis help choosing relevant feature sets. The method based on the combination of feature ranking and forward selection, and using mutual information on sets of features rather than individually, makes it possible to rank feature subsets. Then, an application-driven procedure can be used to assess the (clinical in this example) relevance of the feature sets, starting from the highest-ranked ones by the proposed procedure. Acknowledgments M. Verleysen is Research Director of the Belgian FNRS. C. Krier and D. Francois are funded by a Belgian FRIA grant. Parts of this research results from the Belgian Program on Interuniversity Attraction Poles, initiated by the Belgian Federal Science Policy Office. The scientific responsibility rests with its authors. References 1. BL. Adam et al., Serum protein fingerprinting coupled with a patternmatching algorithm distinguishes prostate cancer from benign prostate hyperplasia and healthy men, Cancer Research, 62, 3609 (2002). 2. G. Ball et al., An integrated approach utilizing artificial neural networks and SELDI mass spectrometry for the classification of human tumours and rapid identification of potential biomarkers. Bioinformatics, 18,395 (2002). 3. H. Zhou et al., Quantitative proteome analysis by solid-phase isotope tagging and mass spectrometry, Nature Biotechnology, 20, 512 (2002). 4. H. Liu, J. Li and L. Wong., A Comparative Study on Feature Selection and Classication Methods Using Gene Expression Proles and Proteomic Patterns, Genome Informatics 13, 51 (2002) 5. E. Petricoin III et al., Use of proteomic patterns in serum to identify ovarian cancer, The Lancet, 359 572 (2002) 6. R. H. Lilien, H. Farin, B. R. Donald, Probabilistic Disease Classification of Expression-Dependent Proteomic data from Mass Spectrometry of Human Serum, Journal of Computational Biology 10(6), 925 (2003). 7. C.E. Shannon, W. Weaver, The Mathematical Theory of Communication, University of Illinois Press, Urbana, IL, 1949. 8. D.W. Scott, Multivariate Density Estimation: Theory, Practice, and Visualization, Wiley, New-York, 1992. 9. R.L. Dobrushin, A simplified method of experimental evaluation of the entropy of stationary sequence, Theory Prob. Appl. 3(4), 462 (1958). 10. O. Vasicek, Test for normality based on sample entropy, J. Royal Statist. Soc. B38, 54 (1976). 11. A. Kraskov, H. Stogbauer, P. Grassberger, Estimating mutual information, Phys. Rev. E69:066138 (2004). 12. F. Rossi, A. Lendasse, D. Francois, V. Wertz, M. Verleysen, Mutual information for the selection of relevant variables in spectrometric nonlinear modeling, Chemometrics & Intelligent Lab. Systems, 80, 215-226 (2006). 13. http://home.ccr.cancer.gov/ncifdaproteomics/ppatterns.asp PEAK INTENSITY PREDICTION FOR P M F MASS SPECTRA USING SUPPORT VECTOR REGRESSION W. TIMM 1 ' 2 - 3 , S. BOCKER 2 , T. TWELLMANN 3 , T. W. NATTKEMPER 3 1. International NRW Graduate School in Bioinformatics and Genome Research 2. Junior Research Group Informatics for Mass Spectrometry, Genome Informatics Group, Faculty of Technology 3. Applied Neuroinformatics Group, Faculty of Technology Bielefeld University, Postfach 100131, 33501 Bielefeld, Germany E-mail: wtimm 1. I n t r o d u c t i o n Mass spectrometry has become the method of choice to analyze the proteome of a cell. One widely-used approach is based on separating proteins via two dimensional electrophoresis, then digesting each protein using an endopeptidase such as trypsin, and finally analyzing the peptide mixture by MALDI-TOF mass spectrometry. Proteins are identified by comparison of the resulting protein mass fingerprints (PMFs) with those in a database of known proteins. W i t h the increasing amount of d a t a produced in this area, automated approaches for reliable protein identification are highly desirable. Shadforth et al.1 give an overview of currently available techniques. The most established programs for this purpose are ProFound 2 565 566 and MASCOT 3 . These query tools require human interaction to evaluate the identification results, which significantly slows down the process of analyzing whole proteomes. In P M F analysis, cleaved peptides stay intact during MS analysis and are only detected if they are ionized. During such an experiment, not only peak masses, but also their intensities (peak height, area under curve) can be assessed. However, current analysis tools for P M F d a t a usually only take a list of peak masses as input. If peptides are ionized all alike and the digestion procedure works perfectly, peaks of equal intensity can be found at all peptide masses, taking into account multiplicities of peptides in a protein. In reality, this is not the case: Due to the variety of ionization processes, and unequal specificity of trypsin for different amino acids, peak intensities can vary significantly. Models have been proposed for these processes 4 ' 5 , but currently these models do not allow to precisely predict peak intensities. Elias et al.6 show that the use of peak intensities enhances the reliability of protein identification for tandem mass spectra. It is reasonable to assume the same to be true for P M F spectra. As noted above, software for P M F interpretation usually ignores intensity information. Modeling of intensities in tandem mass spectra has been dealt with by multiple authors 7 ' 8 , 9 , 1 0 . Such models mainly consider the fragmentation probabilities of molecules. For MALDI P M F spectra, where molecules stay intact in the analysis procedure and the intensities highly depend on the ionization probability of the molecules, Gay et al.n applied a number of different regression and classification methods. They found the M5' decision tree algorithm to perform best among the regression methods tested and derived a few rules regarding the influence of the occurrence frequencies of some amino acids on the peak intensities. 2. Goal The goal of this work is to examine approaches for predicting the intensities of peaks from measured protein MALDI-TOF mass spectra using a numerical representation of the peptide sequences of theoretically cleaved proteins. In a first step towards a solution of this problem, our question is whether this string representation enables us to find a correlation between the peptide sequence and its peak intensity. In the long run, the prediction of intensities should enhance the reliability of protein identification results by calculating more realistic theoretical spectra. 567 For the experiments as presented in this work, we assumed that the peak intensities are reproducible under the same experimental conditions. This assumption is supported by the work of Coombes et al.12 who found peak intensities of multiple experiments under the same conditions with proteins from the same sample to be highly correlated. Another assumption we make is that the intensities only depend on the corresponding peptide's sequence. This means that interactions between peptides inside the device are neglected. Also, the effect of incomplete cleavage is not considered. 3. Materials and methods 3.1. Data The experimental spectra were taken from biological studies on Corynnebacterium glutamicum which involved 2D-PAGE experiments with subsequent tryptic digestion and measurement in a Bruker Ultraflex device. The whole data consists of 369 raw spectra of which 20% (66) were selected belonging to 43 different proteins. These were identified by MASCOT3 with the highest distance to the score of the second-best match. The minimal score of the selected spectra is 66 and the minimal distance 37. In the further process the MASCOT identification is taken to be true. Based on this identification, theoretical tryptic digestion was performed to determine the theoretical peptides. The masses of these peptides lead to theoretical peak lists that are then used to retrieve the corresponding peaks from the preprocessed raw spectra. The preprocessing involves denoising, baseline correction, peak detection, filtering of peaks, and deconvolution (de-isotoping). If a peak is found within 1.2 Da a of the mass of a theoretical peptide, it is declared a match. For each match, the amino acid sequence and the intensity before and after the deconvolution step are taken. The extracted peaks form an initial set. All sequences from this set are embedded into a vectorial feature space to allow for processing by a machine learning algorithm. The transformation and algorithms used are described in the Techniques section (3.2) below. Three data sets were compiled from the initial set. The set r > 8 0 o includes all peaks with a mass above 800 Da, a match accuracy (distance between theoretical and real peak's mass) of at most 1.0 Da, and the intensities from the deconvoluted spectra as target values. The set TQ+ consists a In MALDI experiments, usually only singly charged ions are observed. Therefor, when "Da" or "mass" is written in this paper, "Da/z" or "mass per charge" is meant and would be more accurate, but the difference is not important for our application. 568 of the same peaks as the set r>8oo> but additionally includes peaks with masses below 800 Da because of the low signal-to-noise ratio in that range. The r n ( j set consists of the same peaks as the set r>soo but intensities before deconvolution were used as target values instead. All peak intensities are scaled according to Is = = ^ — ^ - — — . Here, Is is the s |