Data mining

exam

01. Intro

• We are drowning in data, but starving for knowledge.
• What is data mining?
  
  • Data mining:Discovering interesting patterns and knowledge from massive amount of data.
  • A natural evolution of science and information technology, in great demand, with wide applications.
  • Knowledge Discovery(KDD) Process
    
    • A KDD process includes data cleaning,data intergration,data selection,transformation,data mining,pattern evalution,and konwledge presentation.
• What kinds of Patterns can be mined?
  Mining can be performed in a variety of data.
• Data mining functionalities: characterization,discrimination,association,classifiction,clustering,trend and outlier analysis,etc.
• Major isssue in Data Mining
  
  • ( 1 )
    
    • Mining Methodology
    • User Interaction
    • Presentation and visualization of data mining
  • ( 2 )
    
    • Diversity of data types
    • Data mining and society

02. Getting to Know your data

1. Data objects and attribute types

   • Types of data sets
     
     • Record
     • Graph and network
     • Ordered
       
       • video data
     • Spatial, image and multimedia
   • important characteristics of structured data
     
     • dimensionality
     • sparsity
     • resolution 分辨率？分离度？
     • Distribution
   • Data objects
     
     • A data object represents an entity.
     • Also called samples, examples, instance, data points $\dots$
     • Data objects are describled by attributes.
   • Attributes(or dimensions, features, variables)
     
     • Attribute Types
       
       • Nomial 名词性的
       • Ordinal 带顺序性质
         Values have a meaningful order.
       • Binary
         Nomial attribute with only 2 states.
         (Symmetric \ Asymmetric 重要程度不同)
         Convention: assign 1 to most important outcome(e.g.,HIV positive)
     • Numeric attribute types
       
       • Quantity(integer or real-valued)
       • Interval
         
         • Measured on a scale of equal-sized units
         • No true zero-point
       • Ratio
         
         • Inherent zero-point
     • Discrete vs. Continuous Attributes
   • Basic statistical Descriptions of data
     
     • measuring the central tendency
       
       • mean
       • mode
         value that occurs most frequently in the data.
         数据中出现频率最高的值.
       • Median 中位数
         Empirical fomula
         $$mean - mode = 3 \times ( mean - median )$$
     • Measuring the Dispersion of data
       
       • Quartiles, outliers and boxplots
         
         • Quartiles　四分之一点： $\quad$ $Q_1(25\%), Q_3(75\%)$
           Inter-quartile range: $\quad$ $IQR = Q_3 - Q_1$
           Five number summary: $\quad$ min, $Q_1$, median, $Q_3$, max
       • Variance and standard deviation
     • Boxplot Analysis
       
       • whiskers
         极大极小值
       • outliers
         a value higher/lower than $1.5 \times IQR$
     • Properties of Normal Distribution Curve
   • Graphic displays
     
     • Histogram Analysis
       Histograms often tell more than boxplot.
     • Quantile plot
     • Quantile-Quantile (Q-Q) plot
     • Scatter plot
   • Data visulization
     
     • Pixel-Oriented visualization techiniques
       数据点的值与图像点的颜色值相对应。
     • Geometric projection visualization techiques
       
       • scatterplot Matrices
         k维数据扩展成k-by-k的矩阵，画scatter plot
       • Landscapes
       • parallel coordinates
         属性个数一个轴，属性值多个轴，属性值轴平行，相隔固定距离，每一个数据 点就是一条连接多个属性值轴的曲线。
     • Icon-Based visualization techniques
       
       • Chernoff Faces
         脸部的不同特征对应不同的属性。e.g.，头的偏心率、眼睛的大小、瞳孔的大 小等等。
         最终不同的数据点对应不同的脸。
       • Stick Figure
     • Hierarchical visualization techniques
       
       • Dimensional stacking
         堆叠(stack)或者说嵌套式地表示数据，比如说属性１属性２组成两个轴，在 这两个轴划分成的网格中，再嵌套属性３属性４两个轴组成的坐标系。
       • worlds-whthin-worlds
       • tree-map
       • InfoCube
       • Visualizing complex data and relations

   • Measuring data similarity dissimilirity

     • Similarity
       Numerical measure of how alike two data objects are.
       Often falls in the range [0, 1]
       越大越相似
     • Dissimilarity
       Numerical measure of how different two data objects are.
       越大越不相似
     • Proximity rfer to a similarity or dissimilarity
     • Data matrix
     • Dissimilarity matrix
       A triangular matrix.
       对称的，只需要三角阵的信息。
     • Proximity measure for nomial attributes
       
       • Simple matching
         $$d(i,j) = \frac{p-m}{p}$$
         $p$是属性总数，$m$是相同的属性数目。
     • Proximity measure for binary attributes
       
       • a contingency table for binary data, two obtect $i,j$

     value	1	0
     1	q	r
     0	s	t

     * distance measure for symmetric variables
     

     $$d = \frac{r+s}{q+r+s+t}$$
     * asymmetric
     $$d = \frac{r+s}{q+r+s}$$
     * Jaccard coefficient( similarity measure for asymmetric binary variables)
     $$d = \frac{q}{q+r+s}$$

     • Standardizing Numeric data

       • Z-score
         $$z = \frac{x - \mu}{\sigma}$$
         原始数据减去均值除以标准差。
         归一化后均值为0,标准差为1.
         
         • An alternative way：计算mean absolute deviation,替换标准差.
           $$s_f = \frac{1}{n}\Big(\mid x_{1f} - m_f \mid + \dots + \mid x_{nf} - m_f \mid \Big)$$

     • Minkowski distance 明科夫斯基距离
       就是范数。
       

       $$d(i,j) = \Big( \mid x_{i1} - x{j1} \mid^h + \dots + \mid x_{ip} - x_{jp} \mid^h \Big)^{\frac{1}{h}}$$
       非负,对称，满足三角不等式.
       满足这三个性质的距离可以作为一个metric(度量指标).
       Special cases
       • $h=1$ 曼哈顿距离 Manhattan distance
         绝对值相加
       • $h=2$ 欧氏距离 Euclidean distance
         欧式几何距离
       • $h=\infty$ "supremum" distance,
         最大的那个差值占主要
     • Ordinal Variables
       order is important
       用实数代替顺序，再映射到[0,1]之间，最后计算不相似度。
     • Attributes of Mixed Type
       混合属性表示，二值、数字的、有顺序的，分别转换最后求不相似度。
     • Cosine similarity
       $$cos(d_1, d_2) = \frac{d_1 \cdot d_2 }{\Vert d_1 \Vert \Vert d_2 \Vert}$$
   • Summary

