บทช่วยสอนการวิเคราะห์การห่อหุ้มข้อมูล

• กุมภาพันธ์ 24, 2014
• Vasilis Vryniotiso
• . 3 ความคิดเห็น

การวิเคราะห์ Data Envelopment หรือที่เรียกว่า DEA เป็นวิธีการที่ไม่มีพารามิเตอร์สำหรับการวิเคราะห์เขตแดน ใช้โปรแกรมเชิงเส้นตรงเพื่อประเมินประสิทธิภาพของหน่วยการตัดสินใจหลายหน่วย และมักใช้ในการผลิต การจัดการ และเศรษฐศาสตร์ เทคนิคนี้ถูกเสนอครั้งแรกโดย Charnes, Cooper และ Rhodes ในปี 1978 และตั้งแต่นั้นมาก็เป็นเครื่องมืออันทรงคุณค่าในการประเมินขอบเขตการผลิต

อัปเดต: ขณะนี้ Datumbox Machine Learning Framework เป็นโอเพ่นซอร์สและฟรีสำหรับ ดาวน์โหลด. ตรวจสอบแพ็คเกจ com.datumbox.framework.algorithms.dea เพื่อดูการใช้งาน Data Envelopment Analysis ใน Java

เมื่อฉันพบวิธีการนี้ครั้งแรกเมื่อ 5-6 ปีที่แล้ว ฉันรู้สึกทึ่งกับความแปลกใหม่ของอัลกอริทึม ความเรียบง่าย และความฉลาดของแนวคิดที่ใช้ ฉันประหลาดใจมากขึ้นที่เห็นว่าเทคนิคนี้ทำงานได้ดีนอกเหนือจากการใช้งานปกติ (ด้านการเงิน การวิจัยการดำเนินงาน ฯลฯ) เนื่องจากสามารถนำไปใช้ในการตลาดออนไลน์ การจัดอันดับเสิร์ชเอ็นจิ้น และสำหรับการสร้างเมตริกแบบผสมได้สำเร็จ อย่างไรก็ตาม เรื่องนี้ ทุกวันนี้ DEA มักถูกกล่าวถึงในบริบทของธุรกิจเท่านั้น นั่นคือเหตุผลที่ในบทความนี้ ผมจะกล่าวถึงแนวคิดพื้นฐานและกรอบทางคณิตศาสตร์ที่อยู่เบื้องหลัง DEA และในโพสต์ถัดไป ผมจะแสดงแอปพลิเคชั่นใหม่ๆ ของอัลกอริทึมบนเว็บแอปพลิเคชันให้คุณเห็น

ทำไม Data Envelopment Analysis ถึงน่าสนใจ?

การวิเคราะห์การห่อหุ้มข้อมูลเป็นวิธีที่ช่วยให้เราสามารถเปรียบเทียบและจัดลำดับบันทึก (ร้านค้า พนักงาน โรงงาน หน้าเว็บ แคมเปญการตลาด ฯลฯ) ตามคุณลักษณะ (น้ำหนัก ขนาด ต้นทุน รายได้ และตัวชี้วัดหรือ KPI อื่นๆ) โดยไม่ต้องมีการสันนิษฐานใดๆ ล่วงหน้าเกี่ยวกับ ความสำคัญหรือน้ำหนักของคุณสมบัติ ส่วนที่น่าสนใจที่สุดของเทคนิคนี้คือช่วยให้เราสามารถเปรียบเทียบบันทึกที่ประกอบด้วยคุณลักษณะหลายอย่างที่มีหน่วยวัดต่างกันโดยสิ้นเชิง ซึ่งหมายความว่าเราสามารถมีบันทึกที่มีคุณลักษณะที่วัดเป็นกิโลเมตร กิโลกรัม หรือหน่วยเงิน และยังสามารถเปรียบเทียบ จัดอันดับ และค้นหาบันทึกประสิทธิภาพที่ดีที่สุด/แย่ที่สุด และโดยเฉลี่ย ฟังดูน่าสนใจ? อ่านต่อไป

คำอธิบายและสมมติฐานของการวิเคราะห์การห่อหุ้มข้อมูล

