Pre-exam Flashcards
(290 cards)
1
Q
What is bagging with respect to data mining and ensemble methods?
A
Bagging (bootstrap aggregating) is basically out of bag estimation.
Sample repreatedly with replacement from the original data to create new training sets.
Reduces variance and helps to avoid overfitting.
2
Q
What is agglomerative hierarchical clustering?
A
start with the points as indiivudual clusters
at each step, merge the closest pair of clusters until only one cluster (or k clusters) are left
3
Q
What is true positive rate?
A
The fraction of positive examples predicted correctly by the model.
TPR = TP / ( TP + FN )
4
Q
What is the challenge of applying assocation analysis to non-asymmetric binary variables?
A
Can cause computation issues.
Need to bin and use discretization.
Bin continuous and map categorical.
5
Q
When are statistical approaches to outlier detection effective?
A
When there is sufficient knowledge of the data and ype of test that should be applied.
Fewer options are available for multivariate data.
These statistical tests perform poorly on highly dimensional data.
6
Q
What is the drawback of using confidence level for association rule analysis?
A
The rules can be misleading even though confidence may be high
eg.
Confidence(Coffee|Tea) = 0.75
but P(Coffee) = 0.9
Although confidence is high,
the rule is misleading: P(Coffee| !Tea) = 0.9375
7
Q
What are alternative methods to the Apriori algorithms for generating frequient itemsets?
A
- Traversal of itemset lattice
- FP-Growth Algorithm
8
Q
What approach can be used if a support vector machine is not linear?
A
Math can be used to map the data to a new space and the new data can be used to classify.
In this case, the data needs to be numerical.
9
Q
Using a ROC curve, how is one model compared to another?
A
The area under the curve tells you how the model performed. The ideal area is one. You want the curve to be as close to the upper left corner as possible (high TP rate and low FP rate).
10
Q
Describe the Correlation learning method for ANNs.
A
Correlation (similar things should be more similar and less similar things should be made less similar)
- When different nerurons fire at the same time, the weight representing the connection between them should be increased (associative learning).
11
Q
What are 2 approaches to outler detection?
A
Approach depends on the format of the data
- generalized approach: build a model of the normal data
- graphical: visualize the data using various means - typically subjective
12
Q
What is spaital outlier detection?
A
looks at finding abbrupt changes in behavioural attributes which violate spatial autocorrection and hetreroscedaticity
13
Q
Explain the density based method for outlier dtection
A
assumption that outliers are points in regions of low density
14
Q
What are interestingness measures?
A
used to prune/rank the derived patterns because association rules tend to produce too many rules and many of them are uninteresting or redundant.
15
Q
Explain the statistic freamwork for SSE when evaulating clusters
A
Compare the SSE to random data
Get SSE values
repreat many times
look at the correlation
16
Q
What is dvisive hierarchical clustering?
A
Start with one, all inclusive cluster
At each step, split the cluster until each cluster contains a point (or there are k clusters)
17
Q
How do support vector machines represent the decision boundary?
A
Using a subset of the training examples, known as support vectors.
18
Q
What is the goal of assocation rule mining?
A
Given a set of transactions T, find rules having:
support >= minsup threshold
confidence >= minconf threshold
19
Q
How does the FP growth algorithm mine frequent itemsets?
A
It uses a recursive divided-and-conquer approach
It uses pointrs to assist frequent itemset generation.
It requires preprocessing.
20
Q
Describe the Apriori algorithm used for assocation rule mining.
A
Let K=1
Generate frequent itemsets of length 1
Repeat until no new frequent itemsets are identified
Generate length (k+1) candidate itemsets from length k frequent itemsets
Prune candidate itemsets containing subsets of length k that are infrequent
Count the support for each candidate by scanning the DB
Eliminate cadidates that are ifnrequent, leaving only those that are frequent
21
Q
What is the issue with using Euclidean distance as a distance measure in algorithms such as k-means clustering?
A
K-means tends to find round / globular clusters because of the use of Euclidean distance as a distance measure.
22
Q
What is the difference between a global model and a local model?
A
A global model is 1 model (SVMs)
A local model combines smaller models (KNN and ANNs)
23
Q
Recite the algorithm for k-means
A
select k points as the initial centroids (usually random points)
repeat:
form k clusters by assigning all points to the closet centroid
recompute the centroid of each cluster
until: the centroids don’t change or stopping critereon is met
24
Q
What are the two main types of clustering?
A
Partiitional
Hierarchical
25
What is partitonal clustering?
A division of data objects into non-oberlapping subsets (clusters) such that each data object is exactly one subset.
Simply put, a division of the data into a group or subset.
26
Explain how to measure cluster valididity via correlectation
Generate two matricies (proximity matrix and incidence matrix)
1 row and 1 colum for each data point. An entry is 1 if the associated pair of points belng to the same cluster and 0 if they belong to different clusters.
Compute the correlation between the two matricies.
High correlation incidates that points that belong to the same cluster are close together.
27
What is recall?
Recall measures the fraction of positive examples correctly predicted by the classifier.
r = TP / ( TP + FN )
28
Define itemset with respect to association rule mining.
A collection of one or more items.
E.g: (Milk, Bread, Diaper)
29
What is the consieuqnce if the minsup threshold is too low?
It can become computationally expensive to process and the number of itmesets will be very large.
30
K-means can yield empty clusters. How are they handled?
Just get rid of them.
31
What is the class imbalance problem?
Data sets with imbalanced class distirubtions.
E.g. Credit card fraud. It's very rare that fraud exists, but when it does, it's important and should be given a higher weight.
32
What is a maximimal frequent itemset?
a frequent itemset for which none of its immediate supersets are frequent.
\* When a border is drawn in a lattice to distinguish between frequent and non frequent, the items residing near the border (on the frequent side) are maximal frequent itemsets. Their immediate supersets are infrequent. This is the same for non-maximal itemsets (on the other side of the border).
33
How are hierarchical clusters represented?
Using a denogram. The horizontal heights of the linkages represent the order in which clusters are formed.
34
What variables will influence how good a clustering is?
Type of proximimity or density measure
Sparseness
Attribute type
Dimensionality
Noise & Outliers
Type of distribution
35
What are the limitations of MAX for hieararchical clustering?
tends to break large clusters
biased toward globular clusters
36
What is sequential pattern mining?
Given a database of sequences and a user-specified minimum support threshold, minsup, find all subsequences with support \>= minsup
37
Describe the approach for updating centers incrementally for k-means clustering.
In the basic k-means algorithm, centroids are updated after all points are assigned to acentroid.
An lternative is to update the centroids after each assignment (incremental approach).
38
Is standardization necessary for Euclidean distnace?
If the scales differ, then yes standardization is necessary.
39
What is the great challenge with cluster valididty?
The validation of clustering is tricky.
The result can look good, but this may not always be the case.
40
Explain the purpose of external index measure of cluster validity
used to measure the extend to which cluster labels match externally supplied class labels
41
What are the disadvantages and advantages of updating centers incrementally for the k-means clustering algorithm?
More expensive
Intorudces an order dependency
Never get an empty cluster
(this approach is not used often)
42
Why is confidence important with respect to assocation rule analysis?
Condience measures the reliability of the inference made by a rule.
The higher the confidence, the more likely it is for Y to be present in transactions that contain X.
Confidence also provides an estimate of the conditional probability of Y given X.
43
What are some of the characteristics of Ward's methods for hiearrchical clustering?
Less sucestible to nosie and outliers
biased towards globular clusters
can be used to initialize k-means
44
What is the mahalnanobis distance?
takes the average values of pairs of attributes and subtracts them from the mean of values
gets the co-variance to scanle the distance measures
an alternative to normalizzation (scaling is built in)
- take into account the dspread of the data in a direction
45
What is an epoch with respect to ANNs?
A full application of a complete data set to a neural network.
46
Can the sum of squared error be used for cluster evaluation?
SSE can be used to cmpare two clusterings or two clusters (average SSE).
It can also be used to estimate the # of clusters.
47
Describe the AdaBoost method used in ensembles.
AdaBoost creates many classifiers / models and repreatedly draws from samples.
Samples that are easy to classifiy get a lower weight, and ones that are harder to classify get a higher weight.
If any intermediate rounds produce an error rate higher than 50%, the weights are reverted back and the resampling procedure is repreated.
The classifier also gets a weight.
48
What are 2 example applications of spatial anomaly?
Brain imaging
Weather
49
What are clusters defined by an objective function?
goal of findingclusters that minimize or maximize an objective function.
Enumerate all possible ways of dividing the points into clusters and evaluate the 'goodness' of each potential set of clusters by using the given objective function.
50
What are conceptual clusters?
Clusters that share some common property or rpresent a particular concept.
(for example, two overlapping rings).
51
What approach can be used for SVMs when decision boundaries aren't as clear?
Allow for some contamination by using slack variables.
52
What are the different aspects of cluster validation?
Determining whether non-random structures exist in the data
Comparing results to externally known results (eg. class label)
Determining which clustering technique is better
Determining the "correct" number of clusters
53
Describe a model with high bias and low variance.
A model constructed with low variance and high bias tends to underfit training data. Both underfitting and overfitting can lead to a model that performs poorly.
54
What is bias?
Bias is a systematic shift in ground truth
The stronger the assumptinos made by a classifier about the nature of its decision boundary, the larger the classifier's bias will be.
Design choices such as choice of algorithm can introduce bias too.
55
Why is support count important?
Rules that have low support may only occur by chance.
A low support rule is likely to be uninteresting from a business perspective.
56
What are the 2 parameters that need to be set for DBSCAN?
1. Threshold (density) MinPts
2. Radius (how far out) Eps
57
What is a border point in DBSCAN?
A border point has fewer than MinPts (user specified threshold) within Eps (a user specified radius) but within the neighbourhood of a core point
58
What is true negative rate (specificity)?
The fraction of negative examples correctly predicted by the model.
TNR = TN / (TN + FP)
59
What is a contingency table for computing interestingness in assocation rule discovery?
A matrix of items that were bought and items that were not bought.
60
Why is it important for an SVM to maximize the margin of their decision boundary?
To ensure that their worst-case generalization errors are minimized.
61
What are the 3 common approaches to outliers detection?
1. supervised
class labels
2. unsupervised
no class labels
3. semisupervised
some class labels
62
What is Ward's method for clusters similarity?
The similarity of two clusters is based on the increase in squarred error when two clusters are merged
63
What happens as the number of items increases in association rule analysis?
The number of items decreases.
It can be difficult to find an appripriate support threshold because most items in a store will have a low support count.
64
What are the strengths of MAX for hiearchical clusters?
it's less succesible to noise and outliers
65
What is a learning curve?
It shows how accuracy changes with varying sample size.
Requires a sampling schedule.
In the graph their is a horizontal bar near the top which is an upper limit on accuracy. You can never surpass this bar due to noise, etc... in the data.
66
Why is the significance of picking the initial centroids in k-means clustering?
One of the disadvantages is that, what should be one cluster, is often split into two.
67
Explain the rare class detection method for anomaly detection
consider the problem to be the same as an imbalanced class problem
two approaches:
cost sensitive
re-smampling
68
What is required for data to be transformed to a new space when using SVMs?
The data must be linearly seperable.
69
What conditions must be satisified for ensemble methods to improve the overall classification accuracy?
1) the different classifiers make different mistakes in the data
2) the different classifiers perform better than random guessing
70
What is accuracy measure?
It's a metric used to compare the performance of classifiers.
Accuracy = TP + TN / TP + TN + FP + FN
71
What are two ways of representing frequent itemsets in a compact way?
1. A binary table
2. A lattice with a boundary where we found frequent items (all subsets will be frequent).
72
What are the advantages of grouping categories of items together into concept hiearchies for assocational analysis?
The items at the lower level of the heirarchy may not have neough support to appear in the frequent itemset (this is good because rules at the bottom tend to be overly specific and may not be as interesting).
73
Is the k-means clustering approach paritional or hierarchical?
partitional
74
What are the two main types of hierarchical clustering?
1. Agglomerative
2. Divisive
75
What happes if the value of d is too large or small with respect to density-based outlier detection.
If d is too small, then many normal points may have low desnity and thus a high outlier score. If d is too large, then many outliers may have desnities (and outlier scores) that are similar to normal points.
76
What is the difference between fuzzy and non fuzzy clusterings?
In fuzzy clustering, a point belongs to every cluster with some weight bewteen 0 and 1.
The weights must sum to 1.
77
What are characteristics of the DBSCAN clustering algorithm?
can handle unknown # of clusters
requires to user-defined parameters to be specified
paritinoed based (fixed # of clusters)
partial clustering (doesn't get rid of all points)
deals best with noise because it gets rid of it
worst of 3 approaches for clustering data with varying densities
deterministic
78
Do confidence of rules have an anti-monotone property?
No, but confidence of rules generated from the same itemset do.
79
What is equal depth binning?
It divides the range into N intervals, each containing approximately same number of samples
80
What is a rule antecedent & consequent?
Antecedent: The condition for a rule (left side)
The end result for a rule (a class). "The consequent" (right side)
81
Why is a large data set required for Bayes classifiers?
Smaller data sets means rows have more influrence
Need repeated passes over the data
82
Why should a concept hierarchy be used in multi-level association rules?
Cuts down on the number of rules by grouping.
83
What is the most common evaluation measure for k-means clustering?
The sum of Squared Error (SSE)
84
What is the MAX method of defining similarity between clusters (inter-cluster similarity)?
Minimize the maximum distance from clusters (tends to produce "round" things).
85
What is the most popular hieararchical clustering technique?
Agglomerative clustering algorithm
86
In the Minikowski Distance, what is the formula equal to with values of 1 to 3 for r?
r= 1 is the hamming distance
r = 2 is the euclidean distance
r \> 3 ( ∞ ) is the supremum distance
87
How can the SSE be used to determine the # of clusters?
Plot the SSE vs k (the # of points?) and look for the knee in the curve.
\* The knee method is good for spehrical clusters because it may not be as pronouced otherwise.
88
What is frequent subgraph mining useful for?
computational chemistry, bioinformatics, spatial data sets,etc..
89
What is a confusion matrix?
It tells you how accurate your model is by showing you the TP FN FP and TN instances for a given classifier in a matrix format.
90
What are some of the characteristics of a KNN classifier?
- It's a lazy learner - It does not build a model explicitly - Classifying unknown records can be relatively expensive
91
What is confidence with respect to assocation rule analysis?
Measures how often items in Y appear in transactions that contain X.
{ X } → { Y }
92
What is hierarchical clustering?
A set of nested clusters organized as a heirarchical tree
Simply put, each cluster can have a sub-cluster
93
What is a model?
a model is an abstract representation of a real system
94
What 3 things does KNN classifiers require?
-The set of stored records -Distance metric to compute the distance between records -The value of k, the number of nearest neighbours to retrieve.
95
What is support count ( s ) with respect to assocation rule analysis?
The fraction of transactions that contain both X and Y.
Support determines how often a rule is applicable to a given data set.
{ X } → { Y }
96
What happens to the bias and variance as the complexity of a model grows (for example, the number of nodes in a decision tree).
If you increase the # of nodes (the complexity of the tree) the variance will increase and the bias will decrease.
97
What is the basic idea of the bisecting k-means algoirthm?
to obtain k clusters, split the set of all points into two clusters, select one of these clusters to split and so on, until k clusters have been produced.
98
How can outliers be visualized in 1 or 2 dimensions?
Box plots, histograms, and scatter plots
99
What are 2 main challenges for mining infrequent patters in asswocation rule analysis?
1. how to identify interesting infrequent patters
2. how to efficently discover them in large data sets
100
what are 3 things that can cause outliers?
measurement error
collection error
natural variation
101
What are some of the disadvantages of using a concept hierarchy for association rule analysis?
Items residing at the higher levels tend to have higher support counts than those resideing at the lower levels. Only the patterns residing in the higher levels are likely to have patterns extracted.
Conversely, if the threshold is set too low, then you get too many rules.
Increases computation time.
May lead to redundant rules.
102
What is boosting with respect to data mining and ensemble methods?
Give more emphasis on specific examples that are difficult to classify. Assign a higher weight, greater probability of being selected to them.
Records that are wrongly classified will have their weights increased.
Records that are classified correctly will have their weights decreased.
103
What are the two strengths of hierarchical clustering?
They do not have to assume any particular number of clusters
They correspond to meaningful taxonomies (eg, biological sciences -- animal kingdon)
104
Compare APRIORI and FP Growth
Apriori pruning strategy: If an itemset is infrequent, then all of its supersets must also be inrequent. All of these infrequent itemsets can be pruned. Multiple scans of DB.
FP-Growth: encodes the data set using a compact data structure called an FP-tree and extracts frequent itemsets directly from this structure. Divide and conquer approach. Outperforms the standard Apriori algorithm by several orders of magnitude. Requires less memory. Scan DB only twice.
105
What is frequent subgraph mining?
Extends assocation rule mining to find frequent subgraphs.
Graphs that extend to subraphs
Looking for common subgraphs
106
Describe how the Apriori algoirthm works.
Every item is considered as a candidate 1-itemset {cola}. Discard itemsets that don't meet support threshold.
Do the same with 2-itemsets using only the frequent 1-itemsets (because the Apriori principal holds).
Repeat for the maximum number of items in an itemset.
107
Why are support vector machines a popular choice of classifer?
They don't get stuck in a local minimum like ANNs and KNNs. Especially when the data is transformed to a new space.
108
Explain the minimum spanning tree (MST) method for divisive hierarchical clustering.
1. Start with a tree that consists of any point
2. In successive steps, look for the closet pair of points such that one point is in the current tree and the other is not.
3. Add the point that is not to the tree into the tree and put an edge between these two points
(this is a top down approach; it is uncommon and rarely used)
109
Describe the algorithm for DBSCAN
1. Label all points as core, border, or noise points
2. Eliminate noise points
3. Put an edge between all core points that are within the user specified radis (Eps) of each other
4. Make each group of connected core points into a speerate cluster
5. Assign each border point to one of the clusters of its associated core points
110
What are some solutions to the k-means initial centroid problem?
1. multiple runs (not the best approach)
2. sample and use hierarchical clustering to determine intial centroids
3. select more than k intiial centroids and then select among these initial centroids
4. postprocessing
5. Bisecting k-means (split clusers into multiple clusters)
111
what is a contexual outlier?
the anomaly completely depends on the context that you are looking at.
112
What is an association rule with respect to association rule mining?
An implication expression of the form X → Y where X and Y are itemsets.
e.g. { milk, diaper } → { beer }
113
WHat are some of the problems and limitations of hieararchical clustering?
cannot undo a decision once two clusters have been combined
no objective function is directly minimized
have problems with one or more of the following:
sensitivity to noise
difficulty handling different sized clusters and convex shapes
breaking large clusters
114
Describe Maximum Margin Hyperplanes for SVMs.
There are infinitely many hyperplanes (ways to split classes in a model).
The SVM must choose one of the hyperplanes to represent its decision boundary, based on how well they are expecte4d to perform on test examples.
Trying to maximize the width of the "road" / margin.
115
What is the difference of partial vs complete clustering?
In some cases, we only want to cluster some of the data.
116
What is lift?
A measure used to evaluate interestingness in association rule analysis that takes prior probabilities into account.
It's much more reliable than other techniques such confidence level.
If the lift value is around 1, we can assume that the rule is statistically independent.
117
What was can the similarity between clusters be defined?
1. Min
2. Max
3. Group average
4. Distance between centroids
5. Other methods with a defined method
118
What are the characteristics of the hierarchical clustering algorithm?
works if the # of clusters are unknown (a horizontal cut in the dendogram specifies the # of clusters)
can set a max distance for threshold
complete clustering
noise depends on linkage criteria
deterministic
119
What is an example of time series anomaly application?
ECG patterns
120
Describe an FP tree used by the FP growth algoriothm for frequent itemset generation
Reads data set one transaction at a time
Maps each transation onto a path in the FP-tree
Paths may overlap as transactions are similar
The more paths overlap, the more compression
Sometimes makes tree small enough to fit into main memory
121
What is hetrososcedasticity?
variance that you would expect to see
Specifically, it refers to the distribution of numbers for one variable in relation to the distribution of numbers for another variable.
find points that would defy this for outlier detection
122
How are non asymmetric binary attributes handled in association rule analysis?
Binning and descretization.
123
Association rule mining: what is confidence?
Confidence is an indication of how often the rule has been found to be true.
conf = (X -\> Y) = supp(X,Y) /supp(X)
Fx:
**Support milk: 5 = 5/10 = 0.5
conf = milk -\> diapers 4/5 = 0.8**
124
Explain the purpose of relative index measure of cluster validity
used to compare two different clusterings or clusters
125
What is the commonality between subgraph mining, sequential pattern mining, multi-level assocation rules, etc...
They all come down to preprocessing the data so that the APRIORI algorithm can be applied to them.
126
Describe a model with high bias, but low variance.
A model constructed with high bias and low variance tends to underfit training data.
127
Describe how the sum of squared error SSE as an evaluation measure for k-means clustering is evaluated
For each point, the error is the distance to the nearest cluster.
To get the SSE, we square the errors and then sum them.
128
what is the cluster cohesion internal measure for cluster evaluation?
measures how closely related objects in a cluster are
measured by the wihtin cluster sum of squares (SSE)
129
What is the difference between exclusive and non-exclusive clusterings?
In non-exclusive clusterings, points may belong to multiple clusters.
130
What is the Apriori Principle with respect to association rule analysis?
If an itemset is frequent, then all of its subsets must also be frequent.
{A B C} = frequent then {A B }, {A C}, {B C} = frequent
Conversely, if an itemset is infrequent, then all of its supersets must be infrequent too.
{A B }
infrequent itemsets can be pruned
131
What are the 3 main clustering algorithms?
K-means (and it's variants)
Hierarchical clustering
Density-based clustering
132
What is variance?
Variance is a measure of spread of data
133
How is the decision boundary selected in SVMs?
The goal is to maximize the width of the margin "road".
134
What are some of the disadvantages ofthe Apriori Algorithm for generating frequent itemsets?
Still incurs considerable I/O overhead since it requires making several passes over the transaction data set.
May degrade significantly for dense data sets because of the increasing width of transactions.
135
What are two applications of cluster analysis?
Understanding: group related items that have similarities
Summarization: reduce the size of large data sets
136
What sort of rules can be created with continuous attributes?
Age(21,35) ^ Salary(70k,120k) - \> buy
137
Exam question: think about how to work with noisy data and what this means with respect to bias and variance.
A model with high variance and low bias tends to generalize new test instances well, but is susceptible to overfitting noisy data.
If data is noisy, perhaps it's better to have high bias, and lower variance.
Choise of classifier is important.
Bagging and Boosting can help.
138
What can be done to reduce the amount of sequence data with respect to association rule mining?
preprocessing
139
How can patters be extracted from sequence data?
The Apriori principal holds for sequential data becase any data sequence contains a particular k-sequence must also contain all of its (k-1) subsequences. An Apriori-like algorithm can be used to extraxt sequential patters from a sequence data set.
140
What is cluster analysis?
Finding groups of objects such that the objects in a group are similar (or related) to one another and different from (or unrelated to) objects in other groups.
141
How are the number of clusters chosen for k-means?
user specified number of clusters
142
What is a statistical approach for outlier detection?
1. use a parameter based model which describes the distribution of the data (eg gaussian distribution etc...)
2. apply statistical tests which depend on the:
distriubtion of the data
population parametes or sample statistics
number of expected outliers
143
How is similarity and dissimilarity defined for ordinal attributes if p and q are the attribute values for two data objects?
values are mapped to integers 0 to n-1 where n is the # of values
dissimilarity = p - q / # of values (n)
similarity = 1 - p-q / # of values (n)
144
What statistical measure is often used for clustering and why?
The median is often more appropriate because outliers affect the mean greatly.
145
What is an instance-based classifier?
Stores the training records Uses the training records to predict the class label of unseen cases
146
What is equal width binning?
divides the range into N intervals of equal size
147
What are the strengths of hierarchical clustering using MIN for inter-cluster similarity?
Can handle non-elliptical shapes.
148
Is a brute-force approach feasible with respect to association rule mining?
It's computationally prohibative.
It would involve:
list all possible assocation rules
computing the suppor tand confidence for each rule
prune rules that fail the minsup and minconf thresholds
149
What is an ensemble method for classification?
Improves classification accuracy by aggregating the predictions of multiple classifiers.
150
How can frequent subgraphs be found from graphs in association analsysis?
Transform each graph into a transaction-like format so that existing algorithms such as Apriori can be applied.
151
Describe 2 preprocessing steps commonly used for k-means clustering
Normalize the data (it's distance based)
Eliminate outliers
152
How can the best threshold for Eps (radius) and MinPts (density) in DBSCAN be found?
Plot the distance of every point to its kth nearest neighbour, then find the biggest change or "knee" in the curve.
153
What is similated annealing?
A momentum term to avoid falling in a local minimum.
A noise term used over multiple iterations. At first the term is very noisy and gets less noisy as tree becomes more accurate. Tries to prevent a local minimum.
154
What is an outlier / anomaly?
A point, patter, or set of patterns which do not conform to what we define as normal within the data
155
In the Apriori frequent itemset generation algorithm, what is a hash tree used for?
Determining if each enuerated k-itemset corresponds to an existing candidate itemset.
156
How are cadidate k-subgraphs pruned after they have been generated in assocation analsysis?
repreatedly remove an edge from the candidate k-subgraph and checking whether the correspnding (k-1) subgraph is cnnneted and frequent.
157
What are the 2 approaches to evaulating an outlier?
1. outlier label: a point or group of popints are labeled as an anomaly or normal
2. outlier score: assign an outlier score to a data point or group of data points
represents degree of outlierness
can create a ranked list or use a threshold
158
What is the 2 step approach to assocation rule mining?
1. Generate all itemsets whose support \>= minsup
2. Generate high confidence rules from each frequent itemset, where each rule is a binary partitioning of a frequent itemset.
159
How are rules generated in association rule mining?
Find all non-empty subsets in a given frequent itemset such that such that the subset satisfies the minimum confidence requirement
160
Using ensemble methods, what can be done to a classifier if one classifer performs better than others.
If one classifier is better than others, you can weight the vote of the classifiers and make the better performing classifier have a higher weight.
161
What is a linear regression?
a simple linear regression is basically an equation of a line
162
When a model is overfit, what happens to the test and training error rate?
Test error rate increases Training error rate continues to decrease
163
What is one of the most common clustering algorithms?
K-means
164
Describe 3 post processing steps commonly used for k-means
Eliminate small clusters that may represent outliers
Split 'loose' clusters with relatively high SSE
Merge clusters that are 'close' and have relatively low SSE
165
What preprocessing techniques are required for ANNs?
- remove redundant or irrelevant features
- transform to numerical values
- normalize data to the range of 0 to 1 or -1 to 1
166
Explain the agglomerative clustering algorithm
1. Compute the proximity matrix
2. Let each data point be a cluster
3. repeat
4. merge the two closest clusters
update the proximity matrix
6. until only a single cluster remains
167
Define similarity
a numerical measure of how alike two data objects are
it is higher when objects are more alike
often falls in the range of 0 and 1
168
Define support with respect to association rule mining.
The fraction of transactions that contain an itemset.
s ( { milk, bread, diaper } ) = 2/5
169
What is the anti-monotone property with respect to association rule analysis and support-based pruning?
The support for an itemset never exceeds the support for its subsets.
170
Why should a data miner be skeptical of an algorithm that just runs repeatedly over and over (for example k-means that can fall into a local minimum)
This introduces bias -- a data miner could simply pick the iteration that produced the best result if they wanted.
It's better to do some form of smart sampling or preprocessing instead.
171
Describe the back propogation algorithm used for ANNs.
1. Present sample to input nodes.
2. Propogate data through layers
3. Calculate results at output nodes
4. Determine error at output nodes
5. Propogate error backwards to adjust the weights
Repeat until stopping criterion is satisified
172
Describe the Feedback-based learning method for ANNs.
Corret behavior should be rewarded by increasing weights
173
\* on exam
What is a ROC curve?
Reciever Operating Characteristic (ROC)
It can be used to visualize the TP (x) vs FP rate (y) of a given model.
It also allows for relative comparrison across different models (each model is represented by a curve).
174
what is novelty detection?
related to anomaly detection but is a field of it's own
the outlier hasn't occured yet, and is only an outlier for a brief period of time and then it becomes a part of the normal model
175
What is an anti-monotone property with respect to association rule mining?
The support for an itemset never exceeds the support for its subsets.
176
what is a collective outlier?
the outlier exists as a seuqnce
AAABBBAAABBB**ABABAB**AAABBBAAABBB
177
How are graphs represented as transactions?
Transform to matrix using adjaceny lists
You can add edge weights but this blowes up the matrix even more.
178
Can outliers be detected in 3 or more dimensions?
Can't directly visualize -- very difficult
179
What is the minkowski distance?
a generalization of the euclidean distance
it's the same as the euclidean distance, but with a parameter r instead of 2
This r parameter gives more flexability. n is the # of parameters.
n is the # of dimensions (attributes)
180
Why is it important to remove redundant or irrelevant attributes in an ANN?
The # of attributes determines the # of input nodes, so its important to remove redundant or irrelevant attributes to keep down the # of connections and avoid a local minimum.
181
Explain the SMOTE method for anomoaly detection
automatically determines the minority class
finds the k nearest neighbours for each minority class
randomly chooes from ke nearest neighbours depending on level of oversampling required
creates a syntehci point along the line sequents connnectiong that points to its k nearesa neiughbor
182
What are center-based clusters?
An object in a cluster is closer (more similar) to the center of a cluster, than to the center of any other cluster.
These types of clusters thend to be globular.
183
Define density with respect to density-based outlier detection.
The density around an object is equal to the # of objects taht are within a specified distance d of the object.
184
Combinatorics & Binomial coefficient
**Combinatoric explosion**: how many different transactions could possibly
occur in the database?
Formula is 2^n (fx: 2^3 = 8 for 3 items) (includes empty set)
* *Binomial coefficient (when its itemsets)**
* *!n/!k(n-k)!** (k is nr of itemsets, n is number of items in D)
How many transactions with exactly 2-itemsets can we have when the database contains
3 and 5 items?
```
3!/2!(3-2)! = 3
5!/2!(5-2)! = 10
```
**Putting it together
What is the maximum size of frequent itemsets that can be extracted (assuming sigma\> 0)?**
See pic - binomial \* 2^n -1
185
What is a well-seperated cluster?
Clusters where points are closer to points in the same cluster than to points in every other cluster.
186
How can the Apriori and FP-growth algorithm be compared to heapsort and merge sort?
Work before vs work after
Lazy learner vs eager learner
187
What is the nearst neighbour approach for outlier detection?
compute the distance between all pairs of points
outlier score can be defined as the distance from the kth nearest neighbour or the average distance from the k-nearest neighbours
188
How is similarity and dissimilarity defined for nominal attributes if p and q are the attribute values for two data objects?
similar if p = q and dissimilar if p \<\> q
189
What is Bayes theorem?
190
How many training sets are required in an ANN?
The number of training sets has to be larger than the # of weights divided by (1 - accuracy).
Training sets = weights / (1 - accuracy)
191
What are some measures used to describe confidence level?
There are over 20...
Gini index
Jaccard
Cosine
Intersect
Laplace...
192
What can be the issue with choosing the value of K for KNN?
- If k is too small, the model is sensitive to noise points - If k is too large, the neighbourhood may include points from other classes
193
What are the limitations of MIN for hierarchical clustering?
sensitive to noise and outliers
194
What is the assumption of the linear agression approach to outlier detection?
The error term is distrubted normally
195
define the cluster seperation measure for cluster evaluation
measures how distinct or well-seperated a cluster is from other clusters
measured by the between cluster sum of squares
196
What are some challengs in outlier detection?
defining normal regions
evolving definition of normal
differing notion of anomalies
number of attributes used to define an anomaly
noise
197
Define support count with respect to association rule mining.
The frequency of occurances of an itemset.
Denoted by σ
e.g. σ ( { milk, bread, diaper } ) = 2
198
When does the DBSCAN clustering algorithm run into issues?
DBSCAN doese not work well for clusters that have varying densities
199
What are two rule evaluation metrics with respect to assocation rule analysis?
Support ( s )
Confidence ( c )
200
In clustering, what is the technique of distinguishing whether non-random structure actually exists in the data
Clustering tendency
201
How can interestingness measure be computed?
Interstingness can be computied using a contingency table.
202
Describe overfitting with respect to the bias-variance decomposition.
Overfitting is modelling a random noise component in the data (model is too complex).
Increasing the complexity of the model means you have to estimate more parameters and their is a greater probability for error.
Simpler models tend to have low variance and potentially higher bias.
Vizualization can help you to pick a good model.
203
What is a Voronoi diagram?
It's basically a model for KNN. It splits the solution space.. on a line = equal distance to parents on an intersectoin = equal distance to 3 parents
204
What happens when items from the left side of the rule are moved to the right side of the rule?
Confidence can only decrease.
If a parent doesn't meet the confidence threshold, the children whon't meet the threshold either.
205
What is a contiguity-based cluster?
two objects are connected only if they are within a specified distances of each other.
206
What are some applications of anomaly detection?
intrusion detection fraud, medical, image processing
207
What is a noise point in DBSCAN?
A noise point is any point that is not a core point or a border point
208
What are the 3 types of outliers?
1. point
2. contextual
3. collective
209
What are some applications of neural networks?
pattern association
character recognition
image compression
classification
forecasting
optimization
etc...
210
What is the algorithm for k-nearest neighbour?
Compute the distance between two points (Euclidean distance) Determine the class from nearest neighbour list - take the majority vote of class labels among the k-nearest neighbours - weight the vote according to distance
211
Explain how a proximity graph bbased approach can be used for cohesion and seperation cluster evaluation
cluster cohesion is the sum of the weights of all the links within the cluster
cluster seperation is the sum of the weights between nodes in the cluster and nodes outside the cluster
212
what is a point outlier?
a point within a graph
213
What is hierarchical clustering?
produces a set of nested clusters organized as a hierarchical tree
these clusters can be vizualized as a dendogram (a tree like structre that records the sequences of merges and splits)
214
What is percision?
Determines the fraction of reecords that actually turns out to be positive in the group the classifier has declared as a positive class.
TP / ( TP + FP )
215
Ex: Confidence pruning
216
What is the issue with evaluating clusters?
Clusters are in the eye of the beholder (they are subjective)
217
what are the disadvantages of using the k-nearest neighbour approach for outlier detection?
computationally expensive
sensitive to the chosen value of k
measningless in high dimensional space
218
How is similarity and dissimilarity defined for interval or ration attributes if p and q are the attribute values for two data objects?
similarity = | p - q |
disimilarity is equal to the negative value of similarity
219
What is multiple minimum support?
You can use different support counts for different support items.
220
What does a high correlation and a low correlation mean with respect to cluster evaluation?
A high correlation means a good clustering, a low correlation means a poor clustering.
221
What is a core point in DBSCAN?
A point is a core point if it has more than a specified number of points (MinPts) within Eps (a specified radius)
222
What is the formula for Euclidean distance?
223
Association rule mining: what is support?
The count of the itemset (then / with total nr of T)
fx the itemset {milk,diapers} has a support of 1/5=0.2 since it occurs in 20% of all transactions (1 out of 5 transactions).
224
What two factors introduce bias into cluster analysis?
The distance measure
The use of clustering algorithm
225
What are maximal frequent itemsets useful for?
Providing a compact representation of frequent itemsets. They form the smallest set of itemsets from which all frequent itemsets can be derived.
226
Explain cluster based methods for anomaly detection
points that are not strongly related can be considered as outliers
cluster, remove outlier, repeat
requires a stopping criterion
227
What is support based pruning with respect to association rule analysis?
trimming the exponential search space based on the support measure.
228
What are some of the characteristics of Naive Bayes classifiers?
Robust to noise points
Can handle missing values by ignoring the instance during probability estimate calculations
Robust to irrelevant attributes
Independance assumption may not hold for some attributes (but can use other techniques such as bayesian belief networks instead)
229
characteristics of DT
+ easy to explain
+ interpretable
+ works with categorical variables
+ fast
- high variance (A DT has high variance because, if you imagine a very large/deep tree, it can basically adjust its predictions to every single input because it gets very specific with the training examples
230
How is the closeness of k-means clusters evaluated?
Using a distance measure such as Euclidean distance, cosine similarity, correlation, etc...
231
What are the two methods for extracting classification rules?
1. Direct methods which extract rules directly from the data 2. Indirect methods which extract rules from other classification models such as decision trees. `
232
What can produce considerably different results in the k-means algorithm?
the choice of inital centroids
233
When are density-based clusters used?
when the clusters are irregular or itnertwined and when noise and outliers are present
234
What is the purpose of evaulating clusters if they are subjective?
To avoid finding patterns in noise
To compare clustering algorithms
To compare two sets of clusters
To compare two clusters
235
Describe the apriori pruning algorithm for association rule analysis
Initally make a pass over data to determine the support of teach item and determine 1-itemsets.
Iteratively generate new candidate k-itemsets using the k-1 itemsets found in the previous iteration.
Make an additional pass over the data set to count the support of canddiates and eliminate candidates whose support is less than minsup.
Terminate when there are no new frequent itemsets generated.
236
Define frequent itemset with respect to association rule mining.
An itemset whose support is greater than or equal to a minsup threshold.
e.g. at least 10 occurances together in the database.
237
What are the 3 common responses to outliers?
1. removal
2. accomodation - keep but use accomodation methods while processing
3. explanation - why does it exist?
238
What is DBSCAN for clustering?
DBscan is a density based algorithm used to find clusters
239
What is F measure?
A measure that tries to maximize both precision and recall.
F1 = 2 x TP / ( 2 x TP + FP + FN )
240
Parameters for DT's
min. leaf size (Each leaf node represents a class)
Pruning a decision tree (pre & post)
max depth of the tree
max nr of nodes
min decrease in loss
241
What is a residual?
a residual is a vertical line sprouting off of the diagonal line of a linear regression
242
What are 2 problems of the k-means clustering algorithm?
K means has problems when clusters differ in size, densities, and are non-spherical (globular) shapes.
K-means has problems when the data contains outliers.
243
are similarity and dissimilarity opposites?
no. one is not the opposite of the other, unless the range is from 0 t o 1.
244
What are the 3 strategies for Frequent Itemset Generation?
1. Reduce the number of candidates (M) using pruning
2. Reduce the number of transactions by reducing the size of N as the size of the itemset increases
3. Reduce the number of comparisions by using efficient data structures to store candidates or transactions. No need to match every candidate against every transaction.
245
What is the silhouette coefficient for internal measures of cluster evaulation?
combines ideas of both choesion and speeration, but for individual points, as well as clusters and clusterings
looks as closeness within a cluster and closeness between clusters
246
What is a density based cluster?
A cluster where a dense region of objects is surrounded by a region of low density.
247
What are 2 problems with discretization of continuous attributes in assocation rule mining?
Execution time (possible ranges of values)
Too many rules
{refund = No, Income {cheat = no}
{refund = No, 90 k Income {cheat = no}
{refund = No, 50K \< Income \< 52K } -\> {cheat = no}
248
Distinguish between outliers created by noise an anomalies
noise is often created by measurement error, extreme values
noise is typically uninteresting and generally meaningless
Anomalies are data points created by different mechanisms - usually very interesting
249
What is the objective of rule generaiton with respect to association rule analsysis?
Extract all the high-confidence rules from the frequent itemsets found in the previous step (frequent itemset generation). These rules are called strong rules.
250
What are the 3 componetnts in the DBSCAN algoirthm?
1. core point
2. border point
3. noise point
251
Describe a model with high variance and low bias.
A model with high variance and low bias tends to generalize new test instances well, but is susceptible to overfitting noisy data.
252
What are the characteristics of the K-means clustering algorithm?
Uses a user specified number of clusters
Paritioned-based
Complete clustering
Non-deterministic (can exhibit different behaviors on different runs)
noise stays in space and contributes to SSE
253
What is association rule mining?
Given a set of transactions, find rules that will predict the occurance of an item based on the occurences of other items in the transaction.
254
What are 3 measures of cluster validatiy?
External index
Internal index
Relative index
255
What is the difference between hierarchical and partitional clustering?
The most common distinction is whether the set of clusters are nested (hierarchical) or unested.
256
What is a Bayes classifier?
A probabilistic framework for solving classification problems. It uses conditional probability.
257
what is the advantage of using the nearest neigubhour approach for outlier detection?
highly granular (detailed)
258
How can outlier be detected in 3 dimensions?
3 dimensional scatter plots
259
What is a cost matrix?
A cost matrix assigns a cost to the TP FN FP TN instances. It's good for imbalanced classes. You can assign a high cost to instances that are classified incorrectly.
The goal is to have high accuracy and low cost.
260
Describe the competitive learning, learning method for ANNs.
Competative learning
- For each sample (set of input value, one node wil lbe the best match. The weights between this winner and the input nodes should be increased.
261
define proximity
refers to a dimilarity or dissimilarity
262
What are support vectors?
Points in a SVM that lie next to the maximized margins. SVMs use a subset of training examples called support vectors.
263
What is a clustering?
A set of clusters
264
What are multi-level association rules?
Items are grouped into categories which cuts down on the # of items. There are then hierarchical levels.
For example, Electronics as the root, then computers... etc..
265
What is an itemset lattice?
A series of connected nodes that show all possible combinations of an itemset, and sometimes a subset of combinations.
266
What is the relationship between closed frequent itemsets, maximal frequent itemsets and frequent itemsets?
Maximal freuqnet itemsets are subset of closed frequent itemsets. Closed frequent itemsets are a subset of frequent itemsets.
267
What is a closed itemset with respect to association analsysis?
An itemset is closed if none of its immediate supersets has the same support as the itemset.
268
What are the conseuqnces if the minsup threshold is too high?
itemsets involving interesting rare items (e.g. expensive products) could be missed.
269
What is the group average method used for cluster similarity?
proximity of two clusters is the average pairwise proximity between points in the two clusters
270
What are closed frequent itemsets?
Provide a mininimal representation of itemsets without losing their support information.
An itemset is a closed frequent itemset if it is closed and its support is greater than or equal to minsup.
271
What is the objective of frequent itemset generation with respect to association rule analysis.
Find all the itemsets that satisfy the minsup threshold. These itemsets are called frequent itemsets.
272
What are 3 methods used for evaluating the performance of a classifier?
1. Holdout (part data training, part data testing)
2. Random subsampling (repeating holdout several times)
3. Cross validation (each record is used the same # of times for training and 1 time for testing) 4. Bootstrap - sample w/ replacement
273
What is cluster evaluation
proposes ways of evaluating unsupervised classifiers (clustering)
evaluating unsupervised classifiers is much more difficult (you can't use measures such as accuracy and class labels, etc...)
274
Why is post processing important in k-means clustering algorithms and clustering algorithms in general?
Unsupervised approaches don't give us feed back about how good our model is. Thsi is why post-processing is important.
275
What is one of the issues with the k-means clustering algorithm?
The cluster centres are usually picked randomly (but you can pick them to speed things up).
This increases the likeliness of the model getting stuck in a local minimum.
276
define dissimilarity
a numerical measure of how different two data objects are
lower when objects are more alike
minimm dissimilarity is often 0
upper limit varies
277
What factors affect the complexity of the Apriori algorithm?
Support threshold (lower the threshold results in more itemsets being declared as frequent)
Number of items (dimensionality - more space will be required to store the support counts of items).
The number of transactions (Apriori makes repeated passes over data set - increases with larger # of transactions)
Average transaction width - dense data sets, the average transaction width can be large.
278
What is sequence data with respect to association rule analysis?
Examines events that occur over time over customers.
Events can be grouped together.
Becomes computationally expensive.
279
Does SVM try to find a global minimum or emply a greedy based strategy to search the hypothesis space?
SVMs try to find the global minimum unlike neural networks, which employ a greedy based strategy to search the hypothsis space.
280
What would the model of a classifier that makes random guesses look like on a ROC curve?
A line across the main diagnonal connecting 0,0 and 1,1.
281
Describe the FP Growth Algorithm
An alternative method for discovering frequent itemsets
It encodes the data using a compact structure called an FP-tree
It extracts frequent itemsets directly from the structure.
282
Describe a high-level overview of how ensemble methods work.
An esemble method constructs a set of base classifiers from training data and performs classification by taking a vote on the predictions made by each base classifier.
283
What are 2 internal measures for cluster evaluation?
cluster cohesion
cluster seperation
284
What is the issue of measuring cluster validity via correlation?
it's not a good measure for some density or contiguity (connected) based clusters
285
What is the MIN method of defining inter cluster similarity?
link the next closest point from another cluster
286
What is the differnces between hetrogenous vs homogeneous clustering?
Clustering of same type or different types.
For example, clusters can vary widley in size, shape, and densities.
287
Explain the purpose of internal index measure of cluster validity
Used to measure the goodness of a clustering structure without respect to external information
288
How is the probability for continuous attributes used in Bayes theorm?
Discretize the range of values into bins
- Can use two way split (A \< v) or (A \> v)
- Or Probnability density estimation
assume the values follow a normal distribution
Use data to estimate parameters of distribution
Can use it to estimate conditional probability
289
What is a Naive Bayes Classifier?
It assumes independence among attributes.
290
What are some reasons overfitting can occur?
Fitting noise points
Not enough representative data
