Skip to content

Implementation of three variants of the Frank-Wolfe method for solving the Minimum Enclosing Ball problem, and application to anomaly detection.

Notifications You must be signed in to change notification settings

Di40/MEB-Anomaly-FW-Optimization

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Minimum Enclosing Ball for Anomaly Detection using variants of Frank-Wolfe

Table of contents

General info

This is the final project for the "Optimization for Data Science" course at the University of Padova.
This repository contains the code, report, presentation and some extra materials.

Task

  1. Analyze in-depth four papers and their theoretical results.
  2. Implement the Away-Steps Frank-Wolfe algorithm from Lacoste-Julien et al., 2015.
  3. Implement the Blended Pairwise Conditional Gradients (BPCG) algorithm from Tsuji et. al., 2022.
  4. Implement the (1+ε)-approximation to MEB algorithm from Yildirim, 2008.
  5. Apply the MEB approach for anomaly detection (locate new points that are out of the MEB) on two real-world datasets.

Team members:

We utilized PyCharm for development and GitHub for version control.

Project structure

├───configs
├───datasets
├───documents
│   ├───Extra papers
│   ├───Extra theory
│   ├───Papers with notes
│   └───Report and Presentation
└───src
│   ├── data_generation.py
│   ├── execution.py
│   ├── FrankWolfeVariants.py
│   ├── logger.py
│   ├── plotting.py
│   ├── utils.py
├── main.py
├── setup.py
└── requirements.txt

Setup

$ conda update conda -y
$ conda create -p venv python==3.10 -y
$ conda activate venv/

Go to the requirements.txt file and uncomment the symbol (#) before "-e .". Then:

$ pip install -r requirements.txt

Usage

Choose a configuration file (.yaml) to run an experiment from the configs folder. For example:

$ python main.py --cfg "exp6_CustomerChurn.yaml"

The results will be saved to the runs/experiment folder.

Contributing

We invite you to explore our analysis, learn from our findings, and adapt our methodologies to your own projects. Your feedback and contributions are highly valued!

About

Implementation of three variants of the Frank-Wolfe method for solving the Minimum Enclosing Ball problem, and application to anomaly detection.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 100.0%