Repository: ctlab/ITMO_FS (language: python)

Issue:
Develop
# Pull Request Template

## Description

Please include a summary of the change and which issue is fixed. Please also include relevant motivation and context. List any dependencies that are required for this change.

Fixes # (issue)

## Type of change

Please delete options that are not relevant.

- [+] Bug fix (non-breaking change which fixes an issue)
- [+] New feature (non-breaking change which adds functionality)
- [+] New method (set a link to paper then)
- [ ] Breaking change (fix or feature that would cause existing functionality to not work as expected)
- [ ] This change requires a documentation update

## How Has This Been Tested?

Please describe the tests or set link to that you ran to verify your changes. Provide instructions so we can reproduce. Please also list any relevant details for your test configuration



## Checklist:

- [ ] My code follows the style guidelines of this project
- [ ] I have performed a self-review of my own code
- [ ] I have commented my code, particularly in hard-to-understand areas
- [ ] I have made corresponding changes to the documentation
- [ ] My changes generate no new warnings
- [ ] I have added tests that prove my fix is effective or that my feature works
- [ ] New and existing unit tests pass locally with my changes
- [ ] Any dependent changes have been merged and published in downstream modules
- [ ] I have checked my code and corrected any misspellings


Discussion / hints:
New version

Fix patch:
diff --git a/.github/workflows/codeql-analysis.yml b/.github/workflows/codeql-analysis.yml
new file mode 100644
index 00000000..a6aad4ff
--- /dev/null
+++ b/.github/workflows/codeql-analysis.yml
@@ -0,0 +1,71 @@
+# For most projects, this workflow file will not need changing; you simply need
+# to commit it to your repository.
+#
+# You may wish to alter this file to override the set of languages analyzed,
+# or to provide custom queries or build logic.
+#
+# ******** NOTE ********
+# We have attempted to detect the languages in your repository. Please check
+# the `language` matrix defined below to confirm you have the correct set of
+# supported CodeQL languages.
+#
+name: "CodeQL"
+
+on:
+  push:
+    branches: [ master ]
+  pull_request:
+    # The branches below must be a subset of the branches above
+    branches: [ master ]
+  schedule:
+    - cron: '21 23 * * 1'
+
+jobs:
+  analyze:
+    name: Analyze
+    runs-on: ubuntu-latest
+    permissions:
+      actions: read
+      contents: read
+      security-events: write
+
+    strategy:
+      fail-fast: false
+      matrix:
+        language: [ 'python' ]
+        # CodeQL supports [ 'cpp', 'csharp', 'go', 'java', 'javascript', 'python' ]
+        # Learn more:
+        # https://docs.github.com/en/free-pro-team@latest/github/finding-security-vulnerabilities-and-errors-in-your-code/configuring-code-scanning#changing-the-languages-that-are-analyzed
+
+    steps:
+    - name: Checkout repository
+      uses: actions/checkout@v2
+
+    # Initializes the CodeQL tools for scanning.
+    - name: Initialize CodeQL
+      uses: github/codeql-action/init@v1
+      with:
+        languages: ${{ matrix.language }}
+        # If you wish to specify custom queries, you can do so here or in a config file.
+        # By default, queries listed here will override any specified in a config file.
+        # Prefix the list here with "+" to use these queries and those in the config file.
+        # queries: ./path/to/local/query, your-org/your-repo/queries@main
+
+    # Autobuild attempts to build any compiled languages  (C/C++, C#, or Java).
+    # If this step fails, then you should remove it and run the build manually (see below)
+    - name: Autobuild
+      uses: github/codeql-action/autobuild@v1
+
+    # ℹ️ Command-line programs to run using the OS shell.
+    # 📚 https://git.io/JvXDl
+
+    # ✏️ If the Autobuild fails above, remove it and uncomment the following three lines
+    #    and modify them (or add more) to build your code if your project
+    #    uses a compiled language
+
+    #- run: |
+    #   make bootstrap
+    #   make release
+
+    - name: Perform CodeQL Analysis
+      uses: github/codeql-action/analyze@v1
diff --git a/ITMO_FS/hybrid/EGSA/Agent.py b/ITMO_FS/hybrid/EGSA/Agent.py
new file mode 100644
index 00000000..d1859bc8
--- /dev/null
+++ b/ITMO_FS/hybrid/EGSA/Agent.py
@@ -0,0 +1,106 @@
+import numpy as np
+
+
+class Agent:
+    """
+    Agent for Evolutionary Gravitational Search-based Feature Selection.
+    Simply a bit vector that stands for selected features with it's fitness, acceleration, velocity and mass.
+
+    Parameters
+    ----------
+    size: int
+        Size of bit vector for selected features.
+    estimator : Estimator class
+        The class of estimator that will be used as evaluator.
+    transfer_function : float -> float
+        Function that defines probability of including/dropping a feature based on agent's velocity.
+        Since it is probability, the domain of function should be [0, 1].
+    seed: int
+        Seed for random generator.
+    """
+    def __init__(self, size, estimator, transfer_function, seed, smooth_coefficient):
+        self.estimator = estimator
+        self.transfer_function = transfer_function
+        self.size = size
+        self.smooth_coefficient = smooth_coefficient
+
+        self.seed = seed
+        self.random = np.random.default_rng(seed)
+        self.bits = self.random.integers(0, 2, size)
+
+        self.fitness = None
+        self.mass = None
+        self.acceleration = None
+        self.velocity = np.zeros(size, dtype=np.float64)
+
+    def count_selected(self):
+        return self.bits.sum()
+
+    def update_fitness(self, data, target, alpha):
+        selected = data[:, self.to_bool()]
+        fitness = self.estimator().fit(selected, target).score(selected, target)
+        self.fitness = alpha * fitness + (1 - alpha) * (1 - (self.count_selected() / self.size))
+
+    def update_mass(self, worst, diff_sum):
+        diff_sum = diff_sum if diff_sum != 0 else self.smooth_coefficient
+        self.mass = (self.fitness - worst) / diff_sum
+
+    def update_acceleration(self, forces):
+        self.acceleration = sum([self.random.random() * f for f in forces])
+        if self.mass != 0:
+            self.acceleration /= self.mass
+        else:
+            self.acceleration /= self.smooth_coefficient
+
+    def update_velocity(self):
+        self.velocity *= self.random.random()
+        self.velocity += self.acceleration
+
+    def update_bits(self):
+        for k, v in enumerate(self.velocity):
+            if self.transfer_function(v) > self.random.random():
+                self.bits[k] = 1 if self.bits[k] == 0 else 0
+
+        if self.count_selected() == 0:
+            self.bits[0] = 1
+
+    def copy(self):
+        new = Agent(self.size, transfer_function=self.transfer_function, estimator=self.estimator,
+                    seed=self.seed + self.random.integers(1000))
+        new.bits = self.bits.copy()
+        new.fitness = self.fitness
+        return new
+
+    def to_bool(self):
+        if self.bits.sum() == 0:
+            self.bits = self.random.integers(0, 2, self.size)
+        return [bool(x) for x in self.bits]
+
+    def __sub__(self, other):
+        new = self.copy()
+        new.bits = np.array([1 if x != 0 else 0 for x in (self.bits - other.bits)])
+        return new.bits
+
+    def __str__(self):
+        return ' '.join([str(self.bits), str(self.fitness)])
+
+    def swap_mutation(self):
+        i, j = self.random.integers(2, 2)
+        new = self.copy()
+        new.bits[i], new.bits[j] = new.bits[j], new.bits[i]
+        return new
+
+    def bit_flip_mutation(self):
+        i = self.random.integers(self.size)
+        new = self.copy()
+        new.bits[i] = (new.bits[i] + 1) % 2
+        return new
+
+    def crossover(self, other):
+        cross_len = self.size // 5
+        i = self.random.integers(self.size)
+        new = self.copy()
+        for j in range(cross_len):
+            k = (i + j) % self.size
+            new.bits[k] = other.bits[k]
+        return new
diff --git a/ITMO_FS/hybrid/EGSA/EGSA.py b/ITMO_FS/hybrid/EGSA/EGSA.py
new file mode 100644
index 00000000..e89dea26
--- /dev/null
+++ b/ITMO_FS/hybrid/EGSA/EGSA.py
@@ -0,0 +1,263 @@
+import numpy as np
+from sklearn.neighbors import KNeighborsClassifier
+
+from Agent import Agent
+
+
+class EGSA:
+    """
+    Performs an Evolutionary Gravitational Search-based Feature Selection
+    For more details see "An Evolutionary Gravitational Search-based Feature Selection" by Mohammad Taradeh et al.
+
+    Parameters
+    ----------
+    estimator : Estimator class (by default sklearn.neighbors.KNeighborsClassifier)
+        The class of estimator that will be used as evaluator.
+    n_agents : int (by default 20)
+        Amount of search agents.
+    iterations : int (by default 200)
+        Amount of iterations to be performed if end condition is never met.
+    stuck_iterations : int (by default 8)
+        If the current best feature subset have not changed for stuck_iterations
+        genetic algorithm mutation will be involved.
+    stop_iterations : int (by default 30)
+        If current best feature subset have not changed for stop_iterations algorithm will terminate.
+    gravitational_factor : float (by default 10)
+        gravitational_factor defines how fast agents are moving towards each other.
+    gravitational_factor_min : float (by default 0)
+        gravitational_factor scales towards gravitational_factor_min over time.
+    gravitational_factor_scale : float (by default 1)
+        gravitational_factor_scale defines how fast gravitational_factor scales over time.
+    transfer_function : float -> float (by default lambda v: np.abs(np.tanh(v)))
+        Function that defines probability of including/dropping a feature based on agent's velocity.
+        Since it is probability, the domain of function should be [0, 1].
+    alpha : float (by default 0.85)
+        alpha defines the trade-off between the quality of feature subset and its size.
+        The bigger alpha is the more agents lean towards maximizing accuracy of the evaluated estimator.
+        And the smaller alpha is the more agents tend to drop selected features.
+    smooth_coefficient : float
+        Minimal agent mass value.
+    agent_distance_metric : np.array of int -> np.array of int -> float (by default np.linalg.norm)
+        Function that will be used to calculate distance between agents.
+    seed: int (by default 31)
+        Seed for random generator.
+
+    Examples
+    --------
+    >>> from sklearn.datasets import make_classification
+    >>> from sklearn.neighbors import KNeighborsClassifier
+    >>> from EGSA import EGSA
+
+    >>> X, y = make_classification(n_samples=250, n_features=10, random_state=0, n_informative=2, n_redundant=0)
+    >>> trX = EGSA(alpha=0.8, iterations=10).fit_transform(X, y)
+
+    >>> X.shape, trX.shape
+    ((250, 10), (250, 4))
+
+    >>> KNeighborsClassifier().fit(X, y).score(X, y)
+    0.9
+
+    >>> KNeighborsClassifier().fit(trX, y).score(trX, y)
+    0.944
+    """
+
+    def __init__(self, n_agents=20, iterations=200, stuck_iterations=8, stop_iterations=30, gravitational_factor=10,
+                 gravitational_factor_min=0, gravitational_factor_scale=1,
+                 transfer_function=lambda v: np.abs(np.tanh(v)), alpha=0.85, estimator=KNeighborsClassifier,
+                 smooth_coefficient=0.0001, agent_distance_metric=np.linalg.norm, seed=31):
+        self.n_agents = n_agents
+        self.iterations = iterations
+        self.stuck_iterations = stuck_iterations
+        self.stop_iterations = stop_iterations
+
+        self.G = gravitational_factor
+        self.G_max = gravitational_factor
+        self.G_min = gravitational_factor_min
+        self.scale = gravitational_factor_scale
+
+        self.alpha = alpha
+        self.estimator = estimator
+        self.transfer_function = transfer_function
+        self.smooth_coefficient = smooth_coefficient
+        self.distance_metric = agent_distance_metric
+
+        self.seed = seed
+
+        self.gbest = None
+        self.iterations_since_last_update = 0
+
+    def fit(self, X, y):
+        """
+        Fit to given data
+
+        Parameters
+        ----------
+        X : array-like, shape (n_samples, n_features)
+            The training input samples.
+        y : array-like, shape (n_samples, )
+            The target values.
+
+        Returns
+        -------
+        fitted : EGSA
+            Fitted instance of EGSA
+        """
+
+        n = len(X[0])
+        agents = [self._make_agent(n) for _ in range(self.n_agents)]
+
+        self._update_fitness(agents)
+        self._update_gbest(agents[0])
+
+        for t in range(self.iterations):
+            agents = self._crossover(agents, X, y)
+
+            # Evaluate the fitness of all objects
+            self._update_fitness(agents)
+
+            if self.iterations_since_last_update == self.stop_iterations:
+                return
+
+            if self.iterations_since_last_update > 8:
+                temp = self.gbest.bit_flip_mutation()
+                temp.update_fitness(X, y, self.alpha)
+
+                if temp.fitness > self.gbest.fitness:
+                    agents[-1] = self.gbest
+                    self._update_gbest(temp)
+                if temp.fitness > agents[0].fitness:
+                    agents[-1] = agents[0]
+                    agents[0] = temp
+                elif temp.fitness > agents[-1].fitness:
+                    agents[-1] = temp
+
+            # Update global best
+            self._update_gbest(agents[0])
+
+            # Calculate Mi
+            worst_fitness = agents[-1].fitness
+            diff_sum = sum([a.fitness for a in agents]) - (self.n_agents * worst_fitness)
+            for agent in agents:
+                agent.update_mass(worst=worst_fitness, diff_sum=diff_sum)
+
+            # Update the gravitational factor
+            self.G *= self.G_max - (self.G_max - self.G_min) * np.log10(self.scale + 10 * t / self.iterations)
+
+            # Calculate forces, update accelerations
+            for agent in agents:
+                forces = [self.G * agent.mass * other.mass * (other - agent) / self.distance_metric(other - agent) ** 2
+                          for other in agents if (agent.bits != other.bits).all()]
+                agent.update_acceleration(forces)
+
+            # Update velocities
+            for agent in agents:
+                agent.update_velocity()
+
+            # Update positions
+            for agent in agents:
+                agent.update_bits()
+
+        return self
+
+    def transform(self, X):
+        """
+        Reduce X to the selected features.
+
+        Parameters
+        ----------
+        X : array-like, shape (n_samples, n_features)
+                The input samples.
+
+        Returns
+        -------
+        X : array-like, shape (n_samples, n_selected_features)
+            The input samples with only the selected features.
+        """
+
+        if self.gbest is None:
+            raise Exception('transform is invoked on the instance that has not fitted yet')
+        return X[:, self.gbest.to_bool()]
+
+    def fit_transform(self, X, y):
+        """
+        Fit to data, then transform it.
+
+        Parameters
+        ----------
+        X : array-like, shape (n_samples, n_features)
+            Input samples.
+        y : array-like, shape (n_samples, )
+            Target values.
+
+        Returns
+        ------
+        X_new : array-like, shape (n_samples, n_selected_features)
+            Transformed array.
+        """
+
+        return self.fit(X, y).transform(X)
+
+    def _update_fitness(self, agents):
+        for agent in agents:
+            agent.update_fitness(X, y, self.alpha)
+
+    def _make_agent(self, size):
+        """
+        Make new agent of given size
+
+        Parameters
+        ----------
+        size
+
+        Returns
+        -------
+        agent : Agent
+            New agent
+        """
+
+        self.seed += 1
+        return Agent(size=size, transfer_function=self.transfer_function, estimator=self.estimator, seed=self.seed, smooth_coefficient=self.smooth_coefficient)
+
+    def _update_gbest(self, candidate):
+        """
+        Attempts to update current the best feature subset
+
+        Parameters
+        ----------
+        candidate : Agent
+            Candidate to new gbest
+        Returns
+        -------
+            None
+        """
+
+        self.iterations_since_last_update += 1
+        if self.gbest is None or self.gbest.fitness < candidate.fitness:
+            self.gbest = candidate.copy()
+            self.iterations_since_last_update = 0
+
+    def _crossover(self, agents, data, target):
+        """
+        Applies crossover on gbest and top half of agents to increase exploration.
+
+        Parameters
+        ----------
+        agents: List[Agent]
+        data: array-like, shape (n_samples, n_features)
+            Input samples.
+        target: array-like, shape (n_samples, )
+            Target values.
+
+        Returns
+        -------
+        pool: List[Agent]
+            New pool of agents.
+        """
+
+        pool = sorted(agents, key=lambda a: a.fitness, reverse=True)
+        for i in range(self.n_agents // 2):
+            new = self.gbest.crossover(pool[i])
+            new.update_fitness(data, target, self.alpha)
+            pool.append(new)
+
+        return sorted(pool, key=lambda a: a.fitness, reverse=True)[:self.n_agents]
diff --git a/ITMO_FS/hybrid/EGSA/__init__.py b/ITMO_FS/hybrid/EGSA/__init__.py
new file mode 100644
index 00000000..faf383ec
--- /dev/null
+++ b/ITMO_FS/hybrid/EGSA/__init__.py
@@ -0,0 +1,1 @@
+from . import EGSA
diff --git a/ITMO_FS/hybrid/__init__.py b/ITMO_FS/hybrid/__init__.py
index c9d2b648..c3717d91 100644
--- a/ITMO_FS/hybrid/__init__.py
+++ b/ITMO_FS/hybrid/__init__.py
@@ -1,3 +1,4 @@
 from .filter_wrapper_hybrid import *
 from .Melif import Melif
 from .IWSSr_SFLA import IWSSr_SFLA
+from .EGSA import EGSA
\ No newline at end of file


Test patch:
diff --git a/test/EGSA_test.py b/test/EGSA_test.py
new file mode 100644
index 00000000..d831c19c
--- /dev/null
+++ b/test/EGSA_test.py
@@ -0,0 +1,23 @@
+import unittest
+from ITMO_FS.hybrid.EGSA.EGSA import EGSA
+from sklearn.datasets import make_classification
+from sklearn.neighbors import KNeighborsClassifier
+
+
+class EgsaTest(unittest.TestCase):
+    @staticmethod
+    def test():
+        for informative, features, alpha, expected in [(2, 10, 0.8, 0.94), (10, 50, 0.9, 0.9), (7, 22, 1, 0.94)]:
+            X, y = make_classification(n_samples=200, n_features=features, random_state=0,
+                                       n_informative=informative, n_redundant=0, shuffle=False)
+
+            egsa = EGSA(alpha=alpha, iterations=50)
+            trX = egsa.fit_transform(X, y)
+
+            score = KNeighborsClassifier().fit(trX, y).score(trX, y)
+
+            assert (score >= expected)
+
+
+if __name__ == '__main__':
+    unittest.main()