Computer-implemented systems and methods for forecasting and estimation using grid regression

• US 8,768,866 B2
• Filed: 10/21/2011
• Issued: 07/01/2014
• Est. Priority Date: 10/21/2011
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Desai, Vijay S.
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US13/278,972
• Publication Number:
  US 20130103617A1
• Time in Patent Office: 984 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

Systems and methods are provided for estimating a value for a target variable. A plurality of known entities are assigned to cells of a grid, where the known entities are assigned to the cells based upon attribute data. A determination is made as to whether each cell has at least a threshold number of assigned known entities. When one of the cells contains fewer than the threshold number of known entities, cells are combined to form a super cell. A model is generated for each cell and super cell based upon target variable values for known entities assigned to that cell or super cell. Data for a target entity is received, and the target entity is assigned to one the cells. One of the models is selected based upon the cell assignment, and an estimate is generated for the target variable for the target entity using the selected model.

Claims

1. A computer-implemented method for estimating a value for a target variable, comprising:

receiving data corresponding to a plurality of known entities, wherein each known entity has an associated first attribute value, an associated second attribute value, and an associated target variable;

assigning each known entity to a grid having one or more single cells, wherein each single cell in the grid has an associated first attribute value and an associated second attribute value, and wherein the known entities are assigned to the single cells using the associated attribute values;

determining whether each single cell includes a pre-determined threshold number of assigned known entities;

forming one or more super cells by combining one or more single cells having less than the threshold number of known entities;

generating a model for uncombined single cells having assigned known entities and for each super cell, wherein models are generated using target variable values for known entities assigned to a single cell or a super cell;

receiving data corresponding to a target entity, wherein the target entity has an associated first attribute value and an associated second attribute value;

assigning the target entity to a single cell or a super cell, wherein the target entity is assigned using the associated attribute values;

selecting a model based upon the assigned cell; and

using the selected model to generate an estimated value for a target variable associated with the target entity.

2. The method of claim 1, wherein each single cell is associated with a range of values for the first attribute and a range of values for the second attribute.

3. The method of claim 1, further comprising:

associating a particular single cell having no assigned known entities with a single cell or super cell having a particular generated model, wherein the target entity is assigned to the particular cell, wherein the particular generated model is used to generate the estimate for the target entity.

4. The method of claim 1, further comprising:

determining single cells to combine based upon target variable values for the known entities.

5. The method of claim 4, wherein a first single cell is determined to be combined with a second single cell based upon a similarity of target variable values among known entities assigned to the first single cell and the second single cell.

6. The method of claim 1, wherein the grid is three-dimensional, wherein each of the known entities is assigned to one of the plurality of single cells based upon the values for a first variable, a second variable, and a third variable.

7. The method of claim 6, wherein the first variable and the second variable form coordinates for identifying a physical location.

8. The method of claim 1, wherein the known entities and the target entity are real estate properties, and wherein the target variable is a property value.

9. The method of claim 8, wherein the property value for the target entity is used in assessing property taxes.

10. The method of claim 1, wherein adjacent single cells are combined to form a super cell.

11. The method of claim 1, wherein a particular single cell is associated with multiple models, wherein the target entity is assigned to the particular single cell, and wherein the estimate is generated using the multiple models.

12. The method of claim 11, wherein the estimate is generated based upon a weighted average of outputs of the multiple models.

13. The method of claim 1, wherein the target entity is assigned to a single cell that does not have a model, wherein a model is selected based upon a distance calculation.

14. The method of claim 13, wherein the distance calculation identifies a single cell or super cell having a model that is closest to the target entity.

15. The method of claim 1, wherein the single cells of the grid are defined so that no more than N known entities are assigned to any single cell.

16. The method of claim 1, wherein the single cells of the grid are represented by a plurality of single cell data records stored in a computer-readable medium, wherein a single cell data record identifies the value for the first attribute and the value for the second attribute associated with the single cell.

17. The method of claim 16, wherein the plurality of known entities are represented by a plurality of entity data records stored in the computer-readable medium, wherein an entity data record for an entity identifies the value of the first attribute associated with the entity, the value of the second attribute associated with the known entity, and a single cell record that represents a single cell to which the known entity is assigned.

18. The method of claim 17, wherein a super cell is represented by one or more super cell records stored in the computer-readable medium, wherein the one or more super cell records identify a plurality of single cells combined to form the super cell.

19. The method of claim 18, wherein a model is represented by a model record stored in the computer-readable medium, wherein the model record identifies one or more model parameters, and wherein a single cell data record or a super cell record identifies a model record for a generated model.

