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.
In order to take into account individual’s interests, we need to utilize the clustering
technology called Self Organizing Map (SOM) [
In the early time of e-commerce, matchmakers focused on mapping the offer attribute
values [
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 [
To find the best offer, recent matchmakers evaluate service description [
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. 3
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 [
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.
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) [
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 mi
in the range of DataAttribute; alpha (t) controls the learning loop and is the learning
rate function which is decreased by learning time t; mc is the closest LVQ to the
selected data x; hci() is the “neighborhood” function that updates LVQ in the learning
time [
void ClusterAttributeData(DataAttribute: Array) {1. SOM(DataAttribute, A1, A2, A3);
//Cluster all data into 3 groups 2. ArrangeClustering(A1, A2, A3);
//Arrange clustering in ascending order 3. for i = 1 to 3 if (IsLargeEnough(Ai))
ClusterAttributeData(Ai); //Cluster each sub-group} Example. Figures 5 and 6 illustrate respectively the CPU and Price clustering (represented as a tree structure).
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
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.
IW _ coek =
DataAttributek SelectedClusteringk ⋅ SelectedLevelTreek k ∈ K
TotalLevelTreek
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.
IWk = K ∑ IW _ coek k =1 IW _ coek k ∈ K 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: IWCPU = 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. 5
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 [
In order to solve this problem, we use the un-linear sigmoid function 1 ς k (x) =
1+ exp-x . 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
(1)
(2)
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 [
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
[
1 1+ exp[α L ⋅Sign⋅( x−LVQ)] ς Attribute (x) = 1 1+ exp[α R ⋅Sign⋅( x−LVQ)] x ∈ [ AL, LVQ] x ∈ [LVQ, AR] αL · (x - LVQ) = - 1· (-2 - 0)
when x = L αL =
2 / (L - LVQ) αR . (x - LVQ) = - 1· (2 - 0)
when x = R αR = - 2 / (R - LVQ) (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
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. According 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. Figure 8 displays the company’s interest rate for CPU.
ςCPU (x) =1+ exp[α L⋅Sign⋅(Dis tan ce( x,BestAttributeData)−Dis tan ce(LVQ,BestAttributeData))] 1 1 1+ exp5.2342⋅[Dis tan ce( x,(3.2,3.2))−2.9705] =
x ∈[2.2, (3.2, 3.2) ]
We suppose that the company selected the Price clustering [(420, 400), (470, 370)]
which is then bound into the area [
K U nj = ∑ bk ⋅ xnjk + ε nj , j ∈ C k=1 (4) where • Unj is the utility for buyer n selecting item j. • (b k . xnjk) is the “representative” taste of the population. This component consists of K observed deterministic features xnjk; b k is the weight for each feature xnjk. • εnj is the individual taste for the item j .
• C is the set of items.
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 U nj = ∑ bk ⋅ ( xnjk + ε njk ) k =1 j ∈ C
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 bk and IR the interest rate value xnjk + ε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.
K IM ( j) = ∑ (IW jk ⋅ IR jk ) j ∈ C k=1
Semantic Matchmakers 11 (5) (6) 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.
IMCompany(Supplier) = 0.0906·ϛ CPU(CPU) + 0.9094·ϛ Price(Price)
For example, we show below how the interest model calculates the interests for the first two suppliers:
IMCompany(Supplier1) = 0.0906 · ϛ CPU(2.5) + 0.9094·ϛ Price[(1100,799)] = 0.0906 · 0.1684 + 0.9094 · 6.2583E-36 = 0.0189 IMCompany(Supplier2) = 0.0906 · ϛ CPU(2.2) + 0.9094 · ϛ Price[(470,370)] = 0.0906·0.1192 + 0.9094·0.1192 = 0.1192 So, we got an interest rate of 0.0189 for Supplier1’s offer and 0.1192 for Supplier2’s offer. 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 Table 1. Table 3 shows that Supplier9 is the best supplier for the company. Supplier ID CPU (GHz) 9* 2.2 2 2.2 12 (1.9, 1.9) * 13 (3.0, 3.0) * 14 (1.8, 1.8)* 15 (3.2, 3.2)* 11 2.8 7 2.66 3 2.5 6 2.5 1 2.5 5 2.4 10 2.4 4 2.33 8 2.3 *: best offer with the max interest degree 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 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 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.
Semantic Matchmakers 13
We implemented our system using Visual Studio C# (on the .net 3.5 framework) and the SQL Server 2008. Figures 14 and 15 show the class diagrams of the client and server side programs. We created two separate databases sources, called serverDB and clientDB, to support server and client side programs. These two classes contain all the necessary functions about database processing and data binding. The other classes are created with a window interface by using software MS Blend3, the interface developing tool for Windows form application. The classes ServerWindow and ClientWindow contain multi-thread and network communication functions.
Semantic Matchmakers 15
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 [