Classification via sequential testing

Abstract

SIRALI TESTLER İLE SINIFLANDIRMA Özet Test düzenleme problemi adı da verilen, minimum maliyetle teşhis koymak için gerekli test sırası oluşturma problemi ele alınmıştır. Test düzenleme problemi, çözümünün NP-tam olduğu bilinen ikili VE/VEYA karar ağacı şeklinde formüle edilebilir. Problemin en iyi çözümü dinamik programlama ve ya VE/VE YA grafiği arama yöntemleriyle (AO*, CF, ve HS) elde edilebilir. Ancak büyük sistemlerde, di namik programlama ve ya VE/ VE YA arama yöntemleri, VE/VE YA arama grafiğinde hızla artan noktalar yüzünden, ağır hesaplamaları beraberinde getirmektedir. Bu hesaplama patlamasının üstesinden gelmek için, test düzenleme problemini çözecek bir-adım ya da çok-adım ileri bakma yöntemi algoritmaları geliştirildi. Bizim yaklaşımımız, bir-adım ileri bakma yöntemi algoritmalarıyla, Huffman kodlamasmda kullanılan stratejileri birleştirmektir. Algoritmaların etkinliği bir çok test durumu için gösterilmiştir. Geleneksel test düzenleme problemi asimetrik testler de katılarak genelleştirilmiştir. Test düzenleme problemine yaklaşımımız, karar tablosu problemi, tıbbî tanı, veri- tabanı sorgu işleme, kalite güvencesi, ve örüntü tanıma problemlerinde karşılaşılan ikili teşhis problemlerine uyarlanabilir. vıı

CLASSIFICATION VIA SEQUENTIAL TESTING Abstract The problem of generating the sequence of tests required to reach a diagnos tic conclusion with minimum average cost, which is also known as test sequencing problem, is considered. The test sequencing problem is formulated as an optimal binary AND/OR decision tree construction problem, whose solution is known to be NP-complete. The problem can be solved optimally using dynamic programming or AND/OR graph search methods (AO*, CF, and HS). However, for large systems, the associated computational effort with dynamic programming or AND/OR graph search methods is substantial, due to the rapidly increasing number of nodes in AND/OR search graph. In order to prevent the computational explosion, one-step or multistep lookahead heuristic algorithms have been developed to solve the test sequencing problem. Our approach is based on integrating concepts from the one- step lookahead heuristic algorithms and the strategies used in Huffman coding. The effectiveness of the algorithms is demonstrated on several test cases. The tradi tional test sequencing problem is generalized here to include asymmetrical tests. Our approach to test sequencing can be adapted to solve a wide variety of binary identification problems arising in decision table programming, medical diagnosis, database query processing, quality assurance, and pattern recognition. VI