Patent Publication Number: US-9836522-B2

Title: Framework for ordered clustering

Description:
TECHNICAL FIELD 
     The present disclosure relates generally to a framework for generating ordered clusters. 
     BACKGROUND 
     Clustering is the task of grouping a set of objects in such a way that the objects in the same group or cluster are more similar to each other than to those in other groups. Various clustering techniques exist. Conventional clustering techniques are based on intrinsic characteristics or attributes of objects which are used to compute similarity degrees or distances between objects. The similarity degrees or distances are processed to group the objects into clusters. As such, conventional clustering techniques group objects into clusters based solely on distances. This may result in inaccurate groupings according to a user&#39;s objective. 
     The present disclosure relates to ordered clusters which takes user preferences into consideration. 
     SUMMARY 
     A framework for clustering is described herein. In accordance with one aspect, a data set having x number of objects, and preference information of a user is provided to a clustering tool. The clustering tool may calculate preference degrees between objects in the data set. In addition, similarity measures of objects in the data set may be calculated. Clusters of objects may then be generated from the data set. 
     In accordance with another aspect, a clustering system for determining an order of clusters is provided. The clustering system includes an input module, which includes user preference information of a user, a preference degree module for calculating preference degrees of a data set containing x number of objects based on user preference information, a similarity module for determining similarity measures of objects in the data set, and a clustering module for generating clusters of objects based on similarity measures. 
     With these and other advantages and features that will become hereinafter apparent, further information may be obtained by reference to the following detailed description and appended claims, and to the figures attached hereto. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Some embodiments are illustrated in the accompanying figures. Like reference numerals in the figures designate like parts. 
         FIG. 1  shows a simplified diagram of an exemplary environment or architecture; 
         FIG. 2  shows a simplified block diagram of an embodiment of an ordered clustering framework; 
         FIG. 3 a    shows a visual representation of preference degrees from pairwise comparison; 
         FIG. 3 b    shows an example of a similarity network; 
         FIG. 4  shows an exemplary process flow for generating clusters; 
         FIGS. 5 a -5 b    illustrate an example of an implementation of clustering; 
         FIG. 6  shows a graph which represents the number of clusters as a function of betweenness-threshold for a data set; 
         FIG. 7  shows a simplified pseudo code illustrating a clustering process of an embodiment of a clustering framework; 
         FIGS. 8 a - b    show examples of determining the order of clusters; and 
         FIG. 9  shows an exemplary embodiment of a preference input graphical interface for collecting preference information from a user. 
     
    
    
     DETAILED DESCRIPTION 
     In the following description, for purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present frameworks and methods and in order to meet statutory written description, enablement, and best-mode requirements. However, it will be apparent to one skilled in the art that the present frameworks and methods may be practiced without the specific exemplary details. In other instances, well-known features are omitted or simplified to clarify the description of the exemplary implementations of present frameworks and methods, and to thereby better explain the present frameworks and methods. Furthermore, for ease of understanding, certain method steps are delineated as separate steps; however, these separately delineated steps should not be construed as necessarily order dependent or being separate in their performance. 
       FIG. 1  shows a simplified diagram of an exemplary environment or architecture  100 . The environment  100  may have a distributed architecture, such as a client-server architecture. The environment, in one implementation, includes a communication network  110 . The communication network, for example, may be the World Wide Web (WWW or Web). Other types of communication networks or combination of networks may also be useful. 
     The environment includes a server  120 . A server may be a computer with a memory and a processor. Various types of computers may be employed for the server. For example, the computer may be a mainframe, a workstation, as well as other types of processing devices. The memory of a computer may include any memory or database module. The memory may be volatile or non-volatile types of non-transitory computer-readable media, such as magnetic media, optical media, random access memory (RAM), read-only memory (ROM), removable media, or any other suitable local or remote memory component. 
     The server  120 , for example, may include a plurality of interconnected servers. For example, the servers are interconnected by a communication network. The communication network may be an internet, an intranet, a local area network (LAN), a wide area network (WAN) or a combination thereof. The servers may be located in a single or multiple locations. The interconnected servers may be collectively referred to as a server. 
     The server  120  is configured to store and process resources requested by client devices  130 . As shown, the environment includes client devices  130   a - 130   c . It is understood that the environment may include other number of client devices. A client device may be a local computing device with, for example, a local memory and a processor. The memory may be volatile or non-volatile types of non-transitory computer-readable media, such as magnetic media, optical media, random access memory (RAM), read-only memory (ROM), removable media, or any other suitable local or remote memory component. Various types of processing devices may serve as the client device. For example, the client device may be a PC, a tablet PC, a workstation, a network computer, or a mobile computing device, such as a laptop, a tab or a smart phone. Other types of processing devices may also be used. It is understood that client devices may be different types of client devices. 
     The environment of the client device may be referred to as a local or native environment. A client (or end-user) and client device may be used interchangeably. For example, when referring to an end-user, it is understood that the end-user connects to the communication network using a client device. The client device may be referred to as the client side while the server may be referred to as the server side. It is understood that client devices need not be of the same type. For example, some client devices may be mobile devices running on different types of platforms, such as iOS or Android, while other client devices may be desktop or laptop computers. 
     In one implementation, the local environment of the client device includes a user agent  135 . The user agent, for example, may be a web browser. The browser facilitates communication with the server. For example, the browser initiates communication to a web server by making a request for a specific resource using, for example, a Hypertext Transfer Protocol (HTTP) and the server responds with the content of that resource. Communication with the server, for example, may be through internet connection. The internet connection may be using a mobile telecommunication network, such as a 4G network. Other types of connections to the server may also be useful. An end-user may access the server by, for example, having a user account. 
     In other implementations, the environment  100  may be a cloud computing environment. In such cases, the interconnected servers  120  form a cloud. The cloud, for example, hosts and processes resources, such as applications and data, as well as other resources. Different servers may be used to store or process different resources. Such hosting and processing may be considered as cloud services. Various types of cloud services may be provided. The cloud services may be provided in a public, private or hybrid network. The cloud services may be provided by a cloud service provider. For example, the cloud services may be SAP HANA Cloud Platform provided by SAP SE. Other types of clouds and cloud providers may also be useful. A client device  130  accesses resources on the cloud using, for example, a browser  135 . Other configurations of the environment may also be useful. 
     The environment  100  includes a framework  150  for generating clusters. The framework, for example, is a software tool. For example, the framework is a software tool which analyzes items or objects and groups them into clusters. In one implementation, the framework groups items into ordered clusters taking into consideration a user&#39;s preference. The framework, for example, may be an ordered clustering framework. The ordered clustering framework generates ordered clusters taking into consideration a user&#39;s preference. In one implementation, the framework is a network-based ordered clustering framework. For example, the framework generates ordered clusters based on a user&#39;s preference using a network-based clustering technique. Various types of network-based clustering techniques, such as Girvan-Newman, OSLOM, modularity maximization, as well as others, may be employed. 
     The framework, in one implementation, resides on the server  120 . Locating the framework in other locations may also be useful. For example, the framework may be a stand-alone framework and resides on an end-user device. The framework may be configured to receive a list of objects for clustering based on user preferences. The framework includes memory for storing user preference information provided by users as well as clustering results. 
       FIG. 2  shows a simplified block diagram of an embodiment of a clustering framework  150 . In one implementation, the clustering framework is a network-based ordered clustering framework. As shown, the framework includes a preference degree module  252 , a similarity module  254 , a clustering module  256 , and an ordering module  258 . The ordered clustering framework receives and processes a data set  235 . The data set may be referred to as data set A. Data set A includes items or objects of interest. For example, data set A includes objects a 1 -a x , where a represents an object and x equals the number of objects in the data set A. The framework processes the objects in data set A and generates a list of ordered clusters  265  using the various framework modules according to preference information  245  of the user, such as a decision maker. 
     The data set can be derived using various techniques. For example, the type of objects in the data set may depend on the application of the clustering framework. For example, objects may be goods for sale listed by a seller or a group of sellers for identifying specific items for sale, information used in management of building resources, traffic information of vehicles for traffic management, employee information of a company for human resource management, supplier information for procurement management. Other types of objects may also be useful. The data set may be derived from a data acquisition system, such as a sensor network, a database containing a list of items of interest, data mining or from other techniques, including, connected objects such as Internet of Thing (IoT) devices. 
     The preference degree module  252  constructs preference degrees K among the objects in the data set. In one implementation, constructing the preference degrees is based on preference information  245  provided by the user. Preference information may include indifference, preference, or veto thresholds. A veto threshold, for example, may be used to exclude objects from consideration by comparing to other objects. Other types of preference information may also be useful. The various preference information may be provided by the user using a preference input module  262 . For example, the preference input module includes a preference input graphical interface (GI) for users to input preference information  245 . Other techniques for providing preference information of the user or decision maker may also be useful. For example, a wizard or non-graphical interface may be used to enable the user to input preference information. 
     In other implementations, the preference input module  262  may be a preference information retrieval module. For example, the preference information retrieval module may be an intelligent module for retrieving user preference information. The intelligent module may be based on a recommendation or statistical aggregation system. For example, the intelligent module may analyze historical user information to determine user preference. User preference may be based on average of preferences of users that are collected. Other techniques for intelligently acquiring user preference information may also be useful. 
     Constructing the preference degrees among the objects includes performing pairwise comparisons of objects a 1 -a x  in the data set A based on user preference information. Pairwise comparisons of objects include comparing an object in the data set with other objects of the data set. Pairwise comparisons include comparing each object as an ordered pair with each and every other object in the data set. For example, a preference degree π ij  corresponds to the preference degree of object a i  compared to object a j . The preference degrees from the pairwise comparisons may be stored in a matrix Π. 
     Preference degrees have values between 0 and 1. Furthermore, preference degrees are not symmetrical. This asymmetry enables a pairwise comparison to have three different situations: 
     1) π ij ≈π ji ≈0; 
     2) π ij ≈π ji ≈0.5; or 
     3) π ij &gt;&gt;π ji . 
     In situation 1, preference degrees for comparison between two objects are about the same in both directions and equal to about 0. This indicates that there is no preferred object between the two compared objects and the compared objects are considered indifferent by the decision maker, such as the user. An indifferent relationship may be expressed as P I : a i P I a j , where P I  is the indifference relationship between object a i  and object a j . In situation 2, preference degrees for comparison between two objects are about the same in both directions and equal to about 0.5. This indicates that there is no preferred object between the two compared objects, but both object a i  and object a j  of the comparison have good and weak points. In such cases, the objects are considered incomparable by the decision maker. An incomparable relationship may be expressed as P J : a i P J a j , where P J  is the incomparability relationship between object a i  and object a j . 
     In situation 3, a preference degree for comparison between two objects is much greater in one direction than the other. This indicates that one object is preferred over the other object. For example, object a i  is preferred over object a j  by the decision maker, such as the user. A preferred relationship may be expressed as P P     +   : a i P P +a j , where P P     +    is the preferred relationship between object a i  to object a j . On the other hand, in the case where object a j  is preferred over a i , the relationship may be a preferred-by relationship. For example, a i  is preferred by a j . A preferred-by relationship may be expressed as a i : a i P P −a j , where P P−  is the preferred-by relationship of object a i  by object a j . For example, P P−  is the preference degree by object j to object i. 
     Various relationships between two actions (two directional comparisons of two objects) may exist as follows based on preference degrees when λ is used as threshold, where 0.5&lt;λ&lt;1: 
     1) a i P I a j   |π ij −π ji |&lt;λ and π ij &lt;λ; 
     2) a i P J a j   |π ij −π ji |&lt;λ and π ij &gt;λ; and 
     3) a i P P +a j   | ij −π ji |&gt;λ and π ij &gt;λ a j P P −a i . 
     The parameter λ is a technical parameter. It has a value from 0.5 to 1. This parameter may be defined by the user. 
     In one implementation, preference degrees may be computed based on a set of criteria. For example, the objects are evaluated by a set criteria F={f 1 , f 2 , . . . , f y }), where the set includes y number of criteria. The criteria may depend on the objects being compared. For example, a retail object may have criteria which includes price, material, quality, and customer evaluations. In the case of an automobile, criteria may include price, miles per gallon, color, convertible, sedan, rear wheel drive and engine type. A criterion, for example, may be maximized or minimized. The maximizing or minimizing may depend on the user. For example, if the user is a seller, the price criterion of the object may be maximized. On the other hand, if the user is a buyer, the price criterion of the object may be minimized. Additionally, some criterion of a set, for example, may be maximized while others from the same set may be minimized. 
     A decision maker, such as a user, may provide parameters for each criterion f m . In one implementation, the parameters include:
         1) w m  (the normalized weight of each criterion in the set);   2) q m  (the indifference threshold that reflects a threshold under which the difference of performances between objects is considered as insignificant);   3) p m  (the preference threshold that reflects a threshold above which the difference of performances between objects lead to prefer strongly the object with the highest value on that criterion); and   4) veto thresholds (a veto threshold may be associated with each criterion).
 