20. The method of claim 1, wherein the model is generated based upon third attribute values associated with the known entities, wherein the third attribute values are time-series values.

23. The method of claim 1, wherein single cells are combined horizontally or vertically.

24. The method of claim 1, wherein a super cell is non-rectangular.

21. A system for estimating a value for a target variable, comprising:

one or more processors;

one or more computer-readable storage media containing instructions configured to cause the one or more processors to perform operations including;

receiving data corresponding to a plurality of known entities, wherein each known entity has an associated first attribute value, an associated second attribute value, and an associated target variable;

assigning each known entity to a grid having one or more single cells, wherein each single cell in the grid has an associated first attribute value and an associated second attribute value, and wherein the known entities are assigned to the single cells using the associated attribute values;

determining whether each single cell includes a pre-determined threshold number of assigned known entities;

forming one or more super cells by combining one or more single cells having less than the threshold number of known entities;

generating a model for uncombined single cells having assigned known entities and for each super cell, wherein models are generated using target variable values for known entities assigned to a single cell or a super cell;

receiving data corresponding to a target entity, wherein the target entity has an associated first attribute value and an associated second attribute value;

assigning the target entity to a single cell or a super cell, wherein the target entity is assigned using the associated attribute values;

selecting a model based upon the assigned cell; and

using the selected model to generate an estimated value for a target variable associated with the target entity.

25. The system of claim 21, wherein each single cell is associated with a range of values for the first attribute and a range of values for the second attribute.

26. The system of claim 21, further comprising instructions configured to cause the one or more processors to perform operations including:

associating a particular single cell having no assigned known entities with a single cell or super cell having a particular generated model, wherein the target entity is assigned to the particular cell, wherein the particular generated model is used to generate the estimate for the target entity.

27. The system of claim 21, further comprising instructions configured to cause the one or more processors to perform operations including:

determining single cells to combine based upon target variable values for the known entities.

28. The system of claim 27, wherein a first single cell is determined to be combined with a second single cell based upon a similarity of target variable values among known entities assigned to the first single cell and the second single cell.

29. The system of claim 21, wherein the grid is three-dimensional, wherein each of the known entities are assigned to one of the plurality of single cells based upon the values for a first variable, a second variable, and a third variable.

30. The system of claim 29, wherein the first variable and the second variable form coordinates for identifying a physical location.

31. The system of claim 21, wherein the known entities and the target entity are real estate properties, and wherein the target variable is a property value.

32. The system of claim 31, wherein the property value for the target entity is used in assessing property taxes.

33. The system of claim 21, wherein adjacent single cells are combined to form a super cell.

34. The system of claim 21, wherein a particular single cell is associated with multiple models, wherein the target entity is assigned to the particular single cell, and wherein the estimate is generated using the multiple models.

35. The system of claim 34, wherein the estimate is generated based upon a weighted average of outputs of the multiple models.

36. The system of claim 21, wherein the target entity is assigned to a single cell that does not have a model, wherein a model is selected based upon a distance calculation.

37. The system of claim 36, wherein the distance calculation identifies a single cell or super cell having a model that is closest to the target entity.

38. The system of claim 21, wherein the single cells of the grid are defined so that no more than N known entities are assigned to any single cell.

39. The system of claim 21, wherein the single cells of the grid are represented by a plurality of single cell data records stored in a computer-readable medium, wherein a single cell data record identifies the value for the first attribute and the value for the second attribute associated with the single cell.

40. The system of claim 39, wherein the plurality of known entities are represented by a plurality of entity data records stored in the computer-readable medium, wherein an entity data record for an entity identifies the value of the first attribute associated with the entity, the value of the second attribute associated with the known entity, and a single cell record that represents a single cell to which the known entity is assigned.

41. The system of claim 40, wherein a super cell is represented by one or more super cell records stored in the computer-readable medium, wherein the one or more super cell records identify a plurality of single cells combined to form the super cell.

42. The system of claim 41, wherein a model is represented by a model record stored in the computer-readable medium, wherein the model record identifies one or more model parameters, and wherein a single cell data record or a super cell record identifies a model record for a generated model.

43. The system of claim 21, wherein the model is generated based upon third attribute values associated with the known entities, wherein the third attribute values are time-series values.

44. The system of claim 21, wherein single cells are combined horizontally or vertically.

45. The system of claim 21, wherein a super cell is non-rectangular.

22. A computer-program product for estimating a value for a target variable, tangibly embodied in a non-transitory machine-readable storage medium, including instructions configured to cause a data processing system to:

