Knowledge Representation : The ways for representing the patterns that can be discovered by machine learning

 

3.1 Decision tables

It just the same as the inpupt

 

3.2 Decision trees

•  Nodes : Testing a particular attribute

  • Compare with a constant
  • Compare two attributes with each other
  • Use some function of one or more attributes 

• Leaf nodes :

  • Give a classification 
  • A set of classifications 
  • A probability distribution over all possible classifications 

• Nominal Attribute 

  • The number of children of a node is the number of possible values of the attribute
  • Always devide into two subsets - the attribute might be tested more than once in a path

• Numeric Attribute

  • 2-way split : Greater or less than a constant

  • 3-way split :

    • Greater or less than or missing value
    • Less than, equal to, greater than 
    • below, within, above 
  • A numeric attribute is often tested several times in any given path down the tree - each test involving a different constant 

• Missing values

  • Simple Solution : Use the most popular branch
  • More Sophisticated : weighted branch 

• Build a decision tree for a dataset manually : The Weka Explorer

  • Good way to get a feel for the tedious business of evaluating different combinations of attributes to split on

 

3.3 Classification Rules

• Anteceden or Precondition : Series of tests
• Concequent or Conclusion : Class or Classes 

• Decision Tree로 부터 직접 만드는 Rules 

  • 실행 순서에 따라 결과가 달라지지 않는 Rule Set을 생성한다.
  • 하지만, 복잡해서 Prunning을 거쳐서 사용한다. 

• Decision Tree Representation의 문제점 

  • Replicated Subtree Problem : Decision Tree는 OR로 연결된 여러개의 Rule을 표현하지 못하기 때문에

    • (If a and b then x) OR (if c and b then x) 
    • 이런  Rule들이 있을 때 Tree를 그려 보면 중복된 Subtree가 생긴다.(Figure 3.2)

• Why rules are popular? 

  •  추가가 쉽다. 기존 rule들을 건드리지 않고 추가된다.
  • cf. Decision Tree는? 새로운 규칙이 추가되면 Tree를 처음부터 다시 만들어야 한다. 
  • 추가되는 rule 들이 독립적이라는 가정. 하지만, 실제 상황에서는 context에 따라서 잘못된 규칙이 되는 경우가 존재한다.

• Rule set이 아무 문제없이 잘 정의되는 경우

  • Yes or No + Closed world assumption

    • Disjunctive normal form : Disjunction(OR) of Conjunctive(AND)
    • 기술된 Rule --> YES 그 외에는 NO 
  • Machine Learning이 이런 가정의 결과를 만들어 내는 것이 쉽지 않다. 

 

3.4 Association Rules

• 한개의 Class 뿐만 아니라, 임의의 Attribute의 value를 예측

• 작은 Dataset이라 할지라도, 수많은 Association Rule들이 생성되므로 

  • Resonably large number of instances에 적용될 수 있고 --> Coverage or Support
  • 적용가능한 instances에 대해서 reasonably high accuracy --> Accuracy or Confidence 

  • 예를 들어, If temperature = cool then humidity = normal 이라는 Association Rule에 대해서

    •  Coverage(Support) : Temperature = cool 이고, Humidity = normal인 instance 개수
    •  Accuracy(Confidence) :  Temperature=cool 인 instance중에서 Humidity = normal 인 비율
  • Association Rule을 사용할 때는 최소 Coverage 와 Accuracy를 명시하고 그 이상의 Rule들만 사용하는 것이 보통 

• Multiple consequences를 예측하는 Association Rule은 must be interpreted rather carefully

• •  예를 들어,
  • If windy = false and play = no than outlook = sunny and humidity = high --- ①  
  • If windy = false and play = no than outlook = sunny --- ②
  • If windy = false and play = no than humidity = high --- ③

  • ① 이 단지 ②, ③ 을 합쳐 놓은 것일까? 아니. 그 이상을 얘기한다.

    • ①의 Association Rule을 사용한다는 이야기는
    • Coverage, 즉 windy = false, play = no, outlook = sunny, humidity = high 인 instance의 개수가 정해진 숫자 이상이고,
    • Accuracy, 즉 windy = false이고, play = no인 instance중에서 outlook = sunny, humidity = high인 instance의 비율이 정해진 숫자 이상이라는 의미 

  •  If humidity = high and windy = false and play = no then outlook = sunny --- ④

    • ① Rule과 비교할 때 Coverage는 같고, Accuracy는 더 높다.
    • 왜 Accuracy가 높지?  humidity = high and windy = false and play = no 인 instance인 개수 보다 windy = false and play = no 인 인스턴스 개수가 적으니까.
  •  서로 인과관계를 가지는 rule들이 나올 때는 중복을 제거해야 하는데, 가장 strong한 Rule을 고른다. 이 경우 ① 을 고른다. 왜? 적은 조건으로 많은 결론을 내리는 Rule이니까.

 

3.5 Rule with Execptions

If petal length >= 2.45 and petal length < 4.45 then Iris versicolor
If petal length >= 2.45 and petal length < 4.45 and

petal width < 1.55 then Iris versicolor 
     --> Rule with Exception
If petal length >= 2.45 and petal length < 4.45 then

Iris versicolor EXCEPT if petal width < 1.0 then Iris setosa

• Default...except if...then... structure 는 if...then...else... structure로 변환 가능하다.

 

3.6 Rules Involving relations

• Propositional Calculus(논리학자들이 이렇게 부름)

  • Attribute와 상수를 이용하여 조건을 표현

    • If width >= 3.5 and height < 7.0 then lying 
    • If height >= 3.5 then standing 

• Rule involving relation

  •  Attribute간의 관계로 조건을 표현

    • If width > height then lying 
    • If height > width then standing

  • 실제 이런식으로 표현하는 것은 너무 비용이 많이 든다. 

    • width - height 를 새로운 Attribute로 도입

 

3.7 Trees for Numeric prediction

•  For Example, CPU Performance 수치를 구하는 문제

• Linear Regression 

  •  예 > Performance = -56.1 + 0.049 MYCT + 0.015 MMIN + 0.006 MMAX + ...

• Regression Tree 

  • Leaf Node에는 그 Node에 해당되는 Instance들의 평균값을 명시한다.

• Model Tree

  • Leaf Node마다 Linear Regression을 하나씩 표시한다. 

 

3.8 Instance-Based Representation

• Instance-based Learning은 Lazy, 실제 작업을 최대한 뒤로 미룬다.

• Instance들을 고대~로 담아 놓고, 실행 단계에서는 가장 비숫한 Instance를 찾는다 

  • 대표적인 예 : KNN --> Test instance와 가까운 K개의 instance를 찾아서 그중에 제일 많은 클래스가 Test instance의 클래스 이다.
• 자세한 내용은 나중에... 

 

3.9 Clusters

• Cluster를 표현하는 몇가지 방법

  • 각각의 cluster에 대해서 영역을 Partitioning
  • Venn diagram 

  • 인스턴스가 클러스터에 속할 비율(합하면 1.0)을 표시 

    • 예> A : c1(0.4) c2(0.2) c3(0.4)
  • Tree 구조로 표현