Codeless Data Structures and Algorithms. Learn DSA Without Writing a Single Line of Code. 📘🧠

Struggling with Data Structures & Algorithms due to coding complexity? This book explains core DSA concepts clearly and visually without coding.

👨‍💻 Author: Armstrong Subero
🏢 Publisher: Apress

📌 Credit Notice:

All rights belong to the author and publisher. This PDF is shared strictly for educational purposes. If you find this resource valuable, please support the author by purchasing the official copy.

📖 Happy learning & keep growing! 💡

✍️ @TheInfinityAI

Article 19: DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 🧬📡

DBSCAN කියන්නෙ දත්තවල ඝනත්වය (Density) පදනම් කරගෙන ක්‍රියා කරන algorithm එකක්. මේකේ විශේෂත්වය අපි විසින් කාණ්ඩ ගණන (K) ලබා දිය යුතු නොවීම සහ ඕනෑම සංකීර්ණ හැඩයකට විසිරිලා තියෙන දත්ත නිවැරදිව හඳුනා ගැනීමට මේකට තියෙන හැකියාවයි. 🏔✨

1. The Core Parameters 📏

● Epsilon (ε) - මේකෙන් කියන්නේ යම් data point එකක් වටේට අපි හොයන අරය (Radius) හෙවත් දුර ප්‍රමාණය.

● MinPts (Minimum Points) - යම් ප්‍රදේශයක් ඝනත්වයෙන් වැඩි (Dense) ලෙස සැලකීමට නම් ε අරය ඇතුළත තිබිය යුතු අවම data point ගණන.

2. Point Classification 📍

DBSCAN මගින් හැම data point එකක්ම ප්‍රධාන වර්ග 3කට බෙදනවා,

● Core Points - යම් data point එකක් වටේට ε දුර ඇතුළත MinPts ප්‍රමාණයට සමාන හෝ ඊට වැඩි data ප්‍රමාණයක් තියෙනවා නම් ඒක Core point එකක්.
● Border Points - මේවා වටේට MinPts ප්‍රමාණයක් නැ. නමුත් මේවා Core point එකක ε පරාසය ඇතුළත පිහිටලා තියෙනවා.
● Noise Points / Outliers - මේවා Core point සහ Border point කියන දෙකෙන් එකක්වත් නෙවේ. DBSCAN මගින් මේවා කාණ්ඩයකට ඇතුළත් නොකර Noise විදියට ඉවත් කරනවා.

3. Advanced Concepts: Connectivity & Reachability 🧬🧠

DBSCAN පිටිපස්සේ තියෙන ගණිතමය තර්කය තේරුම් ගන්න මෙ සංකල්ප දෙක අත්‍යවශ්‍යයි,

I. Directly Density-Reachable
ලක්ෂ්‍යයක් (P) තවත් ලක්ෂ්‍යයකින් (Q) Directly Density-Reachable වන්නේ නම්,
● P ලක්ෂ්‍යය Q ගේ ε-neighborhood එක ඇතුළත තිබිය යුතුයි.
● Q ලක්ෂ්‍යය අනිවාර්යයෙන්ම Core Point එකක් විය යුතුයි.

I. Density-Connected
ලක්ෂ්‍ය දෙකක් (A සහ B) අතර සෘජු සම්බන්ධයක් නැති වුනත් ඒ දෙකට තවත් පොදු Core point එකක (C) ඉදලා reach වෙන්න පුළුවන් නම් A සහ B කියන්නේ Density-Connected ලක්ෂ්‍ය. DBSCAN එකක් Cluster එකක් විදියට හඳුන ගන්නේ මේ විදිහට එකිනෙකට සම්බන්ධ වූ සියලුම ලක්ෂ්‍යයන්ගේ එකතුව.

4. How to find the Optimal Epsilon? (K-Distance Graph) 📈

DBSCAN වල ඇති අමාරුම වැඩේ තමයි නිවැරදි epsilon (ε) අගය තෝර ගන්න එක. මේකට අපි K-Distance Graph කියන ක්‍රමය පාවිච්චි කරනවා.

● අපි සෑම data point එකකටම ඒකේ ළඟම අසල්වැසියාට (k th neighbor) ඇති දුර ගණනය කරනවා.
● පස්සේ ඒ දුරවල් ආරෝහණ විදියට Graph එකක අඳිනවා.
● Graph එකේ curve එක තදින්ම ඉහළ යන ස්ථානය (Elbow Point) අපි හොඳම epsilon අගය ලෙස තෝරා ගන්නවා.

5. Advanced Engineering: Performance & Scalability 🏎🚀

