Apr 15, 2018

House Prices: Advanced Regression Techniques

This project aims to implement and compare variant machine learning techniques for predicting house prices. It is an expanded project from Kaggle House Prices: Advanced Regression Techniques, such that the project is going to use the same dataset provided under this Kaggle competition. The machine learning techniques in this project include Linear Regression, Random Forest, Adaptive Boosting, Support Vector Regression, Gradient Boosted Decision Tree, K Nearest Neighbors, and Neural Network.

Adaptive Boosting Gradient Boosted Decision Tree K Nearest Neighbors Linear Regression Neural Network Random Forest Support Vector Regression

Mar 20, 2018

Data Mining

Comparing Classifiers on UCI Wine Dataset

In this article, the comparison of multiple classifiers will be performed on the "Wine" dataset from the UCI Machine Learning Repository.

Classification DecisionTreeClassifier GaussianNB KNeighborsClassifier LinearSVC MLPClassifier RandomForestClassifier

Aug 29, 2016

Data Structure

Trie

Trie is an ordered tree data structure which stores words in it so that users can search a word or a prefix quickly. Time complexity for adding a word to a Trie is $O(l)$, and for searching a word or a prefix is $O(l)$ too ($l$ is the length of the word or the prefix being added or searched). So it’s why we prefer Trie rather than Set and Hash Table in some situations, such as Dynamic Set, Associative Array and a predictive text or autocomplete Dictionary.

LeetCode Trie

May 06, 2015

Algorithm

Universal and Perfect Hashing

Though hash table is one of the most efficient data structures, it has some weaknesses.

For any hash function $\mathbf{h}$, a set of keys exist that can cause the average access time of a hash table to skyrocket. I.e. all keys from $\{k\in\mathcal{U} : \mathbf{h}(k) = i\}$ for some slot $i$.

Approach:

Choose the hash function at random, independently of the keys.

Algorithm Analysis Perfect Hashing Universal Hashing

Apr 03, 2015

Algorithm

Randomized QuickSort and Randomized Select Analysis

Randomized QuickSort

Randomized QuickSort is an efficient sort algorithm requiring only $\Theta(n\log n)$ expected time on any input.

function RANDOMIZED-QUICKSORT(Array, low, high)
    if low < high then
        partition := RANDOMIZED-PARTITION(Array, low, high)
        RANDOMIZED-QUICKSORT(Array, low, partition - 1)
        RANDOMIZED-QUICKSORT(Array, partition + 1, high)

function RANDOMIZED-PARTITION(Array, low, high)
    pivotIndex := RANDOMIZED-CHOOSEPIVOT(Array, low, high)
    pivotValue := Array[pivotIndex]
    swap Array[high] and Array[pivotIndex]
    storeIndex := low
    for i from low to high do
        if Array[i] < pivotValue then
            swap Array[i] and Array[storeIndex]
            storeIndex := storeIndex + 1
    swap Array[high] and Array[storeIndex]
    return storeIndex

Randomized Select

Randomized Select is an efficient algorithm to find $i$th smallest element of Array[low…high] with only linear expected time on any input.

function RANDOMIZED-SELECT(Array, low, high, i)
    if low = high then
        return Array[low]
    partition := RANDOMIZED-PARTITION(Array, low, high)
    rank      := partition - low + 1
    if i = rank then
        return Array[partition]
    else if i < rank then
        return RANDOMIZED-SELECT(Array, low, partition - 1, i)
    else
        return RANDOMIZED-SELECT(Array, partition + 1, high, i - rank)

QuickSort

page 1 of 1

Randomized QuickSort

Randomized QuickSort is an efficient sort algorithm requiring only $\Theta(n\log n)$ expected time on any input.

function RANDOMIZED-QUICKSORT(Array, low, high)
    if low < high then
        partition := RANDOMIZED-PARTITION(Array, low, high)
        RANDOMIZED-QUICKSORT(Array, low, partition - 1)
        RANDOMIZED-QUICKSORT(Array, partition + 1, high)

function RANDOMIZED-PARTITION(Array, low, high)
    pivotIndex := RANDOMIZED-CHOOSEPIVOT(Array, low, high)
    pivotValue := Array[pivotIndex]
    swap Array[high] and Array[pivotIndex]
    storeIndex := low
    for i from low to high do
        if Array[i] < pivotValue then
            swap Array[i] and Array[storeIndex]
            storeIndex := storeIndex + 1
    swap Array[high] and Array[storeIndex]
    return storeIndex

Randomized Select

Randomized Select is an efficient algorithm to find $i$th smallest element of Array[low…high] with only linear expected time on any input.

function RANDOMIZED-SELECT(Array, low, high, i)
    if low = high then
        return Array[low]
    partition := RANDOMIZED-PARTITION(Array, low, high)
    rank      := partition - low + 1
    if i = rank then
        return Array[partition]
    else if i < rank then
        return RANDOMIZED-SELECT(Array, low, partition - 1, i)
    else
        return RANDOMIZED-SELECT(Array, partition + 1, high, i - rank)

Haiyang Shi

House Prices: Advanced Regression Techniques

Comparing Classifiers on UCI Wine Dataset

Trie

Universal and Perfect Hashing

Approach:

Randomized QuickSort and Randomized Select Analysis

Randomized QuickSort

Randomized Select

Haiyang Shi