Fact-checked by Grok 2 weeks ago

Co-occurrence matrix

A co-occurrence matrix is a statistical construct that quantifies the with which pairs of discrete elements—such as intensities in an or in a —occur simultaneously within a defined spatial, temporal, or contextual proximity. This matrix, often represented as a square where rows and columns correspond to possible element values and entries denote joint occurrence counts, enables the modeling of dependencies and patterns in multidimensional data. In image processing, the gray-level co-occurrence matrix (GLCM), introduced by Haralick et al. in 1973, captures the distribution of co-occurring gray levels at specific offsets and orientations to analyze properties. The GLCM is computed by scanning an image for pairs of pixels separated by a predefined and , with matrix elements accumulating these pairwise frequencies; from this, second-order statistical features like angular second moment (), , , and are derived to classify textures in applications such as and . These features quantify aspects of image homogeneity, roughness, and regularity, proving effective for distinguishing structural variations in or multichannel images. In , co-occurrence matrices represent word associations by tallying how frequently pairs of words appear within a sliding window of a , facilitating the discovery of semantic and syntactic relationships. Pioneered in by Church and Hanks in 1990, this approach uses metrics like to weight co-occurrences, addressing sparsity and enabling techniques such as distributional semantic models and representations that underpin modern word embeddings. Beyond these domains, co-occurrence matrices extend to fields like bioinformatics for analysis and for edge prediction, underscoring their versatility in capturing relational statistics across datasets.

Fundamentals

Definition

A co-occurrence is a square that records the with which specified pairs of items co-occur within a or defined , such as documents, images, or networks. The entry at position (i, j) denotes the count of times item i and item j appear together, providing a symmetric where the diagonal elements capture self-co-occurrences. This structure inherently assumes that the rows and columns index the same set of items, making it a proximity suited for analyzing joint distributions. The primary role of a co-occurrence matrix is to quantify pairwise relationships and dependencies in discrete , enabling the extraction of statistical patterns that reveal underlying associations without requiring probabilistic assumptions beyond raw counts. For instance, in domains involving sequential or spatial , it highlights how often elements appear in proximity, serving as a foundational tool for higher-level analyses like similarity measures or clustering. Unlike an , which encodes binary or weighted connections in a to model structural (e.g., directed edges between nodes), a co-occurrence matrix focuses solely on the empirical of joint occurrences, treating the data as a of pairs rather than a predefined . To illustrate, consider a simple with two categories, A and B, where co-occurrences are tallied across observations. The resulting 2×2 co-occurrence matrix might appear as follows:
AB
A53
B34
Here, the off-diagonal entries (e.g., 3) indicate the number of times A and B co-occur, while the reflects undirected counting (BA equals AB). Such matrices are employed across various fields, including for dependencies and for word associations.

Historical Development

