Abstract:
The present invention is a method of allowing inclusion of more than one variable in a Classification and Regression Tree (CART) analysis. The method includes predicting y using p exploratory variables, where y is a multivariate, continuous response vector, describing a probability density function at “parent” and “child” nodes using a multivariate normal distribution, which is a function of y, and defining a split function where “child” node distributions are individualized, compared to the parent node. In one embodiment a system is configured to implement the multivariate CART analysis for predicting behavior in a non-performing loan portfolio.

Description:
BACKGROUND OF THE INVENTION 
   This invention relates generally to prediction of responses using mathematical algorithms for quality measurements and more specifically to the use of Classification and Regression Tree (CART) analysis for prediction of responses. 
   In a financing example, an amount collected on a charged off loan is a function of many demographic variables, as well as historic and current information on the debtor. If one desired to predict the amount paid for an individual borrower, a statistical model need be built from an analysis of trends between the account information and the amount paid by “similar” borrowers, that is, borrowers with similar profiles. CART tools allow an analyst to sift, i.e. data mine, through the many complex combinations of these explanatory variables to isolate which ones are the key drivers of an amount paid. 
   Commercially available tools for CART analysis exist, however, there is no known tool that allows the user to build a model that predicts more than one measurement at a time (i.e., more than one response in a CART application). It would be desirable to develop a CART tool that allows a user to predict more than one measurement at a time, thereby allowing for a multivariate response CART analysis. 
   BRIEF SUMMARY OF THE INVENTION 
   The present invention is, in one aspect, a method of allowing inclusion of more than one variable in a Classification and Regression Tree (CART) analysis. The method includes predicting y using p exploratory variables, where y is a multivariate response vector. A statistical distribution function is then described at “parent” and “child” nodes using a multivariate normal distribution, which is a function of y. A split function where “child” node distributions are individualized, compared to the parent node is then defined. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a single node split diagram; 
       FIG. 2  is a univariate Classification and Regression Tree (CART) model for recovery amount; 
       FIG. 3  is a univariate CART model for recovery timing; 
       FIG. 4  is a multivariate CART model for recovery amount and timing using negative entropy and Hotelling; 
       FIG. 5  is a multivariate CART model for recovery amount and timing using Kullback-Liebler Divergence; and 
       FIG. 6  is a system block diagram. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Classification and Regression Tree (CART) analysis is founded on the use of p explanatory variables, X 1 , X 2 , . . . , X p , to predict a response, y, using a multi-stage, recursive algorithm as follows: 
   1. For each node, P, evaluate every eligible split, s, of the form X i ∈S, X i ∉S, on each predictor variable, by associating a split function, φ(s,P)≧0 which operates on P. The split forms a segregation of data into two groups. The set S can be derived in any useful way. 
   2. Choose the best split for each node according to φ(s,P). This could be the maximum or minimum split function value for that node, for example. Each split produces two child nodes. 
   3. Repeat 1 and 2 for each child node. 
   4. Stop when apriori conditions are met. 
     FIG. 1  illustrates a single split  10  where a heterogeneous parent node, P,  12  is observed to identify a split that is used to segregate a heterogeneous parent node,  12  into more homogeneous child nodes, such as node L  14  and node R  16 , as defined by an appropriate measure of diversity. Diversity can be a function of the data, {y k } k=1   n , or of an assumed distribution, p(y)=ƒ(y|μ,Σ) being the probability density function, or both. 
   The p(y) notation is used, with subscripts where appropriate, to describe probability density function at the parent and child nodes in the sequel. Parameter nomenclature typically associated with multivariate continuous distributions is used in  FIG. 1 , but the concept applies universally. It is assumed that the observations are independent. 
   Several measures of diversity in the univariate response setting have been advocated. One, called Node Impurity, is negative entropy:
 
 I ( P )=−∫log( p ( y )) p ( y ) dy  
 
