Transcript Algorithms

Algorithms
Emerging IT Fall 2015
Avenbaum, Hamilton, Mirilla, Pisano
Team 1
• Algorithm Basics (intro)
– PB&J
AGENDA
• Algorithms in computing
• Popular Algorithms for data mining
• Conclusion
History of Algorithm
• A book on algebra written by Al-Khwarizmi
– The term ‘algebra’ was translated from the title
as al-jabr and Al-Khwarizmi became algoritme
and later algorithm
• The concept of algorithms has existed for
centuries
• Animate This offers 2500 BC as one of the
earliest citations of a documented algorithm
Algorithm distilled
Algorithm:
1. Input
2. Finite number of steps
3. Outputs
Also important, a well stated goal or
objective
From Wikipedia
• …self-contained, step-by-step operations
to be performed
• For math and computing the goal of
algorithms is calculation, data processing
and automated reasoning
• What algorithms do you use daily?
Related Side Bar: How to…
• Give some thought to all the little steps
involved when:
– Making a PB&J or other favorite sandwich
– Coffee or Tea in the morning
– Morning ritual or preparations
More Formal – any textbook
• Effective method that can be expressed
within a finite amount of space and time
• …in a well-defined formal language
• For calculating a function
• Initial state and initial input
• A finite set of Instructions to be executed
with well defined successive states
• May produce output
• Terminates in an ending state
CLRS – Introduction to
Algorithms
•
Cormen, T, Leiserson, C, Rivest, R & Stein, C (2009). Introduction to Algorithms Third
Edition. The MIT Press
• a tool for solving a well-specified computational
problem.
• statement of the problem specifies in general
terms the desired input/output relationship
• describes a specific computational procedure
• CORRECTNESS:
--for every input instance, it halts with the correct
output.
Real-World Algorithm
• Fourier Transform
– This transforms signals from their time
domain into their frequency domain and
vice versa.
– The internet, your WiFi, smartphone,
phone, computer, router, satellites, almost
everything that has a computer inside uses
these algorithms in one way or another to
function.
Sorting Algorithms
• Bubble Sort
– Simple sorting algorithm
• Quick Sort
– Classic Divide and conquer
•
•
•
•
Insertion Sort - closest to how most people sort things
Selection Sort –also close to how people sort things
Merge Sort –better divide and conquer
Heap Sort -Priority queue to reduce search time
• O(n log n) – general worst case
Advanced Examples
“Top 10 Data Mining Algorithms” -2007
Wu, Kumer, et al
Systems that construct a classifier
• input: a collection of cases
– Each belong to one of small number of classes
– Described by values for fixed number of attributes
• output: a classifier that accurately predict a
class to which a new case belongs
Advanced Examples
1. C4.5 Algorithm – grow a decision tree
using divide-and-conquer
2. k-Means Algorithm – iterative method
to partition a given dataset into a user
specified number of clusters, k.
3. SVM –support vector machine for
machine learning.
Advanced Examples
4. The Apriori Algorithm -characterized as a
level-wise complete search algorithm using antimonotonicity of itemsets, “if an itemset is not
frequent, any of its superset is never frequent”.
5. Expectation-Maximization (EM) Algorithm.
-Finite mixture distributions provide a flexible
and mathematical-based approach to the
modling and clustering of data observed on
randdom phenomena
Advanced Examples
6. PageRank –statically rank web pages based
on number of links leading to it and other simple
characteristics (still classification algorithm)
7. AdaBoost – Ensemble Learning employs
multiple learners to solve a problem
8. kNN Algorithm.
k-nearest neighbor classifier algorithm
-the simplest of machine learning algorithms,
classifications based on nearest neighbor
Advanced Examples
9. Naïve Bayes –easy to construct and apply to
large data sets
10. CART– Classification and Regression Trees
--Binary recursive partitioning procedure
--capable of processing continuous and nominal
attributes both as targets and predictors
Conclusion (Validation)
• Algorithm should be FINITE
– If it never ends it is useless for solving a problem
• Well defined instructions
– Unambiguously specified or precisely defined.
• Effective
– Should solve the problem it was designed to solve
– Verifiable convergence (provable on paper)
The End