Making Of: City Science
Mathematical Foundations and Implemented Algorithms
A detailed analysis of the technologies and methodologies behind the environmental analysis system
🧠 Neural Networks: Perceptron Algorithm
The Perceptron is the most fundamental artificial neuron model, developed by Frank Rosenblatt in 1957. It is a binary linear classifier that learns through an iterative error-correction process.
Mathematical Operation
Activation Function:
y = f(∑ wᵢ × xᵢ + b)
Step Function:
f(z) = { 1 if z ≥ 0, 0 if z < 0 }
Learning Rule:
wᵢ(t+1) = wᵢ(t) + η × (target - output) × xᵢ
b(t+1) = b(t) + η × (target - output)
where η is the learning rate
y = f(∑ wᵢ × xᵢ + b)
Step Function:
f(z) = { 1 if z ≥ 0, 0 if z < 0 }
Learning Rule:
wᵢ(t+1) = wᵢ(t) + η × (target - output) × xᵢ
b(t+1) = b(t) + η × (target - output)
where η is the learning rate
Training Algorithm:
- Initialize weights and bias randomly
- For each training example:
- Calculate the output: y = f(∑wᵢxᵢ + b)
- Compute the error: e = target - y
- Update weights: wᵢ = wᵢ + η × e × xᵢ
- Repeat until convergence or maximum number of epochs
Example: AND Logic Gate
Training Data:
• (0,0) → 0
• (0,1) → 0
• (1,0) → 0
• (1,1) → 1
Process (η = 0.1):
Initial weights: w₁ = 0.3, w₂ = -0.1, b = 0.2
Epoch 1, Example (1,1):
• Output: f(0.3×1 + (-0.1)×1 + 0.2) = f(0.4) = 1
• Error: 1 - 1 = 0 (correct, no update)
Epoch 1, Example (0,1):
• Output: f(0.3×0 + (-0.1)×1 + 0.2) = f(0.1) = 1
• Error: 0 - 1 = -1
• w₁ = 0.3 + 0.1×(-1)×0 = 0.3
• w₂ = -0.1 + 0.1×(-1)×1 = -0.2
• b = 0.2 + 0.1×(-1) = 0.1
Training Data:
• (0,0) → 0
• (0,1) → 0
• (1,0) → 0
• (1,1) → 1
Process (η = 0.1):
Initial weights: w₁ = 0.3, w₂ = -0.1, b = 0.2
Epoch 1, Example (1,1):
• Output: f(0.3×1 + (-0.1)×1 + 0.2) = f(0.4) = 1
• Error: 1 - 1 = 0 (correct, no update)
Epoch 1, Example (0,1):
• Output: f(0.3×0 + (-0.1)×1 + 0.2) = f(0.1) = 1
• Error: 0 - 1 = -1
• w₁ = 0.3 + 0.1×(-1)×0 = 0.3
• w₂ = -0.1 + 0.1×(-1)×1 = -0.2
• b = 0.2 + 0.1×(-1) = 0.1
In the interactive map, the Perceptron is used for binary classification of environmental conditions. For example, determining if conditions are "favorable" or "unfavorable" based on multiple factors such as temperature, humidity, air quality, and UV index. The model learns patterns from historical data to make real-time predictions.
Computational Complexity: O(n×m×e) where n = number of features, m = number of examples, e = number of epochs. Limitation: Can only learn linearly separable functions.
🌍 Geodesic Distance Calculation: Haversine Formula
The Haversine Formula calculates the distance between two points on the surface of a sphere (like Earth) using their latitude and longitude coordinates. It is essential for geolocation systems.
Mathematical Derivation
Full Formula:
a = sin²(Δφ/2) + cos(φ₁) × cos(φ₂) × sin²(Δλ/2)
c = 2 × atan2(√a, √(1-a))
d = R × c
Where:
• φ₁, φ₂ = latitudes of points 1 and 2 (in radians)
• Δφ = φ₂ - φ₁ (latitude difference)
• Δλ = λ₂ - λ₁ (longitude difference)
• R = Earth's radius (6,371 km)
• d = distance between the points
a = sin²(Δφ/2) + cos(φ₁) × cos(φ₂) × sin²(Δλ/2)
c = 2 × atan2(√a, √(1-a))
d = R × c
Where:
• φ₁, φ₂ = latitudes of points 1 and 2 (in radians)
• Δφ = φ₂ - φ₁ (latitude difference)
• Δλ = λ₂ - λ₁ (longitude difference)
• R = Earth's radius (6,371 km)
• d = distance between the points
Calculation Steps:
- Convert coordinates from degrees to radians
- Compute the differences Δφ and Δλ
- Apply the Haversine formula to find 'a'
- Calculate the central angle 'c'
- Multiply by Earth's radius to get the distance
Example: São Paulo → Rio de Janeiro
Coordinates:
• São Paulo: 23.5505°S, 46.6333°W
• Rio de Janeiro: 22.9068°S, 43.1729°W
Conversion to Radians:
• φ₁ = -23.5505° × π/180 = -0.4108 rad
• λ₁ = -46.6333° × π/180 = -0.8139 rad
• φ₂ = -22.9068° × π/180 = -0.3996 rad
• λ₂ = -43.1729° × π/180 = -0.7535 rad
Calculations:
• Δφ = -0.3996 - (-0.4108) = 0.0112 rad
• Δλ = -0.7535 - (-0.8139) = 0.0604 rad
• a = sin²(0.0056) + cos(-0.4108) × cos(-0.3996) × sin²(0.0302)
• a = 0.0000314 + 0.9158 × 0.9211 × 0.0009 = 0.0008
• c = 2 × atan2(√0.0008, √0.9992) = 0.0566 rad
• d = 6371 × 0.0566 = 360.8 km
Coordinates:
• São Paulo: 23.5505°S, 46.6333°W
• Rio de Janeiro: 22.9068°S, 43.1729°W
Conversion to Radians:
• φ₁ = -23.5505° × π/180 = -0.4108 rad
• λ₁ = -46.6333° × π/180 = -0.8139 rad
• φ₂ = -22.9068° × π/180 = -0.3996 rad
• λ₂ = -43.1729° × π/180 = -0.7535 rad
Calculations:
• Δφ = -0.3996 - (-0.4108) = 0.0112 rad
• Δλ = -0.7535 - (-0.8139) = 0.0604 rad
• a = sin²(0.0056) + cos(-0.4108) × cos(-0.3996) × sin²(0.0302)
• a = 0.0000314 + 0.9158 × 0.9211 × 0.0009 = 0.0008
• c = 2 × atan2(√0.0008, √0.9992) = 0.0566 rad
• d = 6371 × 0.0566 = 360.8 km
In the interactive map, the Haversine distance is used to calculate proximity between weather stations, determine the closest station to the user, and compute influence radii for environmental data interpolation. It is also essential for location-based recommendation systems.
Accuracy: Typical error < 0.5% for distances up to 1000 km. Alternatives: Vincenty's formula for higher precision (error < 0.1 mm) but higher computational complexity.
📝 Edit Distance: Levenshtein Algorithm
The Levenshtein Distance measures the minimum number of edit operations (insertion, deletion, substitution) required to transform one string into another. It is widely used in spell checking and approximate string matching.
Dynamic Programming
Recurrence:
D(i,j) = min {
D(i-1,j) + 1, // deletion
D(i,j-1) + 1, // insertion
D(i-1,j-1) + cost // substitution
}
Base Cases:
D(i,0) = i // i deletions
D(0,j) = j // j insertions
Cost:
cost = 0 if s₁[i] = s₂[j], otherwise 1
D(i,j) = min {
D(i-1,j) + 1, // deletion
D(i,j-1) + 1, // insertion
D(i-1,j-1) + cost // substitution
}
Base Cases:
D(i,0) = i // i deletions
D(0,j) = j // j insertions
Cost:
cost = 0 if s₁[i] = s₂[j], otherwise 1
Algorithm:
- Create a (m+1) × (n+1) matrix
- Initialize the first row and column
- For each cell (i,j):
- Compute substitution cost
- Select the operation with minimum cost
- Fill the matrix bottom-up
- Result is in D(m,n)
Example: "KITTEN" → "SITTING"
Required Operations (3 edits):
1. Substitute K → S
2. Substitute E → I
3. Insert G at the end
| ε | S | I | T | T | I | N | G | |
|---|---|---|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| K | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| I | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| T | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| T | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| E | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| N | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
1. Substitute K → S
2. Substitute E → I
3. Insert G at the end
In the interactive map, Levenshtein distance is used for intelligent location search. When a user types a city name with typos, the algorithm finds the closest match in the database. It is also used for autocomplete suggestions and query correction.
Complexity: Time O(m×n), Space O(m×n). Optimization: Space can be reduced to O(min(m,n)) using only two rows of the matrix.
🗺️ Shortest Path: Dijkstra's Algorithm
The Dijkstra Algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative weights. It is fundamental in navigation and routing systems.
Algorithm Operation
Edge Relaxation:
If dist[u] + weight(u,v) < dist[v]:
dist[v] = dist[u] + weight(u,v)
predecessor[v] = u
Invariant:
For every processed vertex u:
dist[u] = actual minimum distance from source to u
Stopping Condition:
All vertices processed OR
Next vertex has infinite distance
If dist[u] + weight(u,v) < dist[v]:
dist[v] = dist[u] + weight(u,v)
predecessor[v] = u
Invariant:
For every processed vertex u:
dist[u] = actual minimum distance from source to u
Stopping Condition:
All vertices processed OR
Next vertex has infinite distance
Detailed Algorithm:
- Initialize: dist[source] = 0, dist[others] = ∞
- Create a set of unvisited vertices
- While there are unvisited vertices:
- Select vertex u with the smallest dist[u]
- Mark u as visited
- For each neighbor v of u:
- Apply relaxation on edge (u,v)
- Update dist[v] if necessary
Example: Graph with 5 vertices
Graph:
• A → B (weight 4), A → C (weight 2)
• B → C (weight 1), B → D (weight 5)
• C → D (weight 8), C → E (weight 10)
• D → E (weight 2)
Execution (source = A):
Shortest Paths:
• A → C: 2 (direct)
• A → B: 3 (A → C → B)
• A → D: 8 (A → C → B → D)
• A → E: 10 (A → C → B → D → E)
Graph:
• A → B (weight 4), A → C (weight 2)
• B → C (weight 1), B → D (weight 5)
• C → D (weight 8), C → E (weight 10)
• D → E (weight 2)
Execution (source = A):
| Iteration | Vertex | dist[A] | dist[B] | dist[C] | dist[D] | dist[E] |
|---|---|---|---|---|---|---|
| 0 | - | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | A | 0 | 4 | 2 | ∞ | ∞ |
| 2 | C | 0 | 3 | 2 | 10 | 12 |
| 3 | B | 0 | 3 | 2 | 8 | 12 |
| 4 | D | 0 | 3 | 2 | 8 | 10 |
| 5 | E | 0 | 3 | 2 | 8 | 10 |
• A → C: 2 (direct)
• A → B: 3 (A → C → B)
• A → D: 8 (A → C → B → D)
• A → E: 10 (A → C → B → D → E)
In the interactive map, Dijkstra is used for optimization of ecological routes. The algorithm finds paths that minimize exposure to pollution, considering factors such as air quality, noise levels, and green areas. Each route segment has an "environmental weight" based on local conditions.
Complexity: O((V + E) log V) with a binary heap, O(V² + E) with a simple array. Limitation: Does not work with negative weights (use Bellman-Ford in that case).
🎨 Color Mapping: HSL System
The HSL System (Hue, Saturation, Lightness) represents colors more intuitively than RGB. It is ideal for creating data-driven gradients, where hue represents different values or categories.
HSL to RGB Conversion
Normalized Parameters:
H' = H / 360° (0 ≤ H' < 1)
S' = S / 100% (0 ≤ S' ≤ 1)
L' = L / 100% (0 ≤ L' ≤ 1)
Intermediate Calculations:
C = (1 - |2L' - 1|) × S'
X = C × (1 - |(H' × 6) mod 2 - 1|)
m = L' - C/2
Temporary RGB Values:
If 0 ≤ H' < 1/6: (R',G',B') = (C,X,0)
If 1/6 ≤ H' < 2/6: (R',G',B') = (X,C,0)
If 2/6 ≤ H' < 3/6: (R',G',B') = (0,C,X)
If 3/6 ≤ H' < 4/6: (R',G',B') = (0,X,C)
If 4/6 ≤ H' < 5/6: (R',G',B') = (X,0,C)
If 5/6 ≤ H' < 1: (R',G',B') = (C,0,X)
Final RGB:
R = (R' + m) × 255
G = (G' + m) × 255
B = (B' + m) × 255
H' = H / 360° (0 ≤ H' < 1)
S' = S / 100% (0 ≤ S' ≤ 1)
L' = L / 100% (0 ≤ L' ≤ 1)
Intermediate Calculations:
C = (1 - |2L' - 1|) × S'
X = C × (1 - |(H' × 6) mod 2 - 1|)
m = L' - C/2
Temporary RGB Values:
If 0 ≤ H' < 1/6: (R',G',B') = (C,X,0)
If 1/6 ≤ H' < 2/6: (R',G',B') = (X,C,0)
If 2/6 ≤ H' < 3/6: (R',G',B') = (0,C,X)
If 3/6 ≤ H' < 4/6: (R',G',B') = (0,X,C)
If 4/6 ≤ H' < 5/6: (R',G',B') = (X,0,C)
If 5/6 ≤ H' < 1: (R',G',B') = (C,0,X)
Final RGB:
R = (R' + m) × 255
G = (G' + m) × 255
B = (B' + m) × 255
Example: HSL(240°, 100%, 50%) → RGB
Normalization:
• H' = 240° / 360° = 0.667
• S' = 100% / 100% = 1.0
• L' = 50% / 100% = 0.5
Calculations:
• C = (1 - |2×0.5 - 1|) × 1.0 = 1.0
• H' × 6 = 0.667 × 6 = 4.0
• X = 1.0 × (1 - |4.0 mod 2 - 1|) = 1.0 × (1 - 1) = 0
• m = 0.5 - 1.0/2 = 0
Region (4/6 ≤ H' < 5/6):
• (R',G',B') = (0,X,C) = (0,0,1)
Final RGB:
• R = (0 + 0) × 255 = 0
• G = (0 + 0) × 255 = 0
• B = (1 + 0) × 255 = 255
Result: RGB(0, 0, 255) = Pure Blue
Normalization:
• H' = 240° / 360° = 0.667
• S' = 100% / 100% = 1.0
• L' = 50% / 100% = 0.5
Calculations:
• C = (1 - |2×0.5 - 1|) × 1.0 = 1.0
• H' × 6 = 0.667 × 6 = 4.0
• X = 1.0 × (1 - |4.0 mod 2 - 1|) = 1.0 × (1 - 1) = 0
• m = 0.5 - 1.0/2 = 0
Region (4/6 ≤ H' < 5/6):
• (R',G',B') = (0,X,C) = (0,0,1)
Final RGB:
• R = (0 + 0) × 255 = 0
• G = (0 + 0) × 255 = 0
• B = (1 + 0) × 255 = 255
Result: RGB(0, 0, 255) = Pure Blue
In the interactive map, the HSL system maps environmental indices to intuitive colors. For example: H=0° (red) for poor conditions, H=60° (yellow) for moderate, H=120° (green) for excellent. Saturation indicates data reliability, and lightness represents the intensity of the phenomenon.
Advantages: Intuitive mapping, smooth gradients, easy interpolation. Applications: Heatmaps, dashboards, scientific data visualization.
📊 Statistical Analysis: Pearson and Spearman Correlation
Correlation analysis measures the strength and direction of the linear relationship between two variables. It is essential for identifying patterns and dependencies in environmental data.
Pearson Correlation
Correlation Coefficient:
r = Σ(xᵢ - x̄)(yᵢ - ȳ) / √[Σ(xᵢ - x̄)² × Σ(yᵢ - ȳ)²]
Alternative Form:
r = (n×Σxᵢyᵢ - Σxᵢ×Σyᵢ) / √[(n×Σxᵢ² - (Σxᵢ)²)(n×Σyᵢ² - (Σyᵢ)²)]
Coefficient of Determination:
R² = r²
Interpretation:
• -1 ≤ r ≤ 1
• r > 0: positive correlation
• r < 0: negative correlation
• |r| close to 1: strong correlation
• |r| close to 0: weak correlation
r = Σ(xᵢ - x̄)(yᵢ - ȳ) / √[Σ(xᵢ - x̄)² × Σ(yᵢ - ȳ)²]
Alternative Form:
r = (n×Σxᵢyᵢ - Σxᵢ×Σyᵢ) / √[(n×Σxᵢ² - (Σxᵢ)²)(n×Σyᵢ² - (Σyᵢ)²)]
Coefficient of Determination:
R² = r²
Interpretation:
• -1 ≤ r ≤ 1
• r > 0: positive correlation
• r < 0: negative correlation
• |r| close to 1: strong correlation
• |r| close to 0: weak correlation
Spearman Correlation
Based on Rankings:
ρ = 1 - (6×Σdᵢ²) / (n×(n² - 1))
where dᵢ = difference between the ranks of xᵢ and yᵢ
When to use:
• Data does not follow a normal distribution
• Monotonic but not linear relationship
• Presence of outliers
• Ordinal data
ρ = 1 - (6×Σdᵢ²) / (n×(n² - 1))
where dᵢ = difference between the ranks of xᵢ and yᵢ
When to use:
• Data does not follow a normal distribution
• Monotonic but not linear relationship
• Presence of outliers
• Ordinal data
Example: Temperature vs Energy Consumption
Data:
Pearson Calculation:
• n = 5
• r = (5×37900 - 150×1180) / √[(5×4750 - 150²)(5×304200 - 1180²)]
• r = (189500 - 177000) / √[(23750 - 22500)(1521000 - 1392400)]
• r = 12500 / √[1250 × 128600] = 12500 / 12679 = 0.986
Interpretation: Very strong positive correlation (r = 0.986)
Data:
| Temp (°C) | Consumption (kWh) | x² | y² | xy | |
|---|---|---|---|---|---|
| 20 | 150 | 400 | 22500 | 3000 | |
| 25 | 180 | 625 | 32400 | 4500 | |
| 30 | 220 | 900 | 48400 | 6600 | |
| 35 | 280 | 1225 | 78400 | 9800 | |
| 40 | 350 | 1600 | 122500 | 14000 | |
| Σ | 150 | 1180 | 4750 | 304200 | 37900 |
• n = 5
• r = (5×37900 - 150×1180) / √[(5×4750 - 150²)(5×304200 - 1180²)]
• r = (189500 - 177000) / √[(23750 - 22500)(1521000 - 1392400)]
• r = 12500 / √[1250 × 128600] = 12500 / 12679 = 0.986
Interpretation: Very strong positive correlation (r = 0.986)
In the interactive map, correlation analysis identifies relationships between environmental variables. For example: correlation between temperature and air quality, humidity and cloud formation, or wind speed and pollutant dispersion. This allows for more accurate predictions and identification of climate patterns.
Significance Test: t = r×√(n-2)/√(1-r²) follows a t-distribution with (n-2) degrees of freedom. Warning: Correlation does not imply causation!
🤖 Machine Learning: K-Means Algorithm
K-Means is an unsupervised clustering algorithm that partitions data into k groups, minimizing intra-cluster variance. It is widely used for segmentation and exploratory data analysis.
Objective Function
Within-Cluster Sum of Squares (WCSS):
J = Σᵢ₌₁ᵏ Σₓ∈Cᵢ ||x - μᵢ||²
Cluster Centroid:
μᵢ = (1/|Cᵢ|) × Σₓ∈Cᵢ x
Euclidean Distance:
d(x,μ) = √(Σⱼ₌₁ᵈ (xⱼ - μⱼ)²)
Convergence Criterion:
||μᵢ⁽ᵗ⁺¹⁾ - μᵢ⁽ᵗ⁾|| < ε for all i
J = Σᵢ₌₁ᵏ Σₓ∈Cᵢ ||x - μᵢ||²
Cluster Centroid:
μᵢ = (1/|Cᵢ|) × Σₓ∈Cᵢ x
Euclidean Distance:
d(x,μ) = √(Σⱼ₌₁ᵈ (xⱼ - μⱼ)²)
Convergence Criterion:
||μᵢ⁽ᵗ⁺¹⁾ - μᵢ⁽ᵗ⁾|| < ε for all i
Lloyd's Algorithm:
- Choose k (number of clusters)
- Initialize k centroids randomly
- Repeat until convergence:
- Assign each point to the nearest centroid
- Recalculate centroids as the mean of assigned points
- Check stopping criterion
Example: 2D Clustering with k=2
Data: {(1,1), (2,1), (4,3), (5,4)}
Initialization:
• μ₁ = (1.5, 2.0)
• μ₂ = (4.0, 3.5)
Iteration 1 - Assignment:
• d((1,1), μ₁) = √((1-1.5)² + (1-2)²) = √1.25 = 1.12
• d((1,1), μ₂) = √((1-4)² + (1-3.5)²) = √15.25 = 3.90
• (1,1) → Cluster 1
• d((2,1), μ₁) = √((2-1.5)² + (1-2)²) = √1.25 = 1.12
• d((2,1), μ₂) = √((2-4)² + (1-3.5)²) = √10.25 = 3.20
• (2,1) → Cluster 1
Final Assignments:
• C₁ = {(1,1), (2,1)}
• C₂ = {(4,3), (5,4)}
New Centroids:
• μ₁ = ((1+2)/2, (1+1)/2) = (1.5, 1.0)
• μ₂ = ((4+5)/2, (3+4)/2) = (4.5, 3.5)
WCSS = 0.5 + 0.5 + 0.5 + 0.5 = 2.0
Data: {(1,1), (2,1), (4,3), (5,4)}
Initialization:
• μ₁ = (1.5, 2.0)
• μ₂ = (4.0, 3.5)
Iteration 1 - Assignment:
• d((1,1), μ₁) = √((1-1.5)² + (1-2)²) = √1.25 = 1.12
• d((1,1), μ₂) = √((1-4)² + (1-3.5)²) = √15.25 = 3.90
• (1,1) → Cluster 1
• d((2,1), μ₁) = √((2-1.5)² + (1-2)²) = √1.25 = 1.12
• d((2,1), μ₂) = √((2-4)² + (1-3.5)²) = √10.25 = 3.20
• (2,1) → Cluster 1
Final Assignments:
• C₁ = {(1,1), (2,1)}
• C₂ = {(4,3), (5,4)}
New Centroids:
• μ₁ = ((1+2)/2, (1+1)/2) = (1.5, 1.0)
• μ₂ = ((4+5)/2, (3+4)/2) = (4.5, 3.5)
WCSS = 0.5 + 0.5 + 0.5 + 0.5 = 2.0
In the interactive map, K-Means groups regions with similar environmental characteristics. For example: identifying climate zones, grouping weather stations by seasonal patterns, or segmenting urban areas by pollution levels. This allows for more efficient monitoring strategies and localized alerts.
Complexity: O(n×k×i×d) where n=points, k=clusters, i=iterations, d=dimensions. Limitations: Sensitive to initialization, assumes spherical clusters, requires predefined k.
🎯 Integration in the Interactive Map
All these technologies work together in the interactive map to create an intelligent environmental analysis system:
Processing Pipeline:
- Collection: Haversine to locate nearby stations
- Search: Levenshtein for query correction
- Analysis: Correlation to identify patterns
- Classification: Perceptron to categorize conditions
- Clustering: K-Means for regional segmentation
- Routing: Dijkstra for optimized paths
- Visualization: HSL for intuitive mapping
Integrated Use Example:
A user searches for "São Paulo" (typo) → Levenshtein corrects to "São Paulo" → Haversine finds nearby stations → Correlation analyzes relationships between variables → Perceptron classifies conditions → HSL maps to colors → Dijkstra suggests an eco-friendly route → K-Means identifies regional patterns.
A user searches for "São Paulo" (typo) → Levenshtein corrects to "São Paulo" → Haversine finds nearby stations → Correlation analyzes relationships between variables → Perceptron classifies conditions → HSL maps to colors → Dijkstra suggests an eco-friendly route → K-Means identifies regional patterns.