DTSA 5505

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/51

encourage image

There's no tags or description

Looks like no tags are added yet.

52 Terms

1
New cards

Information Formula

Info(D) = -Σ pi * log(pi)

Sigma = Sum of

pi = Probability of class Ci = Ci / D

log(pi) = Log of the probability of class Ci

2
New cards

pi Formula

pi = |Ci| / |D|


Ci = # of instances of the i-th answer (Ex. C1 = Approved Applicants, C2 = Denied Applicants)

D = Whole collection of instances (Ex. All the applicants)

3
New cards

Information Formula following Split

InfoA(D) = Σ(|Dj| / |D|) * Info(Dj), where Dj is one pile in the split


It’s the sum of the Information Formula applied to each pile in the split multiplied by their respective weights


Ex. Pile A = 5 (2A, 3D), B = 3 (3,0), C = 4 (2,2)

A = 0.4 * log2(0.4) + 0.6 * log2(0.6) = -0.971, flip the sign and get 0.971

B = 0 because it is pure

C = 1.0 because it is perfectly 50/50

0.971*(5/12) + 0(3/12) + 1(4/12) = 0.738


Gain = Info(D) - InfoA(D) = 0.980 - 0.738 = 0.242

4
New cards

Gain Formula

Info(D) - InfoA(D)

5
New cards

Bayes Theorem

“Chance the guess is right, given what I observed”


(How common the guess is overall) * (How often I’d see this observation if the guess were true) / (How common the observation is overall)


Aka score = likelihood * prior


[P(Ci) * P(X | Ci)] / P(X)

Where Ci is one possible answer (class) like “Picnic = yes/no” and X is the details of that day


We skip dividing by P(X) because both the winner and loser and divided by the same P(X)

6
New cards

Bayes Theorem - Naive Assumption

P( X | Ci) = Π P(xk | Ci)


It is the product of the individual chances of each trait being among picnic days


Example: Overcast, Mild, High Humidity, False (Wind)

Out of 9 picnic days, 4 were O, 4 were M, 3 were H, and 6 were F

P(X | yes) = 4/9 × 4/9 × 3/9 × 6/9 - This is the Likelihood


Take that number, multiply it by the prior to get the score for yes

7
New cards

Laplacian Correction Example

If we have 0 for overcast when looking at Picnic = No, and we add 1 to each count for that trait


Overcast was 0, becomes 1

Rainy was 3, becomes 4

Sunny was 2, becomes 3


So 0/5 becomes 1/8, the denominator updates too

8
New cards

Support Vector Machines

Classification method with supervised learning where the goal is to draw a boundary that separates the classes


In 2D it’s a flat line, in 3D it’s a flat sheet, in more dimensions it’s a hyperplane


Analogy: Two groups of people standing in a field, you put a rope on the ground between them, people on the left are in Group 1, people on the right are in Group 2

9
New cards

Margin

Support Vector Machines (SVMs)


Margin is the distance from the boundary to the nearest points on each side. SVM picks the line with the largest margin, called the maximum margin hyperplane


Why? Because a line squeezed right up against some points is risky. Real data is noisy, so a slightly unusual point could land on the wrong side, so a line with a wide empty buffer on both sides is safer

10
New cards

Support Vectors

Support Vector Machines (SVMs)


Support vectors are the few points sitting right at the edge of the buffer and define the margin


Points far away from the boundary don’t affect where it goes, but if you move one of the support vectors the boundary shifts


This is where the name comes from, it is a machine built from support vectors

11
New cards

Linearly Inseparable

When classes are tangled together along a wavy border, and no single straight line can separate them


This is fixed by adding dimensions

12
New cards

Why does adding dimensions fix data that is linearly inseparable?

You add dimensions by transforming each point into a version with more attributes. In the higher-dimensional space, points get more spread out, and flat boundary may now separate the classes. You then run the normal maximum-margin method in that bigger space


Example: On a number line, we have blue points at -1, 0, and 1, red points at -3 and 3. No single line separates them. If we give each point a second attribute, like it’s value squared, we get (-1,1), (0,0), (1,1), (-3,9), & (3,9), which can be cleanly separated by a line at height 5. The extra dimension did the work

13
New cards

Linearly Inseparable Shortcut: Kernel Trick

Moving every point into a high-dimensional space is expensive. Finding the maximum margin only needs dot products (a way of measuring how similar two points are)


