Scaling Up the Accuracy of Naive-Ba

Scaling Up the Accuracy of Naive-Bayes Classiers:
a Decision-Tree Hybrid
Ron Kohavi
Data Mining and Visualization
Silicon Graphics, Inc.
2011 N. Shoreline Blvd
Mountain View, CA 94043-1389
[e-mail]
Abstract
Naive-Bayes induction algorithms were previously
shown to be surprisingly accurate on many classi-
cation tasks even when the conditional independence
assumption on which they are based is violated. However,
most studies were done on small databases. We
show that in some larger databases, the accuracy of
Naive-Bayes does not scale up as well as decision trees.
We then propose a new algorithm, NBTree, which induces
a hybrid of decision-tree classiers and NaiveBayes
classiers: the decision-tree nodes contain univariate
splits as regular decision-trees, but the leaves
contain Naive-Bayesian classiers. The approach retains
the interpretability of Naive-Bayes and decision
trees, while resulting in classiers that frequently outperform
both constituents, especially in the larger
databases tested.
Introduction
Seeing the future rst requires not only a wide-angle
lens, it requires a multiplicity of lenses
|Hamel & Prahalad (1994), p. 95
Many data mining tasks require classication of data
into classes. For example, loan applications can be
classied into either 'approve' or 'disapprove' classes.
A classier provides a function that maps (classies)
a data item (instance) into one of several predened
classes (Fayyad, Piatetsky-Shapiro, & Smyth 1996).
The automatic induction of classiers from data not
only provides a classier that can be used to map new
instances into their classes, but may also provide a
human-comprehensible characterization of the classes.
In many cases, interpretability|the ability to understand
the output of the induction algorithm|is a crucial
step in the design and analysis cycle. Some classi
ers are naturally easier to interpret than others; for
example, decision-trees (Quinlan 1993) are easy to visualize,
while neural-networks are much harder.
Naive-Bayes classiers (Langley, Iba, & Thompson
1992) are generally easy to understand and the induction
of these classiers is extremely fast, requiring
only a single pass through the data if all attributes
are discrete. Naive-Bayes classiers are also very simple
and easy to understand. Kononenko (1993) wrote
that physicians found the induced classiers easy to
understand when the log probabilities were presented
as evidence that adds up in favor of dierent classes.
Figure 1 shows a visualization of the Naive-Bayes
classier for Fisher's Iris data set, where the task is
to determine the type of iris based on four attributes.
Each bar represents evidence for a given class and attribute
value. Users can immediately see that all values
for petal-width and petal length are excellent determiners,
while the middle range (2.95-3.35) for sepalwidth
adds little evidence in favor of one class or another.
Naive-Bayesian classiers are very robust to irrelevant
attributes, and classication takes into account
evidence from many attributes to make the nal prediction,
a property that is useful in many cases where
there is no main eect." On the downside, NaiveBayes
classiers require making strong independence
assumptions and when these are violated, the achievable
accuracy may asymptote early and will not improve
much as the database size increases.
Decision-tree classiers are also fast and comprehensible,
but current induction methods based on recursive
partitioning suer from the fragmentation problem: as
each split is made, the data is split based on the test
and after two dozen levels there is usually very little
data on which to base decisions.
In this paper we describe a hybrid approach that
attempts to utilize the advantages of both decisiontrees
(i.e., segmentation) and Naive-Bayes (evidence
accumulation from multiple attributes). A decisiontree
is built with univariate splits at each node, but
with Naive-Bayes classiers at the leaves. The nal
classier resembles Utgo 's Perceptron trees (Utgo
1988), but the induction process is very dierent and
geared toward larger datasets.
The resulting classier is as easy to interpret as
Figure 1: Visualization of a Naive-Bayes classier for the iris dataset.
decision-trees and Naive-Bayes. The decision-tree segments
the data, a task that is consider an essential part
of the data mining process in large databases (Brachman
& Anand 1996). Each segment of the data, represented
by a leaf, is described through a Naive-Bayes
classier. As will be shown later, the induction algorithm
segments the data so that the conditional independence
assumptions required for Naive-Bayes are
likely to be true.
The Induction Algorithms
We brie
y review methods for induction of decisiontrees
and Naive-Bayes.
Decision-tree (Quinlan 1993; Breiman et al. 1984)
are commonly built by recursive partitioning. A univariate
(single attribute) split is chosen for the root
of the tree using some criterion (e.g., mutual information,
gain-ratio, gini index). The data is then divided
according to the test, and the process repeats
recursively for each child. After a full tree is built, a
pruning step is executed, which reduces the tree size.
In the experiments, we compared our results with the
C4.5 decision-tree induction algorithm (Quinlan 1993),
which is a state-of-the-art algorithm.
Naive-Bayes (Good 1965; Langley, Iba, & Thompson
1992) uses Bayes rule to compute the probability
of each class given the instance, assuming the attributes
are conditionally independent given the label.
The version of Naive-Bayes we use in our experiments
was implemented in MLC++ (Kohavi et
al. 1994). The data is pre-discretized using the
an entropy-based algorithm (Fayyad & Irani 1993;
Dougherty, Kohavi, & Sahami 1995). The probabilities
are estimated directly from data based directly
on counts (without any corrections, such as Laplace or
m-estimates).
Accuracy Scale-Up: the Learning
Curves
A Naive-Bayes classier requires estimation of the conditional
probabilities for each attribute value given the
label. For discrete data, because only few parameters
need to be estimated, the estimates tend to stabilize
quickly and more data does not change the underlying
model much. With continuous attributes, the discretization
is likely to form more intervals as more data
is available, thus increasing the representation power.
However, even with continuous data, the discretization
is global and cannot take into account attribute interactions.
Decision-trees are non-parametric estimators and
can approximate any
easonable" function as the
database size grows (Gordon & Olshen 1984). This
theoretical result, however, may not be very comforting
if the database size required to reach the asymptotic
performance is more than the number of atoms
in the universe, as is sometimes the case. In practice,
some parametric estimators, such as Naive-Bayes, may
perform better.
Figure 2 shows learning curves for both algorithms
on large datasets from the UC Irvine repository1
(Murphy
& Aha 1996). The learning curves show how the
accuracy changes as more instances (training data) are
shown to the algorithm. The accuracy is computed
based on the data not used for training, so it represents
the true generalization accuracy. Each point was
computed as an average of 20 runs of the algorithm,
and 20 intervals were used. The error bars show 95%
condence intervals on the accuracy, based on the leftout
sample.
In most cases it is clear that even with much more
1
The Adult dataset is from the Census bureau and the
task is to predict whether a given adult makes more than
$50,000 a year based attributes such as education, hours of
work per week, etc..
74
76
78
80
82
84
86
88
90
92
94
96
0 500 1000 1500 2000 2500
accuracy
instances
DNA
Naive-Bayes
C4.5
66
68
70
72
74
76
78
80
82
0 1000 2000 3000 4000
accuracy
instances
waveform-40
Naive-Bayes
C4.5
56
58
60
62
64
66
68
70
72
74
0 500 1000 1500 2000 2500
accuracy
instances
led24
Naive-Bayes
C4.5
99
99.1
99.2
99.3
99.4
99.5
99.6
99.7
99.8
99.9
100
0 15,000 30,000 45,000 60,000
accuracy
instances
shuttle
Naive-Bayes
C4.5
60
65
70
75
80
85
90
0 5,000 10,000 15,000 20,000
accuracy
instances
letter
Naive-Bayes
C4.5
82
82.5
83
83.5
84
84.5
85
85.5
86
86.5
0 15,000 30,000 45,000
accuracy
instances
adult
Naive-Bayes
C4.5
80
82
84
86
88
90
92
94
96
98
100
0 500 1000 1500 2000 2500
accuracy
instances
chess
Naive-Bayes
C4.5
93
94
95
96
97
98
99
100
0 2,000 4,000 6,000 8,000
accuracy
instances
mushroom
Naive-Bayes
C4.5
76
78
80
82
84
86
88
0 1000 2000 3000 4000 5000 6000
accuracy
instances
satimage
Naive-Bayes
C4.5
Figure 2: Learning curves for Naive-Bayes and C4.5. The top three graphs show datasets where Naive-Bayes outperformed
C4.5, and the lower six graphs show datasets where C4.5 outperformed Naive-Bayes. The error bars are 95% condence
intervals on the accuracy.
data, the learning curves will not cross. While it is
well known that no algorithm can outperform all others
in all cases (Wolpert 1994), our world does tend to
have some smoothness conditions and algorithms can
be more successful than others in practice. In the next
section we show that a hybrid approach can improve
both algorithms in important practical datasets.
NBTree: The Hybrid Algorithm
The NBTree algorithm we propose is shown in Figure
3. The algorithm is similar to the classical recursive
partitioning schemes, except that the leaf nodes
created are Naive-Bayes categorizers instead of nodes
predicting a single class.
A threshold for continuous attributes is chosen using
the standard entropy minimization technique, as is
done for decision-trees. The utility of a node is computed
by discretizing the data and computing the 5-
fold cross-validation accuracy estimate of using NaiveBayes
at the node. The utility of a split is the weighted
sum of the utility of the nodes, where the weight given
to a node is proportional to the number of instances
that go down to that node.
Intuitiv

