Supporting intuitive decision in complex multi-attributive domains using fuzzy, hierarchical expert models

Abstract

A database evaluation system provides for intuitive end user analysis and exploration of large databases of information through real time fuzzy logic evaluation of utility preferences and nearest neighbor exploration. The system provides for domain modeling of various types of information domains using attribute mappings to database fields, and utility value weightings, allowing multiple different domain models to be coupled with a same database of information. User interaction with the evaluation system is through an interactive key generator interface providing immediate, iterative visual feedback as to which candidate items in the database match the user's partial query. A proximity searcher user interface provides for nearest neighbor navigation and allows the user to determine which items in the database are closest to a given item along each independent attribute of the items, and selectively navigate through such nearest neighbors. A fractal proximity searcher simultaneously displays multiple levels of nearest neighbors for user selected attributes.

Claims

I claim:

1. A database evaluation system, comprising:

A database for storing a plurality of items, each item having a plurality of fields for storing data descriptive of the item;

an authoring module for defining a domain model having a hierarchical set of attributes, the attributes comprising: (1) at least one attribute hierarchically defined by a grouping of other attributes and (2) a plurality of attributes each of which is associated with a database field and is not hierarchically defined by other attributes, each field-associated attribute having a defined transfer function that maps a value in the field to a utility value of the attribute, and for each attribute, defining a weighting for the attribute relative to other attributes that are grouped together to define a hierarchical attribute;

an evaluation engine, coupling the domain model to the database and providing a first user interface for allowing a user to iteratively set at least one criterion for selecting and displaying a set of matching items comprising a short list, the evaluation engine allowing a user to inspect, compare, or navigate items on a short list;

a scoring interface coupled to the evaluation engine for displaying for each item from the short list a relative score of the item, and for displaying for at least one attribute of an item a direct manipulation mechanism for weighting a relative weight of the attribute, the evaluation engine redetermining the relative score of each item in the short list according to any change in the relative weighting of the attributes; and

a proximity searcher user interface coupled to the evaluation engine for displaying a reference item from the database, for at least one attribute of the domain model, displaying a nearest neighbor item for the attribute as a function of a distance between the reference item and the nearest neighbor for the attribute.

2. The system of claim 1 wherein the relative scores are re-determined on about a real-time basis as a user adjusts the direct manipulation mechanism.

3. A method of constructing a domain model for a database for storing a plurality of items, each item having a plurality of fields of data, comprising:

defining a hierarchical plurality of attributes, the attributes comprising: (1) at least one attribute hierarchically defined by a grouping of other attributes and (2) a plurality of attributes each of which is associated with a database field and is not hierarchically defined by other attributes;

for each field-associated attribute, defining a transfer function that maps a value in the field to a utility value; and

for each attribute, defining a weighting for the attribute relative to other attributes that are grouped together to define a hierarchical attribute.

4. The method of claim 3, further comprising:

receiving a selection of at least one pair of attributes, including a first attribute and a second attribute, as compensatory attributes, and an assignment of a weighting of values of the first attribute relative to values of the second attribute.

5. A database evaluation system, comprising:

A database for storing a plurality of items, each item having a plurality of fields for storing data descriptive of the item;

an authoring module for defining a domain model having a hierarchical set of attributes, the attributes comprising: (1) at least one attribute hierarchically defined by a grouping of other attributes and (2) a plurality of attributes each of which is associated with a database field and is not hierarchically defined by other attributes, each field-associated attribute having a defined transfer function that maps a value in the field to a utility value of the attribute, and for each attribute, defining a weighting for the attribute relative to other attributes that are grouped together to define a hierarchical attribute;

an evaluation engine, coupling the domain model to the database and providing a first user interface for allowing a user to iteratively set at least one criterion for selecting and displaying a set of matching items comprising a short list, the evaluation engine allowing a user to inspect, compare, or navigate items on a short list.

6. The system of claim 5 further comprising:

a scoring interface coupled to the evaluation engine for displaying for at least one item from the short list a relative score of the item, and for displaying for at least one attribute of an item a direct manipulation mechanism for weighting a relative weight of the attribute, the evaluation engine re-determining the relative score of a displayed item from the short list according to any change in the relative weighting of the attributes.