● Computational Complexity - DBSCAN වල සාමාන්‍ය වේගය O(n log n). ඒත් data store කරද්දී KD-Tree, R-Tree වගේ spatial index පාවිච්චි කරේ නැත්තන් මේක O(n^2) දක්වා slow වෙන්න පුලුවන්.

● The Problem of Varying Densities - DBSCAN වල තියෙන ප්‍රධානතම දුර්වලතාවය වෙන්නේ Varying densities සහිත කාණ්ඩ හඳුනා ගැනීමට අපොහොසත් වීම. මේ ප්‍රශ්නය විසදන්න OPTICS (Ordering Points To Identify the Clustering Structure) වගේ තවත් දියුණු algorithms පාවිච්චි කරනවා.

6. Why is DBSCAN better than K-Means? 🤔🏆

K-Means වලට හඳුනගන්න පුලුවන් රවුම් (Globular) හැඩයේ කාණ්ඩ විතරයි. DBSCAN වලට ඕනෑම වක්‍ර, දිගැටි හෝ Nested හැඩයන් හඳුනගන්න පුලුවන්. ඒ වගේම K-Means හැම දත්තයක්ම මොකක් හරි කාණ්ඩයකට බලෙන් හරි ඇතුළත් කරනවා. ඒත් DBSCAN අසාමාන්‍ය දත්ත (Outliers) හඳුනගෙන ඒවා අයින් කරලා පිරිසිදු කාණ්ඩ විතරක් හදනවා. 🧼✨ (For more details)


DBSCAN කියන්නේ දත්තවල Density and Connectivity මත පදනම් වුන powerful algorithm එකක්. 💪 මේක Initial parameters (epsilon සහ MinPts) මත තදින් රදා පැවතුනත් සංකීර්ණ හැඩතල සහ Noise සහිත දත්ත හැසිරවීමේදී ගොඩක් useful. ඊලග ආටිකල් එකෙන් (Article 20) අපි කතා කරන්නේ PCA (Principal Component Analysis) ගැන. 🧠⏭️ 🙊😁

✍️ @TheInfinityAI

Article 20: PCA (Principal Component Analysis) – Let's extract the data 📉✨

PCA කියන්නේ Unsupervised Learning වල ඉතාමත් තීරණාත්මක කොටසක්. කලින් ආටිකල් වලින් අපි data clusters වලට බෙදන හැටි ඉගෙන ගත්තා. හැබැයි ප්‍රායෝගිකව අපිට ලැබෙන data වල Features සිය ගණනක් හෝ දහස් ගණනක් තියෙන්න පුළුවන්. මේ වගේ ලොකු data ප්‍රමාණයක් Process කරන එක මාරම අමාරු වැඩක් වගේම ඒවා Visualize කරන එකත් කළ නොහැක්කක්. මෙන්න මේ ප්‍රශ්නේ විසඳන්න තමයි Dimensionality Reduction පාවිච්චි කරන්නේ. PCA එහෙමත් නැත්තම් Principal Component Analysis කියන්නේ ඒකෙ alsorithm එකක්. තවත් පැහැදිලි කරොත් PCA කියන්නෙ දත්තවල තියෙන variance හැකිතාක් ආරක්ෂා කරගනිමින් ඒවගෙ තියෙන Features ගණන අඩු කරන Linear technology එකක්. ⚙️✂️

01. Foundation Level 🏛

හිතන්න ඔයා මල් පෝච්චියක පොටෝ එකක් ගන්නවා කියලා. මල් පෝච්චිය කියන්නේ 3D object එකක්. හැබැයි පොටෝ 2D තලයක්. ඔයා හොඳම Angle එකකින් ෆොටෝ එක ගත්තොත් ඒ 2D පින්තූරය බැලුවම වුණත් මල් පෝච්චියේ හැඩය ගැන හොඳ අවබෝධයක් ගන්න පුළුවන්. PCA එකෙන් කරන්නේ අන්න ඒ වගේ වැඩි මානයන් ගණනක තියෙන දත්ත වැදගත්ම තොරතුරු ටික විතරක් ඉතිරි කරගෙන අඩු මානයන් ගණනකට Project කරන එක.

02. The mathematics behind PCA 🧬🧮

PCA වැඩ කරන්නේ කොහොමද කියලා තේරුම් ගන්නනම් Linear Algebra වල තියෙන සංකීර්ණ සංකල්ප කිහිපයක් දැනගන්නම ඕනේ.

I. Standardization
PCA algorithm එක Variance එක මත පදනම් වෙන නිසා සෑම Feature එකකම Mean එක 0 සහ Standard Deviation එක 1 විදියට සකස් කරන්න ඕනි.