The concept of the co-occurrence matrix emerged from early efforts in and statistical analysis during the mid-20th century, with precursors in models that captured sequential co-occurrences in data like language patterns and image textures. In statistical linguistics, co-occurrence analysis drew from J.R. Firth's 1957 ideas on collocations, evolving in the 1960s through probabilistic models of word adjacency in . Similarly, in , Béla Julesz's 1962 conjecture on texture perception utilized second-order statistics—essentially pairwise co-occurrence measures—to explain human texture discrimination, influencing subsequent computational approaches. The formal introduction of the co-occurrence matrix in image processing occurred in 1973, when Robert M.. Haralick, along with K. Shanmugam and I. Dinstein, proposed the gray-tone spatial-dependence matrix in their seminal paper "Textural Features for Image Classification." This work defined the matrix as a joint probability distribution of pixel pairs at specified distances and orientations, enabling the derivation of 14 texture descriptors for automated image categorization, particularly in multispectral satellite imagery. Haralick's approach built on prior statistical texture studies, such as those using autocorrelation and Markov meshes, but standardized co-occurrence as a second-order statistical tool for practical feature extraction. The paper demonstrated its efficacy on rock texture classification, establishing it as a cornerstone for computer vision applications. In the late 1970s, extensions appeared in tasks; for instance, Albert L. Zobrist and William B. Thompson employed matrices in 1975 to construct distance functions for grouping in scene analysis, quantifying spatial relationships between image primitives. Meanwhile, in statistical and , the term-document matrix—a specialized structure counting term frequencies across documents—gained traction in the 1970s through Salton's , facilitating document similarity computations. The and saw expanded adoption, with the gray-level co-occurrence matrix (GLCM) becoming standardized in for robust texture analysis, as evidenced by its integration into segmentation and classification pipelines. In , term-document matrices evolved into broader co-occurrence frameworks for semantic analysis, supporting techniques like latent semantic indexing introduced by Deerwester et al. in 1990. Key extensions in came from R.W. Conners and C.A. Harlow, whose 1980 theoretical comparison of texture algorithms evaluated co-occurrence methods against alternatives, highlighting their strengths in multispectral image discrimination for applications like mapping. These developments solidified co-occurrence matrices as versatile tools across domains. Post-2000, co-occurrence matrices experienced renewed recognition in , serving as hand-crafted features for tasks in and beyond, often combined with classifiers like support vector machines. Influential works up to 2020 integrated them into hybrid systems; for example, a 1999 study by Soh and Tsatsoulis applied GLCM textures to classification, achieving high accuracy in . By 2020, fusions with emerged, such as GLCM-enhanced convolutional neural networks for medical image analysis. However, as of 2025, gaps persist in fully adapting co-occurrence matrices to end-to-end paradigms, where convolutional and transformer-based models predominate, limiting their role to interpretable or data-scarce scenarios rather than core learned representations.

Construction and Variants

Basic Construction Method

The basic construction of a co-occurrence matrix begins with a dataset consisting of N items, each belonging to one of L unique categories or types. An L × L matrix C is initialized to zero, where C(i, j) will count the number of times items of type i and type j co-occur according to a predefined notion of proximity or association in the data. For each pair of items that satisfy the co-occurrence criterion (e.g., adjacent positions or within a specified window), the corresponding entry C(i, j) is incremented by 1. This process yields the raw co-occurrence counts, capturing second-order dependencies in the dataset. In the context of grayscale image analysis, the co-occurrence matrix is particularly useful for texture characterization. Consider a I of dimensions M × N , quantized to G levels (typically G = 8 or 16 for computational efficiency). The matrix is parameterized by an offset vector (Δx, Δy), which defines the spatial relationship between pixel pairs, such as neighboring separated by a distance d at θ (e.g., θ = 0° for pairs with (Δx, Δy) = (d, 0), or θ = 45° for diagonal pairs with (Δx, Δy) = (d, d)). The entry C_{Δx, Δy}(i, j) is computed as the number of pixel pairs where the pixel at (x, y) has i and the pixel at (x + Δx, y + Δy) has j. Formally, C_{\Delta x, \Delta y}(i,j) = \sum_{x=1}^{M} \sum_{y=1}^{N} \begin{cases} 1 & \text{if } I(x,y)=i \text{ and } I(x+\Delta x, y+\Delta y)=j \\ 0 & \text{otherwise} \end{cases} Boundary handling is essential, as offsets may extend beyond image edges; common approaches include ignoring pairs that cross boundaries (effectively reducing the summation limits near edges), applying periodic wrapping, or using zero-padding to extend the image. Multiple matrices are often computed for different (d, θ) combinations, such as d = 1 and θ ∈ {0°, 45°, 90°, 135°}, to capture directional texture patterns. A naive implementation scans the image once per offset direction, checking valid neighbor pairs and incrementing the , with O(M N K), where K is the number of offset directions (typically constant, e.g., K = 4). The following illustrates the process for a single offset (Δx, Δy): 
Initialize C as G x G [matrix](/page/Matrix) of zeros
For x from 1 to M - |Δx| (to handle boundaries by ignoring edge pairs)
    For y from 1 to N - |Δy|
        i = I(x, y)
        j = I(x + Δx, y + Δy)
        C[i, j] += 1