Providing other parameters may also be useful.
       

     Unicriterion preference degrees are computed. A unicriterion preference degree P ij   k  reflects how strongly object a i  is preferred over object a j  based on criterion f k . Unicriterion preference degrees have values between 0 and 1. A unicriterion preference degree P ij   k  may be a function of the difference between the evaluations of objects, such as f k (a i )−f k (a j ). The higher the difference, the stronger the unicriterion preference. The unicriterion preference degree for criterion f k  of objects a i  and a j  may be calculated by Equation 1 as follows: 
     
       
         
           
             
               
                 
                   
                     P 
                     ij 
                     k 
                   
                   = 
                   
                     { 
                     
                       
                         
                           0 
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     f 
                                     k 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       a 
                                       i 
                                     
                                     ) 
                                   
                                 
                               
                               - 
                               
                                 
                                   f 
                                   k 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     a 
                                     j 
                                   
                                   ) 
                                 
                               
                             
                             ≤ 
                             
                               q 
                               k 
                             
                           
                         
                       
                       
                         
                           
                             
                               [ 
                               
                                 
                                   
                                     f 
                                     k 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       a 
                                       i 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     f 
                                     k 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       a 
                                       j 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   q 
                                   k 
                                 
                               
                               ] 
                             
                             
                               [ 
                               
                                 
                                   p 
                                   k 
                                 
                                 - 
                                 
                                   q 
                                   k 
                                 
                               
                               ] 
                             
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 q 
                                 k 
                               
                             
                             &lt; 
                             
                               
                                 
                                   f 
                                   k 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     a 
                                     i 
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 
                                   f 
                                   k 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     a 
                                     j 
                                   
                                   ) 
                                 
                               
                             
                             &lt; 
                             
                               p 
                               k 
                             
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     f 
                                     k 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       a 
                                       i 
                                     
                                     ) 
                                   
                                 
                               
                               - 
                               
                                 
                                   f 
                                   k 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     a 
                                     j 
                                   
                                   ) 
                                 
                               
                             
                             ≥ 
                             
                               p 
                               k 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     1 
                   
                   ) 
                 
               
             
           
         
       
     
     The unicriterion preference degree is calculated for all criteria with respect to the pairwise comparison of object a i  versus object a j . For example, the unicriterion preference degree is calculated for f 1 −f y  for object a i  compared to object a j . After unicriterion preference degrees are calculated, they are aggregated. Equation 2 below shows aggregation of unicriterion degrees to produce a preference degree π ij : 
     
       
         
           
             
               
                 
                   
                     π 
                     ⁡ 
                     
                       ( 
                       
                         
                           a 
                           i 
                         
                         , 
                         
                           a 
                           j 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       π 
                       ij 
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         y 
                       
                       ⁢ 
                       
                         
                           w 
                           k 
                         
                         * 
                         
                           P 
                           ij 
                           k 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ) 
                 
               
             
           
         
       
     
     The preference degree π ij  represents the global comparison of object a i  versus object a j . Preference degrees π are calculated for other object pairs in the data set A to produce preference degrees of other pairwise comparisons, which may be stored in the matrix Π. 
     To illustrate the asymmetry of preference degrees, an exemplary data set A with a set of criteria is provided below. Table 1 below illustrates an example of a data set with four objects (e.g., a x =4) and 2 criteria (e.g., f y =2): 
                                 TABLE 1                       criterion 1   criterion 2                                                a   0   0       b   5   0       c   0   5       d   10   10                    