II. Covariance Matrix
Data වල තියෙන විවිධ Features එකිනෙකට සම්බන්ධ වෙන්නේ කොහොමද කියලා බලන්න තමා මේක පාවිච්චි කරන්නේ. n පරාසයක features වලට මේක n by n matrix එකක්.

Cov(X,Y) = ((∑(Xᵢ −X̄)(Yᵢ −Ȳ)) / (n − 1))
(සමීකරණේ පැහැදිලි නැත්නම් මෙතනින් බලන්න)

III. Eigenvectors සහ Eigenvalues
මේක තමයි PCA වල වැදගත්ම කොටස. Covariance matrix ැකෙන් අපි Eigenvectors සහ Eigenvalues ගණනය කරනවා.

● Eigenvectors - දත්ත විසිරිලා තියෙන ප්‍රධාන දිශාවන් (Principal Components) පෙන්වනවා.

● Eigenvalues - ඒ ඒ දිශාවලට දත්ත කොච්චර ප්‍රමාණයක් විසිරිලා තියෙනවද (Variance) කියලා පෙන්නන විශාලත්වය.

Av = λv

A = Matrix එක
v = Eigenvector
λ = Eigenvalue

03. The Process: SVD (Singular Value Decomposition) 🏎💨

නූතන ML Libraries (Scikit-learn වගේ) PCA ගණනය කරන්න ගොඩක් වෙලාවට පාවිච්චි කරන්නෙ SVD. මේක Covariance matrix එකක් හදනවට වඩා ගණිතමය වශයෙන් Stable ක්‍රමයක්. මේකෙදි ඕනම M by N matrix එකක් matrices 3ක ගුණිතයක් විදියට දක්වනවා.

A = UΣVᵀ

04. Explained Variance Ratio 📊📈

PCA වලින් පස්සේ අපි බලන්න ඕනේ මුල් දත්තවල තිබුණු තොරතුරු එහෙමත් නැත්නම් Variance වලින් කොච්චර ප්‍රමාණයක් අලුත් Principal Components වල තියෙනවද කියලා. උදාහරණයක් විදිහට පළමු Principal Components දෙකෙන් (PC1 & PC2) මුළු දත්තවලින් 95% ක තොරතුරු පෙන්වනවා නම් අපිට පුළුවන් ඉතිරි 5% අතහැරලා මානයන් ගණන 2කට අඩු කරන්න. 📉 ✅

05. Limitations of PCA 🚧🛑

● Linear Assumption - PCA උපකල්පනය කරන්නේ data අතර තියෙන්නේ linear සම්බන්ධතාවයක් කියලා. Data Non-linear විදියට තියෙනවනම් PCA සාර්ථක වෙන්නෙ නෑ.
● Interpretability - PCA වලින් පස්සේ ලැබෙන අලුත් Features (PC1, PC2) මොනවද කියලා පැහැදිලි කරන්න අමාරුයි (ඒවා මුල් Features වල මිශ්‍රණයක්).

සාරංශයක් විදියට PCA කියන්නේ විශාල දත්ත ගොනුවක තියෙන අනවශ්‍ය දත්ත (Redundancy data) ඉවත් කරලා වැදගත්ම තොරතුරු (Maximum Variance) සහිත නව අක්ෂයන් (Principal Components) සොයා ගන්න mathematical process එකක්. මේක Eigen-decomposition හෝ SVD හරහා සිදු කරන අතර මොඩල් එකක් වේගවත් කරන්න සහ data visualize කරන්න මේක අත්‍යවශ්‍ය මෙවලමක්. ඊලග ආටිකල් එකෙන් (Article 21) අපි කතා කරන්නේ Non-linear දත්ත සඳහා පාවිච්චි කරන t-SNE සහ UMAP ගැන. ✅✨ 🙊😁

✍️ @TheInfinityAI

Article 21: Non-linear Dimensionality Reduction – Mathematical Analysis of t-SNE and UMAP 🌀📉

අපි කලින් ඉගන ගත්ත PCA වලින් දත්ත වල Linear සම්බන්ධතා හඳුනාගත්තත් දත්ත ඉතාමත් සංකීර්ණ වක්‍ර (Manifolds) විදියට විසිරිලා තියෙනකොට PCA අසාර්ථක වෙනවා. එතකොට අපි පාවිච්චි කරන්නේ දත්තවල Local Structure එක ආරක්ෂා කරන ඊට වඩා උසස් algorithms.

01. t-SNE (t-Distributed Stochastic Neighbor Embedding) 🧩

