[學術]挑到一篇看似簡單卻很多疑問的Paper

 為什麼研二了還這麼緊張

挑到一篇看似簡單卻很多疑問的Paper，是OR這個領域解最佳化問題的，整個很不熟

紀錄一下找到的筆記
 

• non-deterministic polynomial，是NP

O(n^k)的複雜度能解決的問題，都稱為polynomial的問題 (能用 O(n^k) 計算量解決之問題之集合)


NP 問題的代表問題之一是 traveling salesman problem (i.e.無法用 O(n^k) 的計算量來解決)

若有N個城市，就有(N-1)! 窮舉的可能組合，當N(也就是城市數)約超過20以上時， 階乘的結果非常的大，要窮舉出所有可能性就必須花費非常多的時間。另外像購物車問題、質數問題也都是 non-deterministic algorithm

• 近似演算法

所謂「近似」，就是指結果不一定是最優的，但是也在可以承受的範圍內，而且可以比精確求解消耗更少的資源。
無法在多項式時間內精確求到最優解，然而在現實或理論研究中，這類問題都有廣泛的應用，在精確解無法得到的情況下，轉而依靠高效的近似演算法求可以接受的近似解

• Steiner tree problem 

與minimum spanning tree非常像(最小成本擴張樹的經典演算法：Prim's algorithm and Kruskal's algorithm)

Steiner tree問題：給定一個點的集合(vertices)，利用網路圖的最短路徑連接起來，其中，路徑長度是所有edge的weight總和，與最小成本擴張樹不同之處在於，在Steiner tree問題中，會有另外的中介點與邊 (vertices and edges)被加到圖中，藉以減低spanning tree的長度，這些新加入的點被用來降低total length of connection被稱做Steiner points or Steiner vertices.

Dynamic Reordering

列舉樹的集合，排列順序很重要，會影響pruning效率

在set-enumeration tree每個level的node，對其child依照support高低排序

MaxMiner & MAFIA & GenMax 都使用這樣的heuristic(support低到高排序)

support較低的itemset有較小的機會再下一個level產生大集合

越快prune tree，就節省越多work

Frequent pattern mining

三種基本的frequent itemset mining方法

(1) Apriori principle

• A downward closure property(向下封閉)
  a k-itemset is frequent only if all of its sub-itemsets are frequent.
  all subset of a frequent itemset must be frequent.
  //一個itemset只有當他所有的subset都是frequent時，才會是frequent
  
  
• Apriori property
  any super-pattern of a nonfrequent pattern cannot be frequent
  
  
• Antimonotone, if a set cannot pass a test, all its super set will fail the same test as well. It is called "antimonotone" because the property is monotonice in the context of failing a test.
  
  //若一個itemset不frequent，它的superset也不會是frequent
  
  
• horizontal data format
  {TID: itemset}
  

(2) FP-growth

• FP-tree: frequent pattern tree
• horizontal data format

(3) eclat

• vertical data format
  {item: TID_set}
  

closed frequent pattern & maximal frequent pattern (max-pattern)
a pattern a is a closed frequent pattern in a data set in D if
(1) a is frequent
(2) there exists no proper super-pattern b such that b has the same support as a in D

a pattern a is a maximal frequent pattern in a data set in D if
(1) a is frequent
(2) there exists no super-pattern b such that ab
(3) b is frequent in D

Sequential pattern mining

常見的幾種算法
GSP: A Sequential Pattern Mining Algorithm Based on Candidate Generate-and-Test
SPADE: An Apriori-Based Vertical Data Format Sequential Pattern Mining Algorithm
PrefixSpan: Prefix-Projected Sequential Pattern Growth

性能: PrefixSpan > SPADE > GSP

論文方向

暑假要把題目定下來，定下來之後開始寫論文Proposal

1.點集合、多維度(multi-resolution)的data mining

由於高解析度的計算cost高，希望能從低、中解析度做mining，再還原到高解析度的pattern

延伸自柏吟學姐的論文Mining Closed Patterns in Pointset Databases

找人的姿勢 maximal pattern

2.承1. 連續的image也就是處理video

延伸自卡西歐學姐的論文 Mining Closed Patterns In Pointset Video Databases

3.將 time interval 延伸到多維度的mining

1D是線性關係，2D是矩形，3D是立方體 (??這個我沒有很懂意思)

靈感來自中央資管陳彥良老師發過的論文 Mining Nonambiguous Temporal Patterns for Interval-Based Event

Entropy

entropy is a measure of the uncertainty associated with a random variable.

measure of disorder: a measure of the disorder that exists in a system

是一種度量的標準

Entropy 可以用在：

◎熱力學→狀態與熱能之關係
◎機率→亂度、不確定性
◎資訊→資訊的含量

隱藏涵義的程度

假設希望度量所要隱藏資訊的安全性=>大好

H(X)大，不確定性大，資訊量大，越安全。 (指桑罵槐)
H(X)小，不確定性小，資訊量小，越不安全，易被猜中。
H(X)=0，此訊息為真，即背後沒有隱藏其它涵義。(藏不了東西)

“High Entropy” means X is from a uniform (boring) distribution
A histogram of the frequency distribution of values of X would be flat
the values sampled from it would be all over the place

“Low Entropy” means X is from varied (peaks and valleys) distribution
A histogram of the frequency distribution of values of X would have many lows and one or two highs
the values sampled from it would be more predictable

Feature vector 特徵向量

n-dimensional vector of numerical features that represent some object.

a numerical representation of objects

表示圖形時，feature values 可能是對應至圖像的pixel
表示文字時，feature values 可能是term 出現的頻率

Non-trivial的真義

