View and cluster structure: method reference

This chapter specifies the views detector’s models, search, and report fields. For runnable examples and its relationship to CrossCat (Mansinghka et al., 2016), see View and cluster structure.

The detector selects one partition using a greedy score optimization. It does not estimate a posterior distribution over partitions. It is excluded from the default detector set; request detectors=["views"] at the standard or deep budget to run it.

Model¶

Columns are partitioned into views. Within each view, rows are partitioned into clusters. Each cluster has a separate model for each column: Gaussian for continuous values, categorical for strings and booleans. Columns are modeled as independent conditional on the cluster assignment. Different views have independent row clusterings.

This structure can represent columns whose distributions vary together across groups. A single fitted cluster does not represent correlations between its columns. Singleton views produce no association finding, but they may still produce cluster or concentration findings.

Rows are treated as an unordered set. The model does not estimate temporal boundaries or test whether equal values occur consecutively.

Continuous values¶

Integers, floats, dates (days since epoch), and datetimes (microseconds since epoch) enter the continuous model. On the fitting sample, transform non-null values by:

z = (x - median) / IQR

Quartiles use type-7 linear interpolation. If the IQR is zero, use the sample mean and standard deviation. If that scale is also zero, map the observed values to zero. Median/IQR scaling reduces the influence of extreme values on the scale used for the bulk of the column.

The model uses a fixed Normal-Inverse-Gamma prior on this transformed scale: mu0=0, kappa0=1, alpha0=2, beta0=1. Its variance prior has mean one. Because the transformation is estimated from the data, scores refer to this sample-dependent scale. They do not compare raw variation across columns in different units.

For n observed values, mean xbar, and sum of squared deviations S = sum((x_i - xbar)^2), the log marginal likelihood is:

kappa_n = kappa0 + n
alpha_n = alpha0 + n / 2
beta_n  = beta0 + S / 2 + kappa0 * n * (xbar - mu0)^2 / (2 * kappa_n)
log p(x) = lgamma(alpha_n) - lgamma(alpha0)
         + alpha0 * log(beta0) - alpha_n * log(beta_n)
         + (1 / 2) * (log(kappa0) - log(kappa_n))
         - (n / 2) * log(2 * pi)

A component with no observed values contributes zero. The prior keeps the score finite for a single value or a constant cluster.

The posterior predictive distribution is Student-t with nu = 2 * alpha_n, location mu_n = (kappa0 * mu0 + n * xbar) / kappa_n, and scale^2 = beta_n * (kappa_n + 1) / (alpha_n * kappa_n):

log p(x_new) = lgamma((nu+1)/2) - lgamma(nu/2)
             - (1/2) * log(nu * pi * scale^2)
             - ((nu+1)/2) * log(1 + (x_new - mu_n)^2 / (nu * scale^2))

The predictive log density equals the log marginal after adding the value minus the log marginal before adding it. A regression test checks this identity.

Categorical values¶

Strings and booleans use categorical models. The 32 most frequent non-null levels retain their identity, with ties ordered by label. Remaining levels are pooled into one additional level. The pooled level has a distinct name if a retained value is literally "other".

A symmetric Dirichlet prior uses alpha=1 per level. For counts c_1..c_K, including the pooled level, and n = sum(c_k):

log p = lgamma(K * alpha) - lgamma(n + K * alpha)
      + sum_k [lgamma(c_k + alpha) - lgamma(alpha)]

The predictive probability of level k is (c_k + alpha) / (n + K * alpha). Pooling removes distinctions among the rare levels, including rare-level dependencies and anomalies.

Dates and datetimes use the continuous model, so calendar effects such as weekday or seasonality are not modeled explicitly.

Missing values and column eligibility¶

Nulls contribute no component score. Evidence records per-column null counts over the fitting sample; the search does not model a missingness process.

All-null and unsupported columns are excluded. When more than 64 columns are eligible, the pass keeps the 64 with the strongest pairwise dependence under a normalized-mutual-information pre-screen (near-unique columns, such as identifiers, get no ranking signal); on wider tables the screen itself is bounded to 256 rows and 250,000 pair evaluations. Excluded column names and columns omitted when the search budget is exhausted are recorded in coverage. Check these exclusions before interpreting a missing finding.

Partition score¶

For views V and row clusters C(v) in each view:

score = sum_v [ sum_{c in C(v)} sum_{col in v} log-marginal(col values in c)
                - gamma * log(n) * |C(v)| ]
        - gamma * log(n) * |V|