03. Data Preprocessing

• Overview
  
  • Why?
  • Major Tasks
    
    • Data cleaning
    • Data integration 数据集成
    • Data reduction
    • Data transformation and data discretization
• Data Cleaning
  
  • Dirty data
    incomplete,noisy,inconsistent,intentional
    
    • Incomplete(Missing) data
      一些常规处理方法
    • Nosiy data
      binning, regression, cluster, 人工检查
    • Data cleaning as a process
• Data Integration 数据集成
  
  • Handling Redundancy 处理冗余
  • Correlation Analysis (Nominal data)
    
    • $\chi^2 (chi-square) \quad test$
      $$\chi^2 = \sum\frac{(observed - expected)^2}{ expected }$$
      值越大相关性越高。
    • correlation coefficient 相关系数
      $r_{A,B}$
    • covariance 协方差
      $$r_{A, B} = \frac{Cov(A,B)}{\sigma_A\sigma_B}$$
      简化计算
      $$Cov(A,B) = E(AB) - \bar{A}\bar{B}$$
• Data Reduction
  
  • Dimensionality Reduction
    
    • wavelet transform
    • PCA
  • Numerosity Reduction
    
    • Regression Analysis
      
      • Linear regression
        $$Y = wX +b$$
      • Multiple regression
        $$Y = b_0 +b_1X_1+b_2X_2$$
      • Log-linear models
    • Histogram analysis
    • Clustering
    • Sampling
      
      • sampling random sampling
      • sampling without replacement 不放回抽样
      • sampling with replacement 放回抽样
      • Stratified sampling
      • Data cube aggregation
  • Data compression
• Data transformation
  
  • Normalization
    
    • Min-max normalization to $[new\_max, new\_min]$
      $$v^{'} = \frac{v - min}{ max - min} \times ( new\_max - new\_min ) + new\_min$$
    • Z-score normalization
    • Normalization by decimal scaling
      $$v^{'} = \frac{v}{10^j}$$
      $j$是使$max(v^{'})$

06. Mining Frequent patterns, association and correlations

basic concepts

• Frequent patterns
  item set
  k-itemset 包含k个itemset
  支持度计数(abousolute support）: itemset的出现频数。
  an itemset X is Frequent if X's support is no less than a minsup threshold
• Association rules
  找两个Pattern $X, Y$ 之间的关系。$X \to Y$。
  support： a transaction 包含 $X \cup Y$ 的出现概率$P(X \cup Y)$
  confidence： a transaction在包含$X$的情况下也包含$Y$的出现概率$P(Y\mid X)$
• Closed patterns and max-pattern
  closed 不存在真超项集与其具有相同的支持度计数。
  closed patten($X$), 他不是任何其他itemset(with same support as X)的子集。
  max-pattern，是frequent并且不是任何其他frequent itemset的子集。

Method

• Aprior
  使用频繁项(frequent itenset)集的先验知识。

  • 频繁项的非空子集一定是频繁项
  • 反单调性: 若一个itemset不是频繁项，则其super itemset也不是频繁项。

• 提高Aprior的效率

  • Frequent-Pattern Growth，FP-Growth
    FP-Tree

appendix

1. words record
   
   • discipline $\qquad$ n. 纪律，惩罚,学科　vt.训导
   • workshop $\qquad$ 【计】专题研究组，讨论会
   • diversity $\qquad$ n. 差异，多样性
   • Hierarchical $\qquad$ adj. 分层的，分级的
2. Conferences and Journals
   
   • Conf.
     
     • KDD
     • ICDM
   • Journal
     
     • TKDE