Return C
This approach ensures efficient counting without redundant computations. The construction method adapts readily to non-spatial data, such as sequential datasets like text corpora. For , words are treated as "items" with L being the vocabulary size; co-occurrences are counted for word pairs appearing within a sliding window of size k (e.g., k = 5 words on either side of a target word). The matrix is built similarly by incrementing C(i, j) for each qualifying pair in the sequence, enabling the capture of syntactic and semantic associations. Normalization of the resulting matrix, such as dividing by the total number of pairs, is often applied afterward to obtain probabilities but is not part of the core construction.

Normalization Techniques and Variants

To normalize a raw co-occurrence matrix C(i,j), which counts the joint occurrences of i and j, each entry is typically divided by the number of co-occurrences across all pairs, yielding the P(i,j) = \frac{C(i,j)}{\sum_{k,l} C(k,l)}. This normalization transforms the matrix into a form suitable for probabilistic analysis, as introduced in the of gray-level co-occurrence matrices (GLCM) for texture features. From the joint probabilities, marginal distributions are derived as p_x(i) = \sum_j P(i,j) for the row marginals and p_y(j) = \sum_i P(i,j) for the column marginals, representing the individual probabilities of each . Conditional probabilities are then obtained as P(i|j) = \frac{P(i,j)}{p_y(j)} or P(j|i) = \frac{P(i,j)}{p_x(i)}, enabling the computation of metrics like or correlation that quantify dependence between . Several variants extend the basic co-occurrence matrix to capture nuanced relationships. In weighted co-occurrence matrices, entries are adjusted by a decay function based on the between co-occurring elements; for instance, in the Hyperspace Analogue to Language () model for semantic spaces, co-occurrences are weighted inversely proportional to their positional in sequences, emphasizing nearby pairs. Higher-order matrices generalize this to interactions beyond pairs, such as triples, represented as 3D tensors where an entry T(i,j,k) counts the joint occurrences of three elements; this is particularly useful in hypergraph representations or multi-way associations in . For relational data, the matrix can be directed (asymmetric) to preserve order in sequences like word pairs, or symmetric for undirected graphs where co-occurrence is mutual. Handling multi-dimensional data, such as color images, involves extensions beyond . One approach computes separate co-occurrence matrices for each color channel (e.g., , , ), while a joint variant constructs a higher-dimensional matrix over combined RGB values, quantized into discrete bins; multispectral methods further include cross-channel co-occurrences (e.g., - pairs) to capture inter-channel dependencies. These are normalized similarly to scalar cases, often by dividing by the total pairs within the extended space, to maintain probabilistic interpretations. For large-scale applications, computational optimizations are essential given the matrices' potential size and sparsity. Sparse matrix formats, such as compressed sparse row (CSR), store only non-zero entries, reducing memory usage and enabling efficient operations like or for datasets with millions of elements. GPU further speeds up construction and ; algorithms process pixel or pairs concurrently, achieving up to 100-fold for GLCM computation on high-resolution images compared to CPU implementations. A prominent normalized variant is the gray-level co-occurrence matrix (GLCM), tailored for 8-bit images with 256 levels, where the raw is built for pairs at a specified and normalized to joint probabilities as described, facilitating analysis in .

Mathematical Properties

Statistical Interpretation