ดังที่เราได้กล่าวไว้ก่อนหน้านี้ DEA เป็นวิธีการที่คิดค้นขึ้นเพื่อวัดประสิทธิภาพการทำงานในธุรกิจ ดังนั้นแนวคิดหลายประการจึงมาจากวิธีการวัดประสิทธิภาพในบริบทนี้ ลักษณะสำคัญของวิธีการประการหนึ่งคือการแยกคุณลักษณะบันทึกออกเป็นสองประเภท: อินพุตและเอาต์พุต ตัวอย่างเช่น หากเราวัดประสิทธิภาพของรถยนต์ เราอาจกล่าวได้ว่าอินพุตคือลิตรของน้ำมันและเอาต์พุตคือจำนวนกิโลเมตรที่เดินทาง

ใน DEA คุณลักษณะทั้งหมดต้องเป็นค่าบวก และถือว่ายิ่งค่าสูงเท่าใด ค่าอินพุต/เอาต์พุตก็จะมากขึ้นเท่านั้น นอกจากนี้ การวิเคราะห์ Data Envelopment ยังอนุมานว่าคุณลักษณะต่างๆ สามารถรวมกันเป็นเส้นตรงเป็นผลรวมถ่วงน้ำหนักของน้ำหนักที่ไม่เป็นลบ และสร้างอัตราส่วนระหว่างอินพุตและเอาต์พุตที่จะวัดประสิทธิภาพของแต่ละเร็กคอร์ด เพื่อให้บันทึกมีประสิทธิภาพ จะต้องให้ผลลัพธ์ที่ "ดี" เทียบกับข้อมูลที่ให้มา ประสิทธิภาพวัดจากอัตราส่วนระหว่างเอาต์พุตและอินพุต จากนั้นเปรียบเทียบกับอัตราส่วนของเรกคอร์ดอื่นๆ

ความคิดสร้างสรรค์เบื้องหลัง DEA

สิ่งที่เรากล่าวถึงจนถึงตอนนี้คือสามัญสำนึก/การปฏิบัติ เราใช้อินพุตและเอาต์พุต ผลรวมถ่วงน้ำหนัก และอัตราส่วนเพื่อจัดอันดับระเบียนของเรา แนวคิดอันชาญฉลาดของ DEA อยู่ที่วิธีการคำนวณน้ำหนักของคุณสมบัติต่างๆ แทนที่จะต้องกำหนดน้ำหนักของคุณลักษณะและตัดสินใจเกี่ยวกับความสำคัญของคุณลักษณะก่อนที่เราจะทำการวิเคราะห์ Data Envelopment Analysis จะคำนวณจากข้อมูล ยิ่งกว่านั้นน้ำหนักจะไม่เท่ากันสำหรับทุกเร็กคอร์ด!

นี่คือวิธีที่ DEA เลือกน้ำหนัก: เราพยายามเพิ่มอัตราส่วนของทุกระเบียนให้สูงสุดโดยเลือกน้ำหนักคุณลักษณะที่เหมาะสม ในเวลาเดียวกัน แม้ว่าเราต้องแน่ใจว่าถ้าเราใช้น้ำหนักเท่ากันในการคำนวณอัตราส่วนของระเบียนอื่น ๆ ทั้งหมด จะไม่มีใครมีขนาดใหญ่กว่า 1

แนวคิดนี้ฟังดูแปลกไปเล็กน้อยในตอนเริ่มต้น สิ่งนี้จะไม่นำไปสู่การคำนวณอัตราส่วนน้ำหนักต่างกันใช่หรือไม่ คำตอบคือใช่ นี่ไม่ได้หมายความว่าจริง ๆ แล้วเราคำนวณอัตราส่วนสำหรับแต่ละเรคคอร์ดแตกต่างกันใช่หรือไม่? คำตอบคือใช่อีกครั้ง แล้วมันทำงานอย่างไร? คำตอบนั้นง่าย: สำหรับทุกเร็กคอร์ด เมื่อพิจารณาถึงคุณลักษณะแล้ว เราพยายามค้นหา "สถานการณ์ในอุดมคติ" (น้ำหนัก) ซึ่งอัตราส่วนของเร็กคอร์ดจะสูงที่สุดเท่าที่จะเป็นไปได้ และทำให้มีประสิทธิภาพมากที่สุด แต่ในขณะเดียวกัน เนื่องจาก "สถานการณ์ในอุดมคติ" นี้ ไม่มีอัตราส่วนเอาต์พุต/อินพุตของระเบียนอื่นใดควรมากกว่า 1 ซึ่งหมายความว่าไม่สามารถมีประสิทธิภาพมากกว่า 100%! เมื่อเราคำนวณอัตราส่วนของระเบียนทั้งหมดภายใต้ "สถานการณ์ในอุดมคติ" แล้ว เราจะใช้อัตราส่วนเพื่อจัดอันดับ

