Patent Publication Number: US-8996576-B1

Title: Systems and methods for creating geographic connection matrices

Description:
RELATED APPLICATIONS 
     This application is a continuation of U.S. patent application Ser. No. 13/674,494, entitled “Systems and Methods for Creating Geographic Connection Matrices,” filed Nov. 12, 2012, which is a continuation of U.S. patent application Ser. No. 12/557,147, entitled “Systems and Methods for Creating Geographic Connection Matrices,” filed Sep. 10, 2009, which is a continuation of U.S. patent application Ser. No. 11/057,163, entitled “Systems and Methods for Creating Geographic Connection Matrices,” filed Feb. 15, 2005, which issued as U.S. Pat. No. 7,596,542, which claims the benefit of priority from U.S. Provisional Application No. 60/573,928, entitled “Systems and Methods for Creating Geographic Connection Matrices,” filed May 25, 2004, and U.S. Provisional Application No. 60/573,925, entitled “Systems and Methods for Determining Territorial Rates,” filed May 25, 2004, the disclosure of each of which are expressly incorporated herein by reference in their entireties. 
     The disclosure of the present invention is related to U.S. application Ser. No. 11/057,162, entitled “Systems and Methods for Determining Territorial Rates,” filed Feb. 15, 2005, the disclosure of which is expressly incorporated herein by reference in its entirety. 
    
    
     TECHNICAL HELD 
     The present invention relates to creating geographic connection matrices. 
     BACKGROUND 
     Generally, “insurance” is an agreement by which an insurer, sometimes referred to as an underwriter, undertakes to indemnify the insured party against loss, damage, or liability arising from certain risks, in exchange for consideration. The consideration paid by an insured party is typically referred to as a “premium,” which is paid to keep the insurance in effect. An “insurance policy” is a contract of insurance that defines the rights and duties of the contracting parties. A typical insurance policy includes limits on the amount of risk that the insurer will cover. 
     For the purposes of the following discussion, an “insurance product” includes more than the insurance policy. It also includes services, distribution channels, and other components that may impact the customer experience. 
     Property insurance protects persons or businesses from financial loss caused by perils. Perils can include losses due to fire, water, earthquake, wind, explosions, aircraft damage (as when an aircraft crashes into a structure), lightning, hail, riot or civil commotion, smoke, vandalism, falling objects, theft, volcanic eruptions, and freezing. An insurance policy providing property insurance may cover some or all of these categories of perils. By paying a premium on a regular basis, a policyholder is insured against a loss caused by a peril within the scope of the policy. 
     Insurance rates are determined through an actuarial process. The process looks at data related to customer characteristics to determine differences in expected loss costs for different customers. One part of the actuarial process, referred to as “territorial ratemaking,” is an actuarial process for adjusting rates in insurance or other risk transfer mechanisms based on location. The ratemaking process is prospective because property and casualty rates are typically developed prior to the transfer of risk from a customer to an insurance company. Accordingly, the rate in an insurance policy reflects an estimate of the expected value of future costs, so techniques estimate future losses and costs to determine insurance rates. 
     By analyzing loss-cost data of a region over a number of years, a company can estimate future exposure to risk more accurately by invoking mathematical methodologies. In the insurance industry, a common practice for determining rates involves estimating future costs by looking at past loss-cost data. Different actuarial methodologies further improve the credibility of the data available in the ratemaking process. 
     Data in many companies and government agencies is often organized according to ZIP code. Often, there is a need to identify geographical relationships of occurrences or experiences of a particular group with the experiences of another group. However, experiences may be less relevant if the other group is located a significant distance from the studied group&#39;s location. 
     The credibility of the data is a predictive value that an actuary attaches to a particular body of data. One way of increasing the credibility of the data is to increase the size of the group or to make groupings more homogeneous. Loss cost data is frequently broken down into commonly used, geographically defined regions such as postal ZIP codes. When data is sorted by ZIP code, some areas defined by ZIP codes may have little or no recent data from which to predict premiums accurately. 
     Pure premium data values can vary significantly among ZIP codes. The same data can also change significantly from year to year. In addition, losses from a given peril are statistically just as likely to occur across the street or on the next block, as where a particular loss occurred. The property located on the other side of the street may fall, however, within a different ZIP code where few if any such losses were experienced. 
     It is reasonable to assume that properties in neighboring areas are most likely to experience the same loss as the property that experienced the actual loss. However, an exposure to all perils may have a measurable difference in frequency or severity for properties that get further away from a given location. 
     One way to estimate bordering ZIP codes is to determine the shortest distance of the target ZIP code to the closest centroid of a neighboring ZIP code. However, using such a method creates a problem when an automated system cannot determine whether the shortest distance describes the only neighboring ZIP code or if there are others, and if so, how many there are. Given an irregular border, many ZIP codes could border the target ZIP code. In addition, because a centroid of a region may not be located in the center or even within a region, using such a methodology based on centroids might not be accurate. As a result, centroids alone may not be the best approach for determining neighboring ZIP codes. 
     Therefore, it is useful to relate the experience of neighboring properties and recognize that the relevance of the neighboring experience will diminish with distance. 
     SUMMARY 
     A method for identifying common borders of geographically defined regions consistent with this invention comprises reading ZIP codes and associated cartographic boundaries from a database; storing pairs of coordinates for the boundaries in a matrix; calculating values representing each pair of coordinates in the matrix; storing the calculated values in an encoded coordinates matrix; using the values in the encoded coordinates matrix to determine common segments; forming a connection matrix wherein each row represents a connection of a ZIP code with another ZIP code; and calculating a neighborhood matrix storing values that represent an indication of closeness of each ZIP code in the neighborhood matrix to a target ZIP code. 
     A system for identifying common borders of geographically defined regions consistent with this invention comprises a data processor; a module for causing the data processor to read ZIP codes and associated cartographic boundaries from a database; a module for causing the data processor to store pairs of coordinates for the boundaries in a matrix; a module for causing the data processor to calculate values representing each pair of coordinates in the matrix; a module for causing the data processor to store the calculated values in an encoded coordinates matrix; a module for causing the data processor to use the values in the encoded coordinates matrix to determine common segments; a module for causing the data processor to form a connection matrix wherein each row represents a connection of a ZIP code with another ZIP code; and a module for causing the data processor to calculate a neighborhood matrix storing values that represent an indication of closeness of each ZIP code in the neighborhood matrix to a target ZIP code. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       All descriptions are exemplary and explanatory only and do not restrict the invention, as claimed. The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention. In the drawings: 
         FIG. 1  is a flow diagram of a process for creating ZIP-code connection matrices; 
         FIG. 2  represents the first 20 rows of the matrices ZIP and COORD for the state of Iowa; 
         FIG. 3  is a exemplary matrix used in the process of  FIG. 1 ; 
         FIG. 4  is an exemplary matrix that represents the result of encoding the first twenty coordinates of the Iowa polygon data; 
         FIG. 5  is an exemplary segment matrix; 
         FIGS. 6A and 6B  show a process for aligning the ZIP values with the SEGMENT values; 
         FIG. 7  is a procedure for ensuring that all sets of adjoining ZIP codes touch all other sets; and 
         FIG. 8  illustrates a diagram of a system consistent with the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     Reference will now be made in detail to exemplary embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts. 
     The term “geocoding” refers to converting features found on a map into a computer-digital form. Through a gecoding process, spatial locations of map features are referenced geographically to a coordinate system stored by a computer system. Gecoding tools have various applications. For example, geocoding tools are used in marketing applications to define regions and create customer profiles. Geocoding tools also create maps that display relationships between regions that form a territory. A geocoding tool may use either a radius or a driving time to create a territory. For example, one may perform analysis of regions by forming territories based on distance from a target location identified by latitude and longitude. A radius of a specified distance extending from the target location may define a region. 
     Systems and methods consistent with the present invention provide a geocoding tool using a target region, for example, such as a ZIP code. Since a ZIP code typically describes a region and not a point, systems and methods consistent with the present invention identify geographically-based regions that neighbor a target region. Surrounding regions may form “rings” of neighbors that together combine to create a single neighboring territory. 
     This neighborhood process is useful in various industries, including the insurance industry. Embodiments consistent with the present invention may help an insurance company determine ZIP codes adjacent to areas with a high risk for natural perils such as hurricanes, floods, mudslides, other water-related perils, brush fires, and earthquakes without requiring physical inspection of an area. For example, an insurance company may determine future potential losses and fulfill state and local governmental compliance requirements that may exist in an area. Similarly, areas exhibiting growth and other strong market characteristics can be linked to adjacent ZIP codes to analyze other risks or common traits. 
       FIG. 1  shows a process  100  for creating ZIP-code connection matrices. While the following example is described in terms of using ZIP codes to designate regions, the present invention is not limited to using ZIP codes. Any geographic region may be considered consistent with the present invention. 
     Process  100  begins by encoding Cartesian coordinates representing ZIP code polygons. First, a data processing system reads in ZIP codes and their associated cartographic polygons. (Step  105 ) A cartographic polygon can be represented as a single column matrix of ZIP codes and a two-column matrix of the associated polygon coordinates. In that two-column matrix, the first column is the set of latitudes and the second column is the set of longitudes. 
     For example, as  FIG. 2  shows, the first matrix  200  is called ZIP and the second  210  is called COORD (representing the coordinate values). Next, the system determines the highest and lowest values (i.e., longitude and latitude) for each column of COORD. (Step  110 ) From this, the system calculates a value range for each column, representing the difference between each maximum and minimum. 
     To illustrate, refer to  FIG. 2 , which represents the first 20 rows of the matrices ZIP and COORD for the state of Iowa. There are as many values of 50001 as there are coordinates for that ZIP code. Both columns of COORD are shown with implicit decimal places. The implicit decimal point for the latitudes is between the second and third decimal place and the implicit decimal point for the longitudes is between the third and fourth columns. Thus, the first row of the matrix is really 41.334663 and −93.428650 respectively. The highest values in the matrix are 43500828 and −90158249 respectively, while the lowest are 40375767 and −96637917 respectively. The ranges for these coordinates are thus 3125062 for latitudes and 6479669 for longitudes. 
     The system next encodes these coordinates into one value for each pair of coordinates. (Step  115 ) This can be done by subtracting the respective minima from both pairs of coordinates, multiplying the result for latitudes by the range for latitudes, and adding the result for longitudes. Using  FIG. 2 , for example, the result of the subtraction yields the matrix shown in  FIG. 3 . 
     Multiplying each column in this matrix by the minimum latitude, 3125062, and adding the second column yields a one-column matrix, or Encoded Coordinates column vector (Step  120 ), as shown in  FIG. 4 . The matrix in  FIG. 4  represents the result of encoding the first twenty coordinates of the Iowa polygon data. There would be one number for each coordinate pair, or 34,069 numbers in all for Iowa. The reason for subtracting the minima is to keep the numbers within the range permitted by double precision floating-point numbers. The maximum number in such a coordinate recoding scheme is 20249365864122 that is 14 digits. This is fewer than the 16 digits allowed for double-precision floating-point numbers. 
     After encoding the coordinates, the system uses the values in the matrix to determine common segments. (Step  125 ) One ZIP code is contiguous to another if it shares a common segment. 
     To align the ZIP code values (Step  130 ) with the SEGMENT values, the system uses the process  600  shown in  FIG. 6 . First, the system creates a Boolean vector (all zeros and ones) (Step  610 ) as follows:
 
 m =[(−1↓ZIP)=(1↓ZIP)]
 
     This vector is equal to one where successive values of ZIP (treated as a vector) are the same and is equal to zero where successive values of ZIP are different. Note that m has n−1 elements. 
     Next, the system creates a new ZIP code vector, ZIP (Step  620 ), as follows:
 