with a split function defined as φ(s,P)=I(P)−I(L)−I(R).
 
   Other known regression tree methodologies include longitudinal data by using split functions that addressed within-node homogeneity in either mean structure (a Hotelling/Wald-type statistic) or covariance structure (a likelihood ratio split function), but not both. Another methodology uses five multivariate split criteria that involved measures of generalized variance, association, and fuzzy logic. In addition, the use of tree methods on multiple binary responses, and introducing a generalized entropy criterion has been investigated. 
   CART analysis and methodology can be applied, for example, for valuation of non-performing commercial loans. A valuation of n non-performing commercial loans involves ascribing (underwriting) the loans with values for a recovery amount, expressed as a percentage of unpaid principal balance, and a value for recovery timing, expressed in months after an appropriate baseline date (e.g., date of acquisition). Recovery amount and timing information is sufficient to calculate the present value of future cash flows, a key part of portfolio valuation. Underwriters of defaulted loans use their individual and collective experience to ascribe these values. Statistical models can be used to associate underwriters&#39; values with key loan attributes that shed light on the valuation process. 
     FIG. 2  illustrates a univariate CART model  20  for a percentage recovery amount for non-performing commercial loans. Statistics at each node are included in the rectangle representing the node. Node  22  shows a number, n which represents the number of loans in the analysis. In the example of  FIG. 2 , n is equal to 151. The 151 loans are examined for a split, and as noted in nodes  24  and  26 , 132 of the loans have a legal status as being in collections or the subject of a lawsuit, shown in node  24 , while nineteen of the loans are classified as being current as shown in node  26 . Nodes  28  and  30  signify where another split has been identified between the 132 loans of node  24  relating to a secured score which is a scoring model prediction of whether or not the borrower account is collateralized (secured by real estate). 
     FIG. 3  illustrates a univariate CART model  40  for a recovery timing amount in months for non-performing commercial loans. Statistics at each node are included in the rectangle representing the node. Node  42  shows a number, n which represents the number of loans in the analysis. In the example of  FIG. 3 , n is equal to 151. The 151 loans are examined for a split, and as noted in nodes  44  and  46 , thirty of the loans have a legal status as being in collections or the subject of a lawsuit, shown in node  44 , while 121 of the loans are classified as being current as shown in node  46 . Nodes  48  and  50  signify where another split has been identified between the thirty loans of node  44 , node  48  signifying that payers have paid in the last twelve months in nine of the thirty loans in node  44  and node  50  signifying that no payments have been made in the last twelve months for twenty-one of the thirty loans. Nodes  52  and  54  signify where another split has been identified between the 121 loans of node  46  relating to a secured score which is a scoring model prediction of whether or not the borrower&#39;s account is collateralized (secured by real estate). 
   In the multivariate normal case, the node impurity equation results in 
         φ   ⁡     (     s   ,   P     )       =         n   2     ⁢     log   ⁡     (          Σ   p          )         -         n   L     2     ⁢     log   ⁡     (          Σ   L          )         -         n   R     2     ⁢       log   ⁡     (          Σ   R          )       .             
 
   An implementation using the above equation, with maximum likelihood estimations imputed, when compared to the split function acts as a diversity measure on covariance structure only. A Hotelling/Wald-type statistic, as a diversity measure on mean structure only, results in: 
         φ   ⁡     (     s   ,   P     )       =           n   L     ⁢     n   R           n   L     +     n   R         ⁢       (       μ   L     -     μ   R       )     ′     ⁢         Σ     -   1       ⁡     (       μ   L     -     μ   R       )       .           
 
     FIG. 4  illustrates a single CART model  60 , resulting from an implementation version of either of the covariance structure split function equation or the mean structure split function equation above. The explanatory variables used in the analysis are: account status, secured score, and legal status which are described above. Using an example of 151 commercial loans, a split is identified in node  62  regarding the legal status of the 151 loans. Node  64  signifies that nineteen of the 151 loans have a legal status of current, while node  66  signifies that 132 of the 151 loans are in collections or are the subject of a lawsuit. Splits are identified in both nodes  64  and  66 . The split in node  64 , the nineteen loans that are current, is indicated in node  68  which shows that ten of the nineteen loans have had no payment activity over the last twelve months and node  70  shows that nine of the nineteen loans from node  64  have had payment activity. 
   Node  66  is split into two nodes  72  and  74  where node  72  signifies that 121 of the 132 loans of node  66  are the subject of a lawsuit, while node  74  signifies that eleven of the loans are in collections. The 121 loans of node  72  are further separated into nodes  76  and  78 , showing that of the 121 loans that are subjects of lawsuits, 54 are secured by assets such as real estate, shown in node  76 , while 67 of the loans are unsecured, shown by node  78 . 
   Typically, in known applications, separate CART models are built for each response variable. Described below are applications where a single multivariate CART model, which uses multiple response variables, is built. The form of the probability density function under multivariate normality is: 
         p   ⁡     (   y   )       =     f   (         y   ⁢          μ   ,   Σ     )       =         (     2   ⁢   π     )       -     nr   2         ⁢          Σ          -     1   2         ⁢   exp   ⁢     {       -     1   2       ⁢     tr   ⁡     (     y   -   μ     )       ⁢         Σ     -   1       ⁡     (     y   -   μ     )       ′       }         ,           
 