The dot product in the high-dimensional space can be calculated by applying a kernel function to the original points, with no actual transformation needed

14
New cards

Classification vs Clustering: Which is supervised?

Classification is supervised

Clustering is unsupervised

15
New cards

Decision Tree - Bullet Points

Top-down, Recursive, Attribute Selection, Split

16
New cards

Bayesian Classification - Bullet Points

Probability, Naive Assumption, Belief Network

17
New cards

Classification Methods - Review Slide

Decision Tree Induction: Efficient, Easy to Interpret

Bayesian Classification: Efficient, Explainable, Incremental (If you get new data just update the counts)

Support Vector Machines: Good/High Performance

Neural Networks: Complex, High Performance, Poor Interpretability

18
New cards

Ensemble

Combined use of multiple models

Analogy: Consulting multiple doctors


Bagging: Equal weights, majority voting

- Training set: random sample with replacement


Boosting: Weighted votes (this is when you think certain models are better than others)

- Adjusted weights to focus more on misclassified cases

<p>Combined use of multiple models</p><p>Analogy: Consulting multiple doctors</p><p></p><p><strong>Bagging: </strong>Equal weights, majority voting</p><p>- Training set: random sample with replacement</p><p></p><p><strong>Boosting:</strong> Weighted votes (this is when you think certain models are better than others)</p><p>- Adjusted weights to focus more on misclassified cases</p>
19
New cards

Model Evaluation

Holdout, random sampling
- Split into training set (for model construction) & test set (80/20)

(k-fold) Cross-validation
- Split into k partitions, each 1 for testing & (k-1) for training
- Divide your data into k segments then do k runs, each time selecting 1 holdout and using the remaining k-1 segments as the training data

Bootstrapping
- .632 Bootstrapping
- Random sample with replacement

20
New cards

Classification Accuracy

Confusion Matrix
- TP, FP, TN, FN
- Maximize TP’s and TN’s, minimize FP’s and FN’s

21
New cards

Classification Accuracy - Measures

Sensitivity: TP / Total Positives

Specificity: TN / Total Negatives

Precision: TP / (TP + FP)

Accuracy: (TP + TN) / (TP + TN + FP + FN)
- On the slide she had Sensitivity(Pos / Pos + Neg) + Specificity(Neg / Pos + Neg)

22
New cards

Costs & Benefits of TP/TN/FP/FN

Depending on the situation you may want to consider which are more important:


If you are dealing with Fraud Detection:
- FP: Normal case flagged as fraud
- FN: Fraud misclassified as normal
Probably want to err on the side of FP’s

23
New cards

When TP/TN/FP/FN doesn’t work

Multi-class Classification
Example: Human Activity Recognition

Model will make errors, but the type of mistake matters: misclassifying one activity as a closely related activity may be far less severe than confusing it with a completely different one


If Activity 1 and 2 are similar, but 1 and 3 are not, misclassifying 1 as 3 is worse than misclassifying 1 as 2. So you would assign different weights or penalties to different types of errors


Big Takeaway: There is not one measure or calculation to compare everybody. You need to understand your scenario and then decide which measure or metrics are more important in that scenario

24
New cards

Big Takeaway on Classification Metrics

There is not one measure or calculation to compare everybody. You need to understand your scenario and then decide which measure or metrics are more important in that scenario

25
New cards

Scoring Number Predictions

When the answer is a number (stock price, temperature, wind speed), an exact hit is nearly impossible, so you score how far off each guess was


She named these measures:

Absolute Error

Squared Error

Mean Absolute Error

Mean Squared Error

Relative Absolute Error

Relative Squared Error

26
New cards

Equations for Scoring Number Predictions

knowt flashcard image
27
New cards

ROC Curve

Across (x-axis): False Positive Rate - FP / All Real Negatives

Up (y-axis): True Positive Rate - TP / All Real Positives


You want to be as far up and as far left as possible

28
New cards

T-Test Formula

t=err‾(M1)−err‾(M2)var(M1−M2)/kt=\frac{\overline{err}(M_1) - \overline{err}(M_2)}{\sqrt{\text{var}(M_1 - M_2)/k}}


var(M1−M2)=1k∑i=1k[err(M1)i−err(M2)i−(err‾(M1)−err‾(M2))]2\text{var}(M_1 - M_2) = \frac{1}{k} \sum_{i=1}^{k} \left[err(M_1)_i - err(M_2)_i - (\overline{err}(M_1) - \overline{err}(M_2))\right]^2

