บทความนี้อธิบายถึงอัลกอริทึมของแผนผังทรีที่ดำเนินการโดย Java แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
อัลกอริทึมแผนผังการตัดสินใจเป็นวิธีการประมาณค่าของฟังก์ชันที่ไม่ต่อเนื่อง มันเป็นวิธีการจำแนกทั่วไปการประมวลผลข้อมูลครั้งแรกโดยใช้อัลกอริทึมการเหนี่ยวนำเพื่อสร้างกฎและต้นไม้ตัดสินใจที่อ่านได้จากนั้นใช้การตัดสินใจเพื่อวิเคราะห์ข้อมูลใหม่ ในสาระสำคัญต้นไม้ตัดสินใจเป็นกระบวนการของการจำแนกข้อมูลผ่านชุดของกฎ
การก่อสร้างต้นไม้ตัดสินใจสามารถดำเนินการได้สองขั้นตอน ขั้นตอนแรกคือการสร้างแผนผังการตัดสินใจ: กระบวนการสร้างแผนผังการตัดสินใจจากชุดตัวอย่างการฝึกอบรม โดยทั่วไปชุดข้อมูลตัวอย่างการฝึกอบรมเป็นชุดข้อมูลที่มีประวัติและความครอบคลุมในระดับหนึ่งตามความต้องการที่แท้จริงและใช้สำหรับการวิเคราะห์ข้อมูลและการประมวลผล ขั้นตอนที่สองคือการตัดแต่งกิ่งของแผนผังการตัดสินใจ: การตัดแต่งกิ่งของแผนผังการตัดสินใจเป็นกระบวนการของการตรวจสอบแก้ไขและแก้ไขแผนผังการตัดสินใจที่เกิดขึ้นในขั้นตอนก่อนหน้า ส่วนใหญ่ใช้ข้อมูลจากชุดข้อมูลตัวอย่างใหม่ (เรียกว่าชุดข้อมูลทดสอบ) เพื่อตรวจสอบกฎเบื้องต้นที่สร้างขึ้นในระหว่างกระบวนการสร้างของแผนผังการตัดสินใจ
รหัสการใช้งาน Java มีดังนี้:
การสาธิตแพ็คเกจ; นำเข้า java.util.hashmap; นำเข้า java.util.linkedlist; นำเข้า java.util.list; นำเข้า java.util.map; นำเข้า java.util.map.entry; นำเข้า java.util.set; ผลลัพธ์:"); String [] attrNames = new String [] {"อายุ", "รายได้", "นักเรียน", "credit_rating"}; // อ่านแผนที่ชุดตัวอย่าง <วัตถุรายการ <ตัวอย่าง >> ตัวอย่าง = ReadSamples (attrNames); // สร้างทรีตัดสินใจวัตถุ decisiontree = generatedecisiontree (ตัวอย่าง, attrNames); // เอาท์พุทแผนผังทรี decision outputDecisionTree (DecisionTree, 0, null); } / *** อ่านชุดตัวอย่างที่ได้รับการจัดประเภทและส่งคืนแผนที่: การจำแนกประเภท-> รายการตัวอย่างที่อยู่ในหมวดหมู่* / แผนที่คงที่ <วัตถุ, รายการ <ตัวอย่าง >> readsamples (สตริง [] attrNames) {// ตัวอย่างแอตทริบิวต์ "สูง", "ไม่", "ยุติธรรม", "0"}, {"<30", "สูง", "ไม่", "ยอดเยี่ยม", "0"}, {"30-40", "High", "No", "Fair", "1", {"40" }, {"> 40", "ต่ำ", "ใช่", "ยอดเยี่ยม", "0"}, {"30-40", "ต่ำ", "ใช่", "ยอดเยี่ยม", "1"}, {"<30", "กลาง", "ไม่" "ใช่", "ยุติธรรม", "1"}, {"<30", "ปานกลาง", "ใช่", "ยอดเยี่ยม", "1"}, {"30-40", "ปานกลาง", "ไม่", "ยอดเยี่ยม", "1"}, {"30-40", "สูง", " - // อ่านแอตทริบิวต์ตัวอย่างและการจำแนกประเภทของพวกเขาสร้างวัตถุตัวอย่างที่แสดงตัวอย่างและหารชุดตัวอย่างที่กำหนดโดยแผนที่การจำแนกประเภท <วัตถุ, รายการ <ตัวอย่าง >> ret = new hashmap <วัตถุ, รายการ <ตัวอย่าง >> (); สำหรับ (วัตถุ [] แถว: rawData) {ตัวอย่างตัวอย่าง = ตัวอย่างใหม่ (); int i = 0; สำหรับ (int n = row.length - 1; i <n; i ++) sample.setAttribute (attrNames [i], row [i]); sample.setCategory (แถว [i]); รายการ <eample> samples = ret.get (แถว [i]); if (samples == null) {samples = new LinkedList <eample> (); ret.put (แถว [i], ตัวอย่าง); } samples.add (ตัวอย่าง); } return ret; } / *** สร้างแผนผังการตัดสินใจ* / วัตถุคงที่สร้างขึ้น ecisionTree (แผนที่ <วัตถุ, รายการ <ตัวอย่าง >> categoryTosamples, string [] attrNames) {// ถ้ามีเพียงตัวอย่างเดียวให้ใช้การจำแนกประเภท // หากไม่มีแอตทริบิวต์สำหรับการตัดสินใจการจัดหมวดหมู่ที่มีตัวอย่างมากที่สุดในชุดตัวอย่างจะใช้เป็นการจำแนกประเภทของตัวอย่างใหม่นั่นคือโหวตสำหรับการจำแนกประเภทถ้า (attrNames.length == 0) {int max = 0; Object MaxCategory = null; สำหรับ (รายการ <วัตถุ, รายการ <ตัวอย่าง >> รายการ: categoryTosamples .EntrySet ()) {int cur = entry.getValue (). size (); if (cur> max) {max = cur; maxCategory = entry.getKey (); }} ส่งคืน MaxCategory; } // เลือกวัตถุแอตทริบิวต์การทดสอบ [] rst = selectebesttestattribute (categoryTosamples, attrNames); // โหนดรูทของแผนผังการตัดสินใจแอตทริบิวต์สาขาคือทรีแอตทริบิวต์การทดสอบที่เลือกต้นไม้ = ต้นไม้ใหม่ (attrNames [(จำนวนเต็ม) rst [0]]); // ไม่ควรเลือกแอตทริบิวต์การทดสอบที่ใช้เป็นแอตทริบิวต์ทดสอบอีกครั้งสตริง [] suba = สตริงใหม่ [attrNames.length - 1]; สำหรับ (int i = 0, j = 0; i <attrNames.length; i ++) ถ้า (i! = (จำนวนเต็ม) rst [0]) suba [j ++] = attrNames [i]; // สร้างสาขาตามแอตทริบิวต์สาขา @suppresswarnings ("ไม่ได้ตรวจสอบ") แผนที่ <วัตถุ, แผนที่ <วัตถุ, รายการ <ตัวอย่าง >>> splits = * บรรทัดใหม่ */(แผนที่ <วัตถุ, แผนที่ <วัตถุ, รายการ <ตัวอย่าง >>>) rst [2]; สำหรับ (รายการ <วัตถุ, แผนที่ <วัตถุ, รายการ <ตัวอย่าง >>> รายการ: split.entryset ()) {object attrvalue = entry.getKey (); แผนที่ <วัตถุรายการ <ตัวอย่าง >> split = entry.getValue (); Object Child = generatedecisionTree (แยก, suba); Tree.Setchild (attrvalue, เด็ก); } Tree return; } /*** เลือกแอตทริบิวต์การทดสอบที่ดีที่สุด วิธีการที่ดีที่สุดหากสาขาแอตทริบิวต์การทดสอบที่เลือกนั้นขึ้นอยู่กับสาขาการทดสอบที่เลือกผลรวมของข้อมูลที่จำเป็นสำหรับการจำแนกประเภทของตัวอย่างใหม่* จะถูกกำหนดจากแต่ละสาขาซึ่งเทียบเท่ากับข้อมูลสูงสุดที่ได้รับ แผนที่ <วัตถุ, รายการ <ตัวอย่าง >> categoryTosamples, string [] attrNames) {int minindex = -1; // แอตทริบิวต์ที่ดีที่สุดตัวห้อย double minValue = double.max_value; // แผนที่ข้อมูลขั้นต่ำ <วัตถุ, แผนที่ <วัตถุ, รายการ <ตัวอย่าง >>> minsplits = null; // รูปแบบสาขาที่ดีที่สุด // สำหรับแต่ละแอตทริบิวต์ให้คำนวณผลรวมของข้อมูลที่จำเป็นในการกำหนดการจำแนกประเภทของตัวอย่างใหม่ในแต่ละสาขาเมื่อใช้เป็นแอตทริบิวต์ทดสอบและเลือกขั้นต่ำที่เหมาะสมที่สุดสำหรับ (inttrindex = 0; attrindex <attrNames.length; attrindex ++) {int AllCount = 0; // ตัวนับสำหรับการนับจำนวนตัวอย่างทั้งหมด // สร้างแผนที่ตามแอตทริบิวต์ปัจจุบัน: ค่าแอตทริบิวต์-> (การจำแนกประเภท-> รายการตัวอย่าง) แผนที่ <วัตถุ, แผนที่ <วัตถุ, รายการ <ตัวอย่าง >>> cursplits =/ * บรรทัดใหม่ */ใหม่ hashmap <วัตถุ, แผนที่ <วัตถุ, รายการ <ตัวอย่าง >>> (); สำหรับ (รายการ <วัตถุ, รายการ <ตัวอย่าง >> รายการ: categoryToSamples .EntrySet ()) {หมวดหมู่วัตถุ = entry.getKey (); รายการ <eample> samples = entry.getValue (); สำหรับ (ตัวอย่างตัวอย่าง: ตัวอย่าง) {Object attrValue = ตัวอย่าง. getAttribute (attrNames [attrindex]); แผนที่ <วัตถุรายการ <ตัวอย่าง >> split = cursplits.get (attrvalue); if (split == null) {split = new hashmap <object, list <ตัวอย่าง >> (); cursplits.put (attrvalue, แยก); } list <Apple> splitSamples = split.get (หมวดหมู่); if (splitSamples == null) {splitSamples = new linkedList <eample> (); split.put.put (หมวดหมู่, splitsamples); } splitsamples.add (ตัวอย่าง); } allCount += samples.size (); } // คำนวณผลรวมของข้อมูลที่จำเป็นในการพิจารณาการจำแนกประเภทของตัวอย่างใหม่ในแต่ละสาขาเมื่อใช้แอตทริบิวต์ปัจจุบันเป็นแอตทริบิวต์การทดสอบสองโค้ง = 0.0; // ตัวนับ: สะสมแต่ละสาขาสำหรับ (แผนที่ <วัตถุ, รายการ <ตัวอย่าง >> แยก: cursplits.values ()) {double persplitCount = 0; สำหรับ (รายการ <Sample> รายการ: split.values ()) persPlitCount += list.size (); // ตัวอย่างสาขาสะสมในกระแสไฟฟ้าสอง persplitValue = 0.0; // เคาน์เตอร์: สาขาปัจจุบันสำหรับ (รายการ <eample> รายการ: split.values ()) {double p = list.size () / persplitCount; persplitValue -= p * (math.log (p) / math.log (2)); } curvalue += (persplitCount / allCount) * persplitValue; } // เลือกขั้นต่ำถึงดีที่สุดถ้า (minvalue> curvalue) {minindex = attrindex; minvalue = curvalue; minsplits = cursplits; }} ส่งคืนวัตถุใหม่ [] {minindex, minValue, minsplits}; } / *** เอาต์พุตแผนผังการตัดสินใจไปยังเอาต์พุตมาตรฐาน* / โมฆะคงที่ outputDecisionTree (Object OBJ, ระดับ int, วัตถุจาก) {สำหรับ (int i = 0; i <ระดับ; i ++) System.out.print ("| ------"); if (จาก! = null) system.out.printf ("(%s):", จาก); if (OBJ Instanceof Tree) {Tree Tree = (Tree) OBJ; สตริง attrName = tree.getAttribute (); System.out.printf ("[%s =?]/n", attrName); สำหรับ (วัตถุ attrvalue: tree.getattributeValues ()) {Object Child = tree.getChild (attrValue); outputDecisionTree (เด็กระดับ + 1, attrName + "=" + attrValue); }} else {system.out.printf ("[category = %s]/n", obj); }} / *** ตัวอย่างที่มีหลายแอตทริบิวต์และค่าการจำแนกประเภทที่ระบุการจำแนกประเภทที่ตัวอย่างเป็นตัวอย่างของคลาส* / คลาสคงที่ {แผนที่ส่วนตัว <String, Object> attributes = new HashMap <String, Object> (); หมวดหมู่วัตถุส่วนตัว วัตถุสาธารณะ getAttribute (ชื่อสตริง) {return attributes.get (ชื่อ); } โมฆะสาธารณะ setAttribute (ชื่อสตริง, ค่าวัตถุ) {attributes.put (ชื่อ, ค่า); } วัตถุสาธารณะ getCategory () {กลับหมวดหมู่; } โมฆะสาธารณะ setCategory (หมวดหมู่วัตถุ) {this.category = หมวดหมู่; } สตริงสาธารณะ toString () {return attributes.toString (); }} /*** แผนผังการตัดสินใจ (โหนดที่ไม่ใช่ใบ) แต่ละโหนดที่ไม่ใช่ใบในแผนผังการตัดสินใจจะเป็นผู้นำการตัดสินใจ* แต่ละโหนดที่ไม่ใช่ใบมีแอตทริบิวต์สาขาและหลายสาขา แต่ละค่าของแอตทริบิวต์สาขาสอดคล้องกับสาขา สาขาจะแนะนำแผนผังการตัดสินใจย่อย*/ ต้นไม้คลาสคงที่ {แอตทริบิวต์สตริงส่วนตัว; แผนที่ส่วนตัว <วัตถุวัตถุ> เด็ก = ใหม่ hashmap <วัตถุวัตถุ> (); ต้นไม้สาธารณะ (แอตทริบิวต์สตริง) {this.attribute = แอตทริบิวต์; } สตริงสาธารณะ getAttribute () {return attribute; } วัตถุสาธารณะ GetChild (Object attrvalue) {return children.get (attrvalue); } โมฆะสาธารณะ setChild (Object attrvalue, Object Child) {เด็ก. บุตร (attrvalue, เด็ก); } ชุดสาธารณะ <Ojrop> getAtTributeValues () {return children.keyset (); -ผลการทำงาน:
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน