{
    "info": {
        "author": "Facundo Sapienza",
        "author_email": "support@aristas.com.ar",
        "bugtrack_url": null,
        "classifiers": [
            "License :: OSI Approved :: MIT License",
            "Operating System :: OS Independent"
        ],
        "description": "# Fermat distance\nFermat is a Python library that computes the Fermat distance estimator (also called d-distance estimator) proposed in \n  * _Weighted Geodesic Distance Following Fermat's Principle_ (see https://openreview.net/pdf?id=BJfaMIJwG).\n  * _Nonhomogeneous Euclidean first-passage percolation and distance learning_ (see https://arxiv.org/abs/1810.09398) \n\n### Table of contents\n\n1. [Introduction](#introduction)\n2. [Installation](#installation)\n3. [Implementation](#implementation)\n4. [Clustering](#clustering)\n5. [Features](#features)\n6. [Support](#support)\n7. [Fermat distance citation](#licence)\n\n\n### Introduction\n---------------\n\nA density-based estimator for weighted geodesic distances is proposed.\nLet M be a D-dimensional manifold and consider a sample of N points X_n living in M. Let l(.,.) be a distance defined \nin M (a typical choice could be Euclidean distance). For d>=1 and given two points p and q in M we define the Fermat \ndistance estimator as \n![](https://bitbucket.org/aristas/fermat/raw/abff1252a68060bef495bf5cf9b6d45db7d8f497/images/estimator.png)\n\nThe minimization is done over all K>=2 and all finite sequences of data points with x1= argmin l(x,p) \nand xK = argmin l(x,q).\n\nWhen d=1, we recover the distance l(.,.) but if d>1, the Fermat distance tends to follow more closely the manifold \nstructure and regions with high density values.\n\nThis distance is useful for clustering pourposes. Replacing Euclidean distance with Fermat distance in standard clustering alorithms leads to much better results.\n\n\n![](https://bitbucket.org/aristas/fermat/raw/abff1252a68060bef495bf5cf9b6d45db7d8f497/images/IlustrationManifoldNormals.svg) \n\nInstallation\n------------\n\n    pip install fermat\n\n### Implementation\n---------------\n\nThe optimization performed to compute the Fermat distance estimator runs all over the possible paths of points between each pair of points. We implement an algorithm that computes the exact Fermat distance and two that compute approximations.\n\n- #### Exact: Floyd-Warshall\nPermorf the _Floyd-Warshall algorithm_ that gives the exact Fermat distance estimator in `O( n^3 )` operations between all possible paths that conects each pair of points.\n\n- #### Aprox: Dijsktra + k-nearest neighbours\n\nWith probability arbitrary high we can restrict the minimum path search to paths where each consecutive pair of points are k-nearest neighbours, with `k = O(log n)`. Then, we use _Dijkstra algorithm_ on the graph of k-nearest neighbours from each point. The complexity is `O( n * ( k * n * log n ) )`.\n\n- #### Aprox: Landmarks\nIf the number of points n is too high and neither Floyd-Warshall and Dijkstra run in appropiate times, we implemente a gready version based on landmarks. Let consider a set of l of point in the data set (the landmarks) and denote `s_j` the distance of the point `s` to the landmark `j`. Then, we can bound the distance `d(s,t)` between any two points `s` and `t` as\n\n`lower = max_j { | s_j - t_j | } <= d(s,t) <= min_j { s_j + t_j } = upper`\n\nand estimate `d(s,t)` as a function of `lower` and `upper` (for example, `d(s,t) ~ (_lower + upper_) / 2` ). The complexity is `O( l * ( k * n * log n ) )`.\n\n### Clustering\n\nThe tool FermatKmeans implements the K-medoids algorithm with Fermat distance as an input. [Here] is an example explaining how to use it to compute clusters in MNIST dataset\n\n\n### Features\n---------------\n\n- Exact and approximate algorithms to compute the Fermat distance.\n- Examples explaining how to use this package.\n    * [Quick start] \n    * [MNIST data set]\n    * [Clustering using Fermat]\n- [Documentation]\n\n### Support\n---------------\n\nIf you have an open-ended or a research question:\n-  `'support@aristas.com.ar'`\n\n### Fermat distance citation\n---------------\n\nFermat distance has been introduced and studied in the following papers\n\n    @inproceedings{SGJ2018,\n          title={Weighted Geodesic Distance Following Fermat's Principle},\n          author={Facundo Sapienza and Pablo Groisman and Matthieu Jonckheere},\n          year={2018},\n          url={https://openreview.net/forum?id=BJfaMIJwG}\n    }\n\n\t@article{GJS2018,\n\t  title={Nonhomogeneous Euclidean first-passage percolation and distance learning},\n\t  author={Groisman, Pablo and Jonckheere, Matthieu and Sapienza, Facundo},\n\t  journal={arXiv preprint arXiv:1810.09398},\n\t  year={2018}\n    }\t\n\n[Quick start]:https://bitbucket.org/aristas/fermat/src/master/examples/Fermat_quick_start.py\n[Documentation]:https://bitbucket.org/aristas/fermat/src/master/DOCUMENTATION.md\n[MNIST data set]: https://bitbucket.org/aristas/fermat/src/master/examples/MNIST_example.py\n[Here]: https://bitbucket.org/aristas/fermat/src/master/examples/Digits.py\n\n\n",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://bitbucket.org/aristas/fermat",
        "keywords": "",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "fermat",
        "package_url": "https://pypi.org/project/fermat/",
        "platform": "",
        "project_url": "https://pypi.org/project/fermat/",
        "project_urls": {
            "Homepage": "https://bitbucket.org/aristas/fermat"
        },
        "release_url": "https://pypi.org/project/fermat/0.2.5/",
        "requires_dist": [
            "scipy",
            "numpy",
            "scikit-learn"
        ],
        "requires_python": ">=3.5",
        "summary": "library to compute fermat distance",
        "version": "0.2.5",
        "yanked": false,
        "yanked_reason": null
    },
    "last_serial": 6088950,
    "releases": {
        "0.0.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "63a3b43c196f60b474042156d387cdd7",
                    "sha256": "06b5a0c02e44184cb79137b9ea2f7260dc544b86bdc6960fae2c830ce082917f"
                },
                "downloads": -1,
                "filename": "fermat-0.0.3-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "63a3b43c196f60b474042156d387cdd7",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 10764,
                "upload_time": "2019-10-09T14:44:05",
                "upload_time_iso_8601": "2019-10-09T14:44:05.334232Z",
                "url": "https://files.pythonhosted.org/packages/71/f0/fdeaa4c7bce6a41b6db48e8e969cc20e6c574b4536bb617c1090b5b0548e/fermat-0.0.3-py3-none-any.whl",
                "yanked": false,
                "yanked_reason": null
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "d03fa4c4e115aa6b8f26d5806f886291",
                    "sha256": "3bc95b8d0bb15f597675655c371c179ba40f8ae89e974825b5f3179f3facdb12"
                },
                "downloads": -1,
                "filename": "fermat-0.0.3.tar.gz",
                "has_sig": false,
                "md5_digest": "d03fa4c4e115aa6b8f26d5806f886291",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 219857,
                "upload_time": "2019-10-09T14:44:13",
                "upload_time_iso_8601": "2019-10-09T14:44:13.485587Z",
                "url": "https://files.pythonhosted.org/packages/39/ba/81f25d406e6d8a04d438b4e965edb4fd36f699857389858cc0bfbb2300a9/fermat-0.0.3.tar.gz",
                "yanked": false,
                "yanked_reason": null
            }
        ],
        "0.1.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "6700821fbdb87c7a45795da548a2b520",
                    "sha256": "5e65ce9061627b3ed2da119a116190598e67300499c88433e9bd68f3a8b0a8ea"
                },
                "downloads": -1,
                "filename": "fermat-0.1.0-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "6700821fbdb87c7a45795da548a2b520",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": ">=3.5",
                "size": 10757,
                "upload_time": "2019-10-09T14:44:08",
                "upload_time_iso_8601": "2019-10-09T14:44:08.455250Z",
                "url": "https://files.pythonhosted.org/packages/ea/8c/1e7244531d1fad8b088fe70cb9b334d887907071369b1dbfca496a194c30/fermat-0.1.0-py3-none-any.whl",
                "yanked": false,
                "yanked_reason": null
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "15ecc4d1209cadf37552e51058f781b0",
                    "sha256": "0d34c27e7a118683cb8a7baed227eccc539d012ce4df3d65eac07f187e941125"
                },
                "downloads": -1,
                "filename": "fermat-0.1.0.tar.gz",
                "has_sig": false,
                "md5_digest": "15ecc4d1209cadf37552e51058f781b0",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": ">=3.5",
                "size": 219715,
                "upload_time": "2019-10-09T14:44:17",
                "upload_time_iso_8601": "2019-10-09T14:44:17.748242Z",
                "url": "https://files.pythonhosted.org/packages/66/a0/05ba4d8f24d04d5f506f800eebf4563b7d3516ba2467814cdc6913914fcf/fermat-0.1.0.tar.gz",
                "yanked": false,
                "yanked_reason": null
            }
        ],
        "0.2.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "864bf2ef86d7b2215bd2083b737942bf",
                    "sha256": "a6026dd97e53d2d36524bedf23da2b83d77780450825b35286ef5937a560448e"
                },
                "downloads": -1,
                "filename": "fermat-0.2.0-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "864bf2ef86d7b2215bd2083b737942bf",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": ">=3.5",
                "size": 14244,
                "upload_time": "2019-10-09T14:44:10",
                "upload_time_iso_8601": "2019-10-09T14:44:10.460230Z",
                "url": "https://files.pythonhosted.org/packages/ce/e7/b70b7b039297810cfd131d5f2d791f7551123cff485aa85d19fe2472c9ae/fermat-0.2.0-py3-none-any.whl",
                "yanked": false,
                "yanked_reason": null
            }
        ],
        "0.2.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "e53992b9c9ef677c291ede3ea7f1f53c",
                    "sha256": "69fbdfb3fd3c483def64b4ca2442e308e9ad57fd210d94163d989867d49f9f17"
                },
                "downloads": -1,
                "filename": "fermat-0.2.2-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "e53992b9c9ef677c291ede3ea7f1f53c",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": ">=3.5",
                "size": 11162,
                "upload_time": "2019-10-10T18:41:39",
                "upload_time_iso_8601": "2019-10-10T18:41:39.621082Z",
                "url": "https://files.pythonhosted.org/packages/d8/e0/fc04f2a715bf53b7282a3ac49acf5a5a90b8c663f4d07299719f0cf8609b/fermat-0.2.2-py3-none-any.whl",
                "yanked": false,
                "yanked_reason": null
            }
        ],
        "0.2.4": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "3bc59574dfe133f1a96598420d490003",
                    "sha256": "f6817bdd095e4f6c423ae3bc8e0289c61080f68a9d3998827f96530d581cc711"
                },
                "downloads": -1,
                "filename": "fermat-0.2.4-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "3bc59574dfe133f1a96598420d490003",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": ">=3.5",
                "size": 11236,
                "upload_time": "2019-10-29T14:53:45",
                "upload_time_iso_8601": "2019-10-29T14:53:45.999017Z",
                "url": "https://files.pythonhosted.org/packages/33/97/a4877ded83877919ca02d76f943e4e3bccd0db15fa2ce6dead5f02faee9c/fermat-0.2.4-py3-none-any.whl",
                "yanked": false,
                "yanked_reason": null
            }
        ],
        "0.2.5": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "e8db957ce267a2e87184e6e47b692730",
                    "sha256": "65b7cabe0c2cccf3bdfd4f6dd0a6706f35565fee796cf4fd4f0d3128cf84db07"
                },
                "downloads": -1,
                "filename": "fermat-0.2.5-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "e8db957ce267a2e87184e6e47b692730",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": ">=3.5",
                "size": 11126,
                "upload_time": "2019-11-06T18:28:59",
                "upload_time_iso_8601": "2019-11-06T18:28:59.568504Z",
                "url": "https://files.pythonhosted.org/packages/36/bc/e593eb7016b6f44e1bdeb90bb2c37147e9af09ff1f9ce815a674072bb4b1/fermat-0.2.5-py3-none-any.whl",
                "yanked": false,
                "yanked_reason": null
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "e8db957ce267a2e87184e6e47b692730",
                "sha256": "65b7cabe0c2cccf3bdfd4f6dd0a6706f35565fee796cf4fd4f0d3128cf84db07"
            },
            "downloads": -1,
            "filename": "fermat-0.2.5-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "e8db957ce267a2e87184e6e47b692730",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.5",
            "size": 11126,
            "upload_time": "2019-11-06T18:28:59",
            "upload_time_iso_8601": "2019-11-06T18:28:59.568504Z",
            "url": "https://files.pythonhosted.org/packages/36/bc/e593eb7016b6f44e1bdeb90bb2c37147e9af09ff1f9ce815a674072bb4b1/fermat-0.2.5-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "vulnerabilities": []
}