t-SNE කියන්නේ data points අතර තියෙන Probabilities මත පදනම් වෙලා ක්‍රියා කරන algorithm එකක්.

I. High-Dimensional Similarity (Gaussian Kernel)
ඉහළ මානවලදි, ලක්ෂ්‍ය xⱼ ලක්ෂ්‍ය xᵢ වල අසල්වැසියෙකු වීමේ සම්භාවිතාව (p₍ⱼ∣ᵢ₎) ගණනය කරන්නේ Gaussian Distribution එකකින්.

p₍ⱼ∣ᵢ₎ = ((exp(− ∥xᵢ − xⱼ∥²/2σᵢ²)) / (∑₍ₖ≠ᵢ₎exp(− ∥xᵢ − xₖ∥²/2σᵢ²)))

II. Low-Dimensional Similarity (Student's t-Distribution)
පහළ මානයේදී (2D), අපි Gaussian වෙනුවට Student's t-distribution (with 1 degree of freedom) පාවිච්චි කරනවා. මේකට හේතුව තමා Crowding Problem (ඉහළ මානයේ සිට පහළට එද්දී දත්ත ලක්ෂ්‍ය එකම තැනක ගොඩ ගැසීම) වළක්වා ගැනීමට t-distribution එකේ ඇති Heavy Tail එක උදව් වීම.

qᵢⱼ = (((1 + ∥yᵢ − yⱼ∥²)⁻¹) / (∑₍ₖ≠ₗ₎(1 + ∥yₖ − yₗ∥²)⁻¹))

III. The Cost Function: Kullback-Leibler (KL) Divergence
t-SNE වල ඉලක්කය වෙන්නෙ P ව්‍යාප්තිය සහ Q ව්‍යාප්තිය අතර ඇති වෙනස අවම කරන එක. මෙහිදී Gradient Descent පාවිච්චි කරන්නේ මේ KL Divergence එක අඩු කරන්න.

C = KL(P∣∣Q) = ∑ᵢ∑ⱼpᵢⱼlog ((pᵢⱼ) / (qᵢⱼ))

02. UMAP (Uniform Manifold Approximation and Projection) 🕸

UMAP කියන්නේ t-SNE වලට වඩා වේගවත් වගේම දත්තවල Global Structure එක වඩා හොඳින් ආරක්ෂා කරන අලුත් තාක්ෂණයක්. මේකේ පදනම වැටෙන්නේ Riemannian Geometry සහ Algebraic Topology මත.

I. Topological Structure Construction
UMAP වලින් දත්ත විසිරිලා තියෙන ආකාරය ඇසුරෙන් Fuzzy Simplicial Complex එකක් නිර්මාණය කරනවා. මේකෙදි එක් එක් ලක්ෂ්‍යය වටා ඇති ප්‍රදේශය (Neighborhood) Locally Uniform බව උපකල්පනය කරනවා.

II. Optimization (Cross Entropy)
t-SNE වලදී KL Divergence පාවිච්චි කරද්දි UMAP විසින් Binary Cross Entropy පාවිච්චි කරමින් ඉහළ මානයේ සහ පහළ මානයේ තියෙන ජ්‍යාමිතික ව්‍යුහයන් අතර සම්බන්ධතාවය ප්‍රශස්ත කරනව.

∑₍ₑ∈E₎wₕ(e)log (((wₕ(e)) / (wₗ(e))))+ (1 − wₕ(e))log (((1 − wₕ(e)) / (1 − wₗ(e))))

මේකේ wₕ සහ wₗ කියන්නේ ඉහළ සහ පහළ මානයන්හි ඇති edge weights.

03. Advanced Implementation Details 🚀

t-SNE සාමාන්‍යයෙන් අහඹු ලෙස (Random) ආරම්භ කරන හින්දා UMAP වලින් Graph Laplacian හරි PCA පාවිච්චි කර වඩා හොඳ ආරම්භයක් ලබා ගන්නවා. t-SNE හි වේගය O(N^2) හෝ O(N log N) (Barnes-Hut) වෙද්දී UMAP හි වේගය O(N^{1.14}) වගේ ඉතා අඩු අගයක්. ඒ හින්දා විශාල දත්ත ගොනු වලට UMAP අතිශය සාර්ථකයි. 🎓✅

අපි අද කතා කලේ Dimensionality Reduction වල තවත් කොටසක්. ඊලග ආටිකල් එකෙන් (Article 22) Gaussian Mixture Models (GMM) සහ EM Algorithm ගැන කතා කරමු. 🧠⏭️ 🙊😁

✍️ @TheInfinityAI