29
New cards

T-Test Steps

- Do the k-fold cross-validation


- Calculate t


- Look up the cutoff (need df and significance level, a)

*If doing a two-sided t-test you need to do 1 - a/2


- Compare

If t is bigger than the cutoff, you reject “the models are equal” (t is statistically significant if t > cutoff)

30
New cards

Summary: Classification

knowt flashcard image
31
New cards

What is Clustering?

You have objects described by several attributes, but no predefined categories and no labels.  Goal is to discover natural groupings.  This is unsupervised learning, in contrast to classification, which is supervised

32
New cards

What are the properties of good clustering?

High intra-cluster similarity (in the same cluster)

Low inter-cluster similarity (between clusters)

33
New cards

What to Judge a Clustering Method On

Quality: Are the clusters good?

Efficiency: Is it fast on large data?

Incremental: When new data arrives, can you update the existing clusters instead of starting over?

34
New cards

Four Questions for Evaluating a Clustering

Clustering Tendency: Does the data have clusters at all?  If the points are spread roughly evenly or randomly, no method will find real groups

Cohesion & Separation: Are objects tight inside their cluster (cohesion), and are clusters far apart (separation)?  These are the two properties above, made measurable

How many clusters?  You usually don’t know the number in advance, and there are measures to compare different numbers

Outside Knowledge:  Domain experts may already know roughly how many
clusters to expect, or what good ones look like.  Use that


You can also compare two different clusterings of the same data to see which is better

35
New cards

Silhouette Coefficient - What is it, scores, and equation

Measures how well-separated and cohesive your clusters are by comparing how close each data point is to its own cluster versus others.  Scores:


Near +1 - P is far closer to its own cluster than to any other (well placed)

Near 0 - P sits on the border between two clusters

Negative -  P is closer to another cluster than its own, it’s probably in the wrong one


Equation: (b - a) / the larger of a and b

a = P’s average distance to the other objects in its own cluster
b = P’s average distance to the objects in the other cluster
Example: a = 1, b = 8, (8 - 1) / 8 = 0.875

36
New cards

Five Families of Clustering Methods

Partitioning: Split the N objects directly into a chosen number of clusters

Hierarchical: Build clusters at many levels, by repeatedly merging small ones or splitting big ones

Grid-based: Chop the space into grid cells and see which objects land in which cell

Density-based: Treat crowded regions as clusters

Probabilistic: Each object belongs to each cluster with some probability (like 70% Cluster 1, 30% Cluster 2) instead of a hard assignment

37
New cards

Closed vs Max Pattern: Example

Closed Pattern means there is no super pattern with the same support, Max Pattern means there is no super pattern that is frequent


Original receipts: bread appears 4 times, milk 3 times, and bread+milk 3 times.

Max keeps: bread+milk. Anything inside it is automatically frequent, so bread and milk need no separate mention. The counts are lost.

Closed keeps: bread (4) and bread+milk (3).

Milk is dropped because bread+milk has the same count (3), so nothing is lost.

Bread is kept because its count (4) differs from bread+milk (3). One receipt had bread without milk, and dropping bread would erase that


Max Pattern: A frequent itemset where no bigger itemset containing it is frequent

Closed Pattern: An itemset where no bigger itemset containing it has the exact same support

38
New cards

Apriori Algorithm

Key idea is pruning: if X is not frequent, then no bigger itemset containing X can be frequent

Analogy: If hardly anyone buys caviar, you don’t need to check “caviar + crackers” or “caviar + lemon” because they can’t be popular either


The steps:

1. Scan dataset to get freq. 1-itemsets

2. Generate Candidates for k+1 itemsets from freq. k-itemsets

3. Scan dataset again to remove infreq. candidate (k+1) itemsets

4. Repeat until no frequent itemsets or candidates are left

39
New cards

Apriori Rules

Self-Joining: To build a k+1 size candidate, combine two frequent groups of size k only if their first k-1 items match

- BC and BE both start with B and differ only at the end, so they join into BCE
- BC and CE don’t share a starting letter, so they don’t join


Pruning: After building a candidate, check that every subset of it is frequent


L3: abc, abd, acd, ace, bcd
- abc + abd -> abcd: Both start with ab, All pieces (abc, abd, acd, bcd) are in L3 → Valid candidate