As shown, data set A includes four objects (a, b, c, d) and the set of criteria includes two criteria (criterion  1 , criterion  2 ). The values for each criterion as it relates to the objects are provided. The values may depend on the criterion. For example, if the criterion is quality, the value would be a quality rating of the object.
 
     Two different scenarios are provided. Scenario  1  relates to a first user and scenario  2  relates to a second user. The parameters of w, q and p of scenario  1  are as follows: 
     w 1 =w 2 =0.5; 
     q 1 =q 2 =0; and 
     p 1 =p 2 =0. 
     The parameters of scenario 2 are as follows: 
     w 1 =0.333, w 2 =0.66; 
     q 1 =0.5, q 2 =0; and 
     p 1 =0.5, p 2 =0. 
     Regarding subscript  1  and  2 , they relate to the criterion. For example, subscript  1  relates to the first criterion, while subscript  2  relates to the second criterion. 
     Preference degrees for scenario  1  are calculated for the different object pairs and provided in Table 2 as follows: 
                                         TABLE 2                       a   b   c   d                                                        a       0   0   0       b   1       0.5   0       c   1   0.5       0       d   1   1   1                    
Table 2, for example, may be an example of a preference degree matrix Π. Clearly, as shown in Table 2, the preference degrees are asymmetrical. For example, π ab =0 while π ba =1. For pairwise comparisons of the same object, the preference degrees are left blank. Alternatively, pairwise comparisons of the same object may be equal to 0.
 
     Preference degrees for scenario 2 are calculated for the different object pairs and provided in Table 3 as follows: 
                                         TABLE 3                       a   b   c   d                                                        a       0   0   0       b   0       0   0       c   0.33   0.33       0       d   1   0.33   1                    
Clearly, as shown in Table 3, the preference degrees are asymmetrical. For example, π ac =0 while π ca =0.33.
 
       FIG. 3 a    shows an exemplary color chart  305  of preference degrees between objects. The preference degrees are for a data set with 160 objects. The various colors of the preference degrees range from blue to red. The color range corresponds to preference degree value from 0 to 1. In one implementation, the color blue represents a preference degree π ij =0 while the color red represents a preference degree π ij =1. As the colors transitions from blue to red, the preference degree π ij  increases from 0 to 1. From the chart, pairwise comparisons are not symmetrical. For example, the preference degree π 100,20 =0 (at  315 ) while preference degree π 20,100  (at  325 ) has a higher value than 0, due the difference in colors. 
     Referring back to  FIG. 2 , after the preference degrees are constructed, the similarity module determines similarity measures or indices of pairwise comparisons. A similarity measure is a measure of distances between two objects of the pairwise comparison, such as a i  and a j . The similarity measures take into account the preferred and preferred-by relationships from the preference degrees analysis. In one implementation, the similarity measures are symmetrical measures. Providing symmetrical measures reduce information while capturing global behavior of an object compared to other objects. 
     In one implementation, a similarity measure between two objects is determined by Equation 3 as follows: 
                     S   ⁡     (     a   ,   b     )       =         ∑   1   4     ⁢            P   R   a     ⋂     P   R   b                   A                  (     Equation   ⁢           ⁢   3     )               
