Head/tail breaks is a clustering algorithm for data with a heavy-tailed distribution such as power laws and lognormal distributions. The heavy-tailed distribution can be simply referred to the scaling pattern of far more small things than large ones, or alternatively numerous smallest, a very few largest, and some in between the smallest and largest. The classification is done through dividing things into large (or called the head) and small (or called the tail) things around the arithmetic mean or average, and then recursively going on for the division process for the large things or the head until the notion of far more small things than large ones is no longer valid, or with more or less similar things left only. [1] Head/tail breaks is not just for classification, but also for visualization of big data by keeping the head, since the head is self-similar to the whole. Head/tail breaks can be applied not only to vector data such as points, lines and polygons, but also to raster data like digital elevation model (DEM).
The head/tail breaks is motivated by inability of conventional classification methods such as equal intervals, quantiles, geometric progressions, standard deviation, and natural breaks - commonly known as Jenks natural breaks optimization or k-means clustering to reveal the underlying scaling or living structure with the inherent hierarchy (or heterogeneity) characterized by the recurring notion of far more small things than large ones. [2] [3] Note that the notion of far more small things than large one is not only referred to geometric property, but also to topological and semantic properties. In this connection, the notion should be interpreted as far more unpopular (or less-connected) things than popular (or well-connected) ones, or far more meaningless things than meaningful ones. Head/tail breaks uses the mean or average to dichotomize a dataset into small and large values, rather than to characterize classes by average values, which is unlike k-means clustering or natural breaks. Through the head/tail breaks, a dataset is seen as a living structure with an inherent hierarchy with far more smalls than larges, or recursively perceived as the head of the head of the head and so on. It opens up new avenues of analyzing data from a holistic and organic point of view while considering different types of scales and scaling in spatial analysis. [4]
Given some variable X that demonstrates a heavy-tailed distribution, there are far more small x than large ones. Take the average of all xi, and obtain the first mean m1. Then calculate the second mean for those xi greater than m1, and obtain m2. In the same recursive way, we can get m3 depending on whether the ending condition of no longer far more small x than large ones is met. For simplicity, we assume there are three means, m1, m2, and m3. This classification leads to four classes: [minimum, m1], (m1, m2], (m2, m3], (m3, maximum]. In general, it can be represented as a recursive function as follows:
Recursive function Head/tail Breaks: Rank the input data values from the biggest to the smallest; Compute the mean value of the data Break the data (around the mean) into the head and the tail; // the head for data values greater the mean // the tail for data values less the mean If (length(head)/length(data) <=40%): Head/tail Breaks(head); End Function
The resulting number of classes is referred to as ht-index, an alternative index to fractal dimension for characterizing complexity of fractals or geographic features: the higher the ht-index, the more complex the fractals. [5]
The criterion to stop the iterative classification process using the head/tail breaks method is that the remaining data (i.e., the head part) are not heavy-tailed, or simply, the head part is no longer a minority (i.e., the proportion of the head part is no longer less than a threshold such as 40%). This threshold is suggested to be 40% by Jiang et al. (2013), [6] just as the codes above (i.e., (length/head)/length(data) ≤ 40%). This process is called head/tail breaks 1.0. But sometimes a larger threshold, for example 50% or more, can be used, as Jiang and Yin (2014) [5] noted in another article: "this condition can be relaxed for many geographic features, such as 50 percent or even more". However, all heads' percentage on average must be smaller than 40% (or 41, 42%), indicating far more small things than large ones. Many real-world data cannot be fit into a perfect long tailed distribution, therefore its threshold can be relaxed structurally. In head/tail breaks 2.0 the threshold only applies to the overall heads' percentage. [7] This means that the percentages of all heads related to the tails should be around 40% on average. Individual classes can have any percentage spit around the average, as long as this averages out as a whole. For example, if there is data distributed in such a way that it has a clearly defined head and tail during the first and second iteration (length(head)/(length(data)<20%) but a much less well defined long tailed distribution for the third iteration (60% in the head), head/tail breaks 2.0 allows the iteration to continue into the fourth iteration which can be distributed 30% head - 70% tail again and so on. As long as the overall threshold is not surpassed the head/tail breaks classification holds.
A good tool to display the scaling pattern, or the heavy-tailed distribution, is the rank-size plot, which is a scatter plot to display a set of values according to their ranks. With this tool, a new index [8] termed as the ratio of areas (RA) in a rank-size plot was defined to characterize the scaling pattern. The RA index has been successfully used in the estimation of traffic conditions. However, the RA index can only be used as a complementary method to the ht-index, because it is ineffective to capture the scaling structure of geographic features.
In addition to the ht-index, the following indices are also derived with the head/tail breaks.
Instead of more or less similar things, there are far more small things than large ones surrounding us. Given the ubiquity of the scaling pattern, head/tail breaks is found to be of use to statistical mapping, map generalization, cognitive mapping and even perception of beauty . [6] [12] [13] It helps visualize big data, since big data are likely to show the scaling property of far more small things than large ones. Essentially geographic phenomena can be scaleful or scale-free. Scaleful phenomena can be explained by conventional mathematical or geographical operations, but scale-free phenomena can not. Head/tail breaks can be used to characterize the scale-free phenomena, which are in the majority. [14] The visualization strategy is to recursively drop out the tail parts until the head parts are clear or visible enough. [15] [16] In addition, it helps delineate cities or natural cities to be more precise from various geographic information such as street networks, social media geolocation data, and nighttime images.
As the head/tail breaks method can be used iteratively to obtain head parts of a data set, this method actually captures the underlying hierarchy of the data set. For example, if we divide the array (19, 8, 7, 6, 2, 1, 1, 1, 0) with the head/tail breaks method, we can get two head parts, i.e., the first head part (19, 8, 7, 6) and the second head part (19). These two head parts as well as the original array form a three-level hierarchy:
The number of levels of the above-mentioned hierarchy is actually a characterization of the imbalance of the example array, and this number of levels has been termed as the ht-index. [5] With the ht-index, we are able to compare degrees of imbalance of two data sets. For example, the ht-index of the example array (19, 8, 7, 6, 2, 1, 1, 1, 0) is 3, and the ht-index of another array (19, 8, 8, 8, 8, 8, 8, 8, 8) is 2. Therefore, the degree of imbalance of the former array is higher than that of the latter array.
The use of fractals in modelling human geography has for a longer period been seen as useful in measuring the spatial distribution of human settlements. [17] Head/tail breaks can be used to do just that with a concept called natural cities. The term ‘natural cities’ refers to the human settlements or human activities in general on Earth's surface that are naturally or objectively defined and delineated from massive geographic information based on head/tail division rule, a non-recursive form of head/tail breaks. [18] [19] Such geographic information could be from various sources, such as massive street junctions [19] and street ends, a massive number of street blocks, nighttime imagery and social media users’ locations etc. Based on these the different urban forms and configurations detected in cities can be derived. [20] Distinctive from conventional cities, the adjective ‘natural’ could be explained not only by the sources of natural cities, but also by the approach to derive them . Natural cities are derived from a meaningful cutoff averaged from a massive number of units extracted from geographic information. [15] Those units vary according to different kinds of geographic information, for example the units could be area units for the street blocks and pixel values for the nighttime images. [21] A natural cities model has been created using ArcGIS model builder, [22] it follows the same process of deriving natural cities from location-based social media, [18] namely, building up huge triangular irregular network (TIN) based on the point features (street nodes in this case) and regarding the triangles which are smaller than a mean value as the natural cities. These natural cities can also be created from other open access information like OpenStreetMap and further be used as an alternative delineation of administrative boundaries. [23] Scaling law can also at the same time correctly be identified and the administrative borders can be created to respect this by the delineation of the natural cities. [24] [25] This type methodology can help urban geographers and planners by correctly identifying the effective urban territorial scope of the areas they work in. [26]
Natural cities can vary depending on the scale on which the natural cities are delineated, which is why optimally they have to be based on data from the whole world. Due to that being computationally impossible, a country or county scale is suggested as alternative. [27] Due to the scale-free nature of natural cities and the data they are based on there are also possibilities to use the natural cities method for further measurements. One of the main advantages of natural cities is that it is derived bottom-up instead of top-down. That means that the borders are determined by the data of something physical rather than determined by an administrative government or administration. [28] For example by calculating the natural cities of a natural city recursively the dense areas within a natural city are identified. These can be seen as city centers for example. By using the natural cities method in this way further border delineations can be made dependent on the scale the natural cities were generated from. [29] Natural cities derived from smaller regional areas will provide less accurate but still usable results in certain analysis, like for example determining urban expansion over time. [30] As mentioned before though, optimally natural cities should be based on a massive amount of for example street intersections for an entire country or even the world. This is because natural cities are based on the wisdom of crowds thinking, which needs the biggest set of available data for the best results. Also note that the structure of natural cities can be considered to be fractal in nature. [31]
It is important when head/tail breaks are being used to generate natural cities, that the data is not aggregated afterwards. For example, the amount of generated natural cities can only be known after they are generated. It is not possible to use a pre-defined number of cities for an area or country and aggregate the results of the natural cities to administratively determined city borders. Naturally natural cities should follow Zipf's law, if they do not, the area is most likely too small, or data has probably been processed wrongly. An example of this is seen in a research where head/tail breaks were used to extract natural cities, but they were aggregated to administrative borders, which following that concluded that the cities do not follow Zipf's law. [32] This happens more often in science, where papers actually produce results which are actually false. [33]
Current color renderings for DEM or density map are essentially based on conventional classifications such as natural breaks or equal intervals, so they disproportionately exaggerate high elevations or high densities. As a matter of fact, there are not so many high elevations or high-density locations. [34] It was found that coloring based head/tail breaks is more favorable than those by other classifications. [35] [36]
The pattern of far more small things than large ones frequently recurs in geographical data. A spiral layout inspired by the golden ratio or Fibonacci sequence can help visualize this recursive notion of scaling hierarchy and the different levels of scale. [37] [38] In other words, from the smallest to the largest scale, a map can be seen as a map of a map of a map, and so on.
Other applications of Head/tail breaks:
The following implementations are available under Free/Open Source Software licenses.
Chaos theory is an interdisciplinary area of scientific study and branch of mathematics. It focuses on underlying patterns and deterministic laws of dynamical systems that are highly sensitive to initial conditions. These were once thought to have completely random states of disorder and irregularities. Chaos theory states that within the apparent randomness of chaotic complex systems, there are underlying patterns, interconnection, constant feedback loops, repetition, self-similarity, fractals and self-organization. The butterfly effect, an underlying principle of chaos, describes how a small change in one state of a deterministic nonlinear system can result in large differences in a later state. A metaphor for this behavior is that a butterfly flapping its wings in Brazil can cause a tornado in Texas.
In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as illustrated in successive magnifications of the Mandelbrot set. This exhibition of similar patterns at increasingly smaller scales is called self-similarity, also known as expanding symmetry or unfolding symmetry; if this replication is exactly the same at every scale, as in the Menger sponge, the shape is called affine self-similar. Fractal geometry lies within the mathematical branch of measure theory.
Landscape ecology is the science of studying and improving relationships between ecological processes in the environment and particular ecosystems. This is done within a variety of landscape scales, development spatial patterns, and organizational levels of research and policy. Landscape ecology can be described as the science of "landscape diversity" as the synergetic result of biodiversity and geodiversity.
One of the major subfields of urban economics, economies of agglomeration, explains, in broad terms, how urban agglomeration occurs in locations where cost savings can naturally arise. This term is most often discussed in terms of economic firm productivity. However, agglomeration effects also explain some social phenomena, such as large proportions of the population being clustered in cities and major urban centers. Similar to economies of scale, the costs and benefits of agglomerating increase the larger the agglomerated urban cluster becomes. Several prominent examples of where agglomeration has brought together firms of a specific industry are: Silicon Valley and Los Angeles being hubs of technology and entertainment, respectively, in California, United States; and London, United Kingdom, being a hub of finance.
In mathematics, a fractal dimension is a term invoked in the science of geometry to provide a rational statistical index of complexity detail in a pattern. A fractal pattern changes with the scale at which it is measured. It is also a measure of the space-filling capacity of a pattern, and it tells how a fractal scales differently, in a fractal (non-integer) dimension.
Urban ecology is the scientific study of the relation of living organisms with each other and their surroundings in an urban environment. An urban environment refers to environments dominated by high-density residential and commercial buildings, paved surfaces, and other urban-related factors that create a unique landscape. The goal of urban ecology is to achieve a balance between human culture and the natural environment.
Land use planning or Land-use regulation is the process of regulating the use of land by a central authority. Usually, this is done to promote more desirable social and environmental outcomes as well as a more efficient use of resources. More specifically, the goals of modern land use planning often include environmental conservation, restraint of urban sprawl, minimization of transport costs, prevention of land use conflicts, and a reduction in exposure to pollutants. In the pursuit of these goals, planners assume that regulating the use of land will change the patterns of human behavior, and that these changes are beneficial. The first assumption, that regulating land use changes the patterns of human behavior is widely accepted. However, the second assumption - that these changes are beneficial - is contested, and depends on the location and regulations being discussed.
Surface roughness can be regarded as the quality of a surface of not being smooth and it is hence linked to human (haptic) perception of the surface texture. From a mathematical perspective it is related to the spatial variability structure of surfaces, and inherently it is a multiscale property. It has different interpretations and definitions depending on the disciplines considered.
Spatial analysis is any of the formal techniques which studies entities using their topological, geometric, or geographic properties. Spatial analysis includes a variety of techniques using different analytic approaches, especially spatial statistics. It may be applied in fields as diverse as astronomy, with its studies of the placement of galaxies in the cosmos, or to chip fabrication engineering, with its use of "place and route" algorithms to build complex wiring structures. In a more restricted sense, spatial analysis is geospatial analysis, the technique applied to structures at the human scale, most notably in the analysis of geographic data. It may also be applied to genomics, as in transcriptomics data.
The modifiable areal unit problem (MAUP) is a source of statistical bias that can significantly impact the results of statistical hypothesis tests. MAUP affects results when point-based measures of spatial phenomena are aggregated into spatial partitions or areal units as in, for example, population density or illness rates. The resulting summary values are influenced by both the shape and scale of the aggregation unit.
A multifractal system is a generalization of a fractal system in which a single exponent is not enough to describe its dynamics; instead, a continuous spectrum of exponents is needed.
In behavioral geography, a mental map is a person's point-of-view perception of their area of interaction. Although this kind of subject matter would seem most likely to be studied by fields in the social sciences, this particular subject is most often studied by modern-day geographers. They study it to determine subjective qualities from the public such as personal preference and practical uses of geography like driving directions.
Rank–size distribution is the distribution of size by rank, in decreasing order of size. For example, if a data set consists of items of sizes 5, 100, 5, and 8, the rank-size distribution is 100, 8, 5, 5. This is also known as the rank–frequency distribution, when the source data are from a frequency distribution. These are particularly of interest when the data vary significantly in scales, such as city size or word frequency. These distributions frequently follow a power law distribution, or less well-known ones such as a stretched exponential function or parabolic fractal distribution, at least approximately for certain ranges of ranks; see below.
Spatial heterogeneity is a property generally ascribed to a landscape or to a population. It refers to the uneven distribution of various concentrations of each species within an area. A landscape with spatial heterogeneity has a mix of concentrations of multiple species of plants or animals (biological), or of terrain formations (geological), or environmental characteristics filling its area. A population showing spatial heterogeneity is one where various concentrations of individuals of this species are unevenly distributed across an area; nearly synonymous with "patchily distributed."
Fractal analysis is assessing fractal characteristics of data. It consists of several methods to assign a fractal dimension and other fractal characteristics to a dataset which may be a theoretical dataset, or a pattern or signal extracted from phenomena including topography, natural geometric objects, ecology and aquatic sciences, sound, market fluctuations, heart rates, frequency domain in electroencephalography signals, digital images, molecular motion, and data science. Fractal analysis is now widely used in all areas of science. An important limitation of fractal analysis is that arriving at an empirically determined fractal dimension does not necessarily prove that a pattern is fractal; rather, other essential characteristics have to be considered. Fractal analysis is valuable in expanding our knowledge of the structure and function of various systems, and as a potential tool to mathematically assess novel areas of study. Fractal calculus was formulated which is a generalization of ordinary calculus.
Cartographic generalization, or map generalization, includes all changes in a map that are made when one derives a smaller-scale map from a larger-scale map or map data. It is a core part of cartographic design. Whether done manually by a cartographer or by a computer or set of algorithms, generalization seeks to abstract spatial information at a high level of detail to information that can be rendered on a map at a lower level of detail.
Bin Jiang is a professor in geographic information science, geographic information systems or geoinformatics at the University of Gävle, Sweden. He is affiliated to the Royal Institute of Technology Stockholm (KTH) through the KTH Research School at Gävle. He has been coordinating the Nordic Network in Geographic Information Science (NordGISci), and has organized a series of NordGISci summer schools for the Nordic young researchers. He is the founder and chair of the International Cartographic Association Commission on Geospatial Analysis and Modeling, and has established an ICA workshop series on the research topic. He is also an associate editor of the international journal: Computers, Environment and Urban Systems (Elsevier). He has developed the Head/tail Breaks a new classification for data with a heavy-tailed distribution.
Box counting is a method of gathering data for analyzing complex patterns by breaking a dataset, object, image, etc. into smaller and smaller pieces, typically "box"-shaped, and analyzing the pieces at each smaller scale. The essence of the process has been compared to zooming in or out using optical or computer based methods to examine how observations of detail change with scale. In box counting, however, rather than changing the magnification or resolution of a lens, the investigator changes the size of the element used to inspect the object or pattern. Computer based box counting algorithms have been applied to patterns in 1-, 2-, and 3-dimensional spaces. The technique is usually implemented in software for use on patterns extracted from digital media, although the fundamental method can be used to investigate some patterns physically. The technique arose out of and is used in fractal analysis. It also has application in related fields such as lacunarity and multifractal analysis.
Land cover maps are tools that provide vital information about the Earth's land use and cover patterns. They aid policy development, urban planning, and forest and agricultural monitoring.
Urban flooding is the inundation of land or property in cities or other built environment, caused by rainfall or coastal storm surges overwhelming the capacity of drainage systems, such as storm sewers. Urban flooding can occur regardless of whether or not affected communities are located within designated floodplains or near any body of water. It is triggered for example by an overflow of rivers and lakes, flash flooding or snowmelt. During the flood, stormwater or water released from damaged water mains may accumulate on property and in public rights-of-way. It can seep through building walls and floors, or backup into buildings through sewer pipes, cellars, toilets and sinks.