Knee-point detection in Python
Project description
kneed
Knee-point detection in Python
This repository is an attempt to implement the kneedle algorithm, published here. Given a set of x
and y
values, kneed
will return the knee point of the function. The knee point is the point of maximum curvature.
Installation
To install use pip:
$ pip install kneed
Or clone the repo:
$ git clone https://github.com/arvkevi/kneed.git
$ python setup.py install
Tested with Python 3.5 and 3.6
Usage
This reproduces Figure 2 from the manuscript.
x
and y
must be equal length arrays.
DataGenerator
has functions to generate sample datasets.
from kneed import DataGenerator, KneeLocator
x, y = DataGenerator.figure2()
print([round(i, 3) for i in x])
print([round(i, 3) for i in y])
[0.0, 0.111, 0.222, 0.333, 0.444, 0.556, 0.667, 0.778, 0.889, 1.0]
[-5.0, 0.263, 1.897, 2.692, 3.163, 3.475, 3.696, 3.861, 3.989, 4.091]
Instantiating KneeLocator
with x
, y
and the appropriate curve
and direction
will find the knee (or elbow) point.
Here, kneedle.knee
stores the knee point of the curve.
kneedle = KneeLocator(x, y, S=1.0, curve='concave', direction='increasing')
print(round(kneedle.knee, 3))
0.222
# .elbow can also be used to access point of maximum curvature
print(round(kneedle.elbow, 3))
0.222
The KneeLocator
class also has some plotting functions for quick visualization of the curve (blue), the distance curve (red) and the knee (dashed line, if present)
kneedle.plot_knee_normalized()
Average Knee from 5000 NoisyGaussians when mu=50 and sigma=10
import numpy as np
knees = []
for i in range(5000):
x,y = DataGenerator.noisy_gaussian(mu=50, sigma=10, N=1000)
kneedle = KneeLocator(x, y, curve='concave', direction='increasing')
knees.append(kneedle.knee)
np.mean(knees)
60.921051806064931
Application
Find the optimal number of clusters (k) to use in k-means clustering.
See the tutorial in the notebooks folder, this can be achieved with the direction
keyword argument:
KneeLocator(x, y, curve='convex', direction='decreasing')
Contributing
Contributions are welcome, if you have suggestions or would like to make improvements please submit an issue or pull request.
Citation
Finding a “Kneedle” in a Haystack: Detecting Knee Points in System Behavior Ville Satopa † , Jeannie Albrecht† , David Irwin‡ , and Barath Raghavan§ †Williams College, Williamstown, MA ‡University of Massachusetts Amherst, Amherst, MA § International Computer Science Institute, Berkeley, CA
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 kneed-0.2.3-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 937c25e712e89637f7d267bfc24450ea48e816c3edb68bea164e460db4fcb298 |
|
MD5 | 5de3483e4753d2dcafc0448d124dd956 |
|
BLAKE2b-256 | 4b5f1a22d47543cec7f64b7e84cfeb04074d8ad8249b3fdca5d5af39e870500a |