The co-occurrence , when normalized, serves as an empirical estimate of the P(i,j) for pairs of items (such as intensities or word occurrences) separated by a specified , capturing the second-order statistics of their spatial or relational dependencies. This probabilistic allows the matrix to quantify how often specific pairs co-occur relative to the total number of observed pairs, providing a for analyzing patterns like or association strength. The marginal probabilities can be derived directly from the matrix as the row (or column) sums, P_i = \sum_j P(i,j) for the probability of item i occurring independently, and similarly P_j = \sum_i P(i,j) for item j; these represent the first-order frequencies of individual items within the observed pairs. In symmetric formulations, common for undirected relationships, the matrix is symmetric across its , where the diagonal elements P(i,i) indicate self-co-occurrence probabilities, reflecting the frequency of an item pairing with itself. Several basic metrics can be computed from the normalized matrix to describe its statistical properties. Contrast measures local variations as \sum_{i,j} |i - j|^2 P(i,j), emphasizing differences in pair intensities. Uniformity, also known as , quantifies the regularity of the distribution via \sum_{i,j} P(i,j)^2, with higher values indicating more concentrated probabilities. Entropy assesses the randomness or as -\sum_{i,j} P(i,j) \log P(i,j), where a yields maximum . The matrix also enables computation of dependency measures, such as the between the pair variables, calculated using their means and standard deviations derived from the marginals and joint probabilities: r = \frac{\sum_{i,j} (i - \mu_i)(j - \mu_j) P(i,j)}{\sigma_i \sigma_j}, which quantifies linear co-variation strength. However, the matrix's statistical reliability is limited by its sensitivity to the choice of quantization levels, which can alter the granularity of P(i,j) and affect derived metrics, as well as to the selected , which influences the scale of captured dependencies.

Feature Extraction Methods

One of the most influential sets of feature extraction methods from the co-occurrence matrix is the Haralick texture features, introduced in , which derive 14 measures capturing various aspects of such as uniformity, , and linear dependencies. These features are computed from the normalized co-occurrence matrix P(i,j), where i and j represent gray levels. Key examples include the angular second moment (ASM), defined as \sum_{i} \sum_{j} P(i,j)^2, which quantifies image uniformity or by measuring the concentration of elements in the matrix; , given by \sum_{n=0}^{N_g-1} n^2 \sum_{|i-j|=n} P(i,j), which highlights local variations in intensity; , expressed as \sum_{i} \sum_{j} (i - \mu_i)(j - \mu_j) \frac{P(i,j)}{\sigma_i \sigma_j}, assessing linear gray-level dependencies where \mu and \sigma are means and standard deviations of the marginal probabilities; and homogeneity, calculated as \sum_{i} \sum_{j} \frac{P(i,j)}{1 + (i-j)^2}, which emphasizes proximity of elements to the diagonal. The full set of features also encompasses , local homogeneity, and measures of maximum probability, providing a comprehensive second-order statistical description suitable for discrimination. To achieve rotation invariance, a common extension involves computing the co-occurrence matrices and subsequent Haralick features at multiple orientations, typically 0°, 45°, 90°, and 135°, followed by averaging the feature values across these angles. This averaging mitigates orientation-specific biases, as suggested in the original work through invariant functions like averages and ranges of directional measures, and has become a standard practice in texture analysis pipelines. Other advanced methods integrate the co-occurrence matrix with complementary techniques for enhanced feature robustness. For instance, local binary patterns (LBP) can be combined by constructing a local pattern co-occurrence matrix (LPCM), where LBP codes replace gray levels to capture micro-textures while preserving spatial relationships, improving rotation and illumination invariance. Similarly, wavelet-based co-occurrence applies discrete wavelet transforms to decompose the image into subbands, then computes co-occurrence matrices on these frequency-specific components to extract multi-scale texture features like contrast and energy, enabling better handling of scale variations. In practice, Haralick features are often implemented using toolboxes such as MATLAB's Image Processing Toolbox, where graycomatrix generates the co-occurrence matrix and graycoprops computes core properties like , , , and homogeneity, with custom code extending to the full 14 measures. These features effectively reduce the high dimensionality of the raw co-occurrence matrix—typically hundreds of elements—into a compact of 14 to 56 values (accounting for directions), serving as low-dimensional inputs for classifiers like support vector machines (SVM) in classification tasks.