ผลลัพธ์ (ไทย) 1:

ปรับมาตราส่วนค่าแม่นยำของ Naive Bayes Classi สกู๊ป:ผสมต้นไม้การตัดสินใจKohavi รอนการทำเหมืองข้อมูลและการแสดงภาพประกอบเพลงซิลิคอนกราฟิก incBlvd 2011 N. ชายฝั่งภูเขา CA [e-mail]บทคัดย่อNaive Bayes เหนี่ยวนำอัลกอริทึมก่อนหน้านี้แสดงเป็นที่น่าแปลกใจที่ถูกต้องบน classi มาก-cation งานแม้เป็นอิสระแบบมีเงื่อนไขมีละเมิดซึ่งจะอยู่อัสสัมชัญ อย่างไรก็ตามการศึกษาส่วนใหญ่ได้ทำในฐานข้อมูลขนาดเล็ก เราแสดงว่าในฐานข้อมูลขนาดใหญ่ ความถูกต้องของNaive Bayes ไม่ปรับและต้นไม้ตัดสินใจเราเสนอตัวใหม่อัลกอริทึม NBTree ซึ่งแท้จริงแล้วผสมของสกู๊ป classi ต้นไม้การตัดสินใจและ NaiveBayesสกู๊ป classi: โหนต้นไม้การตัดสินใจประกอบด้วยอย่างไร univariateแยกเป็นต้นไม้ตัดสินใจปกติ แต่ใบไม้ประกอบด้วยสกู๊ป classi Naive ทฤษฎี วิธีการรักษาinterpretability Naive Bayes และตัดสินใจต้นไม้ ในขณะที่ในสกู๊ป classi ที่มักจะมีประสิทธิภาพสูงกว่าconstituents ทั้ง โดยเฉพาะอย่างยิ่งในใหญ่ทดสอบฐานข้อมูลแนะนำเห็น rst ในอนาคตต้องไม่เพียงแต่เป็นมุมกว้างเลนส์ ต้องการมากมายหลายหลากของเลนส์| Hamel และ Prahalad (1994), p. 95งานทำเหมืองข้อมูลต่าง ๆ ต้องใช้ cation classi ข้อมูลในห้องเรียน ตัวอย่าง โปรแกรมเงินกู้ได้classi ed ในชั้นเรียน 'อนุมัติ' หรือ 'กฤษฎีกาในการปฏิเสธ'การ classi เอ้อ แสดงฟังก์ชันที่แมป (classi es)แบบรายการข้อมูล (ตัวอย่าง) เป็นหนึ่งใน prede หลายบริษัทฯเรียน (Fayyad, Piatetsky Shapiro, & Smyth 1996)เหนี่ยวนำอัตโนมัติของสกู๊ป classi จากข้อมูลไม่ให้เฉพาะ classi กับเอ้อ ที่สามารถใช้กับแผนที่ใหม่อินสแตนซ์ในชั้นเรียนของพวกเขา แต่อาจให้การสมบัติมนุษย์ comprehensible ของคลาในหลายกรณี interpretability|the ความสามารถในการเข้าใจผลผลิตของ algorithm|is เหนี่ยวนำเป็นสำคัญขั้นตอนในการออกแบบและวิเคราะห์วงจร บาง classiสกู๊ปมีธรรมชาติง่ายต่อการแปลอื่น ๆ สำหรับตัวอย่าง การตัดสินใจต้นไม้ (Quinlan 1993) ได้ง่ายเห็นภาพในขณะที่เครือข่ายประสาทจะยากมากNaive Bayes สกู๊ป classi (ลแลงเกลย์ อิบา และทอมป์สัน1992) ง่ายโดยทั่วไปจะเข้าใจและการเหนี่ยวนำเหล่านี้ classi สกู๊ปเป็นเร็วมาก ต้องการตัวเดียวส่งผ่านข้อมูลถ้าคุณลักษณะทั้งหมดจะไม่ต่อเนื่อง Naive Bayes classi สกู๊ปก็ง่ายมากและเข้าใจง่าย เขียน Kononenko (1993)ที่แพทย์พบสกู๊ป classi เหนี่ยวนำให้แก่เข้าใจเมื่อมีการนำเสนอกิจกรรมบันทึกเป็นหลักฐานที่เพิ่มขึ้นสามารถเรียน erent ดิรูปที่ 1 แสดงเพลงของ Naive Bayesclassi เอ้อ ข้อมูล Iris ของ Fisher ตั้ง ตำแหน่งงานการกำหนดชนิดของไอริสตามคุณลักษณะ 4 ประการหลักฐานสำหรับกลุ่มและแอททริบิวต์สามค่า ผู้ใช้สามารถดูทั้งหมดค่าทันทีความยาวความกว้างกลีบดอกไม้และกลีบดอกไม้เป็นนามแห่งในขณะที่ช่วงกลาง (2.95-3.35) สำหรับ sepalwidthเพิ่มหลักฐานน้อยสามารถเรียนหนึ่งหรืออีกทฤษฎี naive classi สกู๊ปจะแข็งแกร่งมากจะเกี่ยวข้องกับคุณลักษณะ และ classi cation จะเข้าบัญชีหลักฐานจากแอตทริบิวต์จำนวนมากจะทำให้การคาดเดา nalคุณสมบัติที่มีประโยชน์ในกรณีe main ไม่มี ect " เกี่ยวกับ NaiveBayesสกู๊ป classi ต้องทำเป็นอิสระแข็งแรงสมมติฐาน และเมื่อเหล่านี้ถูกละเมิด ที่ทำได้ความถูกต้องอาจ asymptote ก่อน และจะปรับปรุงถึงฐานข้อมูลขนาดเพิ่มขึ้นสกู๊ป classi ต้นไม้การตัดสินใจก็รวดเร็ว และ comprehensibleแต่ปัจจุบันวิธีการเหนี่ยวนำตามซ้ำพาร์ทิชัน su เอ้อ จากปัญหาการกระจายตัวของ: เป็นทำการแยกแต่ละ ข้อมูลถูกแบ่งออกตามการทดสอบและหลังจากระดับสองโหล ได้มักมากข้อมูลที่จะใช้เป็นพื้นฐานการตัดสินใจในเอกสารนี้เราอธิบาย ผสมวิธีที่พยายามใช้ข้อดีของทั้งสอง decisiontrees(เช่น เซ็ก) และ Naive Bayes (หลักฐานรวบรวมจากหลายแอตทริบิวต์) Decisiontree การแห่งอย่างไร univariate แยกในแต่ละโหน แต่มีสกู๊ป classi Naive Bayes ที่ใบไม้ Nalclassi เอ้อ คล้ายกับ Utgo ของเพอร์เซปตรอนต้นไม้ (Utgo 1988), แต่การเหนี่ยวนำได้ดีมาก erent และมุ่งไปทาง datasets ขนาดใหญ่Classi ได้เอ้อ จะให้แปลเป็นรูปที่ 1: ภาพแสดง classi Naive Bayes เอ้อ สำหรับชุดข้อมูล irisต้นไม้ตัดสินใจและ Naive Bayes ส่วนต้นไม้การตัดสินใจข้อมูล งานที่จะพิจารณาเป็นส่วนสำคัญการทำเหมืองข้อมูลในฐานข้อมูลขนาดใหญ่ (Brachmanและอานันท์ 1996) แต่ละส่วนของข้อมูล แสดงโดยใบไม้ มีอธิบายผ่านการ Bayes Naiveclassi เอ้อ ตามที่จะปรากฏในภายหลัง อัลกอริทึมการเหนี่ยวนำส่วนข้อมูลที่เป็นอิสระแบบมีเงื่อนไขมีสมมติฐานที่จำเป็นสำหรับ Naive Bayesแนวโน้มที่จะเป็นจริงอัลกอริทึมการเหนี่ยวนำเราบรีฮาร์ดดิ้งy การตรวจสอบวิธีการเหนี่ยวนำของ decisiontreesและ Naive Bayes-ต้นไม้การตัดสินใจ (Quinlan 1993 Breiman et al. 1984)โดยทั่วไปถูกสร้างขึ้น โดยการแบ่งพาร์ทิชันซ้ำ เป็นอย่างไร univariateเลือก (แอตทริบิวต์เดียว) แบ่งรากของแผนภูมิโดยใช้เกณฑ์บางอย่าง (เช่น ข้อมูลซึ่งกันและกันกำไรอัตราส่วน ดัชนี gini) ก็มีแบ่งข้อมูลตามการทดสอบ และทำซ้ำกระบวนการrecursively สำหรับเด็กแต่ละคน หลังจากสร้างแผนภูมิแบบเต็ม แบบขั้นตอนการตัดจะดำเนินการ ซึ่งช่วยลดขนาดของแผนภูมิในการทดลอง เราเปรียบเทียบผลของเราด้วยการขั้นตอนวิธีเหนี่ยวนำต้นไม้ตัดสินใจ C4.5 (Quinlan 1993),ซึ่งเป็นอัลกอริทึมเป็นรัฐ-of-the-artNaive Bayes (1965 ดี ลแลงเกลย์ อิบา และทอมป์สันกฎ Bayes 1992) ใช้เพื่อคำนวณความน่าเป็นของแต่ละชั้นให้อินสแตนซ์ สมมติว่าแอตทริบิวต์ได้อิสระอย่างมีเงื่อนไขกำหนดป้ายชื่อรุ่นเราใช้ในการทดลองของ Bayes Naiveได้ดำเนินการใน MLC ++ (Kohavi etal. 1994) ข้อมูลเป็น discretized ก่อนโดยใช้การการใช้เอนโทรปีอัลกอริทึม (Fayyad และ Irani 1993Dougherty, Kohavi, & Sahami 1995). The probabilitiesare estimated directly from data based directlyon counts (without any corrections, such as Laplace orm-estimates).Accuracy Scale-Up: the LearningCurvesA Naive-Bayes classi er requires estimation of the conditionalprobabilities for each attribute value given thelabel. For discrete data, because only few parametersneed to be estimated, the estimates tend to stabilizequickly and more data does not change the underlyingmodel much. With continuous attributes, the discretizationis likely to form more intervals as more datais available, thus increasing the representation power.However, even with continuous data, the discretizationis global and cannot take into account attribute interactions.Decision-trees are non-parametric estimators andcan approximate any
easonable" function as thedatabase size grows (Gordon & Olshen 1984). Thistheoretical result, however, may not be very comfortingif the database size required to reach the asymptoticperformance is more than the number of atomsin the universe, as is sometimes the case. In practice,some parametric estimators, such as Naive-Bayes, mayperform better.Figure 2 shows learning curves for both algorithmson large datasets from the UC Irvine repository1(Murphy& Aha 1996). The learning curves show how theaccuracy changes as more instances (training data) areshown to the algorithm. The accuracy is computedbased on the data not used for training, so it representsthe true generalization accuracy. Each point wascomputed as an average of 20 runs of the algorithm,and 20 intervals were used. The error bars show 95%con dence intervals on the accuracy, based on the leftoutsample.In most cases it is clear that even with much more1The Adult dataset is from the Census bureau and thetask is to predict whether a given adult makes more than$50,000 a year based attributes such as education, hours ofwork per week, etc..7476788082848688909294960 500 1000 1500 2000 2500accuracyinstancesDNANaive-BayesC4.56668707274767880820 1000 2000 3000 4000accuracyinstanceswaveform-40Naive-BayesC4.5565860626466687072740 500 1000 1500 2000 2500accuracyinstancesled24Naive-BayesC4.59999.199.299.399.499.599.699.799.899.91000 15,000 30,000 45,000 60,000accuracyinstancesshuttleNaive-BayesC4.5606570758085900 5,000 10,000 15,000 20,000accuracyinstancesletterNaive-BayesC4.58282.58383.58484.58585.58686.50 15,000 30,000 45,000accuracyinstancesadultNaive-BayesC4.5808284868890929496981000 500 1000 1500 2000 2500accuracyinstanceschessNaive-BayesC4.5939495969798991000 2,000 4,000 6,000 8,000accuracyinstancesmushroomNaive-BayesC4.5767880828486880 1000 2000 3000 4000 5000 6000accuracyinstancessatimageNaive-BayesC4.5Figure 2: Learning curves for Naive-Bayes and C4.5. The top three graphs show datasets where Naive-Bayes outperformedC4.5, and the lower six graphs show datasets where C4.5 outperformed Naive-Bayes. The error bars are 95% con denceintervals on the accuracy.data, the learning curves will not cross. While it iswell known that no algorithm can outperform all othersin all cases (Wolpert 1994), our world does tend tohave some smoothness conditions and algorithms canbe more successful than others in practice. In the nextsection we show that a hybrid approach can improveboth algorithms in important practical datasets.NBTree: The Hybrid AlgorithmThe NBTree algorithm we propose is shown in Figure3. The algorithm is similar to the classical recursivepartitioning schemes, except that the leaf nodescreated are Naive-Bayes categorizers instead of nodespredicting a single class.A threshold for continuous attributes is chosen usingthe standard entropy minimization technique, as isdone for decision-trees. The utility of a node is computedby discretizing the data and computing the 5-fold cross-validation accuracy estimate of using NaiveBayesat the node. The utility of a split is the weightedsum of the utility of the nodes, where the weight givento a node is proportional to the number of instancesthat go down to that node.Intuitiv

ผลลัพธ์ (ไทย) 2:

การปรับขึ้นความถูกต้องของ ERS Naive Bayes Classi-:
การตัดสินใจต้นไม้ไฮบริดรอน Kohavi การทำเหมืองข้อมูลและการแสดงSilicon Graphics, Inc 2011 N. Shoreline Blvd Mountain View, CA 94043-1389 [e-mail] บทคัดย่อNaive Bayes-ขั้นตอนวิธีการเหนี่ยวนำก่อนหน้านี้แสดงให้เห็นว่ามีความถูกต้องน่าแปลกใจที่ในการจัดประเภทจำนวนมาก - งานไอออนบวกแม้ในขณะที่ความเป็นอิสระเงื่อนไขสมมติฐานที่พวกเขาจะขึ้นเป็นละเมิด อย่างไรก็ตามการศึกษาส่วนใหญ่ได้กระทำในฐานข้อมูลขนาดเล็ก เราแสดงให้เห็นว่าในบางฐานข้อมูลขนาดใหญ่ที่ถูกต้องของหน่อมแน้ม-เบส์ไม่ได้ไต่ขึ้นเช่นเดียวกับต้นไม้ตัดสินใจ. จากนั้นเราจะเสนอวิธีการใหม่ NBTree ซึ่งก่อให้เกิดการไฮบริดของERS จัดประเภทการตัดสินใจต้นไม้และ NaiveBayes ERS จัดประเภท: การตัดสินใจ โหนด -tree มี univariate แยกเป็นปกติตัดสินใจต้นไม้ แต่ใบมีERS จัดประเภทไร้เดียงสา-เบย์ วิธีการที่ยังคงรักษาinterpretability ของหน่อมแน้ม-เบส์และการตัดสินใจต้นไม้ในขณะที่ผลในERS จัดประเภทที่มักจะมีประสิทธิภาพสูงกว่าองค์ประกอบทั้งสองโดยเฉพาะในที่มีขนาดใหญ่ฐานข้อมูลการทดสอบ. บทนำเห็นครั้งแรกในอนาคตต้องไม่เพียงแต่เป็นมุมกว้างเลนส์ก็ต้องหลายหลากของเลนส์| Hamel และ Prahalad (1994), หน้า 95 หลายงานที่ต้องมีการทำเหมืองข้อมูลไอออนจัดประเภทของข้อมูลในชั้นเรียน ตัวอย่างเช่นโปรแกรมเงินกู้สามารถเอ็ดจัดประเภทเข้าไปในทั้ง 'อนุมัติ' หรือ 'ไม่อนุมัติ' เรียน. เอ้อจัดประเภทให้ฟังก์ชั่นที่แมป (จัดประเภท e) รายการข้อมูล (ตัวอย่าง) เป็นหนึ่งใน ned prede หลายชั้นเรียน(Fayyad, Piatetsky- ชาปิโรส์และเบิร์นส 1996). เหนี่ยวนำโดยอัตโนมัติของผูจัดประเภทจากข้อมูลที่ไม่เพียงแต่ให้เอ้อจัดประเภทที่สามารถนำมาใช้ในการทำแผนที่ใหม่กรณีในชั้นเรียนของพวกเขาแต่ยังอาจมีลักษณะของมนุษย์เข้าใจของการเรียน. ในหลายกรณี interpretability | ความสามารถในการเข้าใจการส่งออกของขั้นตอนวิธีการเหนี่ยวนำที่| เป็นสำคัญขั้นตอนในวงจรการออกแบบและการวิเคราะห์ บางจัดประเภทERS เป็นธรรมชาติง่ายต่อการตีความกว่าคนอื่น ๆ ; สำหรับตัวอย่างเช่นการตัดสินใจต้นไม้ (ควินแลน 1993) เป็นเรื่องง่ายที่จะเห็นภาพในขณะที่เครือข่ายประสาทจะยากมาก. หน่อมแน้ม-Bayes ERS จัดประเภท (แลงลีย์, Iba และ ธ อมป์สัน1992) โดยทั่วไปมักจะง่ายต่อการเข้าใจและการเหนี่ยวนำของเหล่านี้ERS จัดประเภทเป็น ได้อย่างรวดเร็วต้องใช้เพียงบัตรเดียวผ่านข้อมูลหากคุณลักษณะทั้งหมดที่มีต่อเนื่อง หน่อมแน้ม-Bayes ERS จัดประเภทนอกจากนี้ยังง่ายมากและง่ายต่อการเข้าใจ Kononenko (1993) เขียนว่าแพทย์พบERS จัดประเภทเหนี่ยวนำให้เกิดเรื่องง่ายที่จะเข้าใจเมื่อความน่าจะเป็นบันทึกที่มีการนำเสนอเป็นหลักฐานที่เพิ่มขึ้นในความโปรดปรานของดิ? เรียนต่างกัน. รูปที่ 1 แสดงให้เห็นถึงการสร้างภาพของหน่อมแน้ม-Bayes จัดประเภทเอ้อข้อมูลไอริสฟิชเชอร์ ชุดที่งานคือเพื่อกำหนดประเภทของไอริสขึ้นอยู่กับสี่คุณลักษณะ. บาร์แต่ละหลักฐานสำหรับการเรียนที่กำหนดและแอตทริบิวต์ค่า ผู้ใช้ทันทีจะเห็นว่าค่าทั้งหมดสำหรับกลีบดอกกว้างและความยาวกลีบดอกมี determiners ที่ยอดเยี่ยมขณะที่ช่วงกลาง(2.95-3.35) สำหรับ sepalwidth เพิ่มหลักฐานเพียงเล็กน้อยในความโปรดปรานของชั้นหนึ่งหรืออื่น. หน่อมแน้ม-คชกรรม ERS จัดประเภทที่มีประสิทธิภาพมากในการที่ไม่เกี่ยวข้องคุณลักษณะและไอออนบวกจัดประเภทคำนึงถึงหลักฐานจากคุณลักษณะมากมายที่จะทำให้การคาดการณ์ NAL, สถานที่ให้บริการที่เป็นประโยชน์ในหลาย ๆ กรณีที่ไม่มี จหลัก? ect. "ในข้อเสีย NaiveBayes ERS จัดประเภทต้องทำให้ความเป็นอิสระที่แข็งแกร่งสมมติฐานและเมื่อเหล่านี้จะถูกละเมิดทำได้ถูกต้องอาจจะสิ้นสุดในช่วงต้นและจะไม่เพิ่มมากที่สุดเท่าที่เพิ่มขนาดของฐานข้อมูล. ERS จัดประเภทการตัดสินใจต้นไม้นอกจากนี้ยังได้อย่างรวดเร็วและเข้าใจแต่วิธีการเหนี่ยวนำในปัจจุบันขึ้นอยู่กับ recursive แบ่ง su เอ้อจากปัญหาการกระจายตัว: เป็นแต่ละแยกทำที่ข้อมูลจะถูกแยกอยู่บนพื้นฐานของการทดสอบและหลังจากที่สองระดับโหลมักจะมีน้อยมากข้อมูลที่จะตัดสินใจ. ในบทความนี้เราจะอธิบายวิธีการไฮบริดที่พยายามที่จะใช้ประโยชน์จากข้อได้เปรียบของ decisiontrees ทั้ง (เช่น การแบ่งส่วน) และไร้เดียงสา-เบส์ (หลักฐานสะสมจากคุณลักษณะหลาย) decisiontree ถูกสร้างขึ้นด้วย univariate แยกในแต่ละโหนด แต่ด้วยความไร้เดียงสา-Bayes ERS จัดประเภทที่ใบ NAL เอ้อจัดประเภทคล้าย Utgo? ของต้นไม้ Perceptron (Utgo? แต่กระบวนการเหนี่ยวนำเป็นอย่างมาก di ต่างกันและ 1988) มุ่งเน้นที่ชุดข้อมูลขนาดใหญ่. เอ่อจัดประเภทที่เกิดขึ้นเป็นเรื่องง่ายที่จะตีความว่าเป็นรูปที่ 1: การแสดงของหน่อมแน้ม-Bayes จัดประเภทเอ้อสำหรับชุดข้อมูลที่ม่านตา . การตัดสินใจของต้นไม้และไร้เดียงสา-Bayes ส่วนการตัดสินใจต้นไม้ข้อมูลเป็นงานที่ต้องพิจารณาเป็นส่วนสำคัญของกระบวนการทำเหมืองข้อมูลในฐานข้อมูลขนาดใหญ่(Brachman และอานันท์ 1996) แต่ละส่วนของข้อมูลที่แสดงโดยใบมีการอธิบายผ่าน Naive Bayes-จัดประเภทเอ้อ ในฐานะที่จะแสดงต่อมาขั้นตอนวิธีการเหนี่ยวนำกลุ่มข้อมูลเพื่อให้ความเป็นอิสระตามเงื่อนไขข้อสมมติฐานที่จำเป็นสำหรับการไร้เดียงสา-เบส์มีแนวโน้มที่จะเป็นจริง. ขั้นตอนวิธีการเหนี่ยวนำเรา Brie y ที่วิธีการตรวจสอบสำหรับการเหนี่ยวนำของ decisiontrees และไร้เดียงสา-Bayes. ตัดสินใจต้นไม้ ( ควินแลน 1993. Breiman et al, 1984) ที่ถูกสร้างขึ้นโดยทั่วไปแบ่ง recursive univariate (แอตทริบิวต์เดี่ยว) แยกเป็นทางเลือกสำหรับรากของต้นไม้โดยใช้เกณฑ์บางอย่าง(เช่นข้อมูลรวมกำไรอัตราส่วนดัชนี gini) ข้อมูลจะถูกแบ่งออกเป็นไปตามผลการทดสอบและกระบวนการซ้ำซ้ำสำหรับเด็กแต่ละคน หลังจากที่มีต้นไม้เต็มรูปแบบที่ถูกสร้างขึ้นเป็นขั้นตอนที่จะดำเนินการตัดแต่งกิ่งซึ่งจะช่วยลดขนาดของต้นไม้. ในการทดลองที่เราเปรียบเทียบผลของเรามีขั้นตอนวิธีการเหนี่ยวนำการตัดสินใจต้นไม้ C4.5 (ควินแลน 1993) ซึ่งเป็นรัฐของ อัลกอริทึม -Art. หน่อมแน้ม-เบส์ (1965 ดี; แลงลีย์, Iba และ ธ อมป์สัน1992) ใช้กฎเบส์ในการคำนวณความน่าจะเป็นของแต่ละระดับได้รับตัวอย่างเช่นสมมติว่าคุณสมบัติมีความเป็นอิสระตามเงื่อนไขที่กำหนดฉลาก. รุ่น Naive Bayes-เรา ใช้ในการทดลองของเราได้ดำเนินการในแอลซี++ (Kohavi et al. 1994) ข้อมูลที่เป็น pre-discretized โดยใช้ขั้นตอนวิธีการปฎิบัติตาม(Fayyad และอิหร่านนิ 1993; โดเฮอร์ที Kohavi และ Sahami 1995) ความน่าจะเป็นประมาณโดยตรงจากข้อมูลโดยตรงในจำนวน(ไม่มีการแก้ไขใด ๆ เช่นเลซหรือมประมาณการ). ความถูกต้องชั่ง-Up: การเรียนรู้โค้งไร้เดียงสา-Bayes เอ้อจัดประเภทต้องใช้การประมาณค่าของเงื่อนไขความน่าจะเป็นของแต่ละแอตทริบิวต์ค่าที่กำหนดฉลาก สำหรับข้อมูลที่ไม่ต่อเนื่องเพราะเพียงไม่กี่พารามิเตอร์จะต้องมีการประมาณประมาณการที่มีแนวโน้มที่จะมีเสถียรภาพได้อย่างรวดเร็วและข้อมูลได้มากขึ้นไม่เปลี่ยนแปลงพื้นฐานรูปแบบมาก ที่มีคุณลักษณะอย่างต่อเนื่องต่อเนื่องมีแนวโน้มที่จะสร้างช่วงเวลาที่มากขึ้นเป็นข้อมูลเพิ่มเติมสามารถใช้ได้ซึ่งจะเป็นการเพิ่มอำนาจการเป็นตัวแทน. อย่างไรก็ตามแม้จะมีข้อมูลอย่างต่อเนื่องต่อเนื่องเป็นทั่วโลกและไม่สามารถนำเข้าบัญชีแอตทริบิวต์ปฏิสัมพันธ์. ตัดสินใจต้นไม้จะไม่พารา ประมาณและสามารถใกล้เคียงกับใดๆ สมเหตุสมผล "ฟังก์ชั่นเป็นขนาดฐานข้อมูลเติบโต(กอร์ดอนและ Olshen 1984). นี้ผลทางทฤษฎีแต่อาจจะไม่มากปลอบโยนถ้าขนาดของฐานข้อมูลที่จำเป็นในการเข้าถึง asymptotic ประสิทธิภาพมากกว่าจำนวนของอะตอมในจักรวาลที่เป็นบางครั้งกรณี. ในทางปฏิบัติบางส่วนประมาณค่าพารามิเตอร์เช่นหน่อมแน้ม-Bayes อาจทำงานได้ดีขึ้น. รูปที่ 2 แสดงให้เห็นว่าเส้นโค้งการเรียนรู้สำหรับขั้นตอนวิธีการทั้งสองในชุดข้อมูลขนาดใหญ่จากUC Irvine repository1 (เมอร์ฟี่และ Aha 1996). โดย เส้นโค้งการเรียนรู้ที่แสดงให้เห็นว่าการเปลี่ยนแปลงความถูกต้องเป็นกรณีที่มากขึ้น(ข้อมูลการฝึกอบรม) จะแสดงให้เห็นว่าอัลกอริทึม. ความถูกต้องคือการคำนวณบนพื้นฐานของข้อมูลที่ไม่ได้ใช้สำหรับการฝึกอบรมเพื่อให้มันหมายถึงความถูกต้องเป็นจริงทั่วไป แต่ละจุดได้รับการคำนวณค่าเฉลี่ยของ 20 วิ่งของอัลกอริทึม, และ 20 ช่วงเวลาที่ถูกนำมาใช้ แถบข้อผิดพลาดแสดง 95% ช่วงเวลาที่มั่นใจแย้งกับความถูกต้องบนพื้นฐานของ leftout ตัวอย่าง. ในกรณีส่วนใหญ่ก็เป็นที่ชัดเจนว่าแม้จะมีมากขึ้น1 ชุดผู้ใหญ่มาจากสำนักสำรวจสำมะโนประชากรและงานคือการคาดการณ์ว่าจะเป็นผู้ใหญ่ที่ได้รับทำให้มากกว่า$ 50,000 ต่อปีตามคุณลักษณะเช่นการศึกษาชั่วโมงการทำงานต่อสัปดาห์ฯลฯ .. 74 76 78 80 82 84 86 88 90 92 94 96 0 500 1000 1500 2000 2500 ความถูกต้องกรณีดีเอ็นเอNaive Bayes-C4.5 66 68 70 72 74 76 78 80 82 0 1000 2000 3000 4000 ความถูกต้องกรณีสัญญาณ-40 Naive Bayes-C4.5 56 58 60 62 64 66 68 70 72 74 0 500 1000 1500 2000 2500 ความถูกต้องกรณีled24 Naive Bayes-C4.5 99 99.1 99.2 99.3 99.4 99.5 99.6 99.7 99.8 99.9 100 0 15,000 30,000 45,000 60,000 ความถูกต้องกรณีรถรับส่งNaive Bayes-C4.5 60 65 70 75 80 85 90 0 5,000 10,000 15,000 20,000 ความถูกต้องกรณีจดหมายNaive Bayes-C4.5 82 82.5 83 83.5 84 84.5 85 85.5 86 86.5 0 15,000 30,000 45,000 ความถูกต้องกรณีผู้ใหญ่ไร้เดียงสาBayes-C4.5 80 82 84 86 88 90 92 94 96 98 100 0 500 1000 1500 2000 2500 ความถูกต้องกรณีหมากรุกNaive Bayes-C4.5 93 94 95 96 97 98 99 100 0 2000 4000 6000 8000 ความถูกต้องกรณีเห็ดNaive Bayes-C4.5 76 78 80 82 84 86 88 0 1000 2000 3000 4000 5000 6000 ความถูกต้องกรณีsatimage Naive Bayes-C4.5 รูปที่ 2: เส้นโค้งการเรียนรู้สำหรับหน่อมแน้ม-Bayes และ C4.5 . ชั้นสามกราฟแสดงชุดข้อมูลที่ไร้เดียงสา-Bayes เฮงC4.5 และต่ำกว่าหกกราฟแสดงชุดข้อมูลที่หน่อมแน้มเฮง C4.5-Bayes แถบข้อผิดพลาดอยู่ 95% มั่นใจนักโทษช่วงเวลากับความถูกต้อง. ข้อมูลเส้นโค้งการเรียนรู้ที่จะไม่ข้าม ในขณะที่มันเป็นที่รู้จักกันดีว่าอัลกอริทึมที่ไม่สามารถมีประสิทธิภาพสูงกว่าคนอื่น ๆ ทั้งหมดในทุกกรณี(Wolpert 1994) โลกของเราจะมีแนวโน้มที่จะมีความเรียบเนียนบางเงื่อนไขและขั้นตอนวิธีสามารถจะประสบความสำเร็จมากกว่าคนอื่นๆ ในทางปฏิบัติ ในครั้งต่อไปส่วนที่เราแสดงให้เห็นว่าวิธีการไฮบริดสามารถปรับปรุงขั้นตอนวิธีการทั้งในชุดข้อมูลปฏิบัติที่สำคัญ. NBTree: ไฮบริดขั้นตอนวิธีอัลกอริทึมNBTree เรานำเสนอจะแสดงในรูปที่3 ขั้นตอนวิธีการคล้ายกับ recursive คลาสสิกรูปแบบการแบ่งพาร์ทิชันยกเว้นว่าโหนดใบที่สร้างขึ้นมีความไร้เดียงสา-Bayes categorizers แทนโหนดทำนายชั้นเดียว. เกณฑ์สำหรับแอตทริบิวต์อย่างต่อเนื่องจะได้รับการแต่งตั้งโดยใช้เทคนิคการลดมาตรฐานเอนโทรปีเป็นที่ทำเพื่อตัดสินใจต้นไม้ ยูทิลิตี้ของโหนดจะถูกคำนวณโดย discretizing ข้อมูลและคำนวณ 5 เท่าประมาณการความถูกต้องของการตรวจสอบข้ามของการใช้ NaiveBayes ที่โหนด ยูทิลิตี้ของแยกเป็นถ่วงน้ำหนักผลรวมของยูทิลิตี้ของโหนดที่น้ำหนักที่กำหนดไปยังโหนดเป็นสัดส่วนกับจำนวนของกรณีที่ลงไปยังโหนดที่. Intuitiv