where n=sample size (number of observations), r=number of response variables, y=n×r matrix of response values, μ=n×r matrix of mean response values, where each row is the same r-vector mean, and Σ=r×r matrix of covariance values for the responses. The structure of the above equation encompasses repeated measures and time series models. It is assumed that the observations are not correlated, i.e., the covariance matrix for the rows of y is the identity matrix of size n. Node homogeneity, as depicted in  FIG. 1 , results in individualized probability density functions for each node. In general terms, the split function of the present invention is 
         φ   ⁢     (     s   ,   P     )       =       KL   ⁡     (         p   L     ⁢     p   R       ,     p   P       )       =       ∫       log   ⁡     (         p   L     ⁢     p   R         p   P       )       ⁢     p   L     ⁢     p   R     ⁢     ⅆ   y         =       E     L   ,   R       ⁡     [     log   ⁡     (         p   L     ⁢     p   R         p   P       )       ]               
 
where 
         E     L   ,   R       ⁡     [     log   ⁡     (         p   L     ⁢     p   R         p   P       )       ]         
 
signifies the expected value, taken over the joint distribution arising from the child nodes. Note that the implied node impurity measure in the above equation is related to the node impurity equation in the univariate case, in that node impurity is measured in comparison with a proposed split, s, and the child probability density functions involved:
 
 I ( s,P )=−∫log( p   p ( y )) p   L ( y   L ) p   R ( y   R ) dy   L   dy   R   =−E   L,R [log( p   p ( y )].
 
   Under probability density function for p(y), the split function (p is calculated, using matrix calculus: 
         φ   ⁡     (     s   ,   P     )       =         -       n   L     2       ⁢     log   ⁡     (            Σ   L               Σ          )         -         n   R     2     ⁢     log   ⁡     (            Σ   R               Σ          )         -       n   ×   r     2     +         n   L     2     ⁢     tr   ⁡     (       Σ     -   1       ⁢     Σ   L       )         +         n   R     2     ⁢     tr   ⁡     (       Σ     -   1       ⁢     Σ   R       )         +       1   2     ⁢     tr   ⁡     (           Σ     -   1       ⁡     (       μ   L     -   μ     )       ′     ⁢     (       μ   L     -   μ     )       )         +       1   2     ⁢       tr   ⁡     (           Σ     -   1       ⁡     (       μ   R     -   μ     )       ′     ⁢     (       μ   R     -   μ     )       )       .             
 
   In one embodiment, the present invention uses Kullback-Liebler divergence as a node split criterion. This criterion has an interpretation related to the node impurity function earlier described. Kullback-Liebler divergence is a general measure of discrepancy between probability distributions, that is usually a function of mean and covariance structure. 
   That φ(s,P) is a valid split function is guaranteed by the information inequality, which states that KL(p L p R ,p p )≧0, and equals zero if and only if p L p R =p p , i.e., the parent node is optimally homogeneous. Kullback-Liebler divergence, in this context, measures the information gain, resulting from the use of individualized statistical distributions for the child nodes in  FIG. 1 , compared to a single statistical distribution, as for the parent node. Maximizing φ(s,P) will produce the best split. Use of the above equation for the split function requires the estimation of parameters (μ,Σ), (μ L ,Σ L ) and (μ R ,Σ R ) from the data in each node, P, L, R, respectively. This is done by the usual method of maximum likelihood estimation. 
     FIG. 5  displays a single CART model  90 , resulting from an implementation version using maximum likelihood estimations of the split function, φ(s,P) defined above. The explanatory variables used in the analysis are: account status, secured score, and legal status which are described above and again the 151 commercial loans example is used. As shown in  FIG. 5 , using model  90 , a split is identified in node  92  regarding account activity of the 151 loans over the past twelve months, resulting in a split into nodes  94  and  96 . In node  96  where no payments have been received for 142 of the original 151 loans another split is identified, regarding the secured status of the 142 loans. Node  98  shows that 61 of the 142 loans of node  96  are secured, perhaps by real estate, while node  100  shows that 81 of the 142 loans of node  96  are unsecured. A split identified in node  100  results in nodes  102  and  104 , where node  102  represents that ten of the 81 loans of node  100  are in collections, while node  104  represents that 71 of the 81 loans of node  100  have a legal status of being current or in lawsuit. 
   Another split function used in practice for univariate response settings, and adaptable for multivariate responses is the least squares split function: 
               φ   ⁡     (     s   ,   P     )       =       ⁢         ∑   P     ⁢           ⁢       (       y   i     -       y   _     P       )     2       -       ∑   L     ⁢       (       y   i     -       y   _     L       )     2       -       ∑   R     ⁢       (       y   i     -       y   _     R       )     2                     =       ⁢               n   L   2     ⁢     n   R       +       n   R   2     ⁢     n   L         n     ⁡     [         y   _     L     -       y   _     R       ]       2               
 
where {overscore (y)} signifies the sample average of observations, with the subscript designating from which node the sum and averages come. The split function equation 
         φ   ⁡     (     s   ,   P     )       =         -       n   L     2       ⁢     log   ⁡     (            Σ   L               Σ          )         -         n   R     2     ⁢     log   ⁡     (            Σ   R               Σ          )         -       n   ×   r     2     +         n   L     2     ⁢     tr   ⁡     (       Σ     -   1       ⁢     Σ   L       )         +         n   R     2     ⁢     tr   ⁡     (       Σ     -   1       ⁢     Σ   R       )         +       1   2     ⁢     tr   ⁡     (           Σ     -   1       ⁡     (       μ   L     -   μ     )       ′     ⁢     (       μ   L     -   μ     )       )         +       1   2     ⁢       tr   ⁡     (           Σ     -   1       ⁡     (       μ   R     -   μ     )       ′     ⁢     (       μ   R     -   μ     )       )       .             
 
in this case reduces to Σ=σ 2 =Σ L =Σ R , r=1, and the implementation version of the above equation, with maximum likelihood estimations imputed is proportional to: 
         φ   ⁡     (     s   ,   P     )       =             n   L   2     +     n   R   2       n     ⁡     [         y   _     L     -       y   _     R       ]       2         
 
and agrees with the least squares equation, but for the dependence on sample sizes n L  and n R .
 
     FIG. 6  illustrates an exemplary system  110  in accordance with one embodiment of the present invention. System  110  includes a computer configured as a server  112  and a plurality of other computers  114  coupled to server  112  to form a network. The network of computers may be local area networks (LAN) or wide area networks (WAN). 
   Server  112  is configured to perform multivariate CART analysis to assess valuation and to predict future performance in non-performing commercial loans. In one embodiment, server  112  is coupled to computers  114  via a WAN or LAN. A user may dial or directly login to an Intranet or the Internet to gain access. Each computer  114  includes an interface for communicating with server  112 . The interface allows a user to input data relating to a portfolio of non-performing loans and to receive valuations of the loans and predictions future loan performance. A CART analysis tool, as described above, is stored in server  112  and can be accessed by a requester at any one of computers  114 . 
   As shown by the commercial loan example, multivariate CART response methodology is useful for determination of recovery timings and amounts and has efficiency over known univariate response models in that one model is used to data mine multiple through multiple covariates to predict future loan performances. 
   While the invention has been described in terms of various specific embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the claims.