receive data corresponding to a plurality of known entities, wherein each known entity has an associated first attribute value, an associated second attribute value, and an associated target variable;

assign each known entity to a grid having one or more single cells, wherein each single cell in the grid has an associated first attribute value and an associated second attribute value, and wherein the known entities are assigned to the single cells using the associated attribute values;

determine whether each single cell includes a pre-determined threshold number of assigned known entities;

form one or more super cells by combining one or more single cells having less than the threshold number of known entities;

generate a model for uncombined single cells having assigned known entities and for each super cell, wherein models are generated using target variable values for known entities assigned to a single cell or a super cell;

receive data corresponding to a target entity, wherein the target entity has an associated first attribute value and an associated second attribute value;

assign the target entity to a single cell or a super cell, wherein the target entity is assigned using the associated attribute values;

select a model based upon the assigned cell; and

use the selected model to generate an estimated value for a target variable associated with the target entity.

46. The non-transitory machine-readable storage medium of claim 22, wherein each single cell is associated with a range of values for the first attribute and a range of values for the second attribute.

47. The non-transitory machine-readable storage medium of claim 22, further comprising instructions configured to cause a data processing system to:

associate a particular single cell having no assigned known entities with a single cell or super cell having a particular generated model, wherein the target entity is assigned to the particular cell, wherein the particular generated model is used to generate the estimated value for the target variable.

48. The non-transitory machine-readable storage medium of claim 22, further comprising instructions configured to cause a data processing system to:

determine single cells to combine based upon target variable values for the known entities.

49. The non-transitory machine-readable storage medium of claim 48, wherein a first single cell is determined to be combined with a second single cell based upon a similarity of target variable values among known entities assigned to the first single cell and the second single cell.

50. The non-transitory machine-readable storage medium of claim 22, wherein the grid is three-dimensional, wherein each of the known entities are assigned to one of the plurality of single cells based upon the values for a first variable, a second variable, and a third variable.

51. The non-transitory machine-readable storage medium of claim 50, wherein the first variable and the second variable form coordinates for identifying a physical location.

52. The non-transitory machine-readable storage medium of claim 22, wherein the known entities and the target entity are real estate properties, and wherein the target variable is a property value.

53. The non-transitory machine-readable storage medium of claim 52, wherein the property value for the target entity is used in assessing property taxes.

54. The non-transitory machine-readable storage medium of claim 22, wherein adjacent single cells are combined to form a super cell.

55. The non-transitory machine-readable storage medium of claim 22, wherein a particular single cell is associated with multiple models, wherein the target entity is assigned to the particular single cell, and wherein the estimate is generated using the multiple models.

56. The non-transitory machine-readable storage medium of claim 55, wherein the estimate is generated based upon a weighted average of outputs of the multiple models.

57. The non-transitory machine-readable storage medium of claim 22, wherein the target entity is assigned to a single cell that does not have a model, wherein a model is selected based upon a distance calculation.

58. The non-transitory machine-readable storage medium of claim 22, wherein the distance calculation identifies a single cell or super cell having a model that is closest to the target entity.

59. The non-transitory machine-readable storage medium of claim 22, wherein the single cells of the grid are defined so that no more than N known entities are assigned to any single cell.

60. The non-transitory machine-readable storage medium of claim 22, wherein the single cells of the grid are represented by a plurality of single cell data records stored in a computer-readable medium, wherein a single cell data record identifies the value for the first attribute and the value for the second attribute associated with the single cell.

61. The non-transitory machine-readable storage medium of claim 60, wherein the plurality of known entities are represented by a plurality of entity data records stored in the computer-readable medium, wherein an entity data record for an entity identifies the value of the first attribute associated with the entity, the value of the second attribute associated with the known entity, and a single cell record that represents a single cell to which the known entity is assigned.

62. The non-transitory machine-readable storage medium of claim 61, wherein a super cell is represented by one or more super cell records stored in the computer-readable medium, wherein the one or more super cell records identify a plurality of single cells combined to form the super cell.

63. The non-transitory machine-readable storage medium of claim 62, wherein a model is represented by a model record stored in the computer-readable medium, wherein the model record identifies one or more model parameters, and wherein a single cell data record or a super cell record identifies a model record for a generated model.

64. The non-transitory machine-readable storage medium of claim 22, wherein the model is generated based upon third attribute values associated with the known entities, wherein the third attribute values are time-series values.

65. The non-transitory machine-readable storage medium of claim 22, wherein single cells are combined horizontally or vertically.

66. The non-transitory machine-readable storage medium of claim 22, wherein a super cell is non-rectangular.