Abstract:
A categorization data structure is described that relates to two groups of individuals. For each of two or more categories, the data structure contains (1) information identifying individuals of the first group assigned to the category, and (2) information identifying individuals of the second group assigned to the category. For each category, the information can be used to adjust the individuals of the first group assigned to the category based upon comparing the proportion of all of the individuals of the second group that are assigned to the category to the proportion of all of the individuals of the first group that are assigned to the category.

Description:
TECHNICAL FIELD 
     The described technology is directed to the field of manipulating data sets, such as data sets corresponding to attributes and/or responses of survey respondents. 
     BACKGROUND 
     In order to evaluate and guide the design and promotion strategy for a product or service, many companies use market research surveys. In a market research survey, a set of questions is posed to each of a number of people, called “respondents.” Survey questions are often directed to the respondent&#39;s personal tastes, behaviors, and preferences as they relate to the product or service. The responses to a survey&#39;s questions, aggregated across its respondents, is typically used as an estimate of how a much larger population, such as the population of all possible customers for the product or service in a particular geographic region, would in the aggregate answer the survey&#39;s questions. The extent to which this estimate is accurate is sometimes referred to as the level of representativeness of the survey&#39;s responses. 
     Because it is generally not possible to measure the level of representativeness of a survey&#39;s responses, it is common to use the level of representativeness of identifiable attributes of a survey&#39;s respondents as a proxy for the level of representativeness of the survey&#39;s responses. As one example, for a survey that is to represent the tastes, behaviors, and preferences of the population of a particular geographic region, it would be typical to seek a number of respondents residing in each subregion of the geographic region (such as each state, ZIP code, or area code) that is proportional to the total number of people residing in the subregion. In this way, the distribution of different values of the subregion variable for the set of respondents would match the distribution of different values of the subregion variable for the population of the region. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility operates. 
         FIG. 2  is a flow diagram showing steps typically performed by the facility in some embodiments to reduce the dissimilarity of a subject data set with a reference data set. 
         FIG. 3  is a table diagram showing sample contents of a subject data set and a reference data set. 
         FIG. 4  is a flow diagram showing steps typically performed by the facility in some embodiments to decompose each major variable that is in both the reference and subject data sets into its complete set of unique binary combinations, also called minor variables. 
         FIG. 5  is a table diagram showing the result of decomposing a sample major variable into minor variables. 
         FIG. 6  is a flow diagram showing steps typically performed by the facility in some embodiments in order to generate a decision tree. 
         FIG. 7  is a flow diagram showing steps typically performed by the facility in order to complete a candidate tree in accordance with step  605  in some embodiments. 
         FIGS. 8 and 9  are data structure diagrams showing sample candidate decision trees during their construction by the facility. 
     
    
    
     DETAILED DESCRIPTION 
     The inventors have recognized that in some cases it is not possible to control the geographic subregions of the respondents, as is often true for surveys presented online. The inventors have also recognized the desirability of providing survey results that are highly representative of arbitrarily-selected sets of respondent attributes; even in cases where it is possible to control the geographic subregions of the respondents, other important attributes of these respondents are often skewed. 
     Accordingly, a software and/or hardware facility for reducing the dissimilarity of a first multivariate data set—called the “subject data set”—with a second multivariate data set—called the “reference data set”—(“the facility”) is described. As an example, in some embodiments, the facility adapts a subject data set representing the distributions of each of a number of attributes among a set of actual survey respondents to minimize its dissimilarity with a reference data set representing the distributions of attributes in a modeled population. The facility can then proceed to use these adaptations of the first data set to transform survey responses received from the set of actual respondents into the survey responses that would be expected from a set of respondents whose attribute distributions closely matched the attribute distributions of the modeled population. For example, the facility can be used to transform survey responses received from a first source into those that would be expected from a second source such as Global Market Insite, Inc. of Bellevue, Wash. (“GMI”), or into those that would be expected from respondents to such generalized surveys as the U.S. Census or the National Opinion Research Center&#39;s General Social Survey (“GSS”). 
     In some embodiments, the facility minimizes a measure of dissimilarity between data sets that takes into account both each variable&#39;s “marginal distribution” in each data set—that is, its distribution standing alone—and each variable&#39;s “interrelationship” with every other variable in each data set—the degree to which a change in one variable&#39;s distribution is associated with a change in another variables distribution. 
     In some embodiments, the facility constructs a decision tree that specifies how attribute distributions are to be partitioned for both the reference and subject data sets and adjusts the observations within each partition of the subject data set to produce a meaningful reduction in the total dissimilarity between the adjusted subject data set and the reference data set, such as a maximum reduction. In various embodiments, the facility uses various approaches to construct decision trees, including fully-automated approaches such as an exhaustive approach and a progressive Monte Carlo approach, as well as partially-automated approaches such as those that permit a human user to specify a portion of the decision tree. In some embodiments, the decision tree is a binary tree in which each interior node corresponds to a single attribute, or “variable” and has two children: a first child that corresponds to one proper subset of the possible values of the variable, and a second child that corresponds to all the remaining possible values of the same variable. Respondents, also called “observations,” are said to be mapped to a given node of the tree if they satisfy all of the conditions imposed by the nodes of the tree that are on the path from the root node of the tree to the node in question. In particular, each observation is said to map to a single leaf node of the tree. 
     In some embodiments, the facility uses the decision tree as a basis for weighting survey responses from actual respondents based upon the identity of the leaf node of the decision tree to which each respondent corresponds. In some embodiments, the facility uses the decision tree as a basis for soliciting and/or accepting survey responses from actual respondents based upon the identity of the leaf of the decision tree to which each respondent corresponds. 
     In some embodiments, the facility uses the decision tree that it constructs to profile the attribute distribution of a source of survey responses. As additional responses are received from the source, the facility monitors for significant deviation in the proportion of new responses mapped to each leaf node by the decision tree and, if it detects significant deviation from the proportions of responses from the source mapped to the leaf node, triggers a warning and may trigger the generation of a new decision tree for the source. 
     In some embodiments, the facility uses its comparison of actual respondents to model populations in order to identify sets of actual respondents that are complementary, i.e., actual respondent sets whose members can be aggregated to more closely match the attribute distributions of the modeled population. 
     In some embodiments, the facility applies the described techniques in order to balance two groups of respondents with respect to a specified set of attributes, such as respondents who are candidates for testing and control groups in medical clinical trials. 
     By operating in some or all of the ways described above, embodiments of the facility provide significant benefits relative to conventional techniques. 
       FIG. 1  is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility operates. In various embodiments, these computer systems and other devices  100  can include server computer systems, desktop computer systems, laptop computer systems, netbooks, mobile phones, personal digital assistants, televisions, cameras, automobile computers, electronic media players, etc. In various embodiments, the computer systems and devices include zero or more of each of the following: a central processing unit (“CPU”)  101  for executing computer programs; a computer memory  102  for storing programs and data while they are being used, including a multithreaded program being tested, a debugger, the facility, an operating system including a kernel, and device drivers; a persistent storage device  103 , such as a hard drive or flash drive for persistently storing programs and data; a computer-readable media drive  104 , such as a floppy, CD-ROM, or DVD drive, for reading programs and data stored on a computer-readable medium; and a network connection  105  for connecting the computer system to other computer systems to send and/or receive data, such as via the Internet or another network and its networking hardware. While computer systems configured as described above are typically used to support the operation of the facility, those skilled in the art will appreciate that the facility may be implemented using devices of various types and configurations, and having various components. 
       FIG. 2  is a flow diagram showing steps typically performed by the facility in some embodiments to reduce the dissimilarity of a subject data set with a reference data set. Those skilled in the art will appreciate that the steps shown in  FIG. 2  and in each of the flow diagrams discussed below may be altered in a variety of ways. For example, the order of the steps may be rearranged; some steps may be performed in parallel; shown steps may be omitted, or other steps may be included; a shown step may be divided into substeps, or multiple shown steps may be combined into a single step, etc. 
     In steps  201  and  202 , facility collects, reads, loads, or otherwise obtains a reference data set and one or more subject data sets, respectively. Each data set contains, for each of a number of respondents, values for each of a set of respondent attributes, or “variables,” such as age, gender, geographic region, church attendance, belief in death penalty, voting behavior etc., which exist within an N dimensional sample space S N ={S 1 , S 2 , . . . , S N }. The N dimensional sample space S N ={S 1 , S 2 , . . . , S N } is the set of all possible values of all variables in combination. 
     For example, if we have 2 variables where variable 1 is gender and variable 2 is region, then S 1 ={Male, Female} is the set of all possible values that variable 1 can have and S 2 ={North, East, South, West} is the set of all possible values that variable 2 can have. 
               S   2     =       {       S   1     ,     S   2       }     =     {       Male   North     ,     Male   East     ,     Male   South     ,     Male   West     ,     Female   North     ,     Female   East     ,     Female   South     ,     Female   West       }             
