Python
Python copied to clipboard
Published
1 month ago
•
TheAlgorithms
TheAlgorithms
Add ART1 algorithm in neural network
Feature description
Description:
This issue aims to implement an Adaptive Resonance Theory (ART1) algorithm for binary data clustering. ART1 is well-suited for unsupervised learning with binary inputs, using a vigilance parameter to determine the clustering threshold. This model will enhance the framework's clustering capabilities, allowing for pattern recognition in binary data.
Goals:
Requirements:
Hi @JeninaAngelin, I would like to work upon this I am new to open-source
Can you please help me with how do I get started ?
Actually I tried adding code for the ART network algorithm but sadly it didn't pass the required tests.
You can work by asking the repo owner to assign this issue to you or create a PR fixing the issue.
To implement the Adaptive Resonance Theory (ART1) algorithm for binary data clustering, we'll create a class that handles online clustering with a vigilance parameter. Below is the complete implementation with detailed documentation:
class ART1:
"""
Adaptive Resonance Theory (ART1) for binary data clustering
Attributes:
num_features (int): Dimensionality of input vectors
vigilance (float): Vigilance parameter (0 < rho <= 1.0)
L (float): Learning parameter (L > 1.0)
max_clusters (int): Maximum clusters allowed (None for unlimited)
templates (list): Cluster prototype vectors (top-down weights)
cluster_history (list): Creation order of clusters
"""
def __init__(self, num_features, vigilance=0.7, L=1.1, max_clusters=None):
"""
Initialize ART1 clustering model
Args:
num_features: Dimension of binary input vectors
vigilance: Vigilance parameter (0.7 typical)
L: Learning parameter >1.0 (1.1 typical)
max_clusters: Maximum clusters to create (None = unlimited)
"""
if not 0 < vigilance <= 1.0:
raise ValueError("Vigilance must be in (0, 1]")
if L <= 1.0:
raise ValueError("L must be > 1.0")
self.num_features = num_features
self.vigilance = vigilance
self.L = L
self.max_clusters = max_clusters
self.templates = []
self.cluster_history = []
def _calculate_choice_function(self, x, template):
"""
Calculate choice function (T_j) for input vector x and cluster template
T_j = |x ∧ w_j| * L / (L - 1 + |w_j|)
Args:
x: Input vector (binary list)
template: Cluster template vector
Returns:
T_j: Choice function value
intersection: |x ∧ w_j|
"""
intersection = sum(x_i & w_i for x_i, w_i in zip(x, template))
template_norm = sum(template)
denominator = self.L - 1 + template_norm
if template_norm == 0: # Avoid division by zero
return 0.0, intersection
return (self.L * intersection) / denominator, intersection
def train(self, data):
"""
Train ART1 model on binary data
Args:
data: Iterable of binary vectors (each vector length = num_features)
"""
for x in data:
self._train_pattern(x)
def _train_pattern(self, x):
"""Process a single input pattern during training"""
# Skip zero vectors
if sum(x) == 0:
return
# Initialize first cluster if none exist
if not self.templates:
self._create_new_cluster(x)
return
# Calculate choice function for all clusters
candidates = []
for idx, template in enumerate(self.templates):
T_j, intersection = self._calculate_choice_function(x, template)
candidates.append((idx, T_j, intersection))
# Sort by choice function descending
candidates.sort(key=lambda c: c[1], reverse=True)
# Find best matching cluster meeting vigilance
matched = False
x_norm = sum(x)
for idx, T_j, intersection in candidates:
similarity = intersection / x_norm
if similarity >= self.vigilance:
self._update_cluster(idx, x)
matched = True
break
# Create new cluster if no match found
if not matched:
self._create_new_cluster(x)
def _update_cluster(self, cluster_idx, x):
"""Update cluster template with new input vector"""
# Update template: w_j ∧ x
self.templates[cluster_idx] = [
x_i & w_i for x_i, w_i in zip(x, self.templates[cluster_idx])
]
def _create_new_cluster(self, x):
"""Create new cluster from input vector"""
if self.max_clusters and len(self.templates) >= self.max_clusters:
return
self.templates.append(x[:]) # Store copy of vector
self.cluster_history.append(len(self.templates) - 1)
def predict(self, x):
"""
Predict cluster assignment for input vector
Args:
x: Binary input vector
Returns:
Cluster index or -1 if no matching cluster
"""
if sum(x) == 0: # Zero vector never matches
return -1
if not self.templates:
return -1
# Calculate choice function for all clusters
candidates = []
for idx, template in enumerate(self.templates):
T_j, intersection = self._calculate_choice_function(x, template)
candidates.append((idx, T_j, intersection))
# Sort by choice function descending
candidates.sort(key=lambda c: c[1], reverse=True)
# Return first cluster meeting vigilance
x_norm = sum(x)
for idx, T_j, intersection in candidates:
similarity = intersection / x_norm
if similarity >= self.vigilance:
return idx
return -1 # No cluster found
@property
def n_clusters(self):
"""Number of clusters currently in model"""
return len(self.templates)
Example Usage
# Create ART1 model
art = ART1(
num_features=4,
vigilance=0.6,
L=1.2,
max_clusters=5
)
# Training data (binary vectors)
data = [
[1, 1, 0, 0],
[1, 0, 0, 0],
[0, 0, 0, 1],
[1, 1, 0, 1],
[0, 0, 1, 1],
[1, 1, 1, 0]
]
# Train model
art.train(data)
# Check results
print(f"Number of clusters: {art.n_clusters}")
print("Cluster templates:")
for i, template in enumerate(art.templates):
print(f"Cluster {i}: {template}")
# Make predictions
test_vectors = [
[1, 0, 0, 0],
[0, 0, 1, 1],
[1, 1, 1, 1]
]
print("\nPredictions:")
for vec in test_vectors:
cluster = art.predict(vec)
print(f"Vector {vec} -> Cluster {cluster}")
Unit Tests
import unittest
class TestART1(unittest.TestCase):
def setUp(self):
self.art = ART1(
num_features=4,
vigilance=0.7,
L=1.1,
max_clusters=3
)
self.data = [
[1, 1, 0, 0],
[1, 0, 0, 0],
[0, 0, 0, 1],
[1, 1, 0, 1],
[0, 0, 1, 1]
]
def test_initialization(self):
self.assertEqual(self.art.n_clusters, 0)
self.assertEqual(self.art.vigilance, 0.7)
self.assertEqual(self.art.L, 1.1)
self.assertEqual(self.art.num_features, 4)
def test_training(self):
self.art.train(self.data)
self.assertEqual(self.art.n_clusters, 3)
def test_prediction(self):
self.art.train(self.data)
# Test known patterns
self.assertEqual(self.art.predict([1, 1, 0, 0]), 0)
self.assertEqual(self.art.predict([1, 0, 0, 0]), 0)
self.assertEqual(self.art.predict([0, 0, 0, 1]), 1)
# Test novel pattern
self.assertEqual(self.art.predict([0, 0, 1, 0]), -1)
# Test zero vector
self.assertEqual(self.art.predict([0, 0, 0, 0]), -1)
def test_max_clusters(self):
extra_data = self.data + [
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 1, 1, 1]
]
self.art.train(extra_data)
self.assertEqual(self.art.n_clusters, 3)
def test_template_update(self):
self.art.train([[1, 1, 1, 1], [1, 1, 0, 1]])
self.assertEqual(self.art.templates[0], [1, 1, 0, 1])
if __name__ == "__main__":
unittest.main()
Key Features:
- Online Learning: Processes data incrementally
- Vigilance Control: Adjustable cluster granularity
-
Cluster Management:
- Automatic cluster creation
- Template updating
- Max cluster constraint
-
Efficient Computation:
- Bitwise operations for binary vectors
- Choice function optimization
- Zero Vector Handling: Special case handling
- History Tracking: Records cluster creation order
The implementation follows ART1 principles:
- Choice Function: Computes similarity-to-template ratio
- Vigilance Test: Enforces cluster quality threshold
- Template Updating: Intersection-based adaptation
- Stability-Plasticity: Balances new learning with existing knowledge
The solution includes comprehensive documentation, usage examples, and unit tests covering core functionality and edge cases.
Hey @JeninaAngelin @SubhaNAG2001 @Vraj2811 , I would like to work on it. So for confirmation, is anybody still working on this?