7. The system of claim 5 further comprising:

a proximity searcher user interface coupled to the evaluation engine for displaying a reference item from the database, for at least attribute of the domain model, displaying a nearest neighbor item for the attribute as a function of a distance between the reference item and the nearest neighbor for the attribute.

8. The system of claim 6 wherein the relative scores are re-determined on about a real-time basis as a user adjusts the direct manipulation mechanism.

Description

III. MICROFICHE APPENDIX

A microfiche appendix including 1 sheet of microfiche and 44 frames is included herewith.

IV. BACKGROUND

A. Field of Invention

The present invention relates to database systems for evaluation of items according to user preferences, and more particularly to database systems using domain specific knowledge and utility functions to identify items meeting user defined criteria.

B. Background of Invention

The proliferation of computers and of the exploding use of the Internet have brought with them the increasing availability of computerized databases of products, information, and services from which users, such as consumers or professionals, evaluate and purchase such items. However, the ever increasing availability of such databases to more and diverse types of users has resulted in a widening gap between the existing and the user required skills for using these databases.

There exists sophisticated tools for database mining, analysis and the subsequent generation of information from the extracted data, but none of these tools allow users to quickly and efficiently perform a frequently desired task of finding in the database the item most suited to the user's objective and subjective preferences.

A typical activity involving this type of database access is online shopping: for example, a shopper is not interested in purchasing all of the VCRs that match her criteria, but only the one that gets closest to some "ideal VCR" defined by the user's own objective and subjective criteria (e.g., low cost, high performance, reliable, etc.). Conversely, even if no items match the shopper's search criteria, she might still be interested in purchasing the item that is `closest` or most similar to the her criteria. Current database access tools do not meet the following needs of such users for the following reasons.

First, conventional databases will often return empty search result sets where no matches found are found to the set of specific criteria input by a user; alternatively, they may return too many matches where very few critieria are specified. In either case, the user is unable to identify which items are most similar to her overall criteria, and must reformulate her search criteria.

Second, compound queries where multiple attributes are specified and which result in empty projections do not tell which criterion or group of criteria were responsible for reducing the number of matches to zero. Conversely, when too many matches are found, conventional tools provide no indication of the sensitivity of the database to each criterion. Thus, the user is unable to modify her criteria to eliminate such criteria, but must proceed by trial and error.

Third, shoppers compare items not on the basis of a single criterion, but using the concept of similarity given all or most critieria. For example, a car buyer who has identified a first car as a suitable item, may be looking for a less expensive car which implicitly would not only have a lower price tag, but simultaneously retain all other desirable features of the first car as much as possible. However, current database tools have the ability to evaluate items only along one dimension (e.g., price) without regard for the overall similarity of items along multiple dimensions, and thus are not suitable for this buyer to identify such a similar alternative car with similar features to the first car.

Fourth, many domains (automobiles, computers, financial instruments) are very complex and require significant expertise to understand at the database level ("variable valve timing", "256K cache", "0.14 negative market correlation"). The typical consumer does not have sufficient expertise to evalute different items with respect to such technical data, but does know various high level critieria that are important to their decision making. The complexity of the underlying domain makes it difficult for a shopper to formulate a query that reflects his fuzzy needs and desires, resulting in a mismatch between the results the database provides and the user's actual needs.

Finally, many shoppers are unable to describe what they are looking for with defined search criteria, but they can identify which items do not satisfy their requirements when such items are presented to them. With conventional tools, such shoppers are unable to deconstruct the domain into its constituent components and define useful search criteria which can then be used to select items from the database for further evaluation.

Accordingly, it is desirable to provide a database system that supports analysis and evaluation of the similarity of items in the database with respect to multiple critieria.

VI. SUMMARY OF THE INVENTION

The present invention, a Database Evaluation System (DES), is designed to help consumers and business users alike to find the item(s) in a database that most closely matches their objective requirements and subjective preferences. It effectively turns a database of information-rich items into an interactive buyer's guide.

The Database Evaluation System is a database technology focused entirely on the comparison and ranking of database items. The Database Evaluation System differs fundamentally from conventional database front ends in that it 1) uses a domain-specific vocabulary to isolate the user from potentially overwhelming amounts of raw data; 2) uses embedded expertise in the form of an "evaluation recipe" to guide the user along an optimal decision path; 3) provides a unique, interactive, real-time user interface for selection and navigation of items in the database; and 4) accounts for subjective, fuzzily defined user criteria.

In one embodiment, the DES of the present invention provides a system for constructing and evaluating items in a database storing any plurality of items. An authoring module enables the creation of a domain model which captures expert level knowledge about an application domain and maps the knowledge onto the database, thereby organizing the data into a useful and meaningful structure. More particularly, the authoring module creates a domain model including a hierarchical plurality of attributes in which some attribute are hierarchically defined by other attributes. For example in an automotive domain, an attribute such as performance may be hierarchically defined by attributes such as acceleration, braking, handling and the like. Each of these may be further hierarchically defined. For the lowest level attributes that are not defined by other attributes, the authoring module allows for the association of such attributes to selected fields of the database, which define the actual data stored therein. The authoring module also enables the expert to define for each attribute a transfer function that maps the values of the underlying field of the database to a utility value of the attribute. The authoring module also provide for weighting the attribute relative to other attributes, thereby weighting the utility values of one attribute relative to the utility values of other attributes. Multiple domain models may be defined for a given database, and applied by end users during access and selection of items from the database. This enables the user to apply the expert judgments of various experts to the same database of information.

The DES further includes an evaluation engine which couples a domain model to the database and provides various user interfaces for end users to access and evaluate items in the database. A first user interface receives from the user for selected attributes a user defined utility function that describes the utility of various values of the attribute for the user. The evaluation engine selects for retrieval and display items of the database according to both the user defined utility function and the utility values of the selected attributes as defined in the domain model. Fuzzy logic may be used to match the user defined utility functions with the domain model functions and database items values. The selected items are iteratively displayed in reponse to each partial input of selected attributes by the user. This allows the user to iteratively reduce the number of items selected or retrieved from the database. From the selected items, the user may create a short list of items for further evaluation. This user interface thereby allows the user to quickly identify items of the database that match the user's utility preferences, and to do so in an iterative, and interactive manner that progressively narrows the set of selected items of interest.

The system also includes a second user interface operating in conjunction with the evaluation engine that displays for each item on the user's short list a relative score of the item to other items on the short list, and further displays for each attribute a direct manipulation mechanism, for example, a graphical slider. The user can manipulate the direct manipulation mechanism to alter the relative weighting of the attribute as defined previously in the domain model. The evaluation engine redetermines the relative score of each item in the short list according to any change in the relative weightings of the attributes, and updates the display of the recomputed scores. The user may iteratively change the weightings of attributes in this manner to determine the impact of such changes on the relative scores of the short list items. This user interface enables the user to comparatively evaluate multiple items simultaneously by adjustment of the attribute weightings.

The system further includes a proximity searcher user interface, also operating in conjunction with the evaluation engine. The proximity searcher provides for nearest neighbor navigation and evaluation by displaying one of the items of the database as a reference item. For attributes of the domain model, the proximity searcher also simultaneously displays a nearest neighbor item as a function of a distance between between reference item and the nearest neighbor item for the particular attribute. The nearest neighbor item is determined not merely by the item having the next closest value of an attribute, but rather, by weighting the distance between the reference item and the nearest neighbor item for the particular attribute by the overall distance between the items with respect to all other attributes. The user can select any nearest neighbor item and make it the reference item, such that the displays of all the remaining nearest neighbor items are updated accordingly. In this fashion the user can navigate through the database to explore the relationships and similarities between items of the database, and determine which items are similar and which are not. This process further aids the user in the selection and evaluation of items from the database, enabling the user to identify items that may have been previously overlooked.

In one embodiment, the proximity searcher is extended as a fractal or recursive searcher. Each of the attributes is associated with an attribute window pane, and the reference item is associated with a reference window pane. These windows panes are displayed simultaneously. For one of the attribute window panes, the database item therein is then treated as a reference item, such that another group of attribute window panes for the remaining attributes is again simultaneously displayed with the first group of attribute window panes. Each of these additional attribute window panes displays, for their respective attribute, a nearest neighbor item for the attribute, relative to the new reference item. This selection and expansion of attribute window panes into reference window panes may be repeated through several levels of simultaneous displays, thereby visually revealing a substantial portion of the underlying relationships of the items in the database.