is the set of all possible values that both variables could have in combination. This can be determined before the data is collected. Said another way, S 1 , S 2 , . . . is the list of variables that define the sample space, the domain within which the facility produces one data set (a subject) such that it matches the reference data set by minimizing the dissimilarity across all of the S 1 , S 2 , . . . dimensions).
 
     If variable 1 is age, then S 1  is the set of all possible values that age may take on. If variable 2 is gender, then S 2  is the set of all possible gender values, i.e. S 2 =(Male, Female). 
     The facility employs two vectors of probability mass functions of length N corresponding to the n th  dimension of S N : f N ={f 1 , f 2 , . . . , f N } and g N ={g 1 , g 2 , . . . , g N }. f N ={f 1 , f 2 , . . . , f N } is the distribution of all the variables in the reference data set and g N ={g 1 , g 2 , . . . , g N } is the distribution of all the variables in the subject data set. For this example and ease of explication, consider a data set created using the GMI panel as the reference and create the subject data set from an alternative outside source that matches the GMI reference (i.e. minimal total data set dissimilarity). 
     If variable 2 is gender, then f 2  is the function that gives the percentage of respondents in the reference data set who are either male or female. For example, consider the distribution of the gender variable in the reference data set of f 2  (Male)=60% and f 2 (Female)=40%. Likewise, g 2  is the function which returns the percentage of respondents in the subject data set who are either male or female. In the example, the distribution of the gender variable in the subject data set is g 2  (Male)=55% and g 2  (Female)=45%. In some embodiments, the facility estimates the F and G functions based on the subject and reference data sets. 
       FIG. 3  is a table diagram showing sample contents of a subject data set and a reference data set. The reference data set  350  contains, for each of number of respondents among a modeled population, the respondent&#39;s values for a number of variables, such as demographic variables. In particular, each of rows  361 - 364  corresponds to a different respondent. The respondent to whom the row corresponds is identified in a user ID column  301 . Each row further contains values for sex, region, age, and ethnicity variables, among others, in corresponding columns  302 - 306 . For example, row  361  indicates that the respondent having user ID  3001  is male, from a North region, of age 18, and is East Asian. Also shown for the reference data set are aggregated values  370  for each of the variables, also referred to herein variously as the “frequency distribution,” “probability distribution,” or “attribute distribution” for the variable. This portion of the table shows, in column  301 , the total number of respondents represented, and in columns  302 - 306  the attribute distribution among all the reference respondents for the variable. As an example, row  370  indicates that there are 750 respondents in the reference data set, 61.3 percent of which are male and 38.7 percentage of which are female. 
       FIG. 3  further shows a subject data set  300 . The rows  311 - 315  of the subject data set table each correspond to a respondent in the subject data set, and section  320  shows attribute distributions for variables within the subject data set. Columns  301 - 306  of the subject data set table closely parallel the same columns of the reference data set table. The subject data set table further contains columns  307 - 309  containing responses by the same respondents to questions of a market research survey posed to the respondents in the subject data set. For example, row  311  indicates that the respondent in the subject data set having user ID  8001  enjoys animated films, enjoys The Incredibles, and is not tolerant of violence in animated films. 
     While  FIG. 3  and each of the table diagrams discussed below show a table whose contents and organization are designed to make them more comprehensible by a human reader, those skilled in the art will appreciate that actual data structures used by the facility to store this information may differ from the table shown, in that they, for example, may be organized in a different manner; may contain more or less information than shown; may be indexed, compressed, and/or encrypted in ways not shown; etc. 
     Returning to  FIG. 2 , in step  211 , the facility maps comparable variables between the reference data set and the collected subject data set or data sets. In some embodiments, step  211  involves receiving input from a human user who performs the mapping. In some embodiments, the facility performs the mapping automatically, such as by using standardized variable codes, natural language matching techniques, etc. 
     In step  221 , the facility decomposes each variable into its complete set of unique binary combinations, where a binary combination maps the variable&#39;s categories to create only two categories. For example, if the variable is region, measured as East, West, South, and North, then its has a set of 7 unique binary combinations: 
     1) East/all other regions 
     2) West/all other regions 
     3) South/all other regions 
     4) North/all other regions 
     5) East and West/South and North 
     6) East and South/West and North 
     7) East and North/West and South 
     The number of unique binary combinations for a variable with N categories is: 
               [       ∑     z   =   1       ⌊     n   2     ⌋       ⁢           ⁢       n   !           (     n   -   z     )     !     ⁢     z   !           ]     -       (     n   +     1   ⁢           ⁢   mod   ⁢           ⁢   2       )     ⁢       n   !       2   ⁢       (     n   -   z     )     !     ⁢     z   !                 