ดังนั้น แนวคิดหลักของ DEA สามารถสรุปได้ดังนี้: "ค้นหาสถานการณ์ในอุดมคติที่เราสามารถบรรลุคะแนนอัตราส่วนที่ดีที่สุดตามลักษณะของแต่ละระเบียน จากนั้นคำนวณอัตราส่วนในอุดมคติของแต่ละบันทึกและใช้เพื่อเปรียบเทียบประสิทธิภาพ”

มาดูตัวอย่างกัน

ลองดูตัวอย่างที่เราสามารถใช้ DEA ได้

สมมุติว่าเราสนใจที่จะประเมินประสิทธิภาพของร้านซุปเปอร์มาร์เก็ตในเครือนั้น ๆ โดยพิจารณาจากคุณสมบัติหลายประการ ได้แก่ จำนวนพนักงานทั้งหมด ขนาดของร้านเป็นตารางเมตร ปริมาณการขายที่ผลิต และจำนวนลูกค้า ที่พวกเขาให้บริการทุกเดือนโดยเฉลี่ย เห็นได้ชัดว่าการค้นหาร้านค้าที่มีประสิทธิภาพสูงสุดต้องการให้เราเปรียบเทียบบันทึกกับคุณสมบัติหลายอย่าง

ในการใช้ DEA เราต้องกำหนดว่าสิ่งใดคืออินพุตและเอาต์พุตของเรา ในกรณีนี้ ผลลัพธ์ที่ชัดเจนคือปริมาณการขายและจำนวนลูกค้าที่พวกเขาให้บริการ ข้อมูลเข้าคือจำนวนพนักงานและขนาดของร้าน หากเราใช้ DEA เราจะประมาณอัตราส่วนเอาต์พุตต่ออินพุตสำหรับร้านค้าทุกแห่งภายใต้น้ำหนักในอุดมคติ (ตามที่กล่าวไว้ข้างต้น) เมื่อเราได้อัตราส่วนแล้ว เราจะจัดอันดับตามประสิทธิภาพ

ถึงเวลาคณิตศาสตร์!

เมื่อเราได้สัญชาตญาณว่า DEA ทำงานอย่างไร ก็ถึงเวลาเจาะลึกคณิตศาสตร์

อัตราส่วนประสิทธิภาพของเร็กคอร์ดเฉพาะ i ที่มีอินพุต x และเอาต์พุต y (เวกเตอร์คุณลักษณะทั้งสองที่มีค่าบวก) ถูกประเมินโดยใช้สูตรต่อไปนี้:

โดยที่ u และ v คือน้ำหนักของเอาต์พุตแต่ละรายการและอินพุตของเร็กคอร์ด s คือจำนวนฟีเจอร์เอาต์พุต และ m คือจำนวนฟีเจอร์อินพุต

ปัญหาในการค้นหาตุ้มน้ำหนักที่ดีที่สุด/เหมาะที่สุดสำหรับเร็กคอร์ดหนึ่ง i สามารถกำหนดได้ดังนี้:

อีกครั้งข้างต้นเป็นเพียงวิธีทางคณิตศาสตร์ในการค้นหาน้ำหนัก u และ v ที่เพิ่มประสิทธิภาพสูงสุดของระเบียน i โดยที่ตุ้มน้ำหนักเหล่านั้นจะไม่ทำให้ระเบียนอื่นๆ มีประสิทธิภาพมากกว่า 100%

เพื่อแก้ปัญหานี้ เราต้องใช้โปรแกรมเชิงเส้น ขออภัย โปรแกรมเชิงเส้นตรงไม่อนุญาตให้เราใช้เศษส่วน เราจึงต้องแปลงสูตรของปัญหาดังต่อไปนี้:

เราควรเน้นว่าปัญหาการโปรแกรมเชิงเส้นตรงข้างต้นจะให้น้ำหนักที่ดีที่สุดสำหรับบันทึก i และคำนวณประสิทธิภาพภายใต้น้ำหนักที่เหมาะสมที่สุดเหล่านั้น ต้องทำซ้ำทุกระเบียนในชุดข้อมูลของเรา ถ้าเรามีระเบียน n ระเบียน เราต้องแก้ปัญหาเชิงเส้น n แบบแยกกัน นี่คือรหัสเทียมของวิธีการทำงานของ DEA:

