Is it true that Linear regression is sufficient for all data, including censored data.?

Linear regression treats all values uniformly and fails to account for the concentration of observations at the censoring point, unlike models like the Tobit model.

Is it true that The 'greedy' approach in optimization always finds the best solution.?

A greedy heuristic (e.g., 'sell to highest-revenue class first') can yield lower revenue than the true optimum, which is found through proper optimization methods.

The Analytics Edge: Weeks 8-13 Cheat Sheet

Decision trees partition predictor space greedily, while ensemble methods like Random Forest and Bagging improve robustness by combining multiple trees. Unsupervised learning discovers structure (clustering) or reduces dimensions (PCA, SVD), and censored data analysis models outcomes with incomplete observations.

Core Principles

Decision Trees: Greedily split data by picking the predictor and split point that most improves the current node, minimizing SSE for regression or impurity for classification.
Ensemble Methods (Bagging & Random Forest): Reduce variance of high-variance learners like CART by averaging predictions from multiple trees trained on bootstrap samples. Random Forest further decorrelates trees by considering only a random subset of predictors at each split.
Clustering: Unsupervised learning to discover groups without labels. Hierarchical clustering builds a dendrogram bottom-up, while K-means requires specifying K clusters upfront and minimizes within-cluster variance.
Censored Data Analysis: Models outcomes where the exact value is unknown (e.g., Tobit for censored variables, Kaplan-Meier for survival curves, Cox Proportional Hazards for hazard rates with predictors).
Matrix Decomposition (SVD, Eigen-decomposition, PCA): Tools for dimensionality reduction and understanding data structure. SVD works on any rectangular matrix, while Eigen-decomposition is for symmetric matrices. PCA finds directions of maximum variance.

Action Steps

Build a Decision Tree: Use Recursive Binary Splitting, selecting predictors and split points greedily to minimize SSE (regression) or impurity (classification).
Apply Bagging: Generate B bootstrap datasets, train a tree on each, and average predictions (regression) or majority vote (classification).
Implement Random Forest: At each split, consider only a random subset of m < p predictors to decorrelate trees.
Perform Hierarchical Clustering: Start with individual observations as clusters and repeatedly merge the two closest until one cluster remains, producing a dendrogram.
Run K-means Clustering: Randomly assign observations to K clusters, compute centroids, reassign observations to nearest centroids, and repeat until convergence.
Fit a Tobit Model: Use Maximum Likelihood Estimation to model a censored dependent variable, accounting for the probability mass at the censoring point.
Estimate Survival Curve with Kaplan-Meier: Use censored lifetime data to directly estimate S(t) by multiplying conditional survival probabilities.
Model Hazard Rate with Cox Proportional Hazards: Use partial likelihood to estimate hazard rates based on predictor variables, modeling λ(t) = λ₀(t)·exp(βx).
Perform PCA: Standardize data, compute the sample covariance matrix, find its eigenvectors (PCs) and eigenvalues, and select PCs explaining sufficient variance (e.g., eigenvalue > 1).

Formulas

Accuracy = (TP+TN) / Total
FPR = FP/(FP+TN)
TPR = TP/(TP+FN)
Cost complexity pruning: minimize SSE (or impurity) + α * T
Pearson correlation coefficient S_uv: ranges -1 to 1
RMSE = sqrt(mean((predicted - actual)²))
Eigen-decomposition: A = UΛUᵀ
PCA: S = (1/(n-1)) XᵀX
Kaplan-Meier Survival function: S(t) = P(T>t) = 1 - F(t)
Kaplan-Meier formula: S(t) = Π (1 - dᵢ/nᵢ) over all event times tᵢ ≤ t
Cox Proportional Hazards Model: λ(t) = λ₀(t)·exp(β₁x₁+...+βₚxₚ)
Multinomial logit probability: P(i purchased) = exp(Vᵢ - pᵢ) / Σⱼ exp(Vⱼ - pⱼ)

Key Terms