If geographic location were measured in 15 census regions, the number of binary combinations is 16,383.
 
       FIG. 4  is a flow diagram showing steps typically performed by the facility in some embodiments to decompose each major variable that is in both the reference and subject data sets into its complete set of unique binary combinations, also called minor variables. The variables contained in the data sets as shown in  FIG. 3  are sometimes referred to herein as “major variables.” In contrast, as is discussed in greater detail below, the facility treats each of the unique binary combinations into which each major variable is decomposed “minor variable.” In steps  401 - 406 , the facility loops through each of N major variables X 1 , X 2 , . . . , X N . In step  402 , the facility branches based upon the type of the major variable: where the major variable is a continuous variable, the facility continues in step  403 ; where the major variable is an ordered categorical variable, the facility continues in step  404 ; and where the major variable is an unordered categorical variable, the facility continues in step  405 . In step  403 , where the major variable is a continuous variable, the facility establishes a number of different quantile categories, such as 100 different percentile categories. For percentile categories, for example, the facility first determines 101 percentile values for the variable. π 0 , π 0.01 , π 0.02 , . . . , π 1 . The facility then determines 100 percentile categories C i  where π 0 ≦C 1 &lt;π 0.01 , π 0.01 ≦C 2 &lt;π 0.02 , . . . , π 0.99 ≦C 100 ≦π 1 . After step  403 , the facility continues in step  404 . 
     In step  404 , where the major variable is an ordered categorical variable or has been converted in step  403  to an ordered categorical variable, the facility partitions the variable between each pair of categories that is adjacent in the order. That is, where X i  is ordered categorical with categories C 1 , C 2 , . . . , C n , the facility decomposes X i  into n−1 variables defined as 
               X     i   z       =         1           X   i     ≤     C   z               0           X   i     &gt;     C   z                   