The default gamma is 2.0. The score penalizes both extra clusters and extra views. Search uses n = n_search; final reported scores use n = n_sample. Sensitivity to this penalty has not been established.

Let score(v) denote a view’s component marginals minus its cluster penalty, excluding the view-count penalty. The gain from merging two views is:

delta = score(merged) - score(v1) - score(v2) + gamma * log(n_search)

The last term accounts for removing one view. The merge is accepted only when the gain is positive and the merged partition has at least two clusters. The latter rule rejects a merge whose only benefit is saving penalties while leaving an unchanged single-cluster product model.

A positive gain can still come from sharing cluster penalties rather than improving the component marginals. Interpret it as a preference for a shared partition under this criterion, not as a calibrated dependence measure.

Search and assignment¶

1. Fit singleton views. Start each column with one cluster of search rows. At each step, try splitting each cluster on each column in the view. Use the distinct-value boundary nearest that column’s median position. This keeps both sides nonempty when values repeat. Categorical boundaries use level IDs in frequency-then-label order. Null rows go to the larger side, with ties assigned to the lower-index side.

2. Accept improving splits. Sum the left and right log marginals across the view’s columns, subtract the unsplit score and the new cluster penalty. Accept the largest positive gain. Stop when no split improves the score or eight clusters have formed. Ties use cluster index, then column index.

3. Rank candidate pairs. Fit every column pair on the search rows. Rank pairs by pair score minus their singleton scores, using column indices to break ties.

4. Merge views. In that order, consider pairs whose columns are in different views. Refit the combined view and apply the merge criterion above. Stop after 64 merge attempts, all pairs, or the work budget.

5. Assign fitting-sample rows. Assign each row to the cluster with the highest sum of predictive log densities across observed columns. A row that contributed to a cluster’s statistics is removed from those statistics while scoring that candidate assignment. Recompute statistics and reassign once, then drop empty clusters.

6. Compute final scores. Recompute marginals over the assigned fitting sample. Report these separately from merge gains, which were evaluated on the search sample.

When the cell-visit budget is exhausted, search retains its current partition. Coverage marks the run as capped and lists columns not yet processed. The optional wall-clock deadline is checked before the pass starts; a running pass is not interrupted. Fixed work limits and index-based tie-breaking make the search deterministic for the same input.

Association findings¶

A multi-column view produces associations/statistical, naming the columns and their merge gain on the search sample. The claim describes a shared row partition. It does not establish pairwise dependence for every pair in the view or a relationship within each cluster.

The report selector recomputes selection priorities. It currently reads Pearson, Spearman, and xi metrics for association strength; this detector supplies none of those, so its association-strength contribution is zero. The initial detector priority does not determine the final rank.

Cluster differences¶

Each view with at least two clusters can produce a changes/residual_level finding describing the largest between-cluster difference. The implementation compares standardized mean differences for continuous columns and total-variation distances for categorical columns. These measures have different scales, so the largest value need not identify the most useful column in a mixed view.

The specification records the reference model, selected column, cluster sizes, raw means or dominant levels, and minimum and maximum row indices. Those ranges can overlap. They describe membership bounds, not contiguous segments or detected temporal change points. A stationary noise column can also produce this finding.

Modal concentration¶

A column produces concentration/modal_share when a cluster has at least 30 non-null observations and one numeric value or encoded categorical level occupies at least 90% of them. A single statement lists all qualifying clusters for that column. A dominant pooled category can contain several distinct raw values; it does not establish that one raw value repeats.

This can identify a repeated value within a fitted group. It does not establish a stuck sensor or a consecutive run: the detector does not use row order, and a repeated block may be too small a share of its fitted cluster to meet the threshold.

The shared selector reads top_share for concentration strength, while this pass emits modal_share. Its final priority therefore uses the selector’s default concentration strength rather than the measured modal share.

Low-density cells¶

For each observed cell, calculate its predictive log density under its assigned cluster. Remove the cell from the component statistics before scoring it. If its cluster has fewer than 30 rows, use the largest cluster in the view instead, unless the assigned cluster is itself the largest. This prevents a tiny cluster of identical extremes from supplying its own reference distribution. It can also flag valid small groups.

For each column, report cells whose scores are below the median score minus 10 nats, ordered by lowest score and capped at 20. The finding type is concentration/spike_cells. Evidence includes the threshold, cell values, scores, and original row indices.