where
 
     a is the first object of the pairwise comparison (e.g., a i ), 
     b is the second object of the pairwise comparison (e.g., a j ), 
     R is from 1-4 which is equal to I, J, P +  and P − , 
     P R   a ={x|aP R x, ∀xΕA} for the relationships P I , P J , P P     +    and P P     −   , 
     |A| is the total number of objects in set A, 
     |.| represents the number of elements/objects in the set, 
     x is element or object x, 
     x may be a, b, or any element of the set A. 
     From equation 3, the set of preferences P I , P J , P P+  and P P−  may be computed for each object to determine the similarity measures. Table 4 shows the different sets for a data set containing objects a, b, c, and d: 
     
       
         
           
               
               
               
               
               
             
               
                   
                 TABLE 4 
               
               
                   
                   
               
               
                   
                 P I , 
                 P J   
                 P P+   
                 P P−   
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 a 
                 a 
                 — 
                 — 
                 d, b, c 
               
               
                 b 
                 b 
                 c 
                 a 
                 d 
               
               
                 c 
                 c 
                 b 
                 a 
                 d 
               
               
                 d 
                 d 
                 — 
                 a, b, c 
                 — 
               
               
                   
               
            
           
         
       
     
     From Table 4, regarding element a,
         1) P I (a)=all the elements of set {a, b, c, d} to which a is indifferent, which is ={a},   2) P J (a)=all the elements of set {a, b, c, d} to which a is incomparable to, which is ={ } or empty,   3) P P+ (a) all the elements of set {a, b, c, d} to which a is preferred to which is ={ } or empty, and   4) P P− (a) all the elements of set {a, b, c, d} which are preferred to a, which is ={d, b, c}.
 
The preference set can be repeated for all elements, such as elements b, c and d, as shown in Table 4.
       

     Based on Equation 3, considering P P+   a ∩P P+   b , provides all the elements to which objects a and b are preferred to. The intersection set of the elements to which a is preferred and the set of elements to which b is preferred are analyzed. 
     If two elements are identical, then all the relationships to all the elements will be similar. As such, the sum of |P i   a ∩P i   b |, will be equal to |A|. This results in S(a,a)=1. The similarity measures S of pairwise comparisons may be stored in a similarity matrix δ. Table 5 as follows shows an example of a similarity matrix containing objects a, b, c, and d: 
                                     TABLE 5               S(,)   a   b   c   d                                                    a   1   0   0   0       b   0   1   0.5   0.25       c   0   0.5   1   0.25       d   0   0.25   0.25   1                    
For instance, the exemplary similarity matrix in Table 5 may be for scenario  1  as described above.
 
     The similarity measures indicate how strong the relation is between two objects. The higher the value is, the stronger the relation is. For example, as shown in Table 5, S(b,c)=0.5 while S(b,d) is 0.25. This means that b has a stronger relation to c than to d. 
     A similarity measure takes the preference relations directly into account. Taking the preference relations directly into account also takes the orientation of the criteria into account. This results in all the measures being symmetrical. For example, objects in a group are considered similar since they are preferred to and preferred by the same objects. 
     A distance matrix Δ can be derived from the similarity matrix. For example, the value in a distance matrix indicates the distance between two objects. The higher the value is, the weaker relation is. In other words, the distance values is the inverse of the similarity measures. The distance matrix, in one implementation, is derived from taking the reciprocal of the similarity measures. For example, D(x,y)=1/S(x,y), if S(x,y) equals to zero, then D(x,y) may be defined to be equal to infinity. Table 6 below shows an example of a distance matrix derived from the similarity matrix of Table 5: 
     
       
         
           
               
               
               
               
               
             
               
                 TABLE 6 
               
               
                   
               
               
                 D(,) 
                 a 
                 b 
                 c 
                 d 
               
               
                   
               
             
            
               
                 a 
                 1 
                 +∞ 
                 +∞ 
                 +∞ 
               
               
                 b 
                 +∞ 
                 1 
                 2 
                 4 
               
               
                 c 
                 +∞ 
                 2 
                 1 
                 4 
               
               
                 d 
                 +∞ 
                 4 
                 4 
                 1 
               
               
                   
               
            
           
         
       
     
     Having both similarity and distance matrices provide flexibility. For example, some clustering techniques uses a similarity matrix while others use a distance matrix. In the case of the Girvan-Newman technique, a distance matrix is used. On the other hand, an OSLOM clustering technique uses a similarity matrix. 
     As discussed, the value in the distance matrix indicates how strong the relation is between an object and another object. Using the values in the distance matrix, a similarity network can be built. The network includes nodes for objects of the data set. An edge of the network is a relation between two objects. An edge is weighted by the corresponding value in the distance matrix. For example, each node is an object, with each edge being weighted by the corresponding value in the distance matrix. 
       FIG. 3 b    shows an example of a similarity network  300 . The similarity network reflects scenario  1 . The preference table (Table 2) for scenario  1  is shown with four objects corresponding to four nodes  324  of the network. Edges  334  with directions and distances are shown reflecting the directional relationship of the pairwise comparison. The distances reflect the distances in Table 2, with corresponding weights shown in Table 1. 
     Referring back to  FIG. 2 , the clustering module  256  generates clusters based on the similarity network. The clustering module may employ various clustering techniques to generate the clusters. The clustering technique finds a subset of nodes within which connections are dense and other subset of nodes whose connections are sparse. Dense connections refer to many connections between nodes while sparse connections refer to few connections between nodes. In one implementation, the clustering technique includes a Girvan-Newman technique. The Girvan-Newman technique is based on betweenness centrality (BC) of edges in the network. The betweenness centrality is equal to the number of shortest paths from all nodes to all others that pass through that edge, as expressed below by Equation 4: 
                     BC   ⁡     (   e   )       =       ∑       s   ≠   t     ∈   V       ⁢         σ   st     ⁡     (   e   )         σ   st                 (     Equation   ⁢           ⁢   4     )               
where
 
     σ st  is the total number of shortest paths from node s to node t, 
     σ st (e) is the number of those paths that pass through edge e, and 
     V refers to vertex set (node set). 
     The betweenness is a property of an edge. For example, each edge has a betweenness centrality value. The betweenness centrality values may be stored in, for example, a BC matrix β. 
     Generating clusters includes various processing steps.  FIG. 4  shows an exemplary process flow  400  for generating clusters using the Girvan-Newman technique. Other clustering techniques may also be useful. In one implementation, the betweenness of existing edges in the similarity network are calculated at step  413 . For example, betweenness of all existing edges of the network is calculated using Equation 4. At step  423 , the edge with the highest betweenness is removed. After removing the edge, betweenness values of edges affected by the removal are recalculated at step  433 . At step  443 , the process determines if there are any edges remaining. If there are, the process returns to step  423 . If there are no more edges, the process ends at step  453 , resulting in clusters. 
       FIGS. 5 a -5 b    illustrate an example of an implementation of clustering. Referring to  FIG. 5 a   , a similarity network  510  is shown. The similarity network shows nodes with betweenness.  FIG. 5 b    shows the similarity network  520  after applying Girvan-Newman clustering technique. As shown, the nodes are grouped into two clusters  532  and  534 . 
     Referring back to  FIG. 2 , the clustering module receives an input parameter k. The input parameter k relates to the number of clusters to be generated by the clustering module. The input parameter k, for example, may be provided by the decision maker, such as the user. The input parameter k, in one implementation, is related to the betweenness-threshold. For example, in the case of a clustering module employing a Girvan-Newman technique, k is indirectly specified by the betweenness-threshold or BC-threshold. The betweenness-threshold indicates which BC values are filtered out from the BC matrix β. In one implementation, low BC values (values below the betweenness-threshold) are filtered out from the matrix. For example, the cluster module preprocesses the BC values to remove edges having BC values below the BC-threshold. 
     The betweenness-threshold is selected to produce about n clusters. In one implementation, the betweenness-threshold is selected to produce about 3-4 clusters (e.g., n=3-4). Selecting a betweenness-threshold which produces other values of n may also be useful. For example, n may be any positive integer. The betweenness-threshold is from 0-1. In one implementation, the betweenness-threshold is about 0.30 to about 0.8. Preferably, the betweenness-threshold value may be about 0.35-0.8. More preferably, the betweenness-threshold value may be about 0.35-0.5. Other betweenness-threshold values are also useful. 
       FIG. 6  illustrates a graph  600  which represents the number of clusters as a function of betweenness-threshold for an exemplary data set. As can be seen, the chart includes “unstable” zones A and B, represented by quick changes in the number of clusters with relatively small changes of the threshold. Also, the chart includes a “stable” zone C, represented by relatively stable number of clusters with relatively large changes in threshold. The stable zone indicates a “natural” number of clusters in the dataset. The natural number, for example, may be about 3-4. As shown, the stable zone C for the exemplary data set has a threshold value between about 0.3-0.8. 
       FIG. 7  shows a simplified pseudo code  700  illustrating a clustering process of an embodiment of a clustering framework. The clustering framework, for example, may be a function which can be called to perform clustering on a data set, such as data set A. As shown, the framework function is named “clustering”. The clustering function receives preference information from a user, such as the decision maker. The preference, for example, may include the weight of the various criteria as well as indifference and preference thresholds. Other preference information, such as betweenness-threshold or k as well as λ may also be provided. The preference information, for example, may depend on the clustering technique employed. For example, the betweenness-threshold may be provided in the case of a clustering framework employing a Girvan-Newman technique. In other cases, k is related or equal to the number of clusters to generate by the function. 
     When the cluster function is called, preference degrees π ij  between all objects of the data set are calculated based on the preference information. For example, preference degrees are calculated using Equation 2. The preference degrees may be stored in a preference degrees matrix Π. After preference degrees for the data set are calculated, preference relationships of the objects are defined. For example, P I , P J , P P+  and P P−  are defined based on a threshold λ. The threshold λ, for example, may be set at 0.5. 
     The process continues to compute the sets P R   a ={x|aP R x, ∀xΕA} for the relationships P I , P J , P P     +    and P P     −   . Afterwards, the similarity measures S(a i ,a j ) are calculated. The similarity measures may be stored in a similarity matrix δ. A distance matrix Δ may be derived from the similarity matrix. A similarity network may be constructed from the distance matrix. For example, the similarity network may be similar to that described in  FIG. 3   b.    
     In one implementation, clusters are generated. The clusters are generated using a Girvan-Newman technique. When employing a Girvan-Newman technique, a betweenness-threshold is defined or provided by the user. Thereafter, betweenness of edges are computed. For example, betweenness of edges of the similarity network are computed using Equation 4. Betweenness values below the betweenness-threshold value are removed. The edge with the highest betweenness value is removed. Calculating and removing the edge with the highest betweenness value is repeated until no edges are left. This results in clusters, which are displayed by the function. 
     Referring back to  FIG. 2 , the ordering module  258  determines an order of the clusters produced by the clustering module. In one implementation, determining the order of the clusters includes counting the number of preference edges between a pair of clusters. In one implementation, the number of preference edges between each pair of clusters produced by the clustering module is determined. 
       FIG. 8 a    illustrates an example of counting preference edges between a pair of clusters (cluster  1  and cluster  2 ). Counting preference edges between a pair of clusters include counting preference edges from a first cluster (cluster  1 ) to the second cluster (cluster  2 ) as well as from the second cluster (cluster  2 ) to the first cluster (cluster  1 ). Preference edges within a cluster are ignored. The cluster having the greater number of preference edges to the other clusters may be considered the cluster with the stronger preference. 
     As shown, cluster  1  has five preference edges to cluster  2 , as indicated by the direction of the preference edges (arrow points). On the other hand, cluster  2  has one preference edge to cluster  1 . Since cluster  1  has a greater number of preference edges, the preference from cluster  1  to cluster  2  is stronger than the preference from cluster  2  to cluster  1 . The order of the clusters may be based on the number of preferences edges. The higher the number of preference edges, the higher the cluster in the preference order. For example, cluster  1  would be prior to cluster  2  in the order (cluster  1 =&gt;cluster  2 ). 
     In some implementations, preference values of the preference edges may be used in determining preference order. For example, after counting the preference edges, the preference values of the preference edges are added to obtain a sum of preference values of the preference edges. The cluster with the higher sum of preference values of preference edges would be prior in the preference order. For example, preference edges of cluster  1  have preference values of 0.1, 0.2, 0.3, 0.4 and 0.5. The sum of the preference values of cluster  1  preference edges is 1.5. On the other hand, the preference edge of cluster  2  has a preference value of 0.5. As such, cluster  1  is prior to cluster  2  in the order (cluster  1 =&gt;cluster  2 ). 
     In some instances, the preference order may result in a circle among clusters. For example, as shown in  FIG. 8 b   , cluster  1  is prior to cluster  2  (cluster  1 =&gt;cluster  2 ), cluster  2  is prior to cluster  3  (cluster  2 =&gt;cluster  3 ), cluster  3  is prior to cluster  1  (cluster  3 =&gt;cluster  1 ). In one implementation, the weakest link is removed. In the example, the link between cluster  1  and  3  is the weakest of the links with respect to the sum of the preference values. As such, the link between clusters  1  and  3  is removed, as indicated by the dotted arrow. After the removal of the weakest link, the order is cluster  3  =&gt;cluster  2 =&gt;cluster  1 . 
     As discussed, preference information, such as the various parameters are provided to the clustering framework. The preference information may include the following parameters for the different factors or criteria: 
     w=weight of a criterion; 
     q=indifference threshold of a criterion; and 
     p=preference threshold of a criterion. 
     Other information, including λ, may also be provided as well. The preference information is provided by the user, such as the decision maker. A preference input module may be provided to receive the preference information from the user. For example, the preference input module may include a preference input GI for users to input preference information. 
       FIG. 9  shows an exemplary embodiment of a preference input GI  900  for collecting preference information from a user, such as the decision maker. As shown, the input GI includes a menu panel  911 . The menu panel, for example, includes a filter, preference and book items for selection by the user. The filter item enables a user to filter out unwanted objects. For example, in the case where objects are restaurants, a user may use the filter item to create a list of available restaurants. The book item may be selected to, for example, make a booking or reservation with a selected object, such as a restaurant or a hotel. 
     When the preference item is selected, a preference pane  921  and a preference setting pane  931  are displayed in the GI. The preference pane includes various preferences or criteria associated with the data set. For example, the preferences may be related to a data set for restaurants. The preferences may include a customer review criterion, price criterion, neighborhood criterion, quality criterion, location criterion and promotions criterion. Each criterion receives a weight category. The weight categories may be most important  933 , medium important  937  and less important  939 . This can be used by the user to indicate the weight of each criterion instead of giving precise values. In some implementations, a user may provide specific weight values. Other techniques for providing preference information may also be useful. 
     The clustering framework may be embodied as an application. For example, the clustering framework may be embodied as a software application. The source code of the applications may be compiled to create an executable code. The codes, for example, may be stored in a storage medium, such as one or more storage disks or in memory of a server and/or end-user devices. Other types of storage media may also be useful. 
     Although the one or more above-described implementations have been described in language specific to structural features and/or methodological steps, it is to be understood that other implementations may be practiced without the specific features or steps described. Rather, the specific features and steps are disclosed as preferred forms of one or more implementations.