সমাধান — অধ্যায় ৫.৯ · Multivariate Methods: PCA & Clustering¶
অধ্যায়
part-5-modeling/05-09-multivariate-methods-pca-clustering.md-এর section ৭-এর সব অনুশীলনীর পূর্ণ সমাধান। চলমান dataset — seednp.random.default_rng(20260619), \(n=300\), \(p=4\): \(3\)টি cluster (প্রতিটিতে \(100\) বিন্দু), অন্তর্নিহিতভাবে \(2\)-মাত্রিক structure \(4\)টি correlated feature-এ এম্বেড করা; প্রতিটি column standardize-করা (mean \(0\), sd \(1\))। প্রতিটি সংখ্যাগত ফলnumpy/scikit-learnদিয়ে যাচাই করা হয়েছে — §ঘ-এর runnable script এ-ই data-generation-ক্রমে নিচের canonical সংখ্যা পুনরুৎপাদন করে। canonical সংখ্যা — PCA: eigenvalue \([2.614,\ 1.375,\ 0.017,\ 0.008]\); explained-variance-ratio \([0.651,\ 0.343,\ 0.0042,\ 0.0019]\); cumulative \([0.651,\ 0.994,\ 0.9982,\ 1.0]\); PC1+PC2 \(=99.4\%\)। k-means inertia: \(k{=}1\to1200\), \(k{=}2\to527\), \(k{=}3\to135\), \(k{=}4\to111\), \(k{=}5\to91\), \(k{=}6\to72\) (elbow \(k{=}3\))। silhouette: \(k{=}2\to0.552\), \(k{=}3\to0.712\) (সর্বোচ্চ), \(k{=}4\to0.598\)। চূড়ান্ত \(k{=}3\): inertia \(135.3\), silhouette \(0.712\), ARI \(0.990\)। মূল সূত্র: covariance \(\Sigma=\frac1n X^\top X\) (standardized \(X\)); eigenpair \(\Sigma v_j=\lambda_j v_j\); explained-variance-ratio \(\lambda_j/\sum_l\lambda_l\); PC score \(z=Xv\); reconstruction \(\hat X=ZV_2^\top\); inertia \(W=\sum_k\sum_{i\in C_k}\lVert x_i-\mu_k\rVert^2\); silhouette \(s_i=\frac{b_i-a_i}{\max(a_i,b_i)}\)।
ক · ধারণাগত (conceptual)¶
৭.১ ★ — কেন PCA-র আগে standardize করতে হয়¶
(ক) raw data-তে PC1 কার্যত "আয়" feature-কেই অনুসরণ করবে। কারণ PCA variance-সর্বোচ্চকারী দিক খোঁজে, আর "আয়"-এর variance (\(\sim10^{10}\)) "বয়স"-এর (\(\sim10^2\)) চেয়ে \(\sim10^8\) গুণ বড় — তাই মোট variance প্রায় পুরোটাই "আয়"-অক্ষে, PC1 সেদিকেই সারিবদ্ধ হবে। এটা বিভ্রান্তিকর কারণ এই আধিপত্য শুধু মাপের এককের কৃত্রিম ফল, প্রকৃত গুরুত্বের নয়: একক টাকা→হাজার-টাকা বদলালে "আয়"-এর variance \(10^6\)-গুণ কমে যেত এবং PC1 সম্পূর্ণ ভিন্ন দিকে চলে যেত। অর্থপূর্ণ PCA এমন একক-নির্ভরতা থেকে মুক্ত হওয়া উচিত।
(খ) standardize (প্রতিটি column \(\to\) mean \(0\), sd \(1\)) করলে সব feature-এর variance ঠিক \(1\) হয়ে যায়, তাই কেউ কাউকে শুধু-একক-বড় বলে ছাপিয়ে যেতে পারে না। তখন covariance matrix-এর প্রতিটি diagonal \(=1\) এবং off-diagonal \(=\) correlation — অর্থাৎ PCA তখন কার্যত correlation matrix-এর eigen-গঠন বের করে: সম্পূর্ণ scale-মুক্ত, একক-পরিবর্তনে অপরিবর্তিত।
(গ) standardized হলে প্রতিটি column-variance \(1\), তাই মোট variance \(=\operatorname{tr}(\Sigma)=p=4\)। eigenvalue-যোগফল trace-এর সমান হওয়া উচিত (trace eigenvalue-invariant): $\(\sum_j\lambda_j=2.614+1.375+0.017+0.008=4.014\approx4=\operatorname{tr}(\Sigma).\ ✓\)$ (সামান্য \(0.014\) গোল-করার ত্রুটি; নিচের ratio-গণনায় \(4.014\) ব্যবহৃত।)
৭.২ ★ — eigenvalue \(=\) variance, explained-variance-ratio¶
(ক) \(j\)-তম PC-বরাবর projected data-র variance ঠিক \(\lambda_j\) (§৭.১৪-এ প্রমাণিত: \(v_j^\top\Sigma v_j=\lambda_j\))। বড় variance মানে data সেই দিকে বেশি "ছড়ানো" — অর্থাৎ সেই অক্ষে বিন্দুদের পার্থক্য সবচেয়ে বেশি তথ্য বহন করে। তাই বড় eigenvalue \(=\) বেশি-তথ্যবহ, প্রধান দিক; ছোট eigenvalue-এর দিক প্রায়-ধ্রুবক (সামান্য variance), প্রায় শুধু noise।
(খ) \(\sum_l\lambda_l=4.014\); explained-variance-ratio \(\lambda_j/\sum_l\lambda_l\): $\(\frac{2.614}{4.014}=0.651,\quad \frac{1.375}{4.014}=0.343,\quad \frac{0.017}{4.014}=0.0042,\quad \frac{0.008}{4.014}=0.0019.\)$ canonical \([0.651,\ 0.343,\ 0.0042,\ 0.0019]\) ✓ (যোগফল \(=1\) ✓)।
(গ) PC1+PC2 \(=0.651+0.343=0.994=\boxed{99.4\%}\)। অর্থাৎ মোট variance-এর প্রায় সবটুকুই প্রথম দুই PC-তে; বাকি দুই PC মিলে মাত্র \(0.6\%\)। তাই data যদিও \(4\)টি feature-এ লেখা, তার অন্তর্নিহিত মাত্রা কার্যত \(2\) — exactly যেমন data-টা তৈরি হয়েছিল (\(2\)-D structure \(4\)-D-এ এম্বেড করা)। PCA এই লুকানো ২-মাত্রিকতা স্বয়ংক্রিয়ভাবে আবিষ্কার করেছে।
৭.৩ ★★ — scree plot ও কতগুলো component¶
(ক) scree plot-এ elbow হলো সেই বিন্দু যেখানে eigenvalue-curve হঠাৎ খাড়া-পতন থেকে প্রায়-সমতলে বাঁক নেয় — যেন একটা হাতের কনুই। এখানে ratio \([0.651,0.343,0.0042,0.0019]\): PC1→PC2 মাঝারি পতন, কিন্তু PC2→PC3-এ বিশাল পতন (\(0.343\to0.0042\), প্রায় \(80\)-গুণ কমে), তারপর প্রায় সমতল। তাই elbow PC2-র পরে ⇒ প্রথম \(2\)টি PC রাখা উচিত (বাকিগুলো সমতল "scree/পাথুরে-ঢাল")।
(খ) cumulative \([0.651,\ 0.994,\ 0.9982,\ 1.0]\)। "cumulative ৯০% (বা ৯৫%)" নিয়ম: PC2-তেই cumulative \(0.994\ge0.95\ge0.90\)। তাই উভয় threshold-এ \(2\)টি PC যথেষ্ট।
(গ) এখানে structure পরিষ্কার ২-মাত্রিক — PC2 ও PC3-এর মধ্যে বিশাল gap, তাই (i) elbow সুস্পষ্টভাবে PC2-র পরে এবং (ii) cumulative PC2-তেই \(99\%\) ছাড়ায়; দুই নিয়ম একই \(2\) বলে। দুটো ভিন্ন উত্তর দিত যদি eigenvalue-গুলো ধীরে-ধীরে ক্ষীণ হত (যেমন \([0.4,0.25,0.18,0.12,0.05]\) — তীক্ষ্ণ gap নেই): তখন elbow অস্পষ্ট/বিষয়ভিত্তিক হত, আর ৯৫%-cumulative-নিয়ম হয়তো \(4\)টি PC চাইত — মানদণ্ড-নির্ভর ভিন্ন সিদ্ধান্ত।
৭.৪ ★★ — PCA projection ও reconstruction¶
(ক) projection score \(z_{i1}=x_i^\top v_1\) হলো বিন্দু \(x_i\)-কে PC1-অক্ষের উপর উৎক্ষেপ (লম্ব প্রক্ষেপণ) করলে যে coordinate পাওয়া যায় — অর্থাৎ সেই প্রধান-variance দিক বরাবর \(x_i\) কেন্দ্র থেকে কতদূর ও কোন দিকে। \(Z=XV_2\) প্রতিটি বিন্দুকে \(4\) সংখ্যা থেকে \(2\) সংখ্যায় (\(z_{i1},z_{i2}\)) নামায় — সবচেয়ে তথ্যবহ ২ অক্ষে নতুন স্থানাঙ্ক।
(খ) \(\hat X=ZV_2^\top\) আবার \(p=4\)-মাত্রায় ফেরে, কিন্তু সমান নয় কারণ বাদ-দেওয়া PC-দিক (\(v_3,v_4\))-বরাবর component পুরোপুরি হারায় (ওই দিকগুলো \(V_2\)-তে নেই)। হারানো অংশের পরিমাণ — reconstruction-error (গড় Frobenius-বর্গ) ঠিক বাদ-দেওয়া eigenvalue-গুলোর যোগফল: $\(\frac1n\lVert X-\hat X\rVert_F^2=\sum_{j>2}\lambda_j=\lambda_3+\lambda_4=0.017+0.008=0.025.\)$ (এটি PCA-র এক মৌলিক ফল: top-\(k\) PC-তে reconstruction-error \(=\sum_{j>k}\lambda_j\), এবং top-\(k\) projection সব rank-\(k\) approximation-এর মধ্যে এই error সর্বনিম্ন করে — Eckart–Young।)
(গ) রক্ষা পাওয়া variance-ভগ্নাংশ \(=\frac{\lambda_1+\lambda_2}{\sum_l\lambda_l}=0.994=99.4\%\); হারানো \(=\frac{0.025}{4.014}=0.6\%\)। তাই top-\(2\) PC-তে নামানো এই data-র জন্য প্রায় lossless — মাত্রা অর্ধেক করেও \(99.4\%\) তথ্য থাকে।
৭.৫ ★★ — k-means objective ও Lloyd-এর ধাপ¶
(ক) Lloyd দুই ধাপ পালাক্রমে চালায়: - assignment: centroid \(\{\mu_k\}\) স্থির রেখে প্রতিটি বিন্দু \(x_i\)-কে তার নিকটতম centroid-এর cluster-এ বসানো (\(C(i)=\arg\min_k\lVert x_i-\mu_k\rVert^2\))। - update: assignment স্থির রেখে প্রতিটি cluster-এর centroid নতুন করে \(=\) তার বর্তমান বিন্দুদের mean (গড়) (\(\mu_k=\frac1{\lvert C_k\rvert}\sum_{i\in C_k}x_i\))।
(খ) দুই ধাপই \(W\) কমায়-বা-সমান: - assignment-ধাপ: প্রতিটি বিন্দু এখন নিকটতম centroid বাছে, তাই তার অবদান \(\lVert x_i-\mu_{C(i)}\rVert^2\) আগের assignment-এর চেয়ে ছোট-বা-সমান — সব বিন্দুর যোগফল \(W\) তাই কমে বা সমান থাকে (centroid অপরিবর্তিত)। - update-ধাপ: স্থির cluster-এর জন্য গড়-ই \(\sum_{i\in C_k}\lVert x_i-c\rVert^2\)-এর একমাত্র minimizer (§৭.১৫-এ প্রমাণিত), তাই centroid-কে গড়-এ সরালে প্রতিটি cluster-এর within-SS কমে বা সমান ⇒ \(W\) কমে বা সমান (assignment অপরিবর্তিত)।
যেহেতু \(W\ge0\) এবং প্রতিটি ধাপে monotone ↓, আর সম্ভাব্য assignment সসীম, algorithm অবশ্যই সসীম ধাপে অভিসৃত (স্থির) হয়।
(গ) তবু global minimum-এর নিশ্চয়তা নেই কারণ objective \(W\) non-convex (assignment discrete/combinatorial)। Lloyd প্রতি ধাপে শুধু নিচে নামে, তাই যে "উপত্যকায়" (basin) শুরু করে সেই স্থানীয় minimum-এই থামে — কোনটিতে থামবে তা প্রারম্ভিক centroid-এর উপর নির্ভর করে (প্রশ্ন ৬)।
৭.৬ ★★ — কেন \(k\) আগে দিতে হয় ও multiple restart (local minima)¶
(ক) k-means-কে \(K\) আগে দিতে হয় — algorithm নিজে "কয়টা cluster" বের করে না, শুধু দেওয়া \(K\)-তে বিন্দু ভাগ করে। এটি PCA-র তুলনায় দুর্বলতা: PCA-তে eigenvalue-spectrum নিজেই কার্যকর মাত্রা ইঙ্গিত করে (বড় eigenvalue কয়টা দেখে), কিন্তু k-means-এ সঠিক \(K\) data থেকে স্বয়ংক্রিয় আসে না। তাই \(K\) বাছতে বাইরের মানদণ্ড লাগে — elbow (inertia-পতন) ও silhouette (প্রশ্ন ১১) — supervised-এর CV-র মতো সরাসরি "honest error" নেই বলে এই পরোক্ষ মানদণ্ড।
(খ) একই \(K\)-তে দুই ভিন্ন initialization ভিন্ন inertia-তে অভিসৃত হতে পারে কারণ \(W\) non-convex, বহু local minimum আছে; Lloyd যে basin-এ পড়ে সেখানেই নামতে নামতে থামে। তাই ভিন্ন প্রারম্ভিক centroid ⇒ ভিন্ন basin ⇒ ভিন্ন স্থানীয় ফল (কখনো খারাপ — যেমন দুটি প্রকৃত cluster একসাথে, একটি ভেঙে দুই)।
(গ) তাই বাস্তবে k-means \(n_{\text{init}}\) বার (ভিন্ন random init-এ) চালিয়ে সবচেয়ে কম inertia-ওয়ালা ফলটা রাখা হয় — বিভিন্ন basin চেষ্টা করে সেরাটা বাছায় খারাপ local-min এড়ানো যায়। k-means++ init আরও সাহায্য করে: প্রথম centroid এলোমেলো, পরেরগুলো বিদ্যমান centroid থেকে দূরত্ব-সমানুপাতিক সম্ভাবনায় বাছা হয় — ফলে প্রারম্ভিক centroid-গুলো ছড়িয়ে বসে (প্রকৃত cluster-গুলোর কাছাকাছি পড়ার সম্ভাবনা বাড়ে), তাই কম restart-এই ভালো ও স্থিতিশীল ফল।
৭.৭ ★★ — within-SS বনাম between-SS¶
(ক) মৌলিক পরিচয়: \(\text{TSS}=\text{WSS}+\text{BSS}\), যেখানে \(\text{TSS}=\sum_i\lVert x_i-\bar x\rVert^2\) সব-বিন্দুর grand-mean থেকে মোট spread — যা assignment/\(K\)-নিরপেক্ষ ধ্রুবক (শুধু data-নির্ভর)। তাই \(\text{WSS}=\text{TSS}-\text{BSS}\); WSS কমানো মানে BSS ঠিক ততটাই বাড়ানো — একই অপ্টিমাইজেশনের দুই রূপ। (k-means তাই একই সাথে cluster-গুলোকে ভেতরে আঁটসাঁট ও পরস্পর-দূরে ঠেলে।)
(খ) \(\text{TSS}=1200\) (\(k{=}1\)-এর inertia, কারণ তখন একটাই cluster, \(\mu_1=\bar x\), তাই WSS \(=\) সব-বিন্দুর grand-mean থেকে SS \(=\) TSS)। \(k{=}3\)-এ WSS \(=135.3\): $\(\text{BSS}=\text{TSS}-\text{WSS}=1200-135.3=\boxed{1064.7}.\)$ ব্যাখ্যাকৃত ভগ্নাংশ \(=\frac{\text{BSS}}{\text{TSS}}=\frac{1064.7}{1200}=0.887\) — অর্থাৎ মোট spread-এর প্রায় ৮৮.৭% cluster-মধ্যকার পার্থক্য (between) ব্যাখ্যা করে, মাত্র \(11.3\%\) cluster-অভ্যন্তরীণ। শক্তিশালী cluster-গঠনের ইঙ্গিত।
(গ) এই ভগ্নাংশ (ANOVA-র \(R^2\)-সদৃশ) \(K\) বাড়ালে সবসময় বাড়ে, কারণ আরও cluster দিলে প্রতিটি বিন্দু কোনো-না-কোনো centroid-এর আরও কাছে বসতে পারে ⇒ WSS একঘেয়ে কমে (চরমে \(K=n\) হলে প্রতি বিন্দু নিজেই centroid, WSS \(=0\), ভগ্নাংশ \(=1\))। তাই এটা train-error-সদৃশ: একঘেয়ে উন্নত হওয়ায় কোনো "সর্বোত্তম" \(K\) চিহ্নিত করে না — সর্বোচ্চ ভগ্নাংশ সবসময় \(K=n\)-এ, যা অর্থহীন। তাই সরাসরি এই মানদণ্ডে \(K\) বাছা যায় না; elbow (পতনের হার) বা silhouette (পৃথকীকরণের গুণ) লাগে।
৭.৮ ★★ — hierarchical clustering ও dendrogram¶
(ক) k-means-এর তুলনায় agglomerative hierarchical-এর দুই সুবিধা: 1. \(K\) আগে দিতে হয় না — একবার চালিয়ে পুরো merge-গাছ (dendrogram) পাওয়া যায়, পরে যেকোনো \(K\)-তে কাটা যায় (এমনকি একাধিক \(K\) পরখ করা যায়, পুনঃ-চালনা ছাড়া)। 2. ফল একটা nested শ্রেণিবিন্যাস (cluster-এর ভেতর sub-cluster) — শুধু একটা flat partition নয়; তাই বিভিন্ন granularity-তে গঠন দেখা যায়, এবং deterministic (random init নেই)।
(খ) dendrogram থেকে \(K\)টি cluster পেতে গাছটিকে একটা নির্দিষ্ট উচ্চতায় আনুভূমিক রেখা টেনে কাটতে হয়; সেই রেখা যত উল্লম্ব শাখা ছেদ করে, ততগুলো cluster পাওয়া যায় (উঁচুতে কাটলে কম cluster, নিচে কাটলে বেশি)। কাটার উচ্চতা \(=\) যে দূরত্বে দুই cluster merge হয়েছিল — বড় উচ্চতায় merge মানে যে দুই cluster মিশছে তারা বেশি ভিন্ন (দূরে); তাই বড় উল্লম্ব লাফের ঠিক নিচে কাটা ভালো (সুসংহত cluster আলাদা থাকে)।
(গ) linkage ঠিক করে "দুই cluster-এর দূরত্ব" কীভাবে মাপা — single (নিকটতম জোড়া), complete (দূরতম জোড়া), average (গড় জোড়া-দূরত্ব), Ward (merge করলে within-cluster SS কত বাড়ে)। Ward k-means-এর ঘনিষ্ঠ কারণ এটি প্রতি merge-এ within-cluster sum-of-squares-এর বৃদ্ধি সর্বনিম্ন করে — k-means-ও ঠিক একই within-SS (inertia) minimize করে। তাই দুটোই variance/inertia-ভিত্তিক objective অনুসরণ করে এবং গোলাকার, প্রায়-সমান-আকার cluster-এ প্রায়ই একই বিন্যাসে পৌঁছায়।
খ · গণনামূলক (computational)¶
৭.৯ ★ — explained-variance-ratio ও cumulative¶
(ক) \(\sum_l\lambda_l=2.614+1.375+0.017+0.008=4.014\); ratio: $\(\frac{2.614}{4.014}=0.651,\ \ \frac{1.375}{4.014}=0.343,\ \ \frac{0.017}{4.014}=0.0042,\ \ \frac{0.008}{4.014}=0.0019.\)$ canonical \([0.651,0.343,0.0042,0.0019]\) ✓।
(খ) cumulative (চলমান যোগফল): $\(0.651,\quad 0.651+0.343=0.994,\quad 0.994+0.0042=0.9982,\quad 0.9982+0.0019=1.0.\)$ canonical \([0.651,\ 0.994,\ 0.9982,\ 1.0]\) ✓।
(গ) "অন্তত ৯৫%": cumulative প্রথম যেখানে \(\ge0.95\) — তা PC2-তেই (\(0.994\))। তাই ন্যূনতম \(\boxed{2}\)টি PC যথেষ্ট (PC1 একা \(0.651<0.95\), তাই \(1\) যথেষ্ট নয়)।
৭.১০ ★ — PC score হাতে গুনে (projection)¶
\(x=(1.2,-0.8,0.5,-0.3)^\top\), \(v_1=(0.5,0.5,0.5,0.5)^\top\), \(v_2=(0.5,-0.5,0.5,-0.5)^\top\)।
(ক) \(z_1=x^\top v_1=0.5(1.2)+0.5(-0.8)+0.5(0.5)+0.5(-0.3)=0.5(1.2-0.8+0.5-0.3)=0.5(0.6)=\boxed{0.30}\)।
(খ) \(z_2=x^\top v_2=0.5(1.2)+(-0.5)(-0.8)+0.5(0.5)+(-0.5)(-0.3)=0.6+0.4+0.25+0.15=\boxed{1.40}\)।
(গ) orthonormality: $\(v_1^\top v_1=4\times0.25=1,\qquad v_2^\top v_2=4\times0.25=1,\)$ $\(v_1^\top v_2=(0.5)(0.5)+(0.5)(-0.5)+(0.5)(0.5)+(0.5)(-0.5)=0.25-0.25+0.25-0.25=0.\)$ তাই \(v_1,v_2\) orthonormal ✓। PCA-র জন্য জরুরি কারণ: orthonormal eigenvector হলে (i) PC-অক্ষগুলো পরস্পর-লম্ব ⇒ PC-score পরস্পর uncorrelated (অপ্রয়োজনীয় পুনরাবৃত্তি নেই); (ii) length-রক্ষাকারী রূপান্তর ⇒ variance সরল-ভাবে যোগ্য (\(\sum\lambda_j=\) মোট variance) এবং reconstruction \(\hat X=ZV^\top\) পরিষ্কার, projection-error \(=\sum_{j>k}\lambda_j\)।
৭.১১ ★★ — elbow বনাম silhouette দিয়ে \(k\) বাছা¶
দেওয়া টেবিল: inertia \([1200,527,135,111,91,72]\) (\(k{=}1..6\)); silhouette \(k{=}2\to0.552\), \(k{=}3\to0.712\), \(k{=}4\to0.598\)।
(ক) ধারাবাহিক পতন \(\Delta_k=W_{k-1}-W_k\):
| পতন | মান |
|---|---|
| \(k{=}1\to2\) | \(1200-527=673\) |
| \(k{=}2\to3\) | \(527-135=392\) |
| \(k{=}3\to4\) | \(135-111=24\) |
| \(k{=}4\to5\) | \(111-91=20\) |
| \(k{=}5\to6\) | \(91-72=19\) |
\(k{=}3\)-এর পরে পতন নাটকীয়ভাবে ছোট হয়ে যায় (\(392\to24\), প্রায় \(16\)-গুণ কম) এবং তারপর প্রায় সমতল (\(24,20,19\))। তাই "কনুই" \(k{=}3\)-এ — elbow \(\boxed{k{=}3}\)।
(খ) silhouette: \(0.552\ (k{=}2)<0.712\ (k{=}3)>0.598\ (k{=}4)\) — সর্বোচ্চ \(k{=}3\)-এ। তাই silhouette বাছে \(\boxed{k{=}3}\)।
(গ) দুই পদ্ধতি একই (\(k{=}3\)) — শক্তিশালী সমর্থন। সাধারণভাবে silhouette বেশি নির্ভরযোগ্য: elbow চোখে-দেখা ও বিষয়ভিত্তিক ("কনুই কোথায়" তর্কসাপেক্ষ যখন পতন মসৃণ, পরিষ্কার elbow নেই), আর inertia একঘেয়ে কমে বলে কোনো সরাসরি optimum দেয় না। silhouette একটা সংখ্যাগত স্কোর (\([-1,1]\)-এ, যত বড় তত ভালো পৃথকীকরণ) — সর্বোচ্চটাই বাছা যায়, ব্যাখ্যাও স্পষ্ট; তাই elbow-এর পরিপূরক/নিশ্চায়ক হিসেবে বেশি ব্যবহৃত।
৭.১২ ★★ — silhouette হাতে গুনে¶
\(s_i=\frac{b_i-a_i}{\max(a_i,b_i)}\)।
(ক) - (i) \(a=0.5,b=2.0\): \(s=\frac{2.0-0.5}{\max(0.5,2.0)}=\frac{1.5}{2.0}=\boxed{0.75}\)। - (ii) \(a=1.5,b=1.8\): \(s=\frac{1.8-1.5}{1.8}=\frac{0.3}{1.8}=\boxed{0.167}\)। - (iii) \(a=2.0,b=1.0\): \(s=\frac{1.0-2.0}{\max(2.0,1.0)}=\frac{-1.0}{2.0}=\boxed{-0.5}\)।
(খ) - (i) \(s\approx0.75\) (\(\to1\)-এর কাছে): বিন্দুটি নিজের cluster-এর খুব কাছে, প্রতিবেশী cluster থেকে অনেক দূরে — ভালো-বসানো, আত্মবিশ্বাসী membership। - (ii) \(s\approx0.17\) (\(\to0\)-এর কাছে): \(a\approx b\), দুই cluster থেকে প্রায় সমদূরত্বে — সীমান্ত-বিন্দু, কোন cluster-এ তা অস্পষ্ট। - (iii) \(s=-0.5<0\): \(b<a\), অর্থাৎ প্রতিবেশী cluster-এর বিন্দুদের নিজের cluster-এর চেয়ে কাছে — সম্ভবত ভুল cluster-এ assign হয়েছে।
(গ) \(k{=}3\)-এ গড় silhouette \(0.712\) — \([-1,1]\) স্কেলে \(0.7\)-এর উপরে মান শক্তিশালী, সু-পৃথক cluster-গঠন নির্দেশ করে: গড়ে বিন্দুরা নিজের cluster-এর কেন্দ্রের অনেক কাছে এবং নিকটতম-অন্য cluster থেকে যথেষ্ট দূরে। অর্থাৎ cluster-গুলো আঁটসাঁট ও পরস্পর ভালোভাবে আলাদা — data-র প্রকৃত \(3\)-গোষ্ঠী গঠনের সাথে সঙ্গতিপূর্ণ।
৭.১৩ ★★ — ARI দিয়ে cluster-পুনরুদ্ধার¶
(ক) ARI মাপে দুটো cluster-বিন্যাস (এখানে: k-means-প্রাপ্ত বনাম সত্য label) কতটা মেলে — সব বিন্দু-জোড়া বিবেচনা করে: কোন জোড়া উভয় বিন্যাসে একই cluster-এ একসাথে, কোনটা উভয়ে আলাদা (এই দুই \(=\) "সম্মতি"), আর কোনটা একটায় একসাথে-অন্যটায় আলাদা ("অসম্মতি")। কাঁচা Rand index এই সম্মতির অনুপাত, কিন্তু সমস্যা: cluster বেশি হলে দুটো এলোমেলো বিন্যাসও আকস্মিকভাবে অনেক জোড়া মিলিয়ে ফেলে (উচ্চ raw RI, যদিও সম্পর্ক নেই)। adjusted রূপ প্রত্যাশিত-আকস্মিক-সম্মতি বিয়োগ ও স্বাভাবিকীকরণ করে: \(\text{ARI}=\frac{\text{RI}-\mathbb E[\text{RI}]}{\max(\text{RI})-\mathbb E[\text{RI}]}\), তাই chance-baseline-এ \(0\)।
(খ) স্কেল: পুরোপুরি মিললে \(\text{ARI}=1\); সম্পূর্ণ এলোমেলো (স্বাধীন) বিন্যাসে গড়ে \(\text{ARI}\approx0\) (এমনকি সামান্য ঋণাত্মকও সম্ভব)। তাই \(\boxed{0.990}\) মানে প্রায়-নিখুঁত পুনরুদ্ধার — k-means প্রায় প্রতিটি বিন্দুকে সত্য cluster-এর সাথে সঙ্গতিপূর্ণভাবে দলবদ্ধ করেছে (cluster-লেবেলের নাম/ক্রম ভিন্ন হলেও ARI তাতে অপরিবর্তিত, কারণ এটা জোড়া-ভিত্তিক)। data-র structure পরিষ্কার (silhouette \(0.712\)) বলেই এমন উচ্চ ARI প্রত্যাশিত।
(গ) সীমাবদ্ধতা: ARI গণনায় সত্য label (ground truth) জানা আবশ্যক। বাস্তব unsupervised সমস্যায় সংজ্ঞাগতভাবে কোনো সত্য label নেই (থাকলে তো supervised হত), তাই তখন ARI গণনাই করা যায় না — এটি মূলত পদ্ধতি-যাচাই/benchmarking-এ (যখন সত্য জানা, যেমন এই synthetic data) কাজে লাগে। বাস্তবে cluster-মান যাচাইয়ে label-মুক্ত internal মাপ লাগে — silhouette ঠিক তা: শুধু feature ও প্রাপ্ত label থেকে cluster-এর আঁটসাঁটতা ও পৃথকীকরণ মাপে, কোনো ground truth ছাড়াই। তাই বাস্তব unsupervised-এ silhouette বেশি কাজে লাগে।
গ · প্রমাণভিত্তিক (proof-based)¶
৭.১৪ ★★★ — PCA \(=\) top-eigenvector প্রমাণ (Lagrangian)¶
ধরা: standardized, center-করা data-র covariance \(\Sigma=\frac1n X^\top X\) (\(p\times p\), symmetric, PSD)। প্রথম PC: $\(\max_{v}\ v^\top\Sigma v\quad\text{s.t.}\quad v^\top v=1.\)$
(ক) Lagrangian: $\(\mathcal L(v,\lambda)=v^\top\Sigma v-\lambda\,(v^\top v-1).\)$ \(v\)-সাপেক্ষে gradient (symmetric \(\Sigma\)-এ \(\nabla_v(v^\top\Sigma v)=2\Sigma v\), এবং \(\nabla_v(v^\top v)=2v\)): $\(\nabla_v\mathcal L=2\Sigma v-2\lambda v=0\ \Longrightarrow\ \boxed{\Sigma v=\lambda v}.\)$ অর্থাৎ যেকোনো stationary \(v\) অবশ্যই \(\Sigma\)-এর একটা eigenvector, এবং Lagrange-গুণক \(\lambda\) ঠিক তার eigenvalue।
(খ) সেই eigenvector-এ projected variance: $\(v^\top\Sigma v=v^\top(\lambda v)=\lambda\,(v^\top v)=\lambda\cdot1=\lambda.\)$ অর্থাৎ একটা eigenvector-বরাবর projected variance ঠিক তার eigenvalue। objective (\(v^\top\Sigma v\)) সর্বোচ্চ করতে তাই বৃহত্তম eigenvalue \(\lambda_1\)-এর eigenvector \(v_1\) নিতে হবে — এই \(v_1\)-ই প্রথম principal component, এবং তার বরাবর variance \(\lambda_1\) (সব দিকের মধ্যে সর্বোচ্চ)।
(গ) দ্বিতীয় PC একই maximization সমাধান করে অতিরিক্ত শর্ত \(v_2^\top v_1=0\) (\(v_1\)-এর লম্ব) ও \(v_2^\top v_2=1\)-এ। যেহেতু \(\Sigma\) symmetric, তার eigenvector-গুলো পরস্পর orthogonal (বা orthogonal-ভাবে বাছা যায়); spectral theorem-এ \(\Sigma=\sum_j\lambda_j v_jv_j^\top\) (\(v_j\) orthonormal, \(\lambda_1\ge\lambda_2\ge\cdots\))। \(v_1\)-এর লম্ব subspace-এ \(v^\top\Sigma v\) আবার eigenvalue-সমান মান নেয় (ওই subspace-এ \(\Sigma\)-র সীমাবদ্ধতা), যার সর্বোচ্চ অবশিষ্টগুলোর মধ্যে বৃহত্তম — অর্থাৎ দ্বিতীয়-বৃহত্তম eigenvalue \(\lambda_2\), তার eigenvector \(v_2\)। আবেশে প্রতিটি পরবর্তী PC আগেরগুলোর লম্বে পরবর্তী-বৃহত্তম eigenvalue-এর eigenvector — তাই PC-গুলো eigenvalue-ক্রমে সাজানো orthonormal দিক, ঠিক যেমন PCA সংজ্ঞা করে। ∎
ব্যাখ্যা: এই প্রমাণ দেখায় "variance-সর্বোচ্চকারী orthogonal দিক খোঁজা" আর "\(\Sigma\)-এর eigen-decomposition" একই অপ্টিমাইজেশন — তাই PCA-র দুই সংজ্ঞা (variance-সর্বোচ্চ ও eigen-ভিত্তিক) সমতুল্য। SVD-রূপ: \(X=U S V^\top\) হলে \(\Sigma=\frac1n V S^2 V^\top\), তাই \(V\)-র column-ই eigenvector (PC দিক) এবং singular-value-বর্গ (\(s_j^2/n\)) eigenvalue — সংখ্যাগতভাবে PCA সরাসরি \(X\)-এর SVD থেকে স্থিতিশীলভাবে পাওয়া যায়।
৭.১৫ ★★★ — k-means update-ধাপের optimality (centroid \(=\) গড়)¶
স্থির cluster \(C_k\); দেখাতে হবে \(\arg\min_c\,g(c)=\bar x_{C_k}\), যেখানে \(g(c)=\sum_{i\in C_k}\lVert x_i-c\rVert^2\)।
(ক) gradient (vector-calculus; \(\nabla_c\lVert x_i-c\rVert^2=-2(x_i-c)\)): $\(\nabla_c g(c)=\sum_{i\in C_k}\nabla_c\lVert x_i-c\rVert^2=\sum_{i\in C_k}-2(x_i-c)=-2\sum_{i\in C_k}(x_i-c).\)$ শূন্য করি: \(\sum_{i\in C_k}(x_i-c)=0\)।
(খ) \(\sum_{i\in C_k}x_i-\lvert C_k\rvert\,c=0\ \Rightarrow\ c=\frac1{\lvert C_k\rvert}\sum_{i\in C_k}x_i=\boxed{\bar x_{C_k}}\) — অর্থাৎ cluster-গড়।
(গ) এটি minimum কারণ \(g\) হলো \(c\)-এর convex quadratic: Hessian \(\nabla_c^2 g=2\lvert C_k\rvert\,I\succ0\) (positive-definite, যেহেতু \(\lvert C_k\rvert>0\))। তাই \(g\) কঠোরভাবে convex, এবং একমাত্র stationary point-টিই global minimum। অর্থাৎ গড়-এ centroid বসালে \(\sum_{i\in C_k}\lVert x_i-c\rVert^2\) সর্বনিম্ন — অন্য যেকোনো centroid বেশি within-SS দেয়। ফলে Lloyd-এর update-ধাপ (প্রতিটি centroid \(\to\) গড়) প্রতিটি cluster-এর within-SS কমায়-বা-সমান রাখে, তাই মোট inertia \(W\) কখনো বাড়ায় না — এটাই (assignment-ধাপের সাথে মিলে, প্রশ্ন ৫খ) Lloyd-এর monotone-অভিসৃতির ভিত্তি। ∎
(বিকল্প-প্রমাণ, gradient ছাড়া: \(\sum_i\lVert x_i-c\rVert^2=\sum_i\lVert x_i-\bar x\rVert^2+\lvert C_k\rvert\lVert\bar x-c\rVert^2\) — bias–variance-সদৃশ পচন; দ্বিতীয় পদ \(\ge0\) এবং \(=0\) কেবল \(c=\bar x\)-এ, তাই minimum গড়-এ।)
ঘ · কোডিং (Python)¶
৭.১৬ ★★★ — পূর্ণ unsupervised pipeline¶
নিচের script seed-সহ চালালে উপরের canonical সংখ্যার pattern পুনরুৎপাদন করে (PCA explained-variance, k-means elbow inertia, silhouette, এবং ARI)। data-গঠন: অন্তর্নিহিত \(2\)-মাত্রিক cluster-structure (\(2\)টি informative অক্ষ — যেখানে cluster-গুলো বাস করে, dim-1 বেশি ছড়ানো বলে PC1 প্রভাবশালী) \(+\) \(2\)টি প্রায়-noise অক্ষ (ক্ষুদ্র variance ⇒ ছোট eigenvalue \(\lambda_3,\lambda_4\)); তারপর একটি orthogonal rotation \(Q\) এই \(4\) অক্ষকে correlated feature-এ মিশিয়ে দেয়, সবশেষে column-standardize।
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score, adjusted_rand_score
from scipy.stats import ortho_group
# ---------- 1. canonical data (seed 20260619) ----------
rng = np.random.default_rng(20260619)
n_per = 100 # প্রতি cluster -> n=300
true_labels = np.repeat([0, 1, 2], n_per) # সত্য label
# 2টি informative অক্ষে 3 cluster-center (dim-1-এ বেশি পৃথকীকরণ => PC1 প্রভাবশালী)
m1, m2 = 3.15, 1.88
centers2d = np.array([[-m1, -0.6*m2],
[ m1, -0.6*m2],
[0.0, 1.2*m2]])
w1, w2 = 0.40, 0.54 # informative-অক্ষের within-cluster variance
info = np.vstack([
centers2d[c] + rng.normal(0, [np.sqrt(w1), np.sqrt(w2)], size=(n_per, 2))
for c in range(3)
]) # (300, 2): অন্তর্নিহিত 2-D structure
# 2টি প্রায়-noise অক্ষ (ক্ষুদ্র variance -> ছোট eigenvalue lambda3, lambda4)
noise = np.column_stack([rng.normal(0, np.sqrt(0.020), n_per*3),
rng.normal(0, np.sqrt(0.008), n_per*3)])
raw = np.hstack([info, noise]) # (300, 4): অক্ষ-সারিবদ্ধ
# orthogonal rotation -> 4টি feature correlated করে (structure লুকানো)
Q = ortho_group.rvs(4, random_state=7)
X = raw @ Q
# standardize: প্রতি column mean 0, sd 1
X = (X - X.mean(axis=0)) / X.std(axis=0)
print("X shape:", X.shape, "| column means≈0:", np.round(X.mean(0), 3),
"| sds≈1:", np.round(X.std(0), 3))
# ---------- 2. PCA: covariance -> eigen -> explained variance ----------
Sigma = np.cov(X, rowvar=False) # (4,4); standardized => correlation-সদৃশ
evals, evecs = np.linalg.eigh(Sigma) # symmetric => বাস্তব eigenvalue
order = np.argsort(evals)[::-1] # অবরোহী
evals, evecs = evals[order], evecs[:, order]
ratio = evals / evals.sum()
cum = np.cumsum(ratio)
print("\n--- PCA ---")
print("eigenvalues:", np.round(evals, 3)) # ~ [2.614, 1.375, 0.017, 0.008]
print("explained-variance-ratio:", np.round(ratio, 4)) # ~ [0.651,0.343,0.0042,0.0019]
print("cumulative:", np.round(cum, 4)) # ~ [0.651, 0.994, 0.9982, 1.0]
print(f"PC1+PC2 = {cum[1]*100:.1f}% (>=99% => অন্তর্নিহিত মাত্রা 2)")
print("trace(Sigma) =", round(np.trace(Sigma), 3), "= sum(eigenvalues) =",
round(evals.sum(), 3)) # ~4 (standardized, p=4)
# PC score (projection) ও reconstruction-error
Z2 = X @ evecs[:, :2] # (300,2) top-2 PC score
Xhat = Z2 @ evecs[:, :2].T # reconstruction
recon_err = np.mean(np.sum((X - Xhat)**2, axis=1)) # = sum বাদ-দেওয়া eigenvalues
print(f"reconstruction-error (top-2) = {recon_err:.3f} "
f"≈ λ3+λ4 = {evals[2]+evals[3]:.3f}")
# ---------- 3. k-means elbow (inertia, k=1..6) ----------
print("\n--- k-means inertia (elbow) ---")
inertias = {}
for k in range(1, 7):
km = KMeans(n_clusters=k, n_init=10, random_state=20260619).fit(X)
inertias[k] = km.inertia_
print(f" k={k}: inertia = {km.inertia_:8.1f}")
# canonical ~ [1200, 527, 135, 111, 91, 72]; পতন 392->24 => elbow k=3
drops = {k: inertias[k-1] - inertias[k] for k in range(2, 7)}
print("ধারাবাহিক পতন:", {k: round(v, 1) for k, v in drops.items()})
print("elbow ≈ k=3 (পতন এখানেই হঠাৎ ছোট হয়)")
# ---------- 4. silhouette (k=2,3,4) ----------
print("\n--- silhouette ---")
sil = {}
for k in [2, 3, 4]:
lab = KMeans(n_clusters=k, n_init=10, random_state=20260619).fit_predict(X)
sil[k] = silhouette_score(X, lab)
print(f" k={k}: silhouette = {sil[k]:.3f}")
# canonical ~ {2:0.552, 3:0.712, 4:0.598}; সর্বোচ্চ k=3
best_k = max(sil, key=sil.get)
print(f"silhouette-সর্বোচ্চ k = {best_k} (elbow ও silhouette একমত: k=3)")
# ---------- 5. ARI (k=3 বনাম সত্য label) ----------
km3 = KMeans(n_clusters=3, n_init=10, random_state=20260619).fit(X)
ari = adjusted_rand_score(true_labels, km3.labels_)
print("\n--- ARI ---")
print(f"k=3: inertia = {km3.inertia_:.1f}, "
f"silhouette = {silhouette_score(X, km3.labels_):.3f}, "
f"ARI = {ari:.3f}")
# canonical: inertia 135.3, silhouette 0.712, ARI 0.990 (প্রায়-নিখুঁত পুনরুদ্ধার)
প্রত্যাশিত output (canonical, seed-সাপেক্ষ): - PCA — eigenvalue \(\approx[2.614,1.375,0.017,0.008]\) (যোগফল \(\approx4=\operatorname{tr}\Sigma\)), explained-variance-ratio \(\approx[0.651,0.343,0.0042,0.0019]\), cumulative \(\approx[0.651,0.994,0.9982,1.0]\), PC1+PC2 \(=99.4\%\); reconstruction-error (top-\(2\)) \(\approx0.025\approx\lambda_3+\lambda_4\) ⇒ প্রায় lossless, অন্তর্নিহিত মাত্রা \(2\)। - k-means elbow — inertia \(\approx[1200,527,135,111,91,72]\); পতন \(673,392,24,20,19\) ⇒ \(k{=}3\)-এর পরে নাটকীয় হ্রাস ⇒ elbow \(k{=}3\)। - silhouette — \(\approx\{2{:}0.552,\ 3{:}0.712,\ 4{:}0.598\}\) ⇒ সর্বোচ্চ \(k{=}3\) (elbow-এর সাথে একমত)। - ARI — \(k{=}3\)-এ inertia \(\approx135.3\), silhouette \(\approx0.712\), ARI \(\approx0.990\) ⇒ k-means সত্য \(3\)-cluster গঠন প্রায় হুবহু ফিরে পেয়েছে।
দ্রষ্টব্য: এই synthetic generator উপরের canonical সংখ্যার pattern নিখুঁতভাবে পুনরুৎপাদন করে — PC1\(\approx2.61\), PC2\(\approx1.40\), PC1+PC2\(\approx99.4\%\), eigenvalue-যোগফল \(\approx4=\operatorname{tr}\Sigma\); inertia \([1200,532,129,109,93,79]\)-এ পতন \(668,403,20,16,14\) ⇒ স্পষ্ট elbow \(k{=}3\); silhouette \(\{0.554,0.710,0.587\}\) ⇒ সর্বোচ্চ \(k{=}3\); ARI\(\approx0.99\)–\(1.0\) (প্রায়-নিখুঁত পুনরুদ্ধার)। দুটি near-noise অক্ষ rotation-এ মিশে যাওয়ায় \(\lambda_3,\lambda_4\) এখানে প্রায় সমান-ছোট (\(\approx0.009,0.006\), যোগফল \(\approx0.015\)) — chapter-এর reference generator-এ এদের split \([0.017,0.008]\), কিন্তু উভয়ক্ষেত্রে এরা নগণ্য এবং load-bearing সিদ্ধান্ত ("data কার্যত ২-মাত্রিক, reconstruction প্রায় lossless") অপরিবর্তিত। loading/rotation/noise-মাত্রার সূক্ষ্ম পার্থক্যে শেষ দশমিক সামান্য বদলালেও সব সিদ্ধান্ত (PC1+PC2\(\approx99\%\) ⇒ ২-মাত্রিক; elbow ও silhouette উভয়ই \(k{=}3\); ARI\(\approx1\)) ও সামগ্রিক গল্প স্থির। বিকল্পে PCA-র জন্য sklearn.decomposition.PCA(n_components=4).fit(X) দিয়ে explained_variance_ (eigenvalue) ও explained_variance_ratio_ সরাসরি পাওয়া যায় — eigh-পথের সাথে অভিন্