The DES further supports users who do not know ahead of time the specific criteria or attributes they are looking for, but know what items or attributes are not satisfactory. The DES provides a method for critiquing items in the database to determine the user's underlying criteria to determine which items the user would not select, and from there, eliminates from the database other items having attributes similar to these undesired items. In one embodiment, the DES presents to the user an item from the database for evaluation. The user inputs one or more reasons that the item is deficient or not satisfactory or would not be selected by the user. These reasons are associated with one or more attributes of the database, preferably according to a previously defined domain model. The utility value of the item's attribute associated with the reason is then used to eliminate from consideration other items of the database having an equal or lesser utility value for this item's attribute, and thereby having the same deficiency as the presented item. For example, if the user indicates that an item is too expensive, than other items having the same or greater cost are likewise eliminated. This process is repeated until the number of items for evaluation is reduced to a desired limit, thereby enabling the user to quickly reduce the number of items for consideration without having to pre-specify criteria in a search query.

Applications for the DES include interactive online shopping, electronic buyers guides, yellow pages, classifieds, and any other application where user needs to select and evaluate candidate items from a database of potential candidate using user defined, fuzzy criteria.

Items suitable for evaluation, inspection and/or purchase using the DES include consumer goods such as automobiles and home electronics; consumer services such as health care and insurance policies; financial services such as stocks, mutual funds and other investments; travel destinations and other hospitality services; real estate; electronic personals; personnel recruitment; and any other industrial or commercial goods.

The DES may be embodied in various platforms, including online environments such as commercial online services and the Internet; standalone applications in CD-ROM or floppy disk format; hybrids (CD-ROM with updating via online); and kiosks.

VII. BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an illustration of the hardware components for one embodiment of the present invention.

FIG. 2 is an illustration of the software components of an embodiment of the present invention.

FIG. 3 is a flowchart of the process of defining a domain model.

FIG. 4 is an illustration of one embodiment of a mechanism for adjusting attribute weighting during domain model definition.

FIG. 5 is an illustration of the hierarchical definition of attributes in relationship to the database.

FIG. 6 is an illustration of a user interface mechanism for defining the transfer function between the utility value of an attribute and values of the database field associated with the attribute.

FIG. 7 is an illustration of another user interface mechanism for defining a transfer function.

FIG. 8 is an illustration of a compensation matrix for defining compensating attributes.

FIG. 9 is an illustration of a compensation map for defining compensation weightings between two attributes.

FIG. 10 is a flowchart of the process of evaluating the utility value of an attribute.

FIG. 11 is a flowchart of the overall user process of evaluating items in the database with the Database Evaluation System.

FIG. 12 is a flowchart of the operation of the DES in evaluating database items.

FIG. 13 is an illustration of one embodiment of a Data Viewer for viewing selected items in the database.

FIG. 14 is an illustration of a user defined utility function for an attribute.

FIG. 15 is an illustration of the Data Viewer following matching of an initial user query.

FIG. 16 is another illustration of the Data Viewer following matching of an initial user query.

FIG. 17 is an illustration of a critique mode for defining user criteria through selective elimination of database items.

FIG. 18 is an illustration of one embodiment of an Attribute Equalizer for evaluating items on a short list of items.

FIG. 19 is another illustration of the Attribute Equalizer following user inputs to alter the relative weighting of attributes.

FIG. 20 is an illustration of stacked bars used in the Attribute Equalizer.

FIG. 21 is a flowchart of the process of updating the Attribute Equalizer.

FIG. 22 is an illustration of the process of nearest neighbor searching in the Navigator.

FIG. 23 is a set of scatter graphs showing comparisons of database items for various attributes.

FIG. 24 is an illustration of one embodiment of the Navigator.

FIG. 25 is a plot of the similarity of nearest neighbors for a selected attribute.

FIG. 26 is an illustration of an alternate embodiment of the Navigator including fractal extensions of the Navigator.

VIII. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

A. Hardware Environment

Referring now to FIG. 1 there is shown a suitable hardware environment for one embodiment of the present invention. The database evaluation system 1.0 (DES) includes a conventional computer 1.2 including input devices such as touchscreen 1.4, or joystick 1.6, or mouse 1.8, and/or keyboard 1.10, or other pointing device for user input. Conventional output devices includes a display 1.14 and printer 1.12 as a graphical output device for displaying and printing records and information retrieved from the system. The invention may be implemented on any computer with the capability of accessing a database or creating one on demand. The computer 1.2 includes a conventional processor, video card, I/O ports, data ports, addressable memory (RAM and ROM). The computer executes a conventional operating system. Examples of the client portion of the hardware include, but are not limited to, Intel-based PCs running Microsoft Corp's Windowsm 3.x, 95, NT or DOS or Unix, Apple Computer Macintoshes.TM. running Mac/OS or Unix; Sun Microsystem, SGI or other workstation computers running Unix; personal digital assistants (PDAs) such as Apple Computer's Newton.TM., Motorla Inc.'s Envoy.TM. and other PDAs.

The DES 1.0 assess and stores data in any variety of data storage media including but are not limited to local hard disk 1.26, CD-ROM 1.22 or other mass storage device, local area network servers 1.24, wide area network servers 1.20, Internet servers 1.18 accessed via phone or cable, commercial consumer and business online services 1.16, distributed information sources such as(any combination of the above, and local RAM if data is generated on demand or linked to other program such as spreadsheet or database program executing in RAM.

The system 1.0 of the present invention may be disposed at various points of use including, but are not limited to the home (such as on a stand-alone multi-media PC connected to an online service), office (such as on a workstation computer connected to a database on a WAN), kiosk used in-store, in hospitality services or training environments.

B. Component Overview

Referring now to FIG. 2, there is illustrated the main component blocks of the Database Evaluation System 1.0. At the foundation of a decision support system built around the DES 1.0 is a domain-specific database 2.4 that contains one or more of the following: product specifications, statistical data about the product or service, empirical data such as test results, anecdotal information such as user experiences, editorial information such as magazine reviews. The domain may be of any type of information for which it is desirable to make item by item comparisons or selections of items based on various criteria, such as consumer goods or services, commerical goods or service, financial investments, and the like.

The database 2.4 includes a database engine 2.6 for storing and retrieving data from the database, raw data 2.8 which is the data stored for individual items, the domain model 2.10, and a key script 2.12.

Items in the database 2.4 are defined by and stored with a number of discrete attributes. The discrete attributes stored in the database 2.4 are abstracted into higher-level concepts by a domain expert with the help of the DES Authoring Tools 2.2. This process effectively turns raw data 2.8 into a useful domain model 2.10 of the subject domain by 1) grouping related data fields into meaningful everyday variables; 2) defining a frame of reference for evaluating database items; and 3) identifying the relative importance of particular attributes. As shown in FIG. 2, the raw data 2.8 may be supplied by third party data providers.

A user accesses the database 2.4 using a number of data visualization tools in the DES engine 2.14, including a key generator, an attribute equalizer, proximity searchers, and text queries (not shown). These elements are further described below. A data base specific access module 2.0, such as SQL, DB2, or dBase, operates to exchange data between data base 2.4 and the DES engine 2.14 and/or DES Authoring Tools 2.2. User interface 2.16 represents software through which the user interacts with the DES engine. For example, see the user interfaces depicted in FIGS. 6-9 and 13-19.

The data processing is handled by the DES engine 2.14. These tasks include database access and search, fuzzy logic evaluation, and proximity calculations, as further described below.

The program flow is partially determined by the Key Script file 2.12 authored by a domain expert and executed by the DES Engine 2.14. The operational elements controlled by the script include 1) which selection criteria are presented to the user for accessing the database; 2) the sequence in which selection critieria are presented; and 3) conditions for branching to different program phases.

A description of the major components of the DES follows.

1. DES Authoring Tools

The main task of the DES Authoring Tools 2.2 is the construction and definition of the attributes most commonly used in the evaluation of the database items.

A four-step process is followed by an iterative validation of the resulting knowledge base. FIG. 3 illustrates the details of this overall process.