for z=1 to n−1. After step  404 , the facility continues in step  406 .
 
     In step  405 , where the major variable is an unordered categorical variable, the facility partitions each unique combination of categories. That is, for unordered categorical variable X i  with categories C 1 , C 2 , . . . , C n  the facility decomposes X i  into 
               [       ∑     z   =   1       ⌊     n   2     ⌋       ⁢           ⁢       n   !           (     n   -   z     )     !     ⁢     z   !           ]     -       (     n   +     1   ⁢           ⁢   mod   ⁢           ⁢   2       )     ⁢       n   !       2   ⁢       (     n   -   z     )     !     ⁢     z   !                 
variables defined as
 
               X     i   z       =         1           X   i     =     C   z   ′               0             X   i     ≠     C   z   ′       ,                 
where C z ′ represents the z th  combination of C 1 , C 2 , . . . , C n . After step  405 , the facility continues in step  406 . In step  406 , if additional major variables remain to be processed, then the facility continues in step  401  to process the next major variable, else the steps conclude. This approach creates an exhaustive set of all unique binary combinations taking into consideration ordered and non-ordered variable types.
 
       FIG. 5  is a table diagram showing the result of decomposing a sample major variable into minor variables.  FIG. 5  shows major column  303  containing values for the major variable region that corresponds to column  303  as shown in  FIG. 3 .  FIG. 5  further includes minor columns  501 - 507 , each of which contains values for one of the minor variables into which the facility decomposes the major variable region. As an example, minor column  501  contains a  1  for each respondent in the East region, and a 0 for each respondent in the North, South or West region. As another example, column  507  contains a 1 for each respondent in the East region or West region, and a 0 for each respondent in the North region or South region. It is minor columns like these, corresponding to minor variables, that will be included in each interior node of the decision tree later generated by the facility. 
     Returning to  FIG. 2 , in step  231 , where multiple subject data sets were collected in step  202 , the facility identifies an optimal mix of the multiple subject data sets to minimize total set dissimilarity between the combined subject data sets and the reference data set. In some embodiments, step  231  involves determining, for each of the multiple subject data sets, a weight that is 0 or larger that determines the relative level of influence of the individual subject data set on the combined subject data sets. In some embodiments, the facility uses a particle swarm optimization algorithm to experimentally establish the weights used to combine the subject data sets. The measure of total set dissimilarity used by the facility is described in the following discussion. 
     G is a real valued function which measures the dissimilarity of two probability distributions on the same sample space (i.e., proportionate age distribution in reference data set compared to proportionate age distribution in subject data set). H is a real valued function which measures the dissimilarity of two interactions or dissimilarity of interrelatedness on the same sample space (i.e., relationship of age distribution to marital status distribution in the reference compared to the relationship of age distribution to marital status distribution in subject data set). 
     The marginal dissimilarity for the n th  variable is defined as:
 
 M   n   =G ( f   n   ,g   n )
 