A 10-nat gap corresponds to a density ratio of about 22,000. This is a heuristic threshold; it is not a tail probability or an estimated chance that a value is erroneous. Leave-one-out component scoring still uses a partition selected from the same dataset, so it is not independent validation.

Configuration and evidence¶

Python’s sample_rows overrides the fitting-sample limit. The remaining fields belong to the Rust ViewsConfig; they are not separate Python keyword arguments.

Evidence records the fitting-sample size, search limit, model limits, per-column null counts, excluded columns, full-sample view score, and search-sample merge gain. The basis is estimated; there is no independent validation attached to these findings.

Limitations¶

• Noise can form clusters. The score can improve by cutting a single noise distribution into narrower components. Cluster counts and mean differences therefore do not establish distinct populations or regimes. No null-calibrated reporting gate is implemented.

• Small-cluster scoring changes at 30 rows. Crossing that threshold changes the reference from the largest cluster to the assigned cluster. An added row can consequently change which values are flagged.

• Pooling hides rare-level structure. Individual rare levels share one category, so the model cannot distinguish their relationships or score their rarity separately.

• Search is approximate. Samples can omit rare patterns. Greedy splits and merges can miss better partitions, and their gains may not persist on the larger fitting sample.

• Width and work are capped. Columns past the 64-column cap are excluded; the cap keeps the strongest by pairwise dependence, so a dependent column is no longer excluded for sitting late in the table, but a rare column whose sample association is weak can still rank below the cut. The work budget can stop search earlier. Runtime and memory at larger widths need measurement for this pass.

• Some structure is unmodeled. The pass has no temporal ordering, calendar features, missingness model, or within-cluster dependence. Use another analysis when those properties matter.

Evaluation¶

The unit tests cover component formulas, repeatable output, shared partitions, independent binary columns, constant columns, category pooling, leave-one-out component scoring, and separate modal/spike statements. The companion notebook checks a shared-state example and reports both planted extremes and other flagged cells.

The reproducible sensor-v1 benchmark has 50,000 rows, a temperature shift at row 25,000, a repeated-value block, and 15 planted extremes. With the 20,000-row fitting sample, the pass found all eight sampled extremes and flagged one additional temperature cell. Using all 50,000 rows, it found all 15 extremes and flagged no additional temperature cells. Repeated runs produced identical report JSON in both configurations.

The fitted views changed with the sample: the standard run grouped device_id with temperature, while the full-sample run kept all columns in separate views. The benchmark’s cluster-range diagnostic also missed the known time boundary at the standard budget. An independent Gaussian control was split into eight clusters. Recovery counts and fitted groups therefore need to be examined separately, even for this single fixture.

Run python benchmarks/views.py --output /tmp/views.json from the repository root. The fixture, seed, measured times, row-level recovery counts, and controls are recorded in benchmarks/results/views-sensor.json. See the benchmark instructions for the measurement scope.

Broader evaluation still needs repeated null controls, sensitivity to gamma, held-out prediction, and anomaly precision and recall across datasets. The profiler-wide scale benchmark covers other detectors’ late-column behavior; this pass models at most 64 eligible columns, selected by pairwise dependence when more are eligible.

Worked scores¶

For raw values [19, 20, 21], the median is 20 and the type-7 quartiles are 19.5 and 20.5. The IQR is 1, giving standardized values [-1, 0, 1]. With the stated prior, n=3, xbar=0, S=2, kappa_n=4, alpha_n=3.5, and beta_n=2:

log p = lgamma(3.5) - lgamma(2) - 3.5 * log(2)
        + 0.5 * (log(1) - log(4)) - 1.5 * log(2 * pi)
      = -4.67500

For categorical counts [3, 1], K=2 and alpha=1:

log p = lgamma(2) - lgamma(6) + lgamma(4) + lgamma(2)
      = -2.99573

The continuous component’s predictive distribution has mu_n=0, nu=7, and scale^2=0.7143. Its log density is approximately -0.7863 at zero and -51.07 at 1200. These are component calculations; they do not evaluate anomaly detection on a dataset.

References¶

• Mansinghka et al. (2016). CrossCat: A Fully Bayesian Nonparametric Method for Analyzing Heterogeneous, High Dimensional Data. JMLR, 17(138), 1–49.

• Saad and Mansinghka (2017). Detecting Dependencies in Sparse, Multivariate Databases Using Probabilistic Programming and Non-parametric Bayes. AISTATS, PMLR 54, 632–641. This describes dependence queries over Bayesian models; onceover’s greedy partition does not provide those uncertainty estimates.