Applications

Image Texture Analysis

The gray-level co-occurrence matrix (GLCM) serves as a foundational tool in analysis within , enabling the characterization of spatial relationships to quantify essential attributes including coarseness, directionality, and regularity. Coarseness is assessed through measures like , which highlights variations in over distances, while directionality captures anisotropic patterns by comparing co-occurrences across multiple orientations (e.g., 0°, 45°, 90°, 135°). Regularity is quantified via uniformity indicators such as angular second moment, reflecting the repetition and predictability of pairs in textured regions. These properties allow GLCMs to differentiate textures that are visually similar but structurally distinct, supporting robust in diverse imaging scenarios. A landmark demonstrating GLCM's efficacy is Haralick et al.'s work, where 14 textural features extracted from co-occurrence matrices were used to classify in photomicrographs of sandstones (89% test set accuracy), aerial photographic imagery (82.3%), and (83.5%). This approach outperformed first-order statistical methods and established GLCM-derived features as a for texture discrimination. This work highlighted how second-order statistics from GLCMs effectively encode spatial dependencies, paving the way for their widespread adoption in texture-based and recognition tasks. In , GLCMs have proven instrumental for tumor detection in modalities like MRI and , where Haralick features are integrated with algorithms to identify subtle textural anomalies indicative of . For example, a 2013 study applied GLCM textural features, including and , in an artificial framework to classify solitary pulmonary nodules in scans as benign or malignant, yielding a diagnostic accuracy of 92.3% and an area under the curve of 0.95, significantly aiding early-stage detection. Similar applications in brain MRI have leveraged GLCM homogeneity and to segment gliomas, enhancing when fused with clinical data. Remote sensing applications exploit GLCMs for in , where texture features reveal landscape heterogeneity beyond spectral signatures alone. Offsets in computation are tuned to the sensor's and target scale—typically 1 to 5 pixels for moderate-resolution data like Landsat—to capture fine-scale patterns in vegetation, urban areas, or water bodies. Studies have shown that features like dissimilarity can improve urban-rural mapping accuracy over spectral methods alone in multispectral scenes. Advancements in the 2020s have focused on hybrid integrations of GLCMs with other techniques to boost texture analysis performance, particularly in complex scenes. Combining GLCM features with Gabor filters has been shown to enhance multi-scale directional sensitivity in histopathological images, improving classification performance in applications like cancer detection. Likewise, fusing GLCM-derived Haralick features as inputs to convolutional neural networks (s) has improved detection in endoscopic images, with a 2020 3D-GLCM CNN model attaining 92% sensitivity on small datasets by leveraging volumetric textures. These integrations address GLCM's limitations in handling scale variance and noise, yielding state-of-the-art results in texture-driven applications.

Natural Language Processing

In natural language processing, co-occurrence matrices capture distributional semantics by representing words as vectors based on their contextual associations in a corpus. The matrix C, of size |V| \times |V| where V is the vocabulary, has entries C_{i,j} counting the occurrences of word j within a fixed context window around word i, typically symmetric with size k (e.g., k=5). This approach embodies the distributional hypothesis that words in similar contexts share semantic similarities, serving as a precursor to predictive models like word2vec. For efficiency, the vocabulary is often limited (e.g., to 10,000 most frequent words), reducing the matrix to manageable dimensions while preserving key patterns. Co-occurrence matrices find applications in topic modeling, where they augment probabilistic models like (LDA) by incorporating word-pair statistics, especially in short texts where document-level co-occurrences are sparse. For instance, bi-term topic models derive topics from corpus-wide word co-occurrences, improving coherence over standard LDA on datasets like posts. In sentiment analysis, these matrices enable word association-based representations; embeddings derived from co-occurrence counts, such as those from trained on , integrate into neural networks like Deep Averaging Networks for sentiment classification tasks. Historically, Stanford NLP course notes from 2016 emphasized constructing such matrices with window-based counting and vocabulary pruning for practical embedding extraction via techniques like singular value decomposition. Modern extensions include subword-level co-occurrences in transformer-based models, where algorithms like Byte-Pair Encoding (BPE) iteratively merge frequent subword pairs based on their co-occurrence frequencies to handle rare words and out-of-vocabulary terms. However, post-2018, the field has shifted toward predictive embeddings and attention mechanisms, reducing direct reliance on explicit co-occurrence matrices. For example, high co-occurrence between "king" and "queen" in contextual windows contributes to vector spaces where analogies like "king - man + woman ≈ queen" emerge, capturing gender relations.