That is, M n  is used as a shorthand label for the function G on the n th  variable.
 
     The interaction dissimilarity for the n th  and m th  variable is defined as:
 
 n,m   =H ( f   n   |f   m   ,g   n   |g   m )
 
where, for example, if n is region and m is ethnicity, f n |f m  represents the interaction of the region variable with the ethnicity variable in the reference data set, and g n |g m  represents the interaction of the region variable with the ethnicity variable in the subject data set. I n,m  is used as a shorthand label for the function H on the n th  and m th  variables, respectively.
 
     Then, given two real valued functions Y 1  over m and Y 2  over n, and a norm on a two dimensional vector space, the total set dissimilarity is defined as:
 
 T=Y   2 (∥ M   n   ,Y   1 ( I   n,m )∥)
 
In this equation, Y 1  is typically the average function, and if the n th  variable is age, then T represents the average dissimilarity of the age distribution interaction with all other variables in the reference compared to the age distribution interaction with all other variables in the subject data set.
 
     If Y 1  is the average function, then Y 1 (I n,m ) represents the average dissimilarity of the age distribution interaction with marital status, age distribution interaction with employment status, age distribution interaction with church attendance, age distribution interaction with foreign born, etc. In various embodiments, Y 1  is the average, maximum, median, 75 th  percentile, or the root mean square of the interaction dissimilarities. 
     Recall from above that M n  is the dissimilarity of two probability distributions of the same variable (e.g., age, marital status, church attendance, etc.), so it is possible to plot each variable&#39;s dissimilarity by its marginal distribution difference and its interaction difference. Where there are no differences, a (0,0) places the point at the origin of a Euclidian plane. If, for example, the marginal distribution difference between the reference and subject is significantly different, but the average interaction difference is only slightly different, the point might be plotted at (10, 1). A variable with a large difference in both its marginal distribution and its interaction distance might be plotted at (10, 10). 
     While Euclidian space is used for the foregoing example, any definition of space and distance can be used. The vertical parallel bars indicate any norm can be used to define distance in space. 
     Continuing with 2-dimensional Euclidian space, the facility determines the distance from the plotted point to the origin using the Pythagorean theorem for distance,
 
 C=SQRT ( x   2   +y   2 ).
 
     In some embodiments, Y 2  is the average distance from the origin (0, 0) of all variables plotted in this (x, y) space. In various embodiments, various other summary measures are used. 
     Thus, T is the total multi-dimensional dissimilarity of the subject data set from the reference data set, which takes into account both the differences in the proportionate distribution of all variables and the interaction differences among all the variables. 
     The measurement equation further comprises a specific form of the total data set dissimilarity index in which the dissimilarity between two sets is based on the Kullback-Leibler divergence (“K-L divergence”) measure combined with the mutual information index and an algebraic direction modifier such that the combination of these terms measure the total data set dissimilarity between two data sets. 
     Given two discrete probability distributions (X 1  and X 2 ) with n categories defined on the same sample space, the K-L divergence of X 1  (subject distribution) from X 2  (reference distribution) is defined as: 
               KL   ⁡     (       X   1     ,     X   2       )       =       ∑     i   =   1     n     ⁢           ⁢       P   ⁡     (     X     2   i       )       ⁢       log   2     ⁡     (       P   ⁡     (     X     2   i       )         P   ⁡     (     X     1   i       )         )                 
This is G—the proportionate distribution difference.
 
     Given two discrete probability distributions (X 1  and X 2 ) and their joint distribution, the mutual information between X 1  and X 2  is defined as the K-L divergence of the product of the marginal distributions from the joint distribution: 
               I   ⁡     (       X   1     ,     X   2       )       =       ∑     i   =   1     n     ⁢           ⁢       P   ⁡     (       X     1   i       ,     X     2   i         )       ⁢       log   2     ⁡     (       P   ⁡     (       X     1   i       ,     X     2   i         )           P   ⁡     (     X     1   i       )       ⁢     P   ⁡     (     X     2   i       )           )                 
This I does not map to I n,m  up above; this is a sub-component starting point. It lacks “direction” or an algebraic sign. It tells us the magnitude if the direction but not whether it is positive or negative. We add the direction below in the term labeled D.
 
     Given two decomposed datasets X and Y, the facility decomposes variables as shown in  FIG. 4  and described in its description into binary categories to simplify and asses the direction, positive or negative, of the interrelatedness. Each data set consists of N major variables, each decomposed into z 1 , z 2 , . . . , z N  minor variables: 
     
       
         
           
             X 
             = 
             
               { 
               
                 
                   X 
                   
                     1 
                     1 
                   
                 
                 , 
                 
                   … 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     X 
                     
                       1 
                       
                         z 
                         1 
                       
                     
                   
                 
                 , 
                 
                   X 
                   
                     2 
                     1 
                   
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   X 
                   
                     2 
                     
                       z 
                       2 
                     
                   
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   X 
                   
                     N 
                     1 
                   
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   X 
                   
                     N 
                     
                       z 
                       N 
                     
                   
                 
               
               } 
             
           
         
       
       
         
           
             Y 
             = 
             
               { 
               
                 
                   Y 
                   
                     1 
                     1 
                   
                 
                 , 
                 
                   … 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     Y 
                     
                       1 
                       
                         z 
                         1 
                       
                     
                   
                 
                 , 
                 
                   Y 
                   
                     2 
                     1 
                   
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   Y 
                   
                     2 
                     
                       z 
                       2 
                     
                   
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   Y 
                   
                     N 
                     1 
                   
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   Y 
                   
                     N 
                     
                       z 
                       N 
                     
                   
                 
               
               } 
             
           
         
       
     
     The marginal dissimilarity for the n th  variable is defined as: 
     
       
         
           
             
               G 
               ⁡ 
               
                 ( 
                 
                   
                     X 
                     n 
                   
                   , 
                   
                     Y 
                     n 
                   
                 
                 ) 
               
             
             = 
             
               
                 1 
                 
                   z 
                   n 
                 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   
                     z 
                     n 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     KL 
                     ⁡ 
                     
                       ( 
                       
                         
                           X 
                           
                             n 
                             i 
                           
                         
                         , 
                         
                           Y 
                           
                             n 
                             i 
                           
                         
                       
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     The interaction dissimilarity for the n th  variable is defined by: First calculating all of the mutual information between all variables in Y and X:
 
 I ( Y   n     i     ,Y   m     i   ) and  I ( X   n     i     ,X   m     i   ) for all  n,mεN  and  iεz   n   ,tεz   m ;
 
Second calculating each covariance between all variables in Y and X:
 
 Cov ( Y   n     i     ,Y   m     i   ) and  Cov ( X   n     i     ,X   m     i   ) for all  n, mεN  and  iεz   n   ,tεz   m ;
 
Then calculating the direction modifier as:
 
 D ( n   i   ,m   i   |X,Y )=sign( Cov ( X   n     i     ,X   m     i   )· Cov ( Y   n     i     ,Y   m     i   ));
 
Then combining D, with the I above in this section to get the H function from above in the generalized equation section, the interaction dissimilarity is then:
 
     
       
         
           
             
               H 
               ⁡ 
               
                 ( 
                 
                   
                     X 
                     n 
                   
                   , 
                   
                     Y 
                     n 
                   
                 
                 ) 
               
             
             = 
             
               
                 1 
                 
                   z 
                   n 
                 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   
                     z 
                     n 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   ( 
                   
                     
                       1 
                       
                         N 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             j 
                             = 
                             1 
                           
                           
                             j 
                             ≠ 
                             n 
                           
                         
                         
                           N 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         [ 
                         
                           
                             1 
                             
                               z 
                               j 
                             
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               
                                 z 
                                 j 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               abs 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     I 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           X 
                                           
                                             n 
                                             i 
                                           
                                         
                                         , 
                                         
                                           X 
                                           
                                             j 
                                             k 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                   - 
                                   
                                     
                                       D 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             n 
                                             i 
                                           
                                           , 
                                           
                                             j 
                                             k 
                                           
                                         
                                         ) 
                                       
                                     
                                     · 
                                     
                                       I 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             Y 
                                             
                                               n 
                                               i 
                                             
                                           
                                           , 
                                           
                                             Y 
                                             
                                               j 
                                               k 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
     
     The summation sign inside the square brackets averages one binary variable with one other binary variable (e.g., binary age category under age 30 across all binary categories of marital status). The second summation sign, just outside the square brackets averages interaction differences across all variables. The third summation sign, the one outside the parenthesis and brackets, averages all age category breaks (i.e., age under 30, age under 31, age under 32, etc). This results in one average interaction dissimilarity measure for each variable (e.g., age, gender, church attendance, etc.). 
     The total set dissimilarity is then: 
               T   ⁡     (     X   ,   Y     )       =       1   N     ⁢       ∑     i   =   1     N     ⁢           ⁢           G   ⁡     (       X   i     ,     Y   i       )       2     +       H   ⁡     (       X   i     ,     Y   i       )       2                   
This is the average dissimilarity each variable is from the origin, where the origin is (0, 0) implying no dissimilarity in any variable&#39;s proportionate distribution or in any variables interrelatedness.
 
     Returning to  FIG. 2 , in step  241 , the facility generates a decision tree to identify a system of partitions that minimize the total set dissimilarity. In some embodiments, the facility defines an optimal set of partitions for each n exhaustive and mutually exclusive set of binary partitions or a subset of the total data set universe categorized into exhaustive and mutually exclusive binary categories. In some embodiments, the facility approximates the optimal solution without using one or more of these observations or partitions. 
     The facility uses a decision tree structure to define the optimal adjustment partitions which minimize the total dissimilarity between the reference and subject data sets when adjusted. In some embodiments, the facility uses varying combinations of tree-defining parameters that determine the tree&#39;s structure. For example, tree-defining parameters may include:
         1. The maximum number of terminal nodes   2. The maximum number of variables needed to define a given terminal node   3. The minimum number of observations required for a terminal node to be considered   4. The minimum number of observations required in one or more node in order for a split to be considered       

     In various embodiments, the facility uses one or more additional tree-defining parameters, such as the minimum number of nodes, minimum percentage of observations needed to define a given node, the minimum reduction in total dissimilarity accounted for by the additional node, etc. 
     In some embodiments, the facility finds the optimal tree by a complete enumeration of all decision trees possibilities and choosing the one that yields the minimum total data set dissimilarity when leaves are adjusted. When there are a relatively large number of variables and large number of categories within these variables, the universe of all possible decision trees can be very large. For large collections of variables where complete enumeration is cumbersome, time consuming, or expensive, in some embodiments, the facility utilizes an evolutionary algorithm to find a decision tree that is near optimal. 
       FIG. 6  is a flow diagram showing steps typically performed by the facility in some embodiments in order to generate a decision tree. In step  601 , the facility initializes the result tree to be empty. The facility then repeats step  602 - 609  until the result tree can no longer be extended and still satisfies the tree-defining parameters identified above. In steps  603 - 607 , the facility loops through each of a number of candidate trees, such as  100 . In step  604 , the facility makes a copy of the result tree, which forms the basis of the current candidate tree. In step  605 , the facility completes the candidate tree. Additional details about step  605  are discussed below in connection with  FIG. 7 . In step  606 , the facility determines the total data set dissimilarity measure using the candidate tree completed in step  605 . In step  607 , if additional candidate trees remain to be constructed, then the facility continues in step  603 , else the facility continues in step  608 . In step  608 , the facility adds to the result tree one or more nodes from the candidate tree determined in step  606  to have the smallest dissimilarity measure. In some embodiments, step  608  involves adding to the result tree all of the nodes of the best candidate tree from the level below the lowest level of the result tree. In some embodiments, step  608  involves adding only one node to the result tree, such as the first node added to the copy of the result tree as part of completing the best candidate tree. In step  609 , if the result tree can be extended and still satisfied by the tree-defining parameters, then the facility continues in step  602  to construct another set of candidate trees based upon the result tree as expanded in step  608 , else the steps conclude. 
       FIG. 7  is a flow diagram showing steps typically performed by the facility in order to complete a candidate tree in accordance with step  605  in some embodiments. The facility repeats step  701 - 705  until the candidate tree can no longer be extended and still satisfy the tree-defining parameters. In step  702 , the facility selects a leaf node of the candidate tree, such as by selecting it stochastically. For this selection, each leaf node is weighted by the total set dissimilarity of the observations of the subject data set that map to this leaf node when compared to the observations of the reference data set that map to this leaf node. An observation maps to the leaf node if the observation has binary, i.e. minor, variable values that are consistent with the path from the root of the tree to the leaf node in question. In step  703 , the facility selects a minor variable, such as by selecting it stochastically. In some embodiments, in step  703 , the facility selects a minor variable from many of those minor variables that are not already used in any of the existing interior nodes of the candidate tree that are on the path from the root node to the node in question. The selection of step  703  is performed using a weight for each of these minor variables that is based upon the proportion of the leaf node&#39;s total set dissimilarity that is attributable to the minor variable. In step  704 , the facility replaces the leaf node selected in step  702  with a new interior node that splits on the minor variable selected in step  703 , and that has two new leaf nodes as its children. In step  705 , if the candidate tree can be further extended and still satisfy the tree-defining parameters, then the facility continues in step  701  to add another interior node to the candidate tree, else these steps conclude. 
       FIGS. 8 and 9  are data structure diagrams showing sample candidate decision trees during their construction by the facility.  FIG. 8  shows a sample tree having a single interior node  801 . Node  801  splits based upon whether each observation has a value for the region variable that is equal to East. Observations that do have value of the region variable that is equal to East map to leaf node  803 , while observations that have a value of the region major variable that is West, North, or South map to leaf node  802 . In a situation in which tree  800  is the current state of the result tree being constructed by the facility in accordance with  FIG. 6 , the facility copies this result tree as the basis for each of the number of candidate trees. As part of completing one of these candidate trees, the facility extends this candidate tree in step  704  as shown in  FIG. 9 . 
       FIG. 9  is a data structure diagram showing a sample expanded decision tree. To construct this expanded decision tree, the facility has selected leaf node  802  in step  702  and has selected an age&lt;34 minor variable in step  703 . The facility subsequently replaced leaf node  802  with new interior node  904  representing the selected split. Tree  900  has two additional leaf nodes  905  and  906  as children of new interior node  904 . An observation maps to leaf node  905  if it has a value of zero for the region=East minor variable and a value of zero for the age&lt;34 minor variable. That is to say, an observation maps to leaf node  905  if its value for the region major variable is West, North, or South, and its value for the age major variable is greater than or equal to 34. An observation maps to leaf node  906  if its value for the region=East minor variable is zero and its value for the age&lt;34 minor variable is 1. At the point depicted in  FIG. 9 , the facility would continue to expand the shown candidate tree until it could no longer be extended and still satisfy the tree-defining parameters. 
     Returning to  FIG. 2 , in one or more of steps  251 - 253 , the facility employs the decision tree generated in step  241  to reduce the dissimilarity of the subject data set with the reference data set. In step  251 , the facility removes excess observations from the subject data set to better match the reference data set. That is, for any leaf nodes of the decision tree where the proportion of the observations of the subject data set that map to the node exceeds the proportion of observations of the reference data set that map to that node, the facility removes observations of the subject data set that map to that node until this condition no longer exists, or exists only to a degree that is below a predetermined threshold. After the removal of these observations of the subject data set, the dissimilarity of the subject data set with the reference data set has been reduced. At this point, the facility assembles the survey responses of the observations that have not been discarded. 
     In step  252 , the facility weights the observations of the subject data set such that, for each leaf node of the decision tree, the proportion of observations of the subject data set that map to that node when weightings are considered is equal or nearly equal to the proportion of observations of the reference data set that map to that node. At this point, the facility uses the responses of all of the observations in the subject data set, weighted in accordance with the weightings applied in step  252 . For example, if an observation had a value of male for the sex variable and was attributed a weighting of 0.25, this observation would contribute 0.25 to the aggregated male value of the sex variable for the subject data set. Similarly, if this observation has a yes value for the enjoy animated films variable, the observation will contribute 0.25 value to an aggregated value for this variable for the subject data set. 
     In step  253 , the facility collects a new data set from the provider of the subject data set using strata defined by the decision tree generated by the facility. Step  253  is similar to step  251 , but rather than discarding excess observations that correspond to complete responses, omits to accept partial responses that are determine to correspond with excess observations. That is, during completion of a survey, the facility uses the variable values provided by the respondent so far to attempt to determine which leaf node of the decision tree the response would map to. If this is a node to which a significantly higher proportion of observations of the subject data set map than the proportion of observations of the reference data set due, then the facility interrupts the completion of the survey by this respondent, such that a subject data set having a low level of dissimilarity with the reference data set is collected in the first instance. In this instance, the facility simply uses the survey responses contained in the subject data set without alteration. 
     Survey results produced and/or adjusted in accordance with the facility may be used in a variety of ways, including using the survey result internally, selling the survey result, constructing the marketing report around the survey result, combining the survey result with other results for the same or similar surveys, etc. 
     In some embodiments, the facility generates or uses a decision tree that is not uniformly binary—that is, at least one non-leaf node has more than two children, where such nodes partition the possible values of an attribute into more than two categories. 
     It will be appreciated by those skilled in the art that the above-described facility may be straightforwardly adapted or extended in various ways. While the foregoing description makes reference to particular embodiments, the scope of the invention is defined solely by the claims that follow and the elements recited therein.