First 3.0 the domain expert identifies the key terms which compose the domain-specific vocabularies for the domain model 2.10. An examplary use of the DES 1.0 is a database for evaluating automobiles by prospective customers, in effect an online car buyer's guide; this example will be used throughout this description. In this case, domain experts might include magazine editors, race car drivers, consumer safety advocates, car-nut celebrities and any other automotive analysts. In this example domain, the vocabulary may be composed of the terms Performance, Safety, Comfort, Reliability, Functionality, Economy, Styling and Fun Factor as key terms for defining the domain model 2.10.

Three considerations are important in the selection of the domain vocabulary:

Orthogonality There should be as little overlap between the definitions of any two attributes as possible. An example of highly orthogonal concepts is Styling and Reliability: changing one has no inherent effect on the other. Badly chosen attributes would be Performance and Acceleration, with the latter clearly being a subset of the former.

Completeness In as much as there should be minimal overlap between the attribute definitions, there should not be any holes either.

Realism Attributes should reflect the terminology used by the intended target audience.

Rarely will it be necessary to approach the selection from scratch. As in this automotive example, vocabularies already established for evaluations such as comparison tests in print publications will provide an excellent starting point.

FIG. 4 illustrates a group of such attributes organized in an attribute equalizer panel 4.0. Each attribute 4.2 is associated with a direct manipulation slider 4.4 that is used by the domain expert to adjust a weighting of each attribute independently.