zip= m /(1↓ZIP)
 
     where zip=m/x means zip is a vector with a length equal to the sum of m (the number of “ones” in m) and values corresponding to those values of the vector x where m is equal to one. In this manner, the system compresses the vector x to eliminate those positions where m is =zero. 
     The system uses vector m to compress the SEGMENT matrix over its first dimension (rows) (Step  630 ), as follows:
 
 S=m/[ 1]SEGMENT
 
     By doing so, the system eliminates those “segments” which span two different ZIP codes, leaving only segments within a single ZIP code. Thus, the length of ZIP and the number of rows in S are the same. 
     Next, the system rotates those elements of S where the value in the second column is less than the value in the first column. (Step  640 ) This insures that the value in the first column is always less than or equal to the value in the second column. Thus,
 
 S =(&gt;/ S )Φ S  
 
     which means rotate if the first value on a given row is greater than the value in the second row. 
     Next, the system sorts the matrix S and stores the resulting order vector in a vector called o. (Step  650 )
 
 o =(Sort) s  stands for the sort order of S
 
     where (Sort) stands for sorting. The result is the sort order, however, not the actual data in sorted order. 
     The system next arranges the matrix S in sorted order. (Step  660 )
 
 S=S[o;] 
 
     This is equivalent to PL/I notation applying the vector o to the columns of the matrix S. 
     With S in sorted order, all equal segments should be next to each other. With this arrangement, the system compares each row of S to the following row (Step  670 ) as follows:
 
