Skip to content

README.md

Latest commit

 

History

History
169 lines (127 loc) · 7.99 KB

README.md

File metadata and controls

169 lines (127 loc) · 7.99 KB
Raw

cld-reducer for Python

Reduce compact letter displays (CLDs) while preserving the pairwise statistical relationships they encode. This is the Python package of the cld-reducer repository, which also holds an R package and a JavaScript package. All three default to CLD-C, which minimizes distinct letters. The optional CLD-sigma method minimizes assignments, as defined by Ennis, Fayle, and Ennis (2012), https://doi.org/10.1145/2133803.2275596. A feasible essential set can prove the optimum without a solver call. Both methods use HiGHS as the fallback and return the same display across languages. The rules they follow are in docs/algorithm.md in the repository.

The solver is HiGHS through highspy. The dependencies are highspy, NumPy, and pandas.

Installation

The examples need version 0.3.0 or later. Version 0.2.0 minimizes assignments and does not offer CLD-C. Check the installed version before using the examples. Install the published release with:

pip install cld-reducer

To install the development version from the repository:

pip install "git+https://github.com/aigorahub/cld-reducer.git#subdirectory=python"

The #subdirectory=python part is needed because the Python package lives in python/. Python 3.10 or later. The module is cld_reducer and the command line tool is cld-reduce.

For development, work from this folder:

cd python
python -m venv .venv
source .venv/bin/activate
python -m pip install -e ".[dev]"
ruff check . && ruff format --check . && pytest

Usage

import pandas as pd

from cld_reducer import reduce_letters

# One row for each pair. True means the groups differ significantly.
pairs = pd.DataFrame(
    [
        ("1", "2", False),
        ("1", "3", False),
        ("1", "4", True),
        ("1", "5", True),
        ("2", "3", False),
        ("2", "4", False),
        ("2", "5", True),
        ("3", "4", False),
        ("3", "5", False),
        ("4", "5", False),
    ],
    columns=["group1", "group2", "significant"],
)
means = pd.DataFrame({"group": ["1", "2", "3", "4", "5"], "mean": [3.73, 3.57, 3.46, 3.33, 3.30]})

result = reduce_letters(pairs, means)
print(result.letters)
# {'1': 'A', '2': 'AB', '3': 'ABC', '4': 'BC', '5': 'C'}
print(result.to_frame())
#   group letters assignments
# 0     1       A           A
# 1     2      AB         A B
# 2     3     ABC       A B C
# 3     4      BC         B C
# 4     5       C           C
print(result.stats)
# {'assignments_before': 9, 'assignments_after': 9, 'reduction_pct': 0.0, 'num_letters_before': 3, 'num_letters_after': 3, 'num_groups': 5, 'num_edges': 7, 'solver_status': 'Optimal', 'objective': 3}

This example works after package installation and needs no external files. reduce_letters takes complete pairwise results: one row for each pair of groups, with a boolean column that tells whether the pair differs significantly. Missing pairs are rejected. means is optional and orders the groups and the letters. If you already have the non-significance matrix, use reduce_from_adjacency; there, True means two groups are not significantly different and must share a letter.

The result, a CLDReductionResult, has:

  • letters: the display of each group, for example "AC" (tokens are joined with spaces after Z, as in "Z AA")
  • assignments: the letters of each group as a tuple, the safe machine-readable form
  • stats: the counts before and after the reduction and the solver status; reduction_pct is not rounded
  • relationship_preserved: always True for a returned result
  • to_frame(): a tidy pandas.DataFrame

The public names are reduce_letters, reduce_from_adjacency, CLDReductionResult, CLDReducerError, InvalidInputError, and SolverError.

When several displays have the same minimum objective, the package returns the canonical one defined in docs/algorithm.md, so R, Python, and JavaScript agree. time_limit is one time budget in seconds for the essential scan, certificate, and all solves of a call. max_cliques (10,000 by default; None removes it) bounds the number of maximal cliques.

Command line

cld-reduce examples/simple_abc_to_ac_pairs.csv \
  --means examples/simple_abc_to_ac_means.csv \
  --time-limit 30 \
  --out reduced.csv

The paths above refer to files in a checkout or an extracted source archive. For your own data, pass your CSV paths. The pairs file has the columns group1, group2, and significant; the optional means file has group and mean. The output CSV has the reduced letters and the summary statistics. Other flags: --group1, --group2, --significant, --max-cliques, --no-max-cliques, and --method.

Examples

The following scripts and CSV files are included in a repository checkout or the source archive, but not in the installed wheel. Run them from python/ in a checkout, or from the root of an extracted source archive:

python examples/simple_abc_to_ac.py
python examples/piepho2004_wheat.py

The CSV files in examples/ are identical copies of the files in conformance/data/ at the repository root.

Changes in 0.3.0

CLD-C is the default. Use method="assignment_minimum" or the CLI flag --method assignment-minimum to retain the assignment objective. Both methods combine identical closed neighborhoods and scan for essential decisions. A complete essential cover proves the optimum before BIP construction. Otherwise, HiGHS solves the same constrained model. The solver budget includes the scan and proof but excludes graph preparation and BIP compilation.

Changes in 0.2.0

The 0.2.0 release moved the package to python/ and the solver to highspy, which can change the display for inputs with several minimal displays and can rename letters. See the root NEWS.md for the full list.

License

MIT. See LICENSE.

Input and release notes

CSV label columns preserve their exact text, including 001, NA, NaN, and empty strings. A blank CSV label is an empty-string label; missing values in API objects still raise InvalidInputError. Means must remain finite numbers. The means table uses group and mean when both exist, or its first two columns. A list of pair rows preserves each numeric label before conversion to text. Uneven adjacency rows raise the package's square-matrix error.

The source distribution contains example scripts and CSV files. The wheel contains the importable package and its license and data notice. Shared conformance fixtures remain in the repository, so source-distribution tests skip those cases when the fixtures are absent. CI tests both installed distributions outside the checkout. See docs/releasing.md in the repository for release steps. Example data reuse remains subject to the conditions in NOTICE.

Choice of objective

Both methods merge vertices with identical closed neighborhoods before solving. The sigma model weights each merged vertex by its original group count. The result restores the original groups, labels, means, and assignment counts. This is the vertex reduction from Lemma 2.5 of the 2012 paper.

CLD-sigma (assignment_minimum, alias assignment-minimum) minimizes letter-to-group assignments. The default CLD-C (letter_minimum, alias letter-minimum) minimizes distinct letters by selecting full maximal cliques. It does not minimize assignments as a second objective. Equal optima use the lexicographically greatest binary selection vector in canonical clique order. Public method metadata uses the underscore spelling.

For CLD-sigma, objective equals the assignments after reduction. For CLD-C it equals the number of letters after reduction. Assignment counts and reduction percentage remain assignment measures in both methods. For the simple five-group example, sigma uses 8 assignments and 3 letters; C uses 9 assignments and 3 letters.

result = reduce_letters(pairs, means, method="letter_minimum")
assert result.stats["objective"] == result.stats["num_letters_after"]
cld-reduce pairs.csv --method letter-minimum --out reduced.csv