Title: Theory / Important / CS / Algo / Database / Database System Concept 6 - McGraw Hill+27{ / 20 Big data

Name: Data warehouse
Definition: a repository (or archive) of information gathered from
multiple sources, stored under a unified schema, at a single site
Page: 885
Chapter: part 6

Name: Data mining
Definition: The process of discovering pattern from data warehouse.
Page: 885
Chapter: part 6
Example: Product bought together

Name: Dirty data
Definition: data containing error
Page: 885
Chapter: 20

Name: Transaction processing system
Definition: A database used for day to day operation
Page: 885
Chapter: 20
Section: 1
Definition2: (recent) bank transaction
Example: forum, blog

Name: Decision support system
Definition: A database used for analysis
Page: 885
Chapter: 20
Section: 1
Definition2: history of stock prices
Example: history of transactions

Name: A source-driven architecture
Definition: A database that receives new information as they are sent
Page: 890
Chapter: 20
Section: 2.1
Context: database
Example: Database to register all transactions

Name: A destination-driven architecture
Definition: A database that request to receive new information when needed or scheduler
Page: 890
Chapter: 20
Section: 2.1
Context: database
Example: Wharehouse

Question: What is the fundamental downside of a warehouse
Answer: It is always out of date
Page: 890
Chapter: 20
Section: 2.1
Context: database

Name: data cleansing
Definition: Correcting and pre-processing data
Page: 890
Chapter: 20
Section: 2.1

Name: Fuzzy lookup
Definition: Assuming data may have typo, looking for the probably correct answer
Page: 890
Chapter: 20
Section: 2.1
Example: Use a city database to find the actual official name of an address

Name: Deduplication
Definition: Find duplicate entry in a database and merging their information into a single entry
Page: 890
Chapter: 20
Section: 2.1
Example: If you have multiple time the same user (e.g. by database acquisition), transform it into a single entry with all phone numbers, email, address you can find in any of those entry
Name2: Merge-purge operation

Name: Householding
Definition: Finding who lives in who
Page: 891
Chapter: 20
Section: 2.1
Intuition: Send a single advertisement by home, even if there are multiple clients

Name: A fact table
Definition: A table containing multidimensional data
Page: 891
Chapter: 20
Section: 2.2
Example: A table containing all transactions
Intuition: Contains foreign reference to dimension tables

Name: A dimension table
Definition: A table containing dimensions attributes
Page: 891
Chapter: 20
Section: 2.2
Example: e.g. informations about a store. A record of all transactions contains a foreign key to an element of this table instead of containing all informations regarding the shop

Name: The star schema
Definition: A database schema with a fact table with foreign key to dimension table that are self contained
Page: 892
Chapter: 20
Section: 2.2

Name: A snowflake schema
Definition: A database schema with a fact table with foreign key to dimension table that are also fact tables following the star or snowflake scehma
Page: 892
Chapter: 20
Section: 2.2

Name: Row-oriented storage
Definition: Database storage which store the entire content of a row together, storing rows sequentially
Page: 892
Chapter: 20
Section: 2.3

Name: Column-oriented storage
Definition: Each attribute of a relation is stored in separate files, with values from successive tuples stored as successive position in the file
Page: 892
Chapter: 20
Section: 2.3

Question: What are the interest of column oriented storage?
Answer: Saving time and bandwidth by only fetching data from column needed
Page: 893
Chapter: 20
Section: 2.3
Answer2: storing values of same type together help with compression

Question: What are the interest of row oriented storage?
Answer: Fetching a single tuple requires multiple I/O operations
Page: 893
Chapter: 20
Section: 2.3

Name: A rule
Definition: Knowledge guessed from database content
Page: 893
Chapter: 20
Section: 2.3
Context: data warehouse
Example: Young
women with annual incomes greater than $50,000 are the most likely people to
buy small sports cars

Name: Association
Definition: Finding that two things are often related
Page: 893
Chapter: 20
Section: 2.3
Context: data warehouse rule
Example: people who bought this generally bought that

Name: Prediction
Definition: Guessing future state of the world
Page: 893
Chapter: 20
Section: 2.3
Context: data warehouse rule
Example: credit worthyness
Example2: Who will switch to a competitor

Name: Classification
Definition: Given past training, guess to which instance does a row belong
Page: 895
Chapter: 20
Section: 2.3
Context: data warehouse

Name: Purity of a set
Definition: A measure such that a set, if all elements have the same classification, the measure is 0
Page: 895
Chapter: 20
Section: 4.1.2
Context: data classification
Example: gini measure

Name: The gini measure of a set of data
Definition: \[1 - \sum_{i=1}^np_i^2\] with \(p_i\) the proportion of elements of \(S\) having property \(c_i\)
Page: 895
Chapter: 20
Section: 4.1.2
Variables: Classification with values c_1, ..., c_n
A set \(S\) of elements having one of those values.
Context: data classification
Example: 0
Example2: \(1-\frac 1k\)
Applied to: A set with a single class
Applied to2: A set with as many elements in all classes

Name: The entroy of \(S\)
Definition: \[-\sum_{i=1}^kp_i\log_{2}(p_i)\] with \(p_i\) the proportion of elements of \(S\) having property \(c_i\)
Page: 895
Chapter: 20
Section: 4.1.2
Variables: Classification with values c_1, ..., c_n
A set \(S\) of elements having one of those values.
Context: data classification
Example: 0
Example2: \(\log_2k\)
Applied to: A set with a single class
Applied to2: as many elements in each class

Definition: \(\sum_{i=1}^r\frac{|S_i|}{S}\mathtt{purity}(S_i)\)
Page: 895
Chapter: 20
Section: 4.1.2
Variables: Classification with values c_1, ..., c_n
Disjoint sets \(S_1,\dots, S_r\) of elements having one of those values.
\(\texttt{Purity}\), a purity measure on set
Context: data classification,
Notation: \(\mathtt{Purity}(S_1,\dots, S_r)\)

Name: the information gain due to the partition of \(\bigcup_i S_i\) into \(\{S_i\}_i\)
Definition: \(\mathtt{Purity}(S)- \mathtt{purity}(S_1,\dots, S_r)\)
Page: 895
Chapter: 20
Section: 4.1.2
Variables: Classification with values c_1, ..., c_n
Disjoint sets \(S_1,\dots, S_r\) of elements having one of those values.
\(\texttt{Purity}\), a purity measure on set
Context: data classification,

Name: the information content due to the partition of \(\bigcup_i S_i\) into \(\{S_i\}_i\)
Definition: \(-\sum_{i=1}^r\frac{|S_i|}{|S|}\log_2\frac{|S_i|}{|S|}\)
Page: 895
Chapter: 20
Section: 4.1.2
Variables: Classification with values c_1, ..., c_n
Disjoint sets \(S_1,\dots, S_r\) of elements having one of those values.
Context: data classification,

Name: The best split
Definition: The attribute which has the information gain ration
Page: 895
Chapter: 20
Section: 4.1.2
Variables: Classification with values c_1, ..., c_n
A set of tuples \(S\) with attributes
Context: data classification,

Name: The information gain ratio
Definition: \(\frac{\mathtt{Inofrmation_gain}(S, {S_1,\dots, S_r})}{\mathtt{Inofrmation_content}(S, {S_1,\dots, S_r})}\)
Page: 898
Chapter: 20
Section: 4.1.2
Variables: Classification with values c_1, ..., c_n
Disjoint sets \(S_1,\dots, S_r\) of elements having one of those values.
Context: data classification,

Name: A continuous valued attribute
Definition: An attribute whose value can be ordered in a fashion meaningful to classification
Page: 898
Chapter: 20
Section: 4.1.3
Context: data classification,
Example: age
Example2: income

Name: A categorical attribute
Definition: An attribute without meaningful order
Page: 898
Chapter: 20
Section: 4.1.3
Context: data classification,
Example: Country
Example2: Department

Name: Binary split
Definition: Splitting a continuous attribute in two parts, below and above a threshold
Page: 898
Chapter: 20
Section: 4.1.3
Context: data classification,

Name: Multiway split
Definition: Splitting a continuous attribute in more than two bins
Page: 898
Chapter: 20
Section: 4.1.3
Context: data classification,

Name: Overfitting
Definition: A decision process that is trained so precisely on its input that it is not able to classify correctly other things
Page: 899
Chapter: 20
Section: 4.1.4
Context: data classification,

Name: Bayesian classifier
Definition: A system which computes the probability that \(e\in C_i\) for each \(i\) and returns the \(i\) maximizing this probability
Page: 900
Chapter: 20
Section: 4.2
Variables: \(C_1,\dots, C_n\) n distinct classes
\(e\in\bigcup C_i\)
Context: data classification,

Name: Naive Bayesian classifier
Definition: A classifier that assigns that each attributes are  independant
Page: 901
Chapter: 20
Section: 4.2
Variables: \(C_1,\dots, C_n\) n distinct classes
\(e\in\bigcup C_i\)
Context: data classification,

Name: Support vector machine
Definition: Classifying by assuming rows's attribute are number, so a row is a vector, using geometric intuition to classify
Page: 901
Chapter: 20
Section: 4.2
Variables: \(C_1,\dots, C_n\) n distinct classes
\(e\in\bigcup C_i\)
Context: data classification,
Abbreviation: SVM

Name: Regression
Definition: Given a sequence of rows, and a number associated to each of them, find a function from attributes to number which approximate the rows.
Page: 901
Chapter: 20
Section: 4.3
Context: data classification,

Name: Linear regression
Definition: For rows \(X_1,\dots,X_n\), find values \(a_0,\dots, a_n\) such that the number is approximated by \(a_0+\sum_{i} a_iX_i\). A kind of regression
Page: 901
Chapter: 20
Section: 4.3
Context: data classification,

Name: A true positive
Definition: A row, belonging to S, that is classified as belonging to S
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: A false positive
Definition: A row, not belonging to S, that is classified as belonging to S
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: A true negative
Definition: A row, not belonging to S, that is classified as not belonging to S
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: A false negative
Definition: A row, belonging to S, that is classified as not belonging to S
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: accuracy
Definition: the portion of data correctly classified
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: recall
Definition: The percent of positive that are classified as positive
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,
Name2: sensitivity

Name: Precision
Definition: The percent of data classed as positive that are positive
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: Specificity
Definition: The percent of negative classed as negative
Page: 903
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: Cross validation
Definition: Splitting the test set into k part. For i from 1 to k:
train with all data set but i
Test with data set i
If all test are positive, it means the training algorithm is correct
Page: 904
Chapter: 20
Section: 4.4
Variables: S a set
C a classifier for S
Context: Boolean classification,

Name: The support of \(p\implies q\)
Definition: The proportion of the population that satisfies the antecedant \(p\) and the consequence \(q\) of the rule
Page: 904
Chapter: 20
Section: 4.4
Variables: \(P\) a population
\(p, q\) predicates
\(R= p\implies q\) a rule
Context: rule

Name: The confidence of \(p\implies q\)
Definition: \(\frac{|q\cap p|}{|p|}\)
Page: 904
Chapter: 20
Section: 4.4
Variables: \(P\) a population
\(p, q\) predicates
\(R= p\implies q\) a rule
Context: rule

Name: Clustering
Definition: The problem of grouping points in \(k\) sets for a given \(k\) in an easily computable and meaningful way
Page: 907
Chapter: 20
Section: 6
Context: data warehouse

Name: Hierarchical Clustering
Definition: Clustering where the cluster have also subcluster
Page: 907
Chapter: 20
Section: 6
Context: data warehouse
Example: The tree of species, where life form have animals and plants, and animals have mamifere and ovipare and mamifere have carnivore and ominide, and so on

Name: Agglomerative Clustering
Definition: An algorithm that starts by building small cluster and aggregating them together into higher level
Page: 907
Chapter: 20
Section: 6
Context: data warehouse

Name: Divisive Clustering
Definition: An algorithm that starts by building a few number of cluster for the whole dataset, then divide those clusters into smaller clusters
Page: 907
Chapter: 20
Section: 6
Context: data warehouse

Name: Text mining
Definition: Applying data-mining techniques to textual documents
Page: 908
Chapter: 20
Section: 8
Context: data warehouse

Name: Data visualization
Definition: Displaying data in order to help user understand it more easily
Page: 909
Chapter: 20
Section: 8
Context: data warehouse
Example: maps, charts, and
other graphical representations

Name: Information retrieval
Definition: querying of
unstructured textual data
Page: 915
Chapter: 21

Name: A keyword of a document
Definition: A word associated to a document indicating a subject this document concern
Page: 916
Chapter: 21
Section: 1
Context: Information retrieval

Name: Full text retrieval
Definition: A system where all word in the document are considered to be keyword
Page: 916
Chapter: 21
Section: 1
Context: Information retrieval

Name: A term of D
Definition: A word appearing in D
Page: 916
Chapter: 21
Section: 1
Variables: D a document
Context: Information retrieval
Assuming: Full text retrieval

Definition: number of words in \(d\)
Page: 916
Chapter: 21
Section: 2
Variables: D a document
t a term
Context: Information retrieval
Notation: \(n(d)\)

Definition: number of time \(t\) appears in \(d\)
Page: 916
Chapter: 21
Section: 2
Variables: D a document
t a term
Context: Information retrieval
Notation: \(n(d, t)\)

Definition: number of document containing the term \(t\)
Page: 916
Chapter: 21
Section: 2
Variables: t a term
Context: Information retrieval
Notation: \(n(t)\)

Name: The relevance of \(d\) to \(Q\)
Definition: \(\sum_{t\in Q}\mathtt{TF}(d,t)\times\mathtt{IDF}(t)\)
Page: 916
Chapter: 21
Section: 2
Variables: \(d\) a document
\(Q\) a set of term
Context: Information retrieval
Notation: \(r(d, Q)\)

Name: A stop word
Definition: One of the most common word in the language used
Page: 918
Chapter: 21
Section: 2
Context: Information retrieval
Example: a, the, and
Intuition: It can't be used for a search, because it virtually occur in all document

Question: What can be used to determine whether in a document \(d\), a term \(t\) is relevant
Answer: the number of time it occurs
Page: 918
Chapter: 21
Section: 2
Context: Information retrieval
Answer2: whether it is in the title, abstract, or introduction
Answer3: whether it is closed to another searched term

Question: In a document \(d\), which terms are the most relevant as keyword
Answer: the terms that do not occur in a lot of other document
Page: 918
Chapter: 21
Section: 2
Context: Information retrieval
Answer2: term from abstract, title, introduction