결정 트 리 알고리즘, ID3, C 4.5, CART 원리, SparkMllib 의 붓꽃 실전

14145 단어 MachineLearning
결정 트 리 알고리즘 원리
  • 의사 결정 트 리 가 무엇 입 니까?
  • 실생 활 의 나무
  • 뿌리 - > 줄기 - > 나뭇가지 - > 나뭇잎
  • 데이터 구조 중의 나무
  • 뿌리 결산 점
  • 분기 결산 점
  • 잎 결점
  • 기계 학습 중인 나무
  • 분기 결산 점
  • 잎 결점
  • 데이터 집중 의 특징 은 분기 노드, 데이터 집중 의 유형 라벨 열 은 잎 노드 이다.

  • 결정 트 리 의 관건 적 인 절 차 는 분열 속성 이다.분열 속성 이란 특정한 노드 에서 특정한 특징 속성의 차이 에 따라 구조 가 다른 가 지 를 구분 하 는 것 이다. 그 목 표 는 각 분열 부분 을 가능 한 한 '순수' 하 게 하 는 것 이다.가능 한 한 '순수' 는 하나의 분열 자 를 분류 대상 항목 에 집중 시 키 는 것 이다.'순수' 를 판단 하 는 방법 에 따라 우리 의 ID3 알고리즘, C 4.5 알고리즘 과 CART 알고리즘 을 도입 했다.
  • 참고 자료
  • 의사 결정 트 리 알고리즘 이해 하기 (1) - 핵심 사상


  • 규칙 에 따라 트 리 만 들 기
  • 규칙 이 뭐 예요?
  • 업무 전문가 가 내 놓 은 규칙 은 훈련 알고리즘 에 필요 한 특징 으로 여 긴 다.

  • 정성 이력서 결정 트 리 와 정량 이력서 결정 트 리
  • 왜 정량 적 인 측면 에서 분석 해 야 합 니까?
  • 답: 이렇게 하면 사용자 의 특징 정 보 를 더욱 정확하게 분석 하고 영업 사원 에 게 더욱 정확 한 데이터 정 보 를 제공 할 수 있다.



  • 모델 기반 트 리
  • 의사 결정 트 리 구축 의 세 가지 요 소 를 정리한다.
  • 특징의 선택: 정보 엔트로피, 정보 이득, 정보 이득 율, 지 니 계수
  • 의사 결정 트 리 의 생 성: ID3, C 4.5, Cart 트 리
  • 결정 나무의 가지치기: 먼저 가 지 를 자 르 고 나중에 가 지 를 자른다
  • 특징 선택
  • 엔트로피: 물리학 적 으로 에너지 분포 불확실 성의 양 을 측정 한다.
  • 정보 엔트로피, 향 농 엔트로피: 정보의 불확실 성 을 없 애기 위해 무 작위 변수의 복잡 도 를 대표 한다.
  • 정보 엔트로피 가 클 수록 정보의 불확실 성 이 크 고 정보의 확정 성 이 작 을 수록 정보의 순도 가 낮다.
  • 정보 엔트로피 가 작 을 수록 정보의 불확실 성 이 적 고 정보의 확정 성 이 클 수록 정보의 순도 가 크다.

  • H X = − ∑ i = 1 n P ( x i ) l o g P ( x i ) HX=-\sum_{i=1}^{n}P_{(x_i)}log^{P_{(x_i)}} HX=−i=1∑n​P(xi​)​logP(xi​)​
  • 조건 엔트로피
  • 특정한 조건 에서 무 작위 변수의 복잡 도
  • H ( Y ∣ X ) = ∑ x ∈ X P ( x ) l o g P ( Y ∣ X = x ) H(Y|X)=\sum_{x \in X}P(x)log^{P(Y|X=x)} H(Y∣X)=x∈X∑​P(x)logP(Y∣X=x)
  • 정보 이득
  • 정보 이득 = 정보 엔트로피 - 조건 엔트로피
  • 정보 이득 은 한 조건 에서 정보 복잡 도 (불확실 성) 가 감소 하 는 정 도 를 나타 낸다
  • .
  • 정보 이득 률
  • 정보 이득 률 로 속성 을 선택 하고 정보 이득 으로 선택 할 때 선택 하 는 다 속성 부족 을 극복 합 니 다.G a i n R a t e ( D , A ) = G a i n ( D , A ) H ( A ) GainRate(D,A) =\frac {Gain(D,A)} {H(A)}\\ GainRate(D,A)=H(A)Gain(D,A)​
  • D 는 데이터 세트 이 고 A 는 하나의 특징 이 며 그 중에서 H (A) 는 A 의 엔트로피
  • 이다.
  • 참고 자료
  • 정보 엔트로피
  • 조건 엔트로피
  • 정보 이득
  • 정보 이득 률


  • ID3 알고리즘, C 4.5 알고리즘
  • ID3
  • 우리 의 ID3 알고리즘 에서 우 리 는 정보 이득 이라는 양 을 순도 의 도량 으로 한다.우 리 는 정보 이득 의 가장 큰 특징 을 선택 하여 분열 시킨다!
  • 우 리 는 위 에서 정보 이득 을 구 하 는 공식 에서 알 수 있 듯 이 정보 이득 준칙 은 사실은 수치 가 비교적 많은 속성 에 대해 선 호 하 는 것 이다!
  • * * 모든 견본 의 번호 가 다 르 기 때 문 입 니 다. (번호 가 독특 하고 유일한 조건 엔트로피 가 0 이기 때문에 모든 결점 에서 한 가지 만 있 고 순도 가 매우 높 습 니 다) 즉, 예측 견본 이 왔 습 니 다. 번 호 를 알려 주면 다른 특징 은 쓸모 가 없습니다. * 이렇게 생 성 된 결정 트 리 는 분명 일반화 능력 을 가지 지 않 습 니 다.

  • C4.5
  • 정보 이득 률 이라는 양 을 순도 의 도량 으로 사용 했다.우 리 는 정보 이 로 운 확률 이 가장 큰 특징 을 선택 하여 분열 시킨다!
  • * * 우 리 는 처음에 분석 한 결과 * * 정보 이득 준칙 은 사실은 수치 가 비교적 많은 속성 을 선 호 하 는 것 이다!(예 를 들 어 위 에서 언급 한 번 호 는 수치 가 실례 개수 일 수 있 습 니 다. 가장 많 고 분류 가 많 을 수록 모든 하위 결점 으로 나 눌 수 있 습 니 다. 하위 결점 의 순도 도 클 수 있 습 니 다. 수량 이 적 기 때문에 한 종류 에 있 을 가능성 이 가장 큽 니 다)
  • 그러나 앞에서 분석 한 결과 좋 지 않 기 때문에 우 리 는 하나의 속성의 고정 값 (이 속성의 엔트로피) 을 나 누 어야 한다. 이 값 은 분 류 된 분류 수가 클 수록 작 아야 한다.그래서 분모 가 되 었 다.이렇게 하면 정보 이득 의 단점 을 피 할 수 있다.
  • 그러면 정보 이 로 운 확률 이 완벽 하고 흠 잡 을 데 가 없 는 것 입 니까?물론 아 닙 니 다. 이 분모 가 생 긴 후에 우 리 는 이 로 운 확률 준칙 이 취 할 수 있 는 유형 수가 비교적 적은 특징 에 대해 선 호 하 는 것 을 볼 수 있 습 니 다!결국 분모 가 작 을 수록 전체 가 커진다.
  • 그래서 C 4.5 알고리즘 은 이 로 운 확률 이 가장 큰 후보 구분 속성 을 직접 선택 하지 않 고 후보 구분 속성 에서 정보 이득 이 평균 수준 보다 높 은 속성 을 찾 아 냈 다 (이렇게 하면 대부분 좋 은 특징 을 확보 했다). 그 중에서 이 로 운 확률 이 가장 높 은 것 을 선택 했다 (현 번호 특징 과 같은 극단 적 인 상황 이 나타 나 지 않도록 보장 했다)
  • 의사 결정 트 리 알고리즘 이해 하기 (2) - ID3 알고리즘 과 C 4.5 알고리즘
  • 카 트 리 알고리즘
  • 약칭: 분류 와 회귀 트 리 - ID3, C 4.5 와 구별
  • 차이 점 과 관계: Cart 나 무 는 이 진 트 리 이 고 ID3 와 C 4.5 여 그루 의 결정 트 리
  • 카 트 리 는 집합 지 니 계 수 를 분류 적 으로 사용한다.
  • 지 니 계 수 는 다음 과 같다.
  • G i n i = ∑ i = 1 m P i ( 1 − P i ) = 1 − ∑ i = 1 m P i 2 Gini=\sum_{i=1}^{m}P_i(1-P_i)=1-\sum_{i=1}^{m}P_i^2 Gini=i=1∑m​Pi​(1−Pi​)=1−i=1∑m​Pi2​
  • GINI 지수
  • 각 특징 A 에 대해 모든 가능 한 값 a 를 취하 고 데이터 세트 를 A = a D1, A! = 로 나눈다.a D2 두 부분 집합, 집합 D 의 지 니 지수 계산:
  • G I N I ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) GINI(D,A)=\frac {|D_1|}{|D|}Gini(D_1)+\frac {|D_2|}{|D|}Gini(D_2) GINI(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)
  • 회귀 문제 상 MSE (mean square error - sum) 1m ∑ i = 1m (y i − y i ‾) 2 \ \ frac 1m \ \ sum{i=1}^{m}(y_i-\overline{y_i})^2 m1​i=1∑m​(yi​−yi​​)2

  • 회귀 트 리
  • 가장 좋 은 절 점 과 절 점 변 수 를 선택한다
  • 선택 한 절 분 점 과 절 분 변수 로 원래 의 데이터 구역 을 구분 합 니 다
  • 재 귀적 호출 알고리즘 생 성 다 구역 의 이 진 트 리
  • 은 GBDT, XGBOOST 알고리즘 의 기초
  • 분류 수
  • 1. 각 특징 A 에 대해 모든 가능 한 값 a 를 취하 고 데이터 세트 를 A = a, A! = 로 나눈다.a. 두 부분 집합, 집합 D 의 지 니 지 수 를 계산 합 니 다.
  • G I N I ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) GINI(D,A)=\frac {|D_1|}{|D|}Gini(D_1)+\frac {|D_2|}{|D|}Gini(D_2) GINI(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)
  • 2 모든 특징 A 를 옮 겨 다 니 며 가 치 를 얻 을 수 있 는 모든 지 니 지 수 를 계산 하고 D 의 지 니 지수 최소 값 에 대응 하 는 특징 과 절 점 을 최 적 으로 구분 하여 데 이 터 를 두 부분 으로 나 누 었 다.
  • 3. 상기 두 개의 키 노드 에 대한 재 귀 호출 절차 (1) (2) 는 정지 조건 을 만족 시 킬 때 까지.
  • 4 CART 의사 결정 트 리 생 성.


  • 의사 결정 트 리, ID3, C 4.5, Cart 회귀 트 리, Cart 분류 트 리 의 가지치기 문 제 는 아직 분석 되 지 않 았 고 매일 분석 했다.
  • SparkMllib 모델 링 분석 실천 완성
  • 아이 리 스 실전, rdd 방식 사용
    import org.apache.spark.mllib.linalg.Vectors
    import org.apache.spark.mllib.regression
    import org.apache.spark.mllib.regression.LabeledPoint
    import org.apache.spark.mllib.tree.DecisionTree
    import org.apache.spark.mllib.tree.model.DecisionTreeModel
    import org.apache.spark.rdd.RDD
    import org.apache.spark.{SparkConf, SparkContext}
    
    object SparkMllibIris1 {
      def main(args: Array[String]): Unit = {
        // 1.    
        val conf: SparkConf = new SparkConf().setMaster("local[*]").setAppName("SparkMllibIris1Rdd")
        val sc = new SparkContext(conf)
        // 2.    
        val path = "iris.csv"
        val rdd: RDD[String] = sc.textFile(path)
        //    rdd.foreach(println)
        //    6.2,3.4,5.4,2.3,Iris-virginica
        //    5.9,3.0,5.1,1.8,Iris-virginica
        // 3,    
        // 3-1  LabelPoint rdd      API   ,               ,  ,  
        var rddLp: RDD[LabeledPoint] = rdd.map(
          x => {
            val strings: Array[String] = x.split(",")
            regression.LabeledPoint(
              strings(4) match {
                case "Iris-setosa" => 0.0
                case "Iris-versicolor" => 1.0
                case "Iris-virginica" => 2.0
              }
            ,
              Vectors.dense(
                strings(0).toDouble,
                strings(1).toDouble,
                strings(2).toDouble,
                strings(3).toDouble))
          }
        )
    //    rddLp.foreach(println)
    //    (1.0,[6.0,2.9,4.5,1.5])
    //    (0.0,[5.1,3.5,1.4,0.2])
        // 4.              
        val Array(trainData,testData): Array[RDD[LabeledPoint]] = rddLp.randomSplit(Array(0.8,0.2))
        // 5.     
        val decisonModel: DecisionTreeModel = DecisionTree.trainClassifier(trainData,3, Map[Int, Int](),"gini",8,16)
        // 6.           ,              ,           
        //  DataFrame       ,          ,RDD        ,          
        val result: RDD[(Double, Double)] = testData.map(
          x=> {
            val pre: Double = decisonModel.predict(x.features)
            (x.label,pre)
          }
        )
        val acc: Double = result.filter(x=>x._1==x._2).count().toDouble /result.count()
        println(acc)
        println("error", (1-acc))
    //    0.9642857142857143
    //    (error,0.0357142857142857)
      }
    }
    
  • 아이 리 스 실전 - DATAFrame 방식 실현
    import org.apache.spark.ml.classification.{DecisionTreeClassificationModel, DecisionTreeClassifier}
    import org.apache.spark.ml.evaluation.MulticlassClassificationEvaluator
    import org.apache.spark.ml.feature.{IndexToString, StringIndexer, StringIndexerModel, VectorAssembler}
    import org.apache.spark.sql.{DataFrame, Dataset, Row, SparkSession}
    
    object SparkMlIris2 {
      def main(args: Array[String]): Unit = {
        //    * 1-    
        val sparkSession: SparkSession = SparkSession.builder().master("local[*]").appName("SparkMllibIris2").getOrCreate()
        //    * 2-    
        // 2-1   CSV        ,         http://spark.apache.org/docs/latest/sql-data-sources-load-save-functions.html
        var path = "irisHeader.csv"
        //       .option("inferSchema", "true"),  df schema   String   
        val df: DataFrame = sparkSession.read.format("csv").option("inferSchema", "true").option("header","true").option("sep",",").load(path)
    //    df.printSchema()
    //    root
    //    |-- sepal_length: double (nullable = true)
    //    |-- sepal_width: double (nullable = true)
    //    |-- petal_length: double (nullable = true)
    //    |-- petal_width: double (nullable = true)
    //    |-- class: string (nullable = true)
        //df.show(false)
        //    +------------+-----------+------------+-----------+-----------+
    //    |sepal_length|sepal_width|petal_length|petal_width|class      |
    //    +------------+-----------+------------+-----------+-----------+
    //    |5.1         |3.5        |1.4         |0.2        |Iris-setosa|
        //* 4-    
        //4-1 4            
        val assembler: VectorAssembler = new VectorAssembler().setInputCols(Array("sepal_length","sepal_width","petal_length","petal_width")).setOutputCol("features")
        val assmblerDf: DataFrame = assembler.transform(df)
        assmblerDf.show(false)
        //4-2    class      
        val stringIndex: StringIndexer = new StringIndexer().setInputCol("class").setOutputCol("label")
        val stingIndexModel: StringIndexerModel = stringIndex.fit(assmblerDf)
        val indexDf: DataFrame = stingIndexModel.transform(assmblerDf)
    //    indexDf.show(false)
    //    +------------+-----------+------------+-----------+-----------+-----------------+-----+
    //    |sepal_length|sepal_width|petal_length|petal_width|class      |features         |label|
    //      +------------+-----------+------------+-----------+-----------+-----------------+-----+
    //    |5.1         |3.5        |1.4         |0.2        |Iris-setosa|[5.1,3.5,1.4,0.2]|0.0  |
    //      |4.9         |3.0        |1.4         |0.2        |Iris-setosa|[4.9,3.0,1.4,0.2]|0.0  |
        //4-3         ,              
        val Array(trainData,testData): Array[Dataset[Row]] = indexDf.randomSplit(Array(0.8,0.2))
        //    * 5-     ,         
        val classifier: DecisionTreeClassifier = new DecisionTreeClassifier().setFeaturesCol("features").setMaxBins(16).setImpurity("gini").setSeed(10)
        val dtcModel: DecisionTreeClassificationModel = classifier.fit(trainData)
        //    * 6-      
        val trainPre: DataFrame = dtcModel.transform(trainData)
        //    * 7-    
        val testPre: DataFrame = dtcModel.transform(testData)
        //    * 8-        
        //val savePath = "E:\\ml\\workspace\\SparkMllibBase\\sparkmllib_part2\\DescitionTree\\model"
        //dtcModel.save(savePath)
    //    trainPre.show(false)
    //    +------------+-----------+------------+-----------+---------------+-----------------+-----+--------------+-------------+----------+
    //    |sepal_length|sepal_width|petal_length|petal_width|class          |features         |label|rawPrediction |probability  |prediction|
    //      +------------+-----------+------------+-----------+---------------+-----------------+-----+--------------+-------------+----------+
    //    |4.3         |3.0        |1.1         |0.1        |Iris-setosa    |[4.3,3.0,1.1,0.1]|0.0  |[47.0,0.0,0.0]|[1.0,0.0,0.0]|0.0       |
    //      |4.4         |2.9        |1.4         |0.2        |Iris-setosa    |[4.4,2.9,1.4,0.2]|0.0  |[47.0,0.0,0.0]|[1.0,0.0,0.0]|0.0       |
    //    testPre.show(false)
    //    +------------+-----------+------------+-----------+---------------+-----------------+-----+--------------+-------------+----------+
    //    |sepal_length|sepal_width|petal_length|petal_width|class          |features         |label|rawPrediction |probability  |prediction|
    //      +------------+-----------+------------+-----------+---------------+-----------------+-----+--------------+-------------+----------+
    //    |4.6         |3.2        |1.4         |0.2        |Iris-setosa    |[4.6,3.2,1.4,0.2]|0.0  |[47.0,0.0,0.0]|[1.0,0.0,0.0]|0.0       |
    //      |4.8         |3.4        |1.9         |0.2        |Iris-setosa    |[4.8,3.4,1.9,0.2]|0.0  |[47.0,0.0,0.0]|[1.0,0.0,0.0]|0.0       |
    //      |5.0         |2.0        |3.5         |1.0        |Iris-versicolor|[5.0,2.0,3.5,1.0]|1.0  |[0.0,33.0,0.0]|[0.0,1.0,0.0]|1.0       |
        val acc: Double = new MulticlassClassificationEvaluator().setMetricName("accuracy").evaluate(testPre)
        println("acc is ", acc)
        println("err is", (1-acc))
        // 9-                      
        val indexToString: IndexToString = new IndexToString().setInputCol("prediction").setOutputCol("preStringLabel").setLabels(stingIndexModel.labels)
        val result: DataFrame = indexToString.transform(testPre)
    //    result.show(false)
    //    +------------+-----------+------------+-----------+---------------+-----------------+-----+--------------+-------------------------------------------+----------+---------------+
    //    |sepal_length|sepal_width|petal_length|petal_width|class          |features         |label|rawPrediction |probability                                |prediction|preStringLabel |
    //      +------------+-----------+------------+-----------+---------------+-----------------+-----+--------------+-------------------------------------------+----------+---------------+
    //    |4.6         |3.6        |1.0         |0.2        |Iris-setosa    |[4.6,3.6,1.0,0.2]|0.0  |[38.0,0.0,0.0]|[1.0,0.0,0.0]                              |0.0       |Iris-setosa    |
    //      |4.8         |3.4        |1.6         |0.2        |Iris-setosa    |[4.8,3.4,1.6,0.2]|0.0  |[38.0,0.0,0.0]|[1.0,0.0,0.0]                              |0.0       |Iris-setosa    |
      }
    }
    
    
  • 좋은 웹페이지 즐겨찾기