improved-fmmds-core 1.1.0

Core implementation of the Improved FMMD-S algorithm for fair max-min diversification

Improved FMMD-S

This repository contains an efficient implementation of the FMMD-S algorithm for 'fair' diverse sampling with significant performance improvements over the original implementation. `Fair' here means that the sample is selected in a stratified fashion, ensuring that specified numbers of data points are selected from specified data groups.

Problem

The algorithm returns an approximately optimal solution to the following problem. Given a set $V$ of data points, partitioned into disjoint groups $V_1, V_2, \ldots, V_C$, select $k$ data points $S\subseteq V$, $|S| = k$, so that the number of selected points from of each group adheres to given constraints, $$l_c \leq |S \cap V_c| \leq h_c$$ and the diversity $div(S)$ of the selected points is maximized. $$div(S) = min_{u, v \in S: u\not \equiv v}\ \mathrm{distance}(u, v) $$

The FMMD-S Algorithm

The FMMD-S algorithm consists of the following main steps:

1. Dataset-wide Selection: Use the natural greedy algorithm for the problem to select $k$ points from the entire dataset and use them to establish a diversity threshold.
2. Group-specific Selection: Similarly, select greedily additional points from each group as long as the group-specific diversity remains above the established threshold.
3. Coreset Graph: Create a graph where nodes represent points selected in Steps (1-2) above, and edges represent pairwise distances below the diversity threshold.
4. ILP Solution: Solve the Maximum Independent Set problem using the Gurobi Integer Linear Programming (ILP) optimizer to find a problem solution.
5. Threshold Relaxation: If the solution returned fewer than $k$ items, decrease the diversity threshold and repeat from step 2.

For details, please refer to the paper.

Key Features and Improvements

This implementation is more efficient than the one used in the paper, achieving 13-200x speedup on our experiments, depending on problem size and constraints. The improvement is due to the following implementation choices.

• Incremental Graph Updates: Avoids redundant distance computations by incrementally updating the coreset graph instead of rebuilding it in each iteration.
• Working Data Persistence: Reuses intermediate computations when relaxing diversity thresholds.
• Parallel Distance Computations: Uses Cython-compiled parallel distance updates using OpenMP.
• Parallel Edge Creation: Cython-compiled parallel coreset graph edge creation.
• Memory-Efficient Operations: Contiguous array operations and optimized data structures.

Moreover, the library implements the following functionality improvements.

• Clean Interface: Both functional and class-based APIs for easy integration.
• Flexible Constraints: Support for uniform balanced, proportional, and manual constraint definitions.
• Comprehensive CLI: Command-line interface with subcommand-based constraint definition.
• Multiple Distance Metrics: Support for L_2_ (Euclidean), L_1_ (Manhattan), and angular distance metrics.
• Detailed Metadata: Rich timing and performance metadata for analysis.

Installation

Prerequisites

• Python 3.8+
• Gurobi Optimizer (with academic license recommended for larger datasets)
• Cython (for parallel computations)

Note for Mac users: You need to have g++-13 installed via Homebrew and set the CXX environment variable before installing the library:

# Install g++-13 via Homebrew
brew install gcc@13

# Set CXX environment variable
export CXX=g++-13

# Then proceed with installation
pip install -e .

Install from Source

git clone https://github.com/yourusername/improved-fmmds-core.git
cd improved-fmmds-core
pip install -e .

Build Cython Extensions

The package includes Cython-compiled parallel utilities for significant performance improvements. If compilation fails, the package will fall back to pure Python implementations.

Manual Building (if needed):

If you encounter issues with automatic Cython compilation, you can build the extensions manually:

# Install build dependencies
pip install Cython numpy

# Build Cython extensions manually
python -c "
import numpy as np
from Cython.Build import cythonize
from setuptools import setup, Extension

ext_modules = [
    Extension(
        'improved_fmmds_core.parallel.cython_utils',
        sources=['improved_fmmds_core/parallel/cython_utils.pyx'],
        extra_compile_args=['-fopenmp', '-std=c++11', '-O3'],
        extra_link_args=['-fopenmp', '-std=c++11'],
        include_dirs=[np.get_include()]
    )
]

setup(
    ext_modules=cythonize(ext_modules, compiler_directives={'language_level': 3})
)
"

Installation Troubleshooting

Common Issues:

1. Gurobi License Issues: Ensure you have a valid Gurobi license. Academic licenses are available for free.

2. Cython Compilation Errors: If Cython compilation fails:

   • Ensure you have a C++ compiler installed
   • On Mac: Install g++-13 via Homebrew and set export CXX=g++-13
   • On Linux: Install build-essential package
   • On Windows: Install Visual Studio Build Tools

3. OpenMP Issues: If you encounter OpenMP-related errors:

   • On Mac: brew install libomp
   • On Linux: sudo apt-get install libomp-dev
   • On Windows: OpenMP should be included with Visual Studio

Development Installation

For development and testing:

git clone https://github.com/yourusername/improved-fmmds-core.git
cd improved-fmmds-core
pip install -e "."

Quick Start

Python API

Functional Interface

import numpy as np
from improved_fmmds_core import solve_fmmd

# Generate sample data
np.random.seed(42)
features = np.random.random((1000, 50))  # 1000 items, 50 features
ids = np.arange(1000)
groups = np.random.randint(0, 5, 1000)  # 5 groups

# Define constraints (group_id: (lower_bound, upper_bound))
constraints = {
    0: (2, 5),  # Group 0: between 2 and 5 items
    1: (1, 3),  # Group 1: between 1 and 3 items
    2: (2, 4),  # Group 2: between 2 and 4 items
    3: (1, 2),  # Group 3: between 1 and 2 items
    4: (2, 6)   # Group 4: between 2 and 6 items
}

# Solve using functional interface
solution, diversity, metadata = solve_fmmd(
    features=features,
    ids=ids,
    groups=groups,
    k=10,
    constraints=constraints,
    parallel_dist_update=True,
    parallel_edge_creation=True,
    metric="l2",
    eps=0.1,
    time_limit=300
)

print(f"Solution: {solution}")
print(f"Diversity: {diversity:.6f}")
print(f"Runtime: {metadata['total_time']:.2f} seconds")
print(f"Iterations: {metadata['num_iterations']}")

Class-based Interface

from improved_fmmds_core import FMMDSolver

# Create solver with comprehensive configuration
solver = FMMDSolver(
    k=10,
    constraints=constraints,
    eps=0.1,
    time_limit=300,
    parallel_dist_update=True,
    parallel_edge_creation=True,
    verbose=False,
    metric="l2"
)

# Solve and get detailed results
result = solver.solve(features, ids, groups)

print(f"Solution: {result.solution}")
print(f"Diversity: {result.diversity:.6f}")
print(f"Runtime: {result.runtime:.2f} seconds")
print(f"Metric: {result.metric}")
print(f"Metadata: {result.metadata}")

Using Constraint Generators

from improved_fmmds_core import (
    ConstraintGenerator, 
    UniformBalancedConfig, 
    ProportionalConfig
)
import numpy as np

# Generate data
features = np.random.random((1000, 50))
ids = np.arange(1000)
groups = np.random.randint(0, 5, 1000)
unique_groups, group_counts = np.unique(groups, return_counts=True)

# Uniform balanced constraints
uniform_config = UniformBalancedConfig(minimum_total_samples=50)
constraints_obj, k = ConstraintGenerator.generate_constraints(
    uniform_config, unique_groups, group_counts
)
constraints = constraints_obj.constraints

# Proportional constraints
proportional_config = ProportionalConfig(k=100, alpha=0.2)
constraints_obj, k = ConstraintGenerator.generate_constraints(
    proportional_config, unique_groups, group_counts
)
constraints = constraints_obj.constraints

Command Line Interface

The CLI uses subcommands for different constraint definitions:

# Uniform balanced sampling
fmmds-run --data dataset.npz uniform-sampling --minimum-samples 50

# Proportional sampling
fmmds-run --data dataset.npz proportional-sampling --k 50 --alpha 0.2

# Custom constraints from file
fmmds-run --data dataset.npz custom-constraints --constraints-file constraints.json --k 50

# With parallel processing and custom parameters
fmmds-run --data dataset.npz uniform-sampling --minimum-samples 100 \
    --parallel --eps 0.05 --time-limit 600 --metric l1 --output results.json

Data Format Requirements

The --data argument expects a .npz file with the following required keys:

• features: 2D numpy array (n × d) containing feature vectors
• ids: 1D numpy array (n) containing unique item identifiers
• groups: 1D numpy array (n) containing group assignments

Performance Recommendations:

• Use contiguous arrays for optimal performance: np.ascontiguousarray()
• Ensure arrays are properly aligned and have consistent dtypes
• For large datasets, consider using float32 instead of float64 to reduce memory usage

Example data preparation:

import numpy as np

# Prepare your data
features = np.ascontiguousarray(features, dtype=np.float32)
ids = np.ascontiguousarray(ids, dtype=np.int32)
groups = np.ascontiguousarray(groups, dtype=np.int32)

# Save to .npz file
np.savez('dataset.npz', features=features, ids=ids, groups=groups)

CLI Options

Global Options:

• --data: Path to .npz file containing features, ids, and groups arrays
• --output: Output file for results (default: results.json)
• --eps: Diversity relaxation factor (default: 0.1)
• --time-limit: Time limit for ILP solver in seconds (default: 300)
• --metric: Distance metric (l2, l1, angular) (default: l2)
• --parallel: Enable all parallel options
• --parallel-dist-update: Enable parallel distance updates
• --parallel-edge-creation: Enable parallel edge creation
• --verbose: Enable verbose ILP solver output
• --quiet: Suppress output except errors

Subcommand-specific Options:

• uniform-sampling --minimum-samples: Minimum total samples for uniform sampling
• proportional-sampling --k: Number of samples, --alpha: Tolerance parameter (default: 0.2)
• custom-constraints --constraints-file: Path to constraints JSON file, --k: Number of samples

Constraint Definitions

The library provides three types of constraint definitions.

Uniform Balanced Sampling

Ensures (roughly) equal number of points selected from each group, regardless of group size.

from improved_fmmds_core import UniformBalancedConfig, ConstraintGenerator
import numpy as np

# Example with group counts
unique_groups = np.array([0, 1, 2, 3, 4])
group_counts = np.array([100, 50, 200, 25, 75])  # Group sizes

config = UniformBalancedConfig(minimum_total_samples=50)
constraints_obj, k = ConstraintGenerator.generate_constraints(config, unique_groups, group_counts)
constraints = constraints_obj.constraints

print(f"Generated k={k} with uniform constraints:")
for group_id, (lb, ub) in constraints.items():
    print(f"  Group {group_id}: {lb}-{ub} samples")

Proportional Sampling

Maintains proportional representation based on group sizes with a tolerance parameter. These constraints preserves the original group proportions while allowing some flexibility.

from improved_fmmds_core import ProportionalConfig

config = ProportionalConfig(k=100, alpha=0.2)  # 20% tolerance
constraints_obj, k = ConstraintGenerator.generate_constraints(config, unique_groups, group_counts)
constraints = constraints_obj.constraints

print(f"Generated k={k} with proportional constraints:")
for group_id, (lb, ub) in constraints.items():
    proportion = group_counts[group_id] / group_counts.sum()
    print(f"  Group {group_id}: {lb}-{ub} samples (proportion: {proportion:.2f})")

Manual Constraints

Specify exact constraints for each group. This provides maximum control over the sampling approach.

# Define constraints manually
constraints = {
    0: (5, 10),   # Group 0: 5-10 samples
    1: (2, 8),    # Group 1: 2-8 samples
    2: (3, 12),   # Group 2: 3-12 samples
    3: (1, 5),    # Group 3: 1-5 samples
    4: (4, 8)     # Group 4: 4-8 samples
}

# Validate feasibility
from improved_fmmds_core import Constraints, validate_k_feasibility
constraints_obj = Constraints(constraints)
k = 25  # Target total samples
validate_k_feasibility(k, constraints_obj)  # Raises error if not feasible

Constraint Validation

The library includes comprehensive validation to ensure constraints are feasible:

from improved_fmmds_core import Constraints

constraints_obj = Constraints(constraints)
print(f"Minimum possible samples: {constraints_obj.get_min_total()}")
print(f"Maximum possible samples: {constraints_obj.get_max_total()}")
print(f"Is k=25 feasible? {constraints_obj.is_k_feasible(25)}")

Data Format

The algorithm expects data in the following format:

• features: 2D numpy array (n × d) where each row is a feature vector
• ids: 1D numpy array (n) containing unique identifiers for each item
• groups: 1D numpy array (n) specifying group assignments
• constraints: Dictionary mapping group IDs to (lower_bound, upper_bound) tuples

Loading Data

import numpy as np

# From separate files
features = np.load('features.npy')
ids = np.load('ids.npy')
groups = np.load('groups.npy')

# From single .npz file
data = np.load('dataset.npz')
features = data['features']
ids = data['ids']
groups = data['groups']

Distance Metrics

The algorithm supports three distance metrics:

• L2 (Euclidean): metric="l2" (default)
• L1 (Manhattan): metric="l1"
• Angular: metric="angular"

Parallel Processing

Enable parallel processing for better performance on large datasets:

# Enable all parallel options
solver = FMMDSolver(
    k=10,
    constraints=constraints,
    parallel_dist_update=True,
    parallel_edge_creation=True
)

# Or via CLI
fmmds-run --data dataset.npz uniform-sampling --minimum-samples 50 --parallel

Examples

The package includes comprehensive examples in the examples/ directory:

• basic_example.py: Demonstrates all three constraint strategies with synthetic data
• Shows both functional and class-based interfaces
• Includes result saving and metadata analysis

Run the examples:

cd examples
python basic_example.py

Requirements

Core Dependencies

• Python 3.8+
• NumPy >= 1.20.0: Numerical computations
• Gurobi Optimizer >= 9.0.0: ILP solver (academic license recommended)
• NetworkX >= 2.5: Graph operations
• tqdm >= 4.60.0: Progress bars

Build Dependencies

• Cython >= 0.29.0: For parallel computations
• C++ Compiler: For building Cython extensions
• OpenMP: For parallel processing (usually included with compiler)

Optional Dependencies

• Pandas: For data manipulation (if needed for your workflow)
• Matplotlib/Seaborn: For visualization (if needed for analysis)

License

MIT License

Citation

If you use this implementation, please cite the original paper:

@inproceedings{wang-fmmd-2023,
  title={Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms},
  author={Wang, Y. and Mathioudakis, M. and Li, J. and Fabbri, F.},
  booktitle={Proceedings of the 2023 SIAM International Conference on Data Mining (SDM)},
  pages={91--99},
  year={2023},
  organization={Society for Industrial and Applied Mathematics}
}

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Support

For questions and support, please open an issue on GitHub.