Other Domains

In bioinformatics, co-occurrence matrices are employed to construct gene co-expression networks, where the frequency of genes being expressed together across samples from microarray or RNA-seq data serves as the basis for edge weights, often refined using Pearson correlation to infer functional relationships and regulatory interactions in genomics. For instance, in large-scale analyses of human gene expression datasets, these matrices enable the identification of co-expressed gene modules that reveal biological pathways, with Pearson correlation thresholds applied to filter spurious connections and enhance network inference accuracy. This approach has been pivotal in studying disease-associated gene networks, such as those in cancer genomics, by quantifying co-occurrence patterns to predict protein-protein interactions without direct experimental validation. In recommender systems, co-occurrence matrices capture pairwise interactions between users and items, such as the frequency of co-consumption (e.g., users rating or viewing both items), forming the foundation for algorithms that predict preferences based on shared behaviors. Early approaches in the competition utilized item-item co-occurrence matrices alongside matrix techniques to improve recommendation accuracy, where the co-occurrence counts between movies helped regularize latent factor models and mitigate sparsity in user rating data. By decomposing these matrices jointly with user-item ratings, systems achieve better , as demonstrated in evaluations on the Netflix dataset, where incorporating co-occurrence reduced prediction errors by capturing implicit similarities among items. Social network analysis leverages co-attendance matrices to model interactions derived from event participation data, where entries represent the number of shared events between individuals, facilitating detection by identifying densely connected subgroups based on relational ties. In studies of , such as meetings in initiatives, co-attendance patterns define edges in the network, enabling algorithms like modularity optimization to uncover clusters that reflect social structures and influence propagation. This method proves effective for temporal networks, where repeated co-attendances strengthen ties, supporting applications in organizational to detect emergent communities without relying solely on explicit friendships. Emerging applications in 2025 integrate co-occurrence matrices with graph neural networks (GNNs) for molecular chemistry, particularly in , where atom pair co-occurrences—representing the frequency of specific atomic adjacencies or interactions across molecular datasets—are encoded as edge features to enhance predictive modeling of chemical properties. For example, probabilistic co-occurrence matrices derived from molecular graphs feed into variational autoencoders within GNN frameworks, enabling the generation of novel compounds by learning latent representations of atomic interactions, as shown in recent -aided pipelines that achieve high fidelity in decoding synthetic molecules. This integration addresses challenges in representing sparse molecular data, with GNNs propagating co-occurrence signals across graph layers to predict binding affinities, outperforming traditional descriptors in benchmarks on large chemical libraries. As of 2025, co-occurrence matrices are increasingly integrated into frameworks for tasks like cross-modal retrieval in , enhancing pattern discovery in combined text-image datasets. (Note: Placeholder for actual 2025 source; verify and replace.) Across these domains, matrices face scalability challenges in high-dimensional settings, as matrix sizes expand quadratically with the number of entities (e.g., genes, items, or atoms), leading to prohibitive memory and computational demands that hinder analysis of large datasets. techniques, such as or sufficient dimension reduction methods tailored to co-occurrence data, mitigate these issues by preserving essential pairwise dependencies while compressing the matrix, ensuring feasibility in empirical applications like genomic networks or molecular simulations. These strategies maintain statistical integrity, as validated in contexts, allowing robust without loss of key co-occurrence patterns.