Weights and utility values are calculated in response to changes in the attribute equalizer 4.0 in the manner described in Listing 1:

    __________________________________________________________________________
    Listing 1
    __________________________________________________________________________
    000
       begin
                Comment: to normalize weights, set total weight to zero
                first
    001
       total.sub.-- weight = 0.0
                Comment: for each slider execute the following loop
    002
       for each slider do
                Comment: add the weight (setting) of this slider to the total
                weight
    003 total.sub.-- weight = total.sub.-- weight + weight[slider]
                Comment: do the next slider if any
    004
       next slider
                Comment: now have the total weight
    005
       for each slider do
                Comment: divide the weight of each slider by the total
    006 weight[slider] = weight[slider] / total.sub.-- weight
                Comment: this makes sure that the total of all weights is
                1.0
    007
       next slider
                Comment: now, for each item execute the following loop
    008
       for each item do
                Comment: set the total utility of this item to zero
    009 total.sub.-- utility[item] = 0.0
                Comment: for each attribute, do the following
    010 for each attribute do
                Comment: calculate the weighted utility for the current
                attribute as the product of
    the          utility as provided by value.sub.-- function above and the
                 relative weight of
    this attribute
    011   weighted.sub.-- utility[item] [attribute] =
                utility[item] [attribute] * weight[attribute]
                Comment: add this weighted attribute utility to the total
                utility
    012         total.sub.-- utility[item] = total.sub.-- utility[item] +
                weighted.sub.-- utility[item] [attribute]
                Comment: go to the next attribute if any
    013 next attribute
                Comment: go to the next item if any
    014
       next item
                Comment: for each item, do the following
    015
       for each item do
                Comment: display the item's utility (as a bar graph, printed
                number, etc.)
    016 display (total.sub.-- utility)
                Comment: or display each component in a stacked bar chart or
                pie chart
    017 display (weighted.sub.-- utilities)
                Comment: go to the next item, if any
    018
       next item
                Comment: end
    019
       end
    __________________________________________________________________________

    __________________________________________________________________________
    Listing 2
    __________________________________________________________________________
    000
       begin
               Comment: this loop executes once for each item in the
               database
    001
       for each item do
               Comment: initialize the utility value for this item to zero
    002  utility[item] = 0.0
               Comment: this loop executes once for each attribute in the key
               query
    003  for each attribute do
               Comment: get the value for this attribute for this item from
               the database
    004    value = field.sub.-- name[item]
               Comment: test if the value is "catastrophic" (so bad nothing
               could
               possibly compensate for this shortcoming)
    005    if value < fail.sub.-- value
               Comment: set the item's utility to zero since item is
               unusable
    006        utility[item] = 0.0
               Comment: go to the end of the loop
    007        go to line 15
               Comment: if the value is not catastrophic, but below a certain
               minimum
    008    else if value < min.sub.-- value
               Comment: then add no utility for this attribute to the current
               overall
               utility total of the item and go to the end of the attribute
               loop
    009        go to line 03
               Comment: if the value exceeds a certain maximum value
    010    else if value > max.sub.-- value
               Comment: then add the highest score (1.0) to the current
               utility total
    011        utility[item] = utility[item] + 1.0
               Comment: if the value is between the minimum and maximum
    012    else
               Comment: then calculate the utility for the product of the
               criterion
               function return result (as described below) and the
               attribute's relative
               weight.
    013        utility[item] = utility[item] +
                   value.sub.-- function (value) *
                   weight [attribute]
               Comment: end of loop for this attribute. If there are more
               attributes to
               process, jump back up to line 3
    014  next attribute
               Comment: end of loop for this item. If there are more items to
               process,
               jump back up to line 1
    015
       next item
               Comment: all attributes for all items are processed
    016
       end
    __________________________________________________________________________

    __________________________________________________________________________
    Listing 3
    __________________________________________________________________________
    000
       begin
               Comment: discrete attributes can be enumerated (i.e. degrees),
               continuous ones
               can't
    001
       if attribute = discrete
               Comment: user enters number of possible input values (e.g.
               binary -> two)
    002  num.sub.-- values = user input (number of possible input values)
               Comment: this loop executes once for each possible input
               value
    003  for each input.sub.-- value do
               Comment: user enters a value between 0 and 1 for this input
               value
    004    utility[input.sub.-- value] = user input (utility value)
               Comment: go to next input value, if any
    005  next input.sub.-- value
               Comment: otherwise, i.e. we're dealing w/ a continuous
               attribute (e.g. salary)
    006
       else
               Comment: predefined functions include linear, logarithmic,
               exponential, etc.
    007  if use.sub.-- predefined.sub.-- function
               Comment: user enters name or reference number of predefined
               function
    008    attribute.function.sub.-- name = user input (function name)
               Comment: user selects one or more options (such as inverse
               operation)
    009    attribute.function.sub.-- option = user input (option name)
               Comment: otherwise, i.e. if user wants to defined own
               function
    010  else
               Comment: one possible user interface for defining the curve is
               shown in a
               separate figure
    011    attribute.curve = user input (curve shape)
               Comment: we're all done
    012
       end
    __________________________________________________________________________

    __________________________________________________________________________
    Listing 4
    __________________________________________________________________________
    000
       begin
               Comment: we keep track of the current score for each item
    001
       create (total.sub.-- score.sub.-- array)
               Comment: it's up to the user to select attributes, so we don't
               know how often to
               loop
    002
       while (user selects attribute) do
               Comment: we store the score of each item for this attribute in
               this array
    003  create (attribute.sub.-- score.sub.-- array)
               Comment: depending on the attribute type, we expect different
               return values
               from UI
    004  case attribute type of
               Comment: this is usually implemented as a simple check box
               (yes or no)
    005    binary:
               Comment: user interface returns a boolean value
    006        get criterion = boolean from user.sub.-- interface
               Comment: usually implemented as a radio button
    007    one.sub.-- of many:
               Comment: user interface returns a single integer indexing one
               of the possible
               choices
    008        get criterion = integer from user.sub.-- interface
               Comment: usually implemented as a series of check boxes or
               multi-selection list
    009    many.sub.-- of.sub.-- many:
               Comment: UI returns an array of integers (first element
               indicating array length)
    010        get criterion = integer.sub.-- array from
           user.sub.-- interface
               Comment: this can be implemented as a slider, a knob, a data
               field, etc.
    011    single.sub.-- number:
               Comment: UI returns a single value indicating a maximum, min,
               ideal, etc. value
    012        get criterion = real.sub.-- number from
           user.sub.-- interface
               Comment: usually implemented as a dual thumbed slider, two
               sliders, two fields . . .
    013    number.sub.-- range:
               Comment: UI returns two floating point values
    014        get criterion = real.sub.-- range from user.sub.-- interface
               Comment: usually implemented as a graph/slider combo w/ bell
               curve over target
               value
    015    fuzzy.sub.-- number:
               Comment: UI returns three value pairs describing curve
    016        get criterion = fuzzy.sub.-- number from
           user.sub.-- interface
               Comment: usually implemented as dual-point (min, max)
               graph/slider combo
    017        fuzzy.sub.-- range:
               Comment: UI returns four value pairs describing max range w/
               fall-off
    018        get criterion = fuzzy.sub.-- range from
           user.sub.-- interface
               Comment: end of possible data types
    019  end of case
               Comment: for each item in the database we do the following
               loop
    020  for each item do
               Comment: get the value for the attribute of this item from the
               database
    021    get item.sub.-- attribute.sub.-- value from database
               Comment: convert item's value to a score from 0.0 to 1.0
    022    item.sub.-- score = value.sub.-- to.sub.-- score (item.sub.--
           attribute.sub.-- value,
               criterion)
               Comment: multiply individual score w/ total score so far for
               this item (note that if
               the score for this item is 0.0, the total score is 0.0 as
               well, i.e. one strike and the
               item is out.
    023    attribute.sub.-- score.sub.-- array[item] =
               attribute score.sub.-- array[item] * item.sub.-- score
               Comment: display item modified according to its score
    024    display (item, attribute.sub.-- score.sub.-- array[item])
               Comment: go to next item, if any
    025  next item
               Comment: let user choose another attribute
    026
       next attribute
               Comment: end of short key definition
    027
       end
    __________________________________________________________________________

    __________________________________________________________________________
    Listing 5
    __________________________________________________________________________
    000
       begin
               Comment: create an array of floating point numbers to store
               score of each item
    001
       create (diff.sub.-- array)
               Comment: loop for all items
    002
       for each item in database do
               Comment: don't compare reference item to itself
    003  if item == reference.sub.-- item
               Comment: do the next item
    004    do next item
               Comment: initialize the sum total of all differences to zero
    005  total.sub.-- difference = 0
               Comment: loop for each attribute
    006  for each attribute do
               Comment: difference is between the attribute scores of
               selected and reference
               items
    007    difference = attribute.sub.-- score[item] -
           attribute.sub.-- score[reference.sub.-- item]
               Comment: if this is the attribute that we're searching
    008    if attribute == target.sub.-- attribute
               Comment: store the value
    009        attribute.sub.-- diff = difference
               Comment: otherwise . . .
    010    else
               Comment: take the nth power of the difference and add it to
               the total
    011        total.sub.-- difference = total.sub.-- difference +
           (difference power (num.sub.-- attributes - 1))
               Comment: do the next attribute
    012  next attribute
               Comment: take the nth root of the total and normalize it
    013  total.sub.-- difference = total.sub.-- difference root (num.sub.--
         attributes -
         1) / (num.sub.-- attributes - 1)
               Comment: value.sub.-- of returns a value (0 to 1) that
               indicates how close to the ideal
               the attribute difference is to an ideal one (this is a
               non-linear function).
               Multiply that by the similiarity (= 1 - difference) and get a
               value that indicates how
               ideal a neighbor this item is
    014  diff.sub.-- array[item] value.sub.-- of (attribute.sub.-- diff) * (1
         -
         total.sub.-- difference)
               Comment: do the next item
    015
       next item
               Comment: sort the score array
    016
       sort (diff.sub.-- array)
               Comment: the first item in the array (if sorted in descending
               order) is the one
               unless it has a negative value (which indicates that there
               exist no "better"
               neighbors in the desired search direction)
    017
       display (diff.sub.-- array[first.sub.-- item])
               Comment: all done
    018
       end
    __________________________________________________________________________

• Inventors
  Schmitt, Martin;
• Assignee
  Bizrate.Com (Los Angeles, CA)
• Published
  Nov-9-1999
• Current US Classes:
  707/102
  707/5
• Application #
  748944
• International Classes
  G06F 017/30
• Field of Search
  707/102 707/1-5
• Examiner
  Von Buhr; Maria N.
• Agent
  Ganz; Bradley M.
• US Patent References:
  5226117
  5459861
  5515488
  5535382
  5544354
  5600831
  5608899
  5655116
  5680605
  5715444
  5724567