Python library for Route Optimization Constrained
Project description
Route Optimization Constrained
Implementation of Clustering with Constrained Algorithm. Route Optimization Constrained can be treated as an optimization problem.
Installation
Requirement Python >= 3.6, Numpy >= 1.13
- install from PyPI
pip install route-optimization-constrained
Methods
- Fuzzy C-means Algorithm: Similar to KMeans, but use membership probability, not 0 or 1
- Same Size Contrained KMeans Heuristics: Use Heuristics methods to reach same size clustering
- Same Size Contrained KMeans Inspired by Minimum Cost Flow Problem
- Minimum and Maximum Size Constrained KMeans Inspired by Minimum Cost Flow Problem
- Deterministic Annealling Algorithm: Input target cluster distribution, return correspondent clusters
- Shrinkage Clustering: base algorithm and minimum size constraints
Usage:
# setup
from size_constrained_clustering import fcm, equal, minmax, shrinkage
# by default it is euclidean distance, but can select others
from sklearn.metrics.pairwise import haversine_distances
import numpy as np
Fuzzy C-means
n_samples = 2000
n_clusters = 4
centers = [(-5, -5), (0, 0), (5, 5), (7, 10)]
X, _ = make_blobs(n_samples=n_samples, n_features=2, cluster_std=1.0,
centers=centers, shuffle=False, random_state=42)
model = fcm.FCM(n_clusters)
# use other distance function: e.g. haversine distance
# model = fcm.FCM(n_clusters, distance_func=haversine_distances)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_
Equal Size Constraint
n_samples = 2000
n_clusters = 3
X = np.random.rand(n_samples, 2)
# use minimum cost flow framework to solve
model = equal.SameSizeKMeansMinCostFlow(n_clusters)
# use heuristics method to solve
model = equal.SameSizeKMeansHeuristics(n_clusters)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_
Cluster size: 667, 667 and 666 in the figure above.
Minimum and Maximum Size Constraint
n_samples = 2000
n_clusters = 3
X = np.random.rand(n_samples, 2)
model = minmax.MinMaxKMeansMinCostFlow(n_clusters, size_min=400, size_max=800)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_
Cluster size: 753, 645 and 602 in the figure above.
Deterministic Annealing
n_samples = 2000
n_clusters = 3
X = np.random.rand(n_samples, 2)
# distribution is the distribution of cluster sizes
model = da.DeterministicAnnealing(n_clusters, distribution=[0.1, 0.6, 0.3])
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_
Cluster size: 1200, 600 and 200 in the figure above, corresponding to distribution [0.6, 0.3, 0.1]
Shrinkage Clustering
The result might be not available.
n_samples = 1000
n_clusters = 4
centers = [(-5, -5), (0, 0), (5, 5), (7, 10)]
X, _ = make_blobs(n_samples=n_samples, n_features=2, cluster_std=1.0, centers=centers, shuffle=False, random_state=42)
model = shrinkage.Shrinkage(n_clusters, size_min=100)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_
Copyright
Copyright (c) 2020 Jing Wang. Released under the MIT License.
Third-party copyright in this distribution is noted where applicable.
Reference
- Clustering with Capacity and Size Constraints: A Deterministic Approach
- Deterministic Annealing, Clustering and Optimization
- Deterministic Annealing, Constrained Clustering, and Opthiieation
- Shrinkage Clustering
- Clustering with size constraints
- Data Clustering with Cluster Size Constraints Using a Modified k-means Algorithm
- KMeans Constrained Clustering Inspired by Minimum Cost Flow Problem
- Same Size Kmeans Heuristics Methods
- Google's Operations Research tools's
SimpleMinCostFlow
- Cluster KMeans Constrained
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for route_optimization_constrained-0.1.1.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 988a517656ca2b6995d8b33cd717714ba88a78da1e80285bd181e6b25b9eccda |
|
MD5 | 55eed0eacb690ffee6d948fac6a2d9a9 |
|
BLAKE2b-256 | 25404d3f76bea0e361f9c87ad135e8be9d82ecc29ddace497c588001279b9099 |
Hashes for route_optimization_constrained-0.1.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eb78d995cf2a535d3732a598c6506ec409c43e6e62a73f437ab877a8ab25acf7 |
|
MD5 | 41b496757c6b27518fe732dd2c178455 |
|
BLAKE2b-256 | 3beeedbb0bd356cacbbc976828be9a2ca6f6ba18b6adaa5600b3e025816b75ce |