It is a term common among communities of engineers and mathematicians, to indicate a statement or theorem that is not obvious or easy to solve.

By wikipedia

簡單說就是很難解，或是不顯而易見的問題...

腦殘的我一直以為是不瑣碎= ="

Signature files

Signature files is a technique applied for document retrieval.

create a quick and dirty filter that will keep all the documents that match to the query and hopefully a few ones that do not.

The way this is done is by creating for each file a signature, typically a hash coded version.

This structure since in most cases is inferior to inverted files in terms of speed, size and functionality, is not used much. However, with proper parameters it can beat the inverted files in certain environments.

資料來源: wiki

ad-hoc query

每次讀的paper幾乎都遇到這個term

ad-hoc query:

1.allow the users to create specific, customized queries.

2.such query has the potential to severely degrade the performance of a live system(因為即時運算結果，非預存的)

arg max

arg max f(x) , x等於多少的時候，會使得函數f(x)最大

例子1: arg max f(x), 如果 f(x)=-x, 則x=0時, f會有最大值

例子2: arg max (x(10-x)) = 5, 因為x=5時，x(10-x)會得到最大值25

例子3: 也可能在很多點，都可以得到最大值，如三角函數的 cos(x)，在x=0 or 2 pi，cos(x)=1最大

Non trivial

It is a term common among communities of engineers and mathematicians, to indicate a statement or theorem that is not obvious or easy to solve.

簡單說就是個不好解的問題~

資料來源：wiki

Ontology

Ontology

源自哲學(存在、本體論)

在電腦與資訊科學上，Ontology指的是資料模型

在各種不同的領域(domain)上，建立individuals (instances), classes (concepts), attributes, 及relations，來描述這個領域上各實體的特性

Ontology是一種概念化的詳細描述 (an explicit specification of a conceptualization)，也就是說，ontology是用於描述說明某一領域知識的一組術語。

Ontology的知識結構在建構時，以描述對象的類型而言，可以是簡單事實或抽象概念。從描述對象的範圍而言，可以是通用的字詞，也可以是特定領域知識中定義的術語。

學術上的SIG

叫做 Special Interest Group

像是
SIGIR 就是 Special Interest Group on Information retrieval
SIGKDD 就是 Special Interest Group on Knowledge discovery and data mining
SIGGraph 就是影像處理方面的

都是學術上研究領域的組織

name disambiguation

Name disambiguation is desired in many cases: e.g., evaluating faculty publications,
calculating statistics of social network and author impacts, etc.

When one is seeking a list of publications of an author who has used different name variations or
when there are multiple other authors with the same name.

heuristic

heuristic rule 經驗法則

wiki, 啟發法，啟發法經常用於模式串識別與匹配，web頁面搜索

heuristic algorithm 啟發式演算法
有時候人們會發現在某些特殊情況下，啟發式演算法會得到很壞的答案或效率極差，然而造成那些特殊情況的資料結構，也許永遠不會在現實世界出現。因此現實世界中啟發式演算法很常用來解決問題。啟發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。

這真是個神奇的字，誰能告訴我他真正的意思.........

Mann-Whitney rank test

Mann-Whitney U test

讀到的paper上寫的是Mann-Whitney rank test

檢驗兩個觀察的樣本是否來自同一個分配
是最廣為人知的無母數顯著性檢定
其虛無假設是兩個樣本從同一個母體中抽出來，因此他們的機率分佈會是相同的

是一種無母數統計分析（Non-parametric Statistics）

無母數統計適用於母群體分佈情況未明、小樣本、母群體分佈不為常態也不易轉換為常態。
無母數統計推論時所使用的統計量的抽樣分配通常與母體分配無關（distribution free）

10-fold cross-validation [評估衡量演算法用]

10-fold cross-validation

十折交叉驗證，用來檢驗演算法的好壞，是常用的validation方法。

將資料集分成十份，輪流將其中9份當作training data，1份當作testing data，10次的結果的平均值作為對演算法好壞的估計。

Apriori algorithm[關聯規則演算法]

聽說Apriori algorithm是Data mining的始祖演算法

history:
1993年：提出關聯法則之數學模式( Agrawal et. al.)
1994年：Apriori演算法為最早被提出之關聯法則( Agrawal & Sirkant)
1995年：以Apriori演算法為基礎，加入時間屬性概念，
提出Mining Sequential Pattern (MSP)演算法，用於
發掘序列型樣或循序特徵 ( Agrawal & Srikant)

整理資料：

• Apriori 是學習「association rules」的經典演算法
• 試圖去找出滿足threshold最常見、出現的子集合
• Apriori uses a "bottom up" approach
• frequent subsets are extended one item at a time (candidate generation)
• Apriori uses breadth-first search and a tree structure to count candidate item sets

Apriori將關聯法則的發掘問題區分為：
找出 frequent itemset(就是Large)
由frequent itemset推導出association rule (關聯規則)
Apriori的困難與瓶頸：
產量大量Candidate
多次掃描資料庫
Terminology

D: Dataset
|D|: Dataset length
C: Candidate
L: Large
Lk: Large k-itemset (符合min support的dataset)
Ck+1: Lk 中 dataset 兩兩 join 成長度為 k+1之候選 dataset
large=frequent= covering=interesting=relevant

Hierarchical Clustering

兩個主要的分群方法

1. hierarchical clustering
2. k-means clustering

hierarchical clustering

樹狀的分割與聚合

分成：

• agglomerative methods (最常用，bottom up 每個node向上聚合成一群)
• divisive methods (top down 分裂)

see http://www.resample.com/xlminer/help/HClst/HClst_intro.htm