Depth First Search (DFS) on the Iris Dataset Using Python
Graph traversal algorithms are among the most important concepts in computer science and machine learning. In this tutorial, we will combine graph theory with one of the most famous machine learning datasets: the Iris dataset.
Instead of treating the Iris dataset purely as a classification problem, we will represent each flower sample as a node in a graph and explore the dataset using a graph traversal algorithm called Depth-First Search (DFS).
This approach helps demonstrate:
- Graph traversal concepts
- Recursive algorithms
- Dataset exploration techniques
- Graph representation in Python
- DFS path tracking
💡 What You Will Learn
- What the Iris dataset contains
- How graphs are represented in Python
- How DFS works internally
- How recursion powers DFS
- How datasets can be treated as graphs
- How feature standardization works
- How to track traversal paths
- DFS mathematical complexity
- Practical Python implementation
Table of Contents
1. Understanding the Iris Dataset
The Iris dataset is one of the most famous datasets in machine learning and statistics.
It contains measurements from three species of Iris flowers:
- Setosa
- Versicolor
- Virginica
Features in the Dataset
| Feature | Description |
|---|---|
| Sepal Length | Length of the flower sepal |
| Sepal Width | Width of the flower sepal |
| Petal Length | Length of the flower petal |
| Petal Width | Width of the flower petal |
Dataset Size
The dataset contains:
$$ 150 \ Samples $$Each species contains:
$$ 50 \ Flowers $$2. Representing the Dataset as a Graph
Normally, datasets are stored in rows and columns.
However, in this tutorial:
$$ Each \ Flower = Graph \ Node $$Every node is connected to every other node.
Fully Connected Graph
If there are:
$$ n \ Nodes $$Then total edges in a fully connected graph are:
$$ \frac{n(n-1)}{2} $$For the Iris dataset:
$$ \frac{150(149)}{2} $$Which equals:
$$ 11175 \ Edges $$This creates a dense graph where every flower can reach every other flower.
3. What is Depth First Search (DFS)?
Depth First Search is a graph traversal algorithm.
DFS explores:
- One branch deeply
- Then backtracks
- Then explores another branch
DFS Strategy
The traversal follows:
$$ Explore \rightarrow Deep \rightarrow Backtrack $$Recursive Nature
DFS is commonly implemented recursively.
The recursive structure is:
$$ DFS(Node) \rightarrow DFS(Neighbor) $$DFS Example
A → B → D
↑
Backtrack
Why DFS is Important
- Graph exploration
- Path finding
- Maze solving
- Web crawling
- Network analysis
- AI search algorithms
4. Feature Standardization
Before exploring the dataset, we standardize the features.
Why?
Different features may have different ranges.
Example
| Feature | Possible Range |
|---|---|
| Sepal Length | 4.3 - 7.9 |
| Petal Width | 0.1 - 2.5 |
Without standardization:
- Larger values dominate calculations.
- Features contribute unequally.
Standardization Formula
$$ z = \frac{x - \mu}{\sigma} $$Where:
| Symbol | Meaning |
|---|---|
| \(x\) | Original value |
| \(\mu\) | Mean |
| \(\sigma\) | Standard deviation |
After scaling:
$$ Mean \approx 0 $$And:
$$ StandardDeviation \approx 1 $$5. Python DFS Implementation
Importing Libraries
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
Loading Dataset
iris = load_iris()
X = iris.data
y = iris.target
Standardizing Features
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
Building Graph
graph = {}
for i in range(len(X_scaled)):
graph[i] = [
j for j in range(len(X_scaled))
if j != i
]
Every node is connected to all others.
DFS Algorithm Implementation
visited = set()
def dfs(node, path=[]):
visited.add(node)
path.append(node)
print("Node:", node)
print("Features:", X_scaled[node])
print("Species:", y[node])
print("Path Length:", len(path))
print("-" * 40)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, path)
path.pop()
Starting DFS
dfs(0)
6. DFS Mathematics and Complexity
Time Complexity
DFS complexity is:
$$ O(V + E) $$Where:
- \(V\) = Number of vertices
- \(E\) = Number of edges
For our graph:
$$ V = 150 $$And:
$$ E = 11175 $$Thus:
$$ O(150 + 11175) $$Space Complexity
DFS recursion stack:
$$ O(V) $$Worst case:
$$ O(150) $$7. Understanding the DFS Traversal Process
DFS explores deeply before backtracking.
Traversal Pattern
Node 0
↓
Node 1
↓
Node 2
↓
Node 3
When no unvisited neighbors remain:
$$ Backtrack $$Then continue exploring.
Visited Set
DFS uses:
$$ Visited = \{Nodes\ Already\ Explored\} $$This prevents infinite loops.
8. CLI Output Examples
Running the Program
python iris_dfs.py
CLI Output
Node: 0
Features:
[-0.90 1.01 -1.34 -1.31]
Species: 0
Path Length: 1
--------------------------------
Another Output Example
Node: 25
Features:
[-0.05 0.78 -1.14 -1.05]
Species: 0
Path Length: 26
--------------------------------
DFS Progress
Visited Nodes: 150
Traversal Complete
9. Advanced Concepts
Why Use DFS on Datasets?
Although unusual, representing datasets as graphs enables:
- Similarity analysis
- Cluster exploration
- Relationship discovery
- Graph-based machine learning
Graph Machine Learning
Modern AI systems often use:
- Graph Neural Networks
- Knowledge Graphs
- Social Network Graphs
- Recommendation Graphs
Recursive Depth
DFS recursion depth can become large:
$$ Depth \rightarrow V $$Large graphs may require iterative DFS implementations.
Iterative DFS Alternative
Instead of recursion, DFS can use a stack:
$$ Stack = LIFO $$This avoids recursion depth limitations.
10. Real World Applications of DFS
Search Engines
Web crawlers explore pages using traversal algorithms.
Social Networks
DFS helps analyze relationships between users.
Maps and Navigation
Graph traversal assists route exploration.
Artificial Intelligence
Game trees use DFS extensively.
Bioinformatics
Protein interaction networks use graph traversal.
Key Insights from This Project
- Datasets can be modeled as graphs.
- DFS explores deeply before backtracking.
- Feature scaling improves consistency.
- Graphs enable relational exploration.
- Recursion powers DFS traversal.
- Complexity depends on vertices and edges.
- Machine learning and graph theory can combine effectively.
11. Conclusion
In this tutorial, we explored a creative way of using Depth First Search (DFS) on the Iris dataset.
Instead of treating the dataset traditionally, we transformed each flower into a graph node and explored the dataset using graph traversal.
We covered:
- Graph representation
- Feature scaling
- Recursive DFS algorithms
- Traversal path tracking
- Graph mathematics
- Computational complexity
Although this example is educational, it demonstrates how graph theory and machine learning concepts can intersect in powerful ways.
Understanding DFS provides a strong foundation for advanced topics like:
- Graph databases
- Network science
- Graph neural networks
- AI search algorithms
- Knowledge graphs
🎯 Final Takeaways
- DFS is a fundamental graph traversal algorithm.
- Datasets can be represented as connected graphs.
- Standardization improves feature consistency.
- Recursion is central to DFS.
- Graph theory plays a major role in AI and ML.
- The Iris dataset remains a powerful educational tool.
No comments:
Post a Comment