ผลลัพธ์ (ไทย) 3:

การเพิ่มความถูกต้องของไร้เดียงสา Bayes classi  ERS :
โครงสร้างการตัดสินใจแบบ kohavi

รอนการทำเหมืองข้อมูลและการแสดง

2011 Silicon Graphics , Inc . Shoreline Blvd
Mountain View , CA 94043-1389
ronnyk @ SGI . com

Naive Bayes เหนี่ยวนามธรรมขั้นตอนวิธีก่อนหน้านี้
เป็นหลาย classi จู่ ๆถูกต้อง  -
ในงาน แม้ว่าเงื่อนไขความเป็นอิสระ
สมมติฐานที่พวกเขาจะขึ้นเป็นละเมิด อย่างไรก็ตาม การศึกษาส่วนใหญ่จบ
บนฐานข้อมูลขนาดเล็ก เรา
แสดงว่าในฐานข้อมูลขนาดใหญ่ , ความถูกต้องของ
Naive Bayes ไม่ได้ปรับขึ้นเช่นเดียวกับต้นไม้การตัดสินใจ .
จากนั้นเราเสนอวิธีใหม่ nbtree ซึ่ง induces
ลูกผสมของต้นไม้ตัดสินใจและ classi  ERS นา ฟ เบส์
classi  ERS : การตัดสินใจของโหนดมีประชากร
แยกเป็นแขนงการตัดสินใจปกติ แต่ใบ
ประกอบด้วยซื่อ classi เบ  ERS . วิธีการรักษาการ
interpretability ของ Bayes ไร้เดียงสาและต้นไม้การตัดสินใจ
, ในขณะที่ผลใน classi  ERS ที่มักดีกว่า
ทั้งองค์ประกอบ โดยเฉพาะอย่างยิ่งในฐานข้อมูลขนาดใหญ่


แนะนำทดสอบ เห็นที  ในอนาคตต้องไม่เพียง แต่เลนส์มุมกว้าง

มันต้องมีหลายหลากของเลนส์