- abd + acd: Don’t start the same, Rule 2: Not checked → Skipped, it would only recreate abcd, a duplicate

- acd + ace -> acde: Both start with ac, Not all pieces (acd, ace, ade, cde) are in L3 → Pruned before counting

40
New cards

Why Apriori is Slow

Multiple scans of the whole dataset

It builds a lot of candidates - Every round creates new possible combinations

It has to check the Support of all candidates by going back through the database

41
New cards

Apriori Speed-Ups

Partitioning - A freq. itemset must be freq. in at least one partition (can parallelize)

Sampling - Random sampled subsets are likely to contain freq. itemsets

Transaction Reduction - Remove Ti if it doesn’t contain any freq. k-itemset

Hash Tree

Vertical Data Format (Flipping the table around)

42
New cards

Support Counting using Hash-Tree

Steps

  1. Create Subset Function - Sets up a Hash Tree where the rules are 1,4,7 go left, 2,5,8 go middle, and 3,6,9 go right

  2. Create Tree Using Subset Function - Run all possible candidates through your tree, this establishes your leaf nodes

  3. Run every transaction, Ti, through the tree

    1. Generate the k-item subsets for the transaction. For a 5-item transaction and k = 3, that gives 10 subsets

    2. Traverse the tree with each subset, hashing its items in order to follow a path down

    3. Check the leaf. If the path ends at a leaf that holds a matching candidate, add 1 to that candidate’s counter


The candidates in the 3-itemset tree are all the freq 2-itemsets that combined and passed the Join and Pruning rules

<p><span style="background-color: transparent;">Steps</span></p><ol><li><p><span style="background-color: transparent;"><strong>Create Subset Function - </strong>Sets up a Hash Tree where the rules are 1,4,7 go left, 2,5,8 go middle, and 3,6,9 go right</span></p></li><li><p><span style="background-color: transparent;"><strong>Create Tree Using Subset Function - </strong>Run all possible candidates through your tree, this establishes your leaf nodes</span></p></li><li><p><span style="background-color: transparent;"><strong>Run every transaction, T<sub>i</sub>, through the tree</strong></span></p><ol><li><p><strong>Generate the k-item subsets</strong> for the transaction. For a 5-item transaction and k = 3, that gives 10 subsets</p></li><li><p><strong>Traverse the tree</strong> with each subset, hashing its items in order to follow a path down</p></li><li><p><strong>Check the leaf. </strong>If the path ends at a leaf that holds a matching candidate, add 1 to that candidate’s counter</p></li></ol></li></ol><p></p><p>The candidates in the 3-itemset tree are all the freq 2-itemsets that combined and passed the Join and Pruning rules</p>
43
New cards

Vertical Data Format

knowt flashcard image
44
New cards

FP-Growth

Asks whether we can skip candidates altogether and only build combinations we already know are frequent

Analogy: Apriori is trying every key on your key ring, FP-growth is like looking at the lock first and only checking keys that could possibly work

45
New cards
<p><span style="background-color: transparent;">FP-Growth Algorithm</span></p>

FP-Growth Algorithm

  • If d is freq. in the database conditioned on abc, then abcd is freq

    • If the cut off is 100 out of 1000 transactions and abc is in 150, and then d is in 110 of those, then not only is d frequent, so is the combination of abcd

  • Grows patterns using local frequency items

  • Find frequent itemsets without candidate generation


46
New cards

Using the FP-Growth Tree

knowt flashcard image
47
New cards

Association Rules

Frequent combinations only tell you things appeared together, an association rule goes one step further and says “if X is on the receipt, then Y probably is too”


Analogy: A frequent combination says “bread and butter are often bought together.”  A rule says “people who buy bread usually buy butter,” and that’s the sentence a store could act on with a recommendation

48
New cards

Association Rule: The Two Scores

Support: P(X U Y), How often do X and Y show up together?
Calculation: Receipts with both / all receipts
Directional? No, the same both ways


Confidence: P(Y | X), When X is there, how often is Y too?
Calculation: Receipts with both / receipts with X
Directional? Yes, changes with direction

49
New cards

What are the 4 Data Mining Methods?

Frequent Pattern Analysis

Classification

Clustering

Anomaly Detection


Originally motivated by Market Basket Analysis

50
New cards
51
New cards
52
New cards