ratio_scores = [];
for every record i {
    i_ratio = get_maximum_effectiveness();
    ratio_scores[i] = i_ratio;
}

ข้อจำกัดของการวิเคราะห์การห่อหุ้มข้อมูล

DEA เป็นเทคนิคที่ยอดเยี่ยม แต่ก็มีข้อจำกัด คุณต้องเข้าใจว่า DEA ก็เหมือนกล่องดำ เนื่องจากตุ้มน้ำหนักที่ใช้ในอัตราส่วนประสิทธิภาพของแต่ละเร็กคอร์ดนั้นแตกต่างกัน การพยายามอธิบายวิธีและเหตุผลที่คำนวณคะแนนแต่ละคะแนนจึงไม่มีประโยชน์ โดยปกติเราจะเน้นที่การจัดอันดับของเรกคอร์ดมากกว่าที่ค่าจริงของคะแนนประสิทธิภาพ นอกจากนี้ โปรดทราบด้วยว่าการมีอยู่ของส่วนปลายอาจทำให้คะแนนมีค่าต่ำมาก

โปรดทราบว่า DEA ใช้ชุดค่าผสมเชิงเส้นของคุณลักษณะต่างๆ เพื่อประเมินอัตราส่วน ดังนั้นหากการรวมพวกมันเชิงเส้นไม่เหมาะสมในแอปพลิเคชันของเรา เราต้องใช้การแปลงบนคุณสมบัติและทำให้พวกมันสามารถรวมกันเป็นเส้นตรงได้ ข้อเสียอีกประการหนึ่งของเทคนิคนี้คือ เราต้องแก้ปัญหาการเขียนโปรแกรมเชิงเส้นมากเท่ากับจำนวนเรคคอร์ด ซึ่งต้องใช้ทรัพยากรในการคำนวณเป็นจำนวนมาก

ปัญหาอีกประการหนึ่งที่ DEA เผชิญคือมันทำงานได้ไม่ดีกับข้อมูลมิติสูง ในการใช้ DEA จำนวนมิติ d = m + s ต้องต่ำกว่าจำนวนการสังเกตอย่างมีนัยสำคัญ การเรียกใช้ DEA เมื่อ d อยู่ใกล้มากหรือมากกว่า n ไม่ได้ให้ผลลัพธ์ที่เป็นประโยชน์ เนื่องจากมีแนวโน้มว่าระเบียนทั้งหมดจะเหมาะสมที่สุด โปรดทราบว่าเมื่อคุณเพิ่มตัวแปรเอาท์พุตใหม่ (มิติ) เร็กคอร์ดทั้งหมดที่มีค่าสูงสุดในมิตินี้จะพบว่าเหมาะสมที่สุด

สุดท้ายนี้ เราควรสังเกตว่า ในรูปแบบทั่วไปของอัลกอริธึม น้ำหนักของฟีเจอร์ใน DEA จะประมาณจากข้อมูล ดังนั้นจึงไม่ใช้ข้อมูลก่อนหน้าเกี่ยวกับความสำคัญของฟีเจอร์ที่เราอาจมีในปัญหาของเรา (แน่นอน เป็นไปได้ที่จะรวมข้อมูลนี้เป็นข้อจำกัดในปัญหาเชิงเส้นของเรา) นอกจากนี้ คะแนนประสิทธิภาพที่คำนวณได้จริง ๆ แล้วเป็นอัตราส่วนประสิทธิภาพขีดจำกัดบนของแต่ละเร็กคอร์ด เนื่องจากคำนวณภายใต้ "สถานการณ์ในอุดมคติ" ซึ่งหมายความว่า DEA สามารถเป็นทางออกที่ดีเมื่อไม่สามารถตั้งสมมติฐานเกี่ยวกับความสำคัญของคุณลักษณะได้ แต่ถ้าเรามีข้อมูลก่อนหน้านี้หรือเราสามารถหาปริมาณความสำคัญของสิ่งเหล่านี้ได้ แนะนำให้ใช้เทคนิคทางเลือกอื่น

ในบทความถัดไป ผมจะแสดงให้คุณเห็นถึงวิธีการพัฒนาการใช้งานของ การวิเคราะห์การห่อหุ้มข้อมูลใน JAVA และเราจะใช้วิธีการประเมินความนิยมของหน้าเว็บและบทความในเครือข่ายโซเชียลมีเดีย

หากคุณชอบบทความนี้ โปรดสละเวลาสักครู่เพื่อแชร์บน Twitter หรือ Facebook 🙂