Δ=(1↓[1 ]S )=(−1↓[1 ]S )
 
Δ=Δ[;1]=Δ[;2]
 
     This yields a Boolean vector with ones wherever two segments are equal. The system next arranges the ZIP codes in the same order as S. (Step  675 )
 
zip=zip[(Sort) s] 
 
     After comparing each member of the sorted ZIP codes (ZIP) to each other, the system eliminates all values where Δ is equal to zero. (Step  680 )
 
 CM =Δ/(−1↓zip),[1.5](1↓zip)
 
     This yields a matrix with ZIP codes in both columns and where each ZIP code shares the same line segment. Such ZIP codes are contiguous. 
     The system next rearranges this matrix by making sure that the ZIP code in the second column is always greater than the ZIP code in the first column. (Step  685 ):
 
 CM =(&gt;/ CM )Φ CM  
 
     The system then eliminates all duplicates. (Step  690 ).
 
 CM =set( CM )
 
     The function set is an APL program that eliminates duplicates after sorting. Finally, the system eliminates all cases where the second ZIP code is equal to the first. (Step  695 )
 
 CM =( CM[; 1 ]≠CM[; 2])/[1 ]CM  
 
     The expression in parentheses represents a Boolean vector where there is no match. This vector is then used to compress out the rows of the matrix CM where a zero implies that the values in both columns are the same. 
     Process  600  produces a list of all ZIP codes that touch each other as determined by having identical segments in the polygon data. All segments that touch each other are identical. That is, if there is a segment break in one ZIP code, there is a corresponding segment break in the adjoining ZIP code. 
     The system can also follow a procedure (as shown in  FIG. 7 ) to make sure that all sets of adjoining ZIP codes touch all other sets. (Step  140 ) This is necessary, for instance, in New York where no ZIP codes in Brooklyn or Staten Island touch any ZIP codes for the rest of the state. 
     As shown in  FIG. 7 , the system first looks for ZIP codes that don&#39;t touch any others. (Step  710 ) These will be missing from the connection matrix produced in the first stage of analysis. The system next takes each such ZIP code and joins it to the four closest ZIP codes as measured by the distance from the centroid of the subject ZIP code to the centroids of all other ZIP codes. (Step  720 ) 
     After joining every ZIP code to the connection matrix, the system determines whether there are noncontiguous groups of ZIP codes (i.e., groups of ZIP codes that do not touch other groups). (Step  730 ) This can be accomplished by an algorithm that starts with one ZIP code and follows through every ZIP code that touches it until all touching ZIP codes have been exhausted. If any are left, the system starts with one of the remaining ZIP codes and repeats the procedure. This continues until every ZIP code has been accounted for. 
     In New York, there are five groups that do not touch: Manhattan, Staten Island, the remainder of the state, two on Long Island that do not touch the rest of the state, and two forming a barrier island south of Long Island that do not touch the rest of the island. 
     The system goes through each such group and determines the ZIP codes from one group with the closest centroids to the centroids of ZIP codes in the other groups. (Step  740 ) The system then joins all such ZIP codes where the centroids are a mile or less apart, and if there are fewer than four, it joins the four closest ZIP codes even if the distances between their centroids are more than a mile. (Step  750 ) 
     After completing this process, the system checks whether all groups are joined (Step  760 ) and repeats the process if not. The final result is a two-column connection matrix where each row indicates a connection of one ZIP code with another. Most such connections are determined because they share common boundary segments. Situations exist where territories do not touch, such as, for example, regions having water boundaries. In these situations, connections are based on centroid closeness. 
     Returning to  FIG. 1 , a two-column connection matrix has been created, in which each row of the matrix lists regions, such as ZIP codes, that are touching. (Step  140 ) After determining the connection matrix (step  150 ), the system creates a neighborhood matrix, preferably by using the data in the connection matrix to determine for each ZIP code the ZIP codes that it borders. 
     The neighborhood matrix is defined to include one row and one column for each ZIP code or region under consideration. For example, in a state with 1,500 ZIP codes, the neighborhood matrix will have 1,500 rows and 1,500 columns. Within the neighborhood matrix, numbers represent a relationship between each ZIP code and the other represented ZIP codes. 
     To create the neighborhood matrix, the system starts at the first row and places a “1” in the first column since the column and row ZIP code are the same. This occurs because the intersection of the first row and the first column represent the same ZIP code. As a result, “1” will represent all elements of the diagonal of the matrix. 
     The neighborhood matrix then uses the connection matrix to determine the ZIP codes that border or touch the ZIP code of the first row. A “2” is placed in each column in the first row underneath the ZIP codes that touch the ZIP code being mapped into the neighborhood matrix. This information defines the set of immediate neighbors for the first ZIP code. The system proceeds to examine the ZIP codes represented by all of the rows in the neighborhood matrix and locates all of the ZIP codes that touch the first ZIP code under consideration. At this point, the neighborhood matrix stores diagonally values of “1” representing rows and columns that represent the same ZIP code and the values of “2” representing ZIP codes touching the ZIP code under consideration. A value of “0” may be used to fill in the remaining elements of the matrix as a placeholder. 
     Next, the system proceeds to examine all remaining ZIP codes using the connection matrix to determine which ZIP codes touch the ZIP codes designated with the value of “2.” In the next iteration, each ZIP code designated by a “2” is examined to determine which ZIP codes border or touch it, and a value of “3” is assigned to the matrix. The process repeats for each row successively and continues until desired or until all ZIP codes are accounted for. 
     At the conclusion of the process, one may determine whether a territory, such as a ZIP code, borders another territory, based on the connection matrix. In addition, the neighborhood matrix provides a regional view for a particular location by providing an analysis of the neighboring regions that touch a selected territory or ZIP code. The above methodology is applicable in the insurance industry, for example, where one is interested in determining geographical relationships when determining insurance rates. 
     For example, in the insurance industry, embodiments consistent with the present invention normalize the loss cost data of territories surrounding a target ZIP code. The loss cost data can identify historic loss costs based on perils that have occurred in a target ZIP code. Embodiments with application to the insurance industry therefore determine ZIP codes adjacent to or near areas that have a high risk for natural perils such as hurricanes, floods, mudslides, brushfires, earthquakes, and other perils. One may determine a high risk based on an incident of risks causing a monetary damage exceeding a certain threshold over a period of time, for example. 
     Embodiments consistent with the present invention have wide ranging applications, such as creating maps that present neighboring relationships by highlighting borders, color coding regions, shading regions, or displaying other graphical indicators. Embodiments consistent with the present invention also identify neighboring ZIP codes that form a territory. The territory represents all neighboring ZIP codes of a target location or region. A database storing ZIP code data collected from all ZIP codes that comprise the territory may be normalized or mathematically manipulated to produce economically useful output. 
     In other industries, embodiments consistent with the present invention may identify neighboring ZIP codes that border stores that are located in a specific ZIP code instead of using an arbitrary radius of distance (such as miles or kilometers) or driving time. Embodiments may identify the ZIP codes that form the closest ring of neighbors, followed by the next closest, and so on. The data produced from such an analysis may determine sales coverage, sales territories, market penetration, or other quantifiable data relationships. 
     System Configuration 
       FIG. 8  illustrates a system  800  consistent with the present invention. System  800  includes a server  805 , connected to a network  860 , including a CPU  820  and a memory  830 . Software loaded into memory  830  from, for example, a disk drive (not shown) at the direction of CPU  820  may be used to implement a program for determining insurance premiums for property. Various program modules may be stored in memory  830  as software for implementing the functionality of the present invention. 
     Network  860  provides communications between the various entities in system  800 , such as user terminals  870 - 890 . Network  860  may be a shared, public, or private network and encompass a wide area or local area. Further, network  860  may be implemented through any suitable combination of wired and/or wireless communication networks. By way of example, network  860  may be implemented through a wide area network (WAN), local area network (LAN), an intranet, or the Internet. 
     Terminals  870 - 890  allow a user to exchange information with server  805 . Terminals  870 - 890  may be any type of appropriate device for communicating with server  805  over network  860 . For example, terminal  870  may be a PDA running a program for communicating with server  805 , while terminal  880  may be a desktop computer running a web browser for communicating with server  805  via the Internet. Terminal  890  may be a standard landline telephone or wireless phone. 
     Users may access server  805  via network  860  to determine insurance premiums for property through a web browser running on, for example, terminal  880 . A website may include options for specifying a customer&#39;s location, and may present the user with a series of screens prompting the user to make various selections. 
     The foregoing descriptions of the invention have been presented for purposes of illustration and description. They are not exhaustive and do not limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practicing of the invention. For example, the described implementation includes software, but the present invention may be implemented as a combination of hardware and software or in hardware alone. Additionally, although aspects of the present invention are described as being stored in memory, one skilled in the art will appreciate that these aspects can also be stored on other types of computer-readable media, such as secondary storage devices, like hard disks, floppy disks, or CD-ROM; a carrier wave from the Internet or other propagation medium; or other forms of RAM or ROM. The scope of the invention is defined by the claims and their equivalents. 
     Other embodiments of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. The specification and examples should be considered as exemplary only, with a true scope and spirit of the invention being indicated by the following claims.