An Inter est-based Offer Evaluation System for Semantic Matchmaker s SamiraSadaoui sadaouis@uregina.ca Computer Science Department University of Regina
S4S 0A2 Regina SK Canada
WeiJiang jiang20w@uregina.ca Computer Science Department University of Regina
S4S 0A2 Regina SK Canada
An Inter est-based Offer Evaluation System for Semantic Matchmaker s 5DADB6A63CC1DB525071A2C9253B955D GROBID - A machine learning software for extracting information from scholarly documents

Abstr act. Matchmaking systems failed to provide the best matched results to individuals. Semantic matchmaking can help the buyer find the requested offers but it is not good enough to find the best offer. In this work, we propose a system that evaluates and sorts the request-matched offers according to the buyers' interests and tastes. To evaluate the offers, we modify the MultiNomial Logit model to produce an interest model that analyzes individual's interests and favors. Our system captures the buyer's interests, builds his interest model, and then returns the best offer. The best offer denotes the highest interest value to the buyer. Through a case study, we present in detail the phases of our offer evaluation process.

Keywor ds: Interest model, multiple offer attributes, best matched offer, Self Organizing Map (SOM), MultiNomial Logit (MNL).

Intr oduction

Matchmaking is the online process through which buyers and sellers trade goods or services. Most of the matchmaking systems are semantic-based. Research on ontology lead the early semantic matchmaking systems to understand and process the purchasing requests much better [1, 2, 3]. Nevertheless, with the blooming of ecommerce and e-services, buyers can obtain more and more request-matched offers. It is really time consuming for buyers to browse, evaluate and sort all the candidate offers in order to find the best offer. Today determining the best offer is more important than before for any matchmaker. Recent matchmakers are trying to determine the best offer by using the semantic ranking [4,5,6,7,8]. Most semantic ranking algorithms examine the similarity of inputs, outputs, preconditions and effects. Yet all existing matchmakers failed to bring the best matched results to individuals. Indeed, they do no guarantee that the best offer will be purchased by the buyer since his specific interests and tastes are ignored. Without studying human interests and only relaying on the semantic matching and ranking, matchmakers cannot recognize the differences between buyers' favors and needs.

Researchers realized that a better matchmaking system "could quicken the trend toward personalization" [9]. Matchmaking based on semantic can help the buyer find

the requested offers but it is not good enough to find the best offer. Consequently, we develop a system that evaluates and sorts the request-matched offers according to the buyers' specific interests and tastes. In our system, the best offer denotes the highest interest value to the buyer. Analyzing individual interests along with the semantic matching brings better results to each individual buyer. As illustrated in Figure 1, first the buyer submits to our system a purchasing request which is then sent to a connected semantic matchmaker. The latter returns a list of request-matched offers.

To sort these offers according to the buyer's interests, our system performs the following tasks: cluster the values of each offer attribute, interact with the buyer to take into account his interests and tastes, calculate the attribute's interest weight and interest rate, build the interest model based on interest weights and rates, evaluate and sort the offers according to the buyer's interest model.

Fig. 1. System Process Overview

In order to take into account individual's interests, we need to utilize the clustering technology called Self Organizing Map (SOM) [10,11]. As a neural-network approach, SOM is employed to cluster high-dimensional inputs onto lowerdimensional outputs. The reason of using SOM in our work is that the offer attributes may be complex or contain high-dimensional data, such as the attributes of our case study. Furthermore, to define the interest model specifically for each buyer, we modify the MultiNomial Logit (MNL) model [12]. MNL is widely used in commerce to study human shopping behaviors [13]. Nevertheless, MNL suggests a model for a group of people and needs an appropriate sample data. The good thing is that we are able to modify MNL to analyze individual's needs alone and without considering a sample data.

Related Work

In the early time of e-commerce, matchmakers focused on mapping the offer attribute values [14]. Requests and offers can be expressed in different schemas and words even when representing the same semantic meaning. This causes matchmakers to be blind to some potential offers. To solve this problem several semantic matching models, based on ontological technologies, have been proposed [1,2,3]. In [1], matching the offers is based on the similarity of the request and services. [2] uses logical relationships to map the offers with the request. [3] focuses on the semantic matching using a platform-independent framework called UDDI. These matchmakers return an unranked list of offers.