Recursive Binary Splitting: A greedy, top-down method for building decision trees where at each step, the predictor and split point are chosen to most improve the current node.
Impurity Measure (Classification): Metrics like Gini index or Entropy used to quantify the 'mixed-up-ness' of classes within a node; minimized during classification tree building.
Bootstrap Dataset: A dataset created by resampling with replacement from the original dataset, used in Bagging and Random Forest to train multiple trees.
Dendrogram: A tree diagram illustrating the arrangement of the clusters produced by hierarchical clustering.
Pearson Correlation Coefficient: Measures linear correlation between two variables, ranging from -1 to 1, used in user-based collaborative filtering to find 'neighbors'.
Eigenvector: A vector that, when a linear transformation is applied to it, only changes by a scalar factor (the eigenvalue); fundamental to Eigen-decomposition and PCA.
Censored Data: Observations where the exact value of a variable is not fully known (e.g., survival time beyond study end).
Hazard Rate (λ(t)): The instantaneous probability that an event occurs at time t, given that it has not occurred before time t.

Pro Tips

For classification trees, R's `rpart` package defaults to the Gini index for impurity.
Use Out-of-Bag (OOB) error in Bagging and Random Forest as a good proxy for test error without needing a separate test set.
When interpreting Random Forest variable importance, distinguish between 'Mean Decrease Gini' (impurity reduction) and raw frequency of use, as they measure different aspects.
For K-means clustering, run the algorithm multiple times with different random initializations (`nstart` in R) and select the result with the lowest within-cluster variance.
When using PCA, standardize variables first to prevent those with larger scales from dominating the analysis.
The 'greedy' approach in optimization (e.g., selling to the highest-revenue class first) does not always yield the true optimum, as demonstrated in the airline revenue management example.

Pitfalls to Avoid

Confusing Bagging and Random Forest: Bagging uses all predictors at each split, while Random Forest uses a random subset, which is crucial for decorrelation.
Misinterpreting Bootstrap vs. Cross-Validation: Bootstrap measures estimate uncertainty, while CV measures generalization performance.
Ignoring random initialization in K-means: Different initializations can lead to different cluster assignments; always run multiple times.
Applying linear regression to censored data: This ignores the concentration of data at the censoring point and doesn't accurately model the underlying process.
Using Eigen-decomposition on non-symmetric matrices: Eigen-decomposition is only applicable to symmetric matrices; use SVD for general rectangular matrices.

Myth vs Reality

Linear regression is sufficient for all data, including censored data.: Linear regression treats all values uniformly and fails to account for the concentration of observations at the censoring point, unlike models like the Tobit model.
The 'greedy' approach in optimization always finds the best solution.: A greedy heuristic (e.g., 'sell to highest-revenue class first') can yield lower revenue than the true optimum, which is found through proper optimization methods.

Real World Examples

Predicting customer churn: Using a Classification Tree (CART) to predict whether a customer will 'spam' (class) based on their behavior.
Airline Revenue Management: Using optimization techniques (like Multinomial Logit) to decide how many seats to sell at different price points (regular, discount, saver) to maximize total revenue, subject to capacity and demand constraints.
Movie Recommendations: Using User-Based Collaborative Filtering to recommend movies by finding users with similar rating patterns (neighbors) and suggesting movies they liked.
Patient Survival Analysis: Using the Kaplan-Meier estimator to estimate the survival curve for a group of patients, or the Cox Proportional Hazards model to understand how factors like age or treatment affect the hazard rate.

Statistics

Random Forest recommended m (regression): p/3
Random Forest recommended m (classification): √p
Bagging default B (number of trees): 25 (ipred package), 500 (randomForest package)

Timeline

Week 8-9: CART & Random Forest
Week 9-10: Clustering & Recommendation Systems
Week 11: Matrix Factorization (Eigen-decomposition, SVD, PCA)
Week 12 (part 1): Censored Data Analysis
Week 12 (part 2) - 13: Optimization

People

R (programming language): Environment for implementing algorithms like CART (`rpart`), Bagging (`ipred`), Random Forest (`randomForest`), Hierarchical Clustering (`hclust`), K-means (`kmeans`), and survival analysis (`survival`).