To find the best offer, recent matchmakers evaluate service description [4,5], service constraints [6], service process [7] or both [8]. The best offer denotes the highest semantic matching degree. These matchmakers map the functional properties of offers with the request's functional description. However, these matchmakers cannot explain why sometimes a buyer prefers an offer different from the returned best offer. To address this issue, non-functional matching methods [15,16] have been introduced by following a matching standard like Qos [17]. These papers argue that the buyer's choice is caused by other criteria often referred to as non-functional properties.

All these matchmakers are based on matching the query words but not on matching individual's interests. Our goal is to build the interest model specifically for the buyer and then find the best matched offer which is the closest to the buyer's real needs.

An Example

Our case study consists of purchasing computers based on 2-dimensional attributes: CPU and Price. We have here a company which submits the following inventory query:

Request computers with CPU ＞ 1.5 GHz, Price < $3500 for the first ten purchased computers, and Price ＜ $3000 for the next ten.

To formulate the requests and offers, matchmakers utilize well known web service languages, such as WSDL, SWSL and WSML, which offer a high degree of flexibility and expressiveness. Thus, we translate the purchasing request to for example WSDL following the structure defined in [18] (cf. Figure 2). We assume the connected semantic matchmaker returns the candidate offers given in Table 1 where CPU contains high dimensional values and Price has two ranges.

In the next phases, our system will evaluate all the candidate offers of Table 1 in order to help the company find the best supplier which might become its long-term business partner. 4 Attr ibute Data Cluster ing

Our system first determines all the attributes from the purchasing request. For each attribute, it extracts all its values from the candidate offers and stores them in a single table . Our system can now cluster the values of each attribute. The purpose of this clustering is to be able to take into account the buyer's interests. So the buyer can select one of the clustering to represent his most interested area. In Figure 3, we define the clustering function called ClusterAttributeData() which is based on the algorithm Self Organizing Map (SOM) [11] given in Figure 4.

We apply SOM to recursively divide a large clustering into three sub-clustering until there are less data in the clustering. During the learning time, a set of Learning Vector Quantizations (LVQs) is tuned towards the input attribute data. SOM applies competitive-learning given in the steps 3.1.1 and 3.1.2 of Figure 4. In SOM function: t is the learning time; CreateLVQ() is a function that generates three random LVQ m i in the range of DataAttribute; alpha (t) controls the learning loop and is the learning rate function which is decreased by learning time t; m c is the closest LVQ to the selected data x; h ci () is the "neighborhood" function that updates LVQ in the learning time [11].

void{ 3.1.1 ||x -m c || = min{||x -m i ||}; //Find closest LVQ m c 3.1.2 m i (t+1) = m i (t) + h ci (t)[x(t)-m i (t)];

//Update mi during learning } 3.2 t = t+1;//Update time }} Our system displays the CPU and Price clustering to the company. The latter can now select the most interested clustering for each attribute. These selections are performed through the GUI of Figure 11. With these selections, our system knows the range and depth of the company's needs. The selection information, representing the company's purchasing interests, will help the system to create the interest model in the following phases. 4 Inter est Weight Computation An interest weight denotes the degree of importance of an attribute in a matching. It is related to the depth and range of the buyer's selection. The smallest and deepest clustering shows the best interest of the buyer. In order to produce the attribute's weight, we use the interest-weight coefficient which contains the buyer's interest in one attribute. We create Formula (1) to compute the interest-weight coefficient of an attribute called k: K is the attribute set, DataAttribute is the data range of k, SelectedClustering is the buyer's selected clustering for k, SelectedLevelTree is the selected clustering level, and TotalLevelTree is the number of levels of the clustering tree.

K k Tree TotalLevel velTree SelectedLe ustering SelectedCl ute DataAttrib coe IW k k k k k ∈ ⋅ = _ (1)

This coefficient has to be compared with the other attributes' coefficients (cf. Formula (2)). An attribute with a larger interest weight coefficient gets a larger interest weight compared to the other attributes. This means we can finally link the interest weights with the buyer's selection.

K k coe IW coe IW IW K k k k k ∈ = ∑ =1 _ _ (2)

Example. We suppose the company chooses the CPU clustering [2.2, 2.5]. This selection is at level 2 of the 5-level CPU tree and all CPU data are in the range of [2.2, (3.2, 3.2)]. So, the CPU interest weight coefficient is calculated as 4.4667 with Formula (1). We perform the same calculation for the Price attribute with a coefficient of 44.8125. According to Formula (2), we can get all the attribute interest weights (as shown in Figure 13). For example, CPU interest weight is the following: Based on the interest weights of Figure 11, we can see that Price is much more important than CPU. Such interest feature will help the company to select its best supplier.

Inter est Rate Function Gener ation

The goal here is to produce the interest rate of each attribute. To do this, we need to define an interest rate function. A linear function is usually used to measure the attributes' rates [1,13,14]. In some cases, linear utility functions cannot assign weights to attributes in order to make an offer as the best one.

In order to solve this problem, we use the un-linear sigmoid function

) - (R / 2 - = αR R = x when 0) - (2 • 1 - = LVQ) - (x . αR LVQ) - (L / 2 = αL L = x when 0) - (-2 • 1 - = LVQ) - (x • αL ] LVQ [ exp 1 1 ] LVQ L, [ exp 1 1 )] LVQ ( [ )] LVQ ( [ L        ∈ ∈ − ⋅ ⋅ − ⋅ ⋅ AR , x + A x + = (x) ς x Sign x Sign Attribute R α α (3)

Example. We can now generate the interest rate functions for CPU and Price by binding all the selected clustering into the quickly changeable area. According to the CPU attribute tree, the selection [2.2, 2.5] has the LVQ of (2.4767, 0.3189). To be An Interest-based Offer Evaluation System for Semantic Matchmakers 9

able to process high dimensional values, we use the distance between attribute data and the best attribute data. Here, we believe CPU clustering [3.2, 3.2] is the best data. Offer Evaluation with the Inter est Model MNL model expresses the utility for a group of people choosing an item. The utility function for an individual in a population includes the deterministic and random components as follows [13]:

∑ = ∈ + ⋅ = K k nj njk k nj C j x b U 1 , ε

where • U nj is the utility for buyer n selecting item j.

• (b k . x njk) is the "representative" taste of the population. This component consists of K observed deterministic features x njk ; b k is the weight for each feature x njk . • ε nj is the individual taste for the item j.

• C is the set of items.

An Interest-based Offer Evaluation System for

Semantic Matchmakers 11 We now adapt the MNL formula to define the interest model for each individual.

First we consider the deterministic features as the offer attributes. Furthermore, ε nj can be decomposed into K attributes since ε nj is the total alternative with K features. This means the evaluation of the attributes may be different according to the interests of each individual (cf. Formula ( 5)). At the market level, the individual taste ε is brought into the population model as a random utility. Since it comes from individuals and its value is random, ε is usually removed when users generate the MNL model. However, in our system individual taste becomes important.

∑ = ∈ + ⋅ = K k njk njk k nj C j x b U 1 ) ( ε

In order to produce the interest model, our system calculates the interest weights, IW, and simulates the interest rates, IR. IW denotes the interest weight b k and IR the interest rate value x njk +ε nj . We propose Formula (6) to build the interest model IM for each individual. IM is the degree of interest of the buyer purchasing an offer j with K attributes. Based on the consumer theory, an individual seeks to maximize his utility in each purchasing behavior.

C j IR IW IM K k jk jk j ∈ ⋅ = ∑ =1 ) ( ) (

Example. After our system gets the interest weights and interest rate functions for the two attributes, it generates the interest model (IM) for the company as follows.

IM Company (Supplier) = 0. 1. Table 3 shows that Supplier9 is the best supplier for the company. We developed our system with a distributed architecture as illustrated in Figure 10.

The buyer interacts with the client side via the GUI. After the buyer submits his request, the GUI passes it to the connected semantic matchmaker. On the server side, the OfferManager component: (1) collects the request-matched offers and stores them in the ContentOffer database, (2) analyzes the request and offers to extract the attributes and their values, and (3) stores them in the OfferAttribute database. For each attribute, the AttributeDataClustering component clusters its values and sends its clustering tree to the client side. GUI helps the buyer to select the most interested clustering (cf. Figure 11). Once the buyer's selection is completed, the offers, and returns to the buyer the list of offers sorted by interests. In Figure 13, we show for instance the offer evaluation process on the client side.

CONCLUSION AND FUTURE WORK

In this paper, we showed the benefits of sorting the request-matched offers according to the buyer's interests and needs. Our interest model provides a solution to existing matchmaking systems and avoids the linear matching problems. Adopting an economic method, we produced a simple and automated model to determine the best matched offer based on the buyer's selections. One possible direction of this work is to include the interest learning [19] in our system. The main purpose of this learning is to update the interest model to fit the buyer's interests instantly. A learned interest model will be able to determine the best offer in these two situations: the buyer shifts his interests, or new offers are added in our database.

Fig. 2 .Fig. 2. Formatting the Purchasing Request
Fig. 4 .Fig. 4. SOM Algorithm
Fig. 5 .Fig. 5. CPU Data Clustering
1 .We believe the sigmoid function is the closest function to human natural interest change. In our work, we use the sigmoid function to simulate each attribute interest rate. Here x denotes the value of an attribute and y its interest value. In Figure 7, we show that x of the sigmoid function has less changes in the two intervals [-∞, -2] and [2, +∞]. The Sigmoid function in these two intervals can be considered as a linear function with an acceptable standard error. Meanwhile the interval [-2, 2] is a quickly changeable area. A buyer's selected attribute clustering contains a specific interest for this attribute. In order to represent such interest in our interest rate function, we need to bind the buyer's selected clustering into the quickly changeable interval [-2, 2].
Fig. 7 .Fig. 7. Sigmoid Function and Value Change We employ LVQ as the center of our interest rate function since LVQ can be considered as the density center of the attribute data. Attribute data [AL, AR] can be distributed accordingly, and the selected clustering [L, R] is bound into the interval [-2, 2]. LVQ point can be either in the selected clustering [L, R] or outside. If LVQ is inside the clustering, we divide the interest rate function into two functions (cf. Formula (3)) where α L is generated when binding [L, LVQ] into the interval [-2, 0], α R is generated when binding [LVQ, R] into [2, 0], Sign is +1 or -1 w.r.t ascending or descending order of the clustering.
LVQ
Fig. 8 . 9 Fig. 9 .Fig. 8. Interest Rate Function for CPU
Fig. 10 .Fig. 11 .Fig. 12 .Fig. 10. System Top-Level Architecture
Fig. 13 . 15 Fig. 14 .Fig. 13. Client Side: Offer Evaluation
Table 1 .Candidate OffersSupplier IDCPU (GHz)PriceRange1
($) For the First 10 Items PriceRange2 ($) For Item 11 to 202.511007992.24703702.56005002.3311008002.49997992.510308302.66250022002.310008802.2420400102.4950900112.81200115012(1.9, 1.9)80070013(3.0, 3.0)2900260014(1.8, 1.8)68068015(3.2, 3.2)32002500
Table 2 .Distances of High-Dimensional DataxBestAttr ibuteDataDistance(x, BestAttr ibuteData)2.2 ***(3.2, 3.2)3.35262.5 **(3.2, 3.2)3.2757(2.4767,0.3189) *(3.2, 3.2)2.9705***Min selection value (L), **Max selection value (R), *LVQAccording to the distance calculation in
Table 2 ,LVQ is closer to the best data than any other data in the selected clustering. Consequently, the following interest rate function for attribute CPU has only α L . Figure8displays the company's interest rate for CPU.11exp [ L(tan(,)tan(LVQ,uteData) BestAttrib)]1exp5.2342[1 tan(,(32 .,3.2))2.9705][2, 2 .(3.2,3.2)]
Based on these values, we can conclude that Supplier2 has a higher chance than Supplier1 to be the company's partner. With our interest model, we can evaluate all the candidate offers of Table0906•ϛ CPU (CPU) + 0.9094•ϛ Price (Price)For example, we show below how the interest model calculates the interests forthe first two suppliers:IM Company (Supplier1) = 0.0906 • ϛ CPU (2.5) + 0.9094•ϛ Price [(1100,799)]= 0.0906 • 0.1684 + 0.9094 • 6.2583E-36= 0.0189IM Company (Supplier2) = 0.0906 • ϛ CPU (2.2) + 0.9094 • ϛ Price [(470,370)]= 0.0906•0.1192 + 0.9094•0.1192= 0.1192So, we got an interest rate of 0.0189 for Supplier1's offer and 0.1192 for Supplier2'soffer.
Table 3 .Sorted Offers for the CompanySupplier IDCPU (GHz)Pr iceRange1Pr iceRange2Inter est9*2.24204000.811822.24703700.119212(1.9, 1.9) *8007000.015213(3.0, 3.0) *290026000.012714(1.8, 1.8)*6806800.013715(3.2, 3.2)*320025000.0152112.8120011500.017372.66250022000.012232.56005000.015262.510308300.013712.511007990.018952.49997990.0903102.49509000.090642.3311008000.090082.310008800.0906*: best offer with the max interest degree7Design and Implementation
InterestModelCreator component is called to build the buyer's interest model. It first passes all the selected clustering and the whole attribute clustering trees to InterestWeightCalculator and InterestRateFunctionCreator. For each attribute, InterestWeightCalculator returns the interest weight coefficient and interest weight (cf. Figure 12), and InterestRateFunctionCreator the interest rate function. The OfferEvaluator component applies the generated interest model on the candidate
Model-Driven Approach to the Integration of Multi-Agent Systems and Semantic Web Services CHahn SNesbigall SWarwas IZinnikus MKlusch KFischer Enterprise Distributed Object Computing Conference Workshops Sept. 2008 A Semantic Matchmaking Method of Web Services Based on SHOIN^+ (D)* HWang LiZ Z Services Computing. IEEE 26 33 Dec. 2006 Web services lookup: a matchmaker experiment TKawamura THasegawa AOhsuga MPaolucci KSycara IT Professional. IEEE 7 2 Mar-Apr 2005 Web Service Discovery Based on Semantic Matchmaking with UDDI TQiu PFLi Proceedings of the The 9th International Conference. Young Computer Scientists the The 9th International Conference. Young Computer Scientists Nov. 2008 Web Services Matchmaking with Incremental Semantic Precision DWBai CCLiu YPeng JLChen Wireless Communications, Networking and Mobile Computing. IEEE Sept. 2006 1 Semantic Matchmaking of Web Services Constraint Conditions DBai AGFei SFCai Wireless Communications, Networking and Mobile Computing. IEEE Sept.2009 1 Semantic Web-based Contextaware Service Selection in Task-computing RHuang YWZhuang JLZhou QYCao Proceedings of the WMSO '08 International Workshop the WMSO '08 International Workshop Dec. 2008 Web Service Ranking Using Semantic Profile Information UBellur HVadodaria Proceedings of the ICWS 2009. IEEE the ICWS 2009. IEEE July 2009 Matchmaker, matchmaker DEssex ACM Communications, ACM 52 May 2009 The Self-Organizing Map TKohonen 2001 Springer 3rd Edition Applying SOM as a Search Mechanism for Dynamic System YYChen YoungK Y Decision and Control Dec. 2005 Economic Choices. American Economic Association DMcfadden American Economic Review 91 3 Jun. 2001 Conditional logit analysis of qualitative choice behavior DMcfadden PZarembka Frontiers in Econometrics 1974 Academic Press Matching buyers and suppliers: an intelligent dynamic exchange model SHHa SCPark IEEE. Intelligent Systems 16 4 Jul-Aug 2001 A QoS-aware selection model for semantic web services XWang TVitvar MKerrigan IToma Proceedings of the 4th Int. Conference on Service-Oriented Computing the 4th Int. Conference on Service-Oriented Computing 2006 Non-functional property based service selection: a survey and classification of approaches QYu SReiff-Marganiec Proceedings of the Non Functional Properties and Service Level Agreements in SOC Workshop the Non Functional Properties and Service Level Agreements in SOC Workshop Nov. 2008 QoS for Web Services: Requirement and Possible Approaches Web Services Description Language 1 Learning users' interests by quality classification in market-based recommender systems YZWei LMoreau NRJennings Knowledge and Data Engineering. IEEE